Explaining 2016 Codejam round 1A

This post is going to explain how I got my answers for codejam round 1A. Hopefully, I will be able to continue writing these posts as the 2016 codejam competition furthers. But that have to depend on whether I will be able to answer the questions.

Yes, I know that Google does provide its own question analysis (it’s available here). So why do I write it, repeat it again?

Google’s answers are writtne by expert coders who have a wealth of experience writing algorithms, thinking of solutions. Most that are stuck on the problem are probably not. The little hints given might not be sufficient, hence, the tutorial.

Also partly for myself, in case I have forgotten how to solve it have couldn’t understand the analysis by Google.

Problem A

This problem is a very simple “step-by-step” problem, as long as you can figure out the method of generating the string, you can get the answer by adding characters to the string one by one.

The method goes like this: to get the largest possible string (alphabetically), process the characters one by one, if the character is larger than the character at the start of the answer, add it to the front, if not, add it to the back.

There really is not much in this, it is a pattern questions, as long as you can figure it out, the solution is easy to write.

Submission for small input

N = input()
for n in range(N):
    chars = raw_input()

    ans = chars[0]
    chars = chars[1:]

    for c in chars:
        if c>=ans[0]:
            ans = c+ans
        else:
            ans += c

    print "Case #%d: %s"%(n+1, ans)

Problem B

The second problem is actually very simple, but it is the question where I found that I am deeply dissapointed in myself. This is the problem where you have to determine the values of a missing row from a grid.

When I first started on the problem, I jumped in immediately and started working on the algorithm to find the correct order of the grid from the different pieces of information. But there was one part I overlooked – because of a few rules that are placed in the problem, there is a much much simpler answer to it.

This is the key rule: “all the row and columns must be in ascending order, from left to right, from top to bottom, with no repetition in each row or column”. From this rule, we can use the existing information from the grid to determine the missing numbers and the order it is in.

When you are in a grid, and you are required to record the sequence of the rows and columns, there a case of double counting, where each person is counted exactly twice. Since only one strip (either row or column) is missing, whatever number only appears an odd number of times, must be one of the missing number.

What if one of the row/columns have two of the same number? Doesn’t that mean that there will be an even number of occurance for that value? Well, that’s covered by the rules, “there is not repeated number in each row”.

What if we got the numbers, how do we arrange them? No problem, it’s also covered by the rules – “all sequences of the rows and columns must be in ascending order”.

success for small input

T = input()
for t in range(T):
    N = input()

    all = []
    for n in range(N*2 - 1):
        all += map(int, raw_input().strip().split())

    line = []
    for i in set(all):
        if all.count(i)%2: line.append(i)

    s = " ".join(map(str, sorted(line)))
    print "Case #%d: %s"%(t+1, s)

Problem C

This is one of the more classical problems, using graph as a model for the problem. To do this question, we will have to refer to a diagram for explaination. This is the diagram taken from Google’s codejam answer.

Try drawing a few graphs on your own. And you probably see how the friendship circle will work out. As explained in the analysis, the way to form the longest chain of amiable students sitting together is to make use of the students who mutually like each other.

But if the chain using the mutual liking students are too short, the only are option in forming a circle is to find the cycle with the longest cycle length. (eg. biggest loop), like in the first example.

So there is 2 parts to the solution. One, find the cycles in the graph. Two, Find the longest tail from the cycles with length of 2, 2 kids liking each other, then add up all of them together to form one big circle (just like in the picture, with the 2nd and 3rd part combined).

Okay, my solution for finding all the cycles in the graph might not be the most efficient, but it is definitely a method that works, and it works well within the time limit.

As for the second part when we need to find the tail, it is a depth first search for the longest link. Don’t get it? Basically we follow the data and start tracking back each chain, starting of the kid in the length-2 cycle. We will try all the combinations and then return the length of the tail which goes the deepest.

success

# current, data, not-to-be-counted
def longest(current, data, nocount): 
    nodes = [n for n in data[current[-1]] if nnocount]    
    if not nodes:
        return current

    max_line = []
    for n in nodes:
        temp = longest(current+[n], data, nocount)
        if len(max_line)<len(temp):
            max_line = temp
    return max_line

T = input()
for t in range(T):
    N = input()
    d = [int(i)-1 for i in raw_input().split()]

    c2 = []

    # normal cycle counting
    c_max = 0
    mv = range(N)
    while mv:
        c = [mv[0]]
        mv = mv[1:]

        while len(c)1][0]
        idx = c.index(start)
        c.remove(start)
        c_len = c.index(start) - idx + 1

        if c_max  m: m= c_max

    print "Case #%d: %d"%(t+1, m)

Conclusion

The problems are solvable, but I do need sometime to write the solution and really think about the edge cases. I hope that 1B will be more lenient (although it is unlikely). And if I do understand and manage to get a solution, I will share them again when I get the writeup written.