Explaning the codejam qualification round

It has been a while since I worked on writing algorithms, but I joined the 2016 codejam anyways. And the qualification round has just passed.

I took quite a bit of time, but managed to finish some questions. In case I forget how I solved those problems, I am going to walk through how I solved them. For those interested, go ahead and read the questions here before continuing.

Problem A

This is the insomia problem. I read the question and tried a little counting myself. It seemed impossible to not get any of the digits, after all, any N can be used in counting.

Unless that number is zero of course, since it will always be zero. Seems like an easy problem. I should have ko problem. I implememted some sort of counting algorithms, and it is done.

Success for small input

N = input()
for n in range(N):
    x = input()
    if not x:
        print "Case #%d: INSOMNIA"%(n+1)
    else:
        C = []
        X = 0

        while len(C)<10:
            X += x
            for c in str(X):
                C += [c]
            C = list(set(C))

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

Problem B

Oh the pancake problem. I am pretty proud of this one. So the problem goes, there is a stack of pancakes which apparently has only one correct side. Find the minimum number of flips required to make them all right side up.

This, I feel is a slight rehash of the original pancake problem which has different sizing pancake. But just flipping them right side up, shouldnt be a problem.

What is the best way of making them all right side up, I asked myself. I wrote out the plus plus minus minus format that codejam used to represent a stack of pancakes.

I put them left to right, couldnt see anything helpful. Then decided to put them rightway around, top to bottom, just like how pancakes should be. Immediately it struck me, of course, i will have to fix the top pancakes first.

The logic goes these way, I make the first flip to form the largest right side up pancake stack possible. After that, subsequent flips will slowly include the bottom pancakes and finally the whole stack will all face the same side. The final will be the one that turns the whole stack right side up if its all facing the wrong direction.

Talking in terms of plus plus minus minus syntax, we are just trying to count the number of groups in the stack, so ++ can be considered a group, — is another group, even a single + can be a group.

Success for small input

N = input()
for n in range(N):
    s = raw_input().strip()

    while s.count("--"):
        s = s.replace("--", "-")
    while s.count("++"):
        s = s.replace("++", "+")

    a = len(s)-1 + 1*(s[-1]=="-")

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

Problem C

Yeah, this is the troublesome one, its not really fun though, so I never really wrote out code for it, but I will describe the logic behind it.

So first you need some kind of function that can generate the strings of ones and zeros. In python, there is permutation generator in itertools (those interested, go and take a look). But remember, front and back can only be 1.

Then to convert into different bases, you can write your own function, or you can copy it from somewhere, it doesnt matter, just get the job done.

Primality test, you need not go through the sieve method, I would use Fermat’s Last Theorem for this, its faster.

Then the divisors, since we are picking out only 500 from the potentially many number of choices, I would recommend you just test out the first 30 primes, if nothing, just skip it.

Problem D

The L G L G problem. This is the most brain juice using one out of the rest, but that gave chance for the small input, but first read the question, try to get what the question is about before reading on.

So basically, the problem is just to check if there is any G. One shortcut is to check the orignal sequence, if it does have gold, then the sequence will pass the test.

The is the simple, but not optimal solution for when s==k (the assumption that makes everything easier).

For the small input, this is the logic – as long as we are able to check the starting sequence, we will be able to confirm the presence of gold.

And if the first one is lead, the starting k number of tiles will always be the original sequence. If there is gold, it will be confirmed, if all those tiles turn out to be lead, you can be sure thelat there is no gold to be found.

Success for small input

N = input()
for n in range(N):
    k, c, s = [int(c) for c in raw_input().split(" ")]
    a = " ".join(range(1,k+1))

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

Now, thats just for when the s==k. But what is the optimal number of tiles to check for? How exactly do we go about choosing which tile to check? Now, that is where the fasinating part comes in, hold on your hat as we enter the land of mumbo jumbo.

The basic idea is still the same. We are still going to check through all of the original values to seaech for gold. But because of the complexity layers, when you check one of the tiles in the final layer, you are actually checking for a few of the original tiles.

Simple example to illustrate. The pictorial below will show the different layers of pattern after a few complexity. 1 represent the first symbol of the original pattern,2 represents the second, so on and so forth. We make a different assumption in this drawing, we assume that for each symbol, it is just going to replace it with the orginal sequence. For simplicity sake, let’s assume k==2.

Do you see it? Let’s take the 3rd number from the last row as an example. It branched out of the 2nd value of the original pattern, which is then branched out from the first. I like to call this the “working backwards” method. See below for pictorial version.

Now, if we want to check through all k of the orignal pattern, we will have to come up with a method that can give us the position of the tiles that can check the most number of original tiles. From the example about we probably can see the pattern.

Lets try once more to see if we can finalize the formula. This time k==4 and c==3. Now here is the chart.

Oh noes, what about the 4th tile? Sadly, only one tile can be checked per layer. This means that when we reach the last layer, the rest of the tiles will have to be checked individually. So here is the correct chart that shows the tiles to check.

All that’s left is to come up with the formula to obtain the position, I will leave that to you, but if you need help, you can refer to the code below.

All the thinking above translated to code

N = input()
for n in range(N):
    k, c, s = [int(c) for c in raw_input().split(" ")]

    x = 1
    for i in range(c):
        p = (i+1)%k or k
        x = ((x-1)*k)+p

    a = [x]
    for i in range(k-c):
        a += [x+i+1] 
    if len(a)>s:
        a = "IMPOSSIBLE"
    else:
        a = " ".join([str(i) for i in a])

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