Topcoder SRM 617 recap: regular

This SRM took me by surprise, I think the programming contest calendar I use wasn't updated correctly or I didn't read it correctly the first time I read it, so I thought SRM 617 was another date. On Sunday, I got the Topcoder email and surprise!. It's a good thing that we no longer have that bug in which invitation emails don't get sent...

This is the 7-th of 10 SRMs in which I am using python exclusively. So far I don't think it has caused any negative impact to my rating. I think that unless you are in such a high rating position that you really need frequent div1 1000s, python's drawbacks are not a big deal and the pros tend to compensate for the cons :/

Div1 250: The one with cutting cake

You have the nonsensical notion of a one-dimensional cake of length `n`. Your friends are going to come visit, all you know is that the number of friends will be a proper divisor of `n`, but you are not sure which one. You want to make cuts to the cake in such a way that you can distribute the contiguous pieces evenly to your friends, no matter what the number of friends is. The pieces a friend receives may be of different length and the number of pieces each friend gets is not necessarily always the same, the only condition is that they are contiguous after cutting the cake and that the total length of cake each friend receives is equal. Return the minimum number of cuts needed so that this always works, regardless of the number of friends.

Well, the key is that the amount of cake should be the same for each friend, so for each `y` that is a proper divisor of `n` and `x = n/y`, there MUST exist cuts at `x,2x, 3x, ... `, The problem asks for the minimum, so we shouldn't do any more cuts than those `x,2x, 3x, ... `, for each `x`. The trick is that some values `kx_0` and `rx_1` may be the same for different divisors `y_0, y_1` . So we should just count all the numbers that are equal to some `k * (n//y)` where `k` is a integer, `y` is a divisor of `n` and `k * (n//y) < n`.

So simple simulation will be fine. During the match, I had the feeling that with `n <= 100000` and the 2 seconds limit, this simulation would be a bit slow for python. I did things like getting the divisiors in `O(sqrt(n))` time. And even after that, I made sure to test the worst input. The worst input is the number `n <= 100000` that has the most divisors. This is equal to the largest possible highly composite number or 83160 , in short. It turns out it wasn't necessary, also, with some knowledge of iterators and sets, the code can be much simpler than the code I submitted during the match:

class MyLongCake:
 def cut(self, n):
    cuts = set()
    for d in properDivisors(n):              # for each proper divisor d:
        cuts |= set( xrange(n/d, n, n/d) )   # add n/d, 2n/d, 3n/d, etc to set
    return len(cuts) + 1                     # return number of cuts + 1

def properDivisors(n):
    return (i for i in xrange(1, n) if n % i == 0)

During the challenge phase, you'd figure from reading other people's codes that the integers that get cut are exactly those who are not coprime with `n`. So result is actually `n - phi(n)`

Div1 800: strings

I opened this problem accidentally when I intended to open div1 500 :/ . It seemed like I had no idea how to solve it. Also, when a problem score is much smaller than usual, it is possibly much harder than usual (Sorry admins, everyone knows you are backward when choosing problem scores). so I skipped to div1 500, a bit too late, perhaps.

Div1 500: The one with pie and dolphins

You have 50 programmers, for each `i < n`, where `n <= 1000`, you should choose between:

• Giving a dolphin to programmer `C_0[i]` and a pie to `C_1[i]`.
• Or
• Giving a dolphin to `C_1[i]` and a pie to `C_0[i]`.

After you give all these pies and dolphins, each programmer will calculate the absolute value of the difference between the number of pie and dolphin they got. You want to minimize the total sum of all these absolute values.

ooh boy. So I stared at the computer screen for more than half an hour. Everything I thought was non-sense for a good while. Eventually, I decided that the problem was most likely greedy. So the new issue was how to think of a greedy solution. If you process the decisions in the order of i, it is difficult to predict what will happen later and how it should affect your decision. But there is no need to do that. You can really do a decision whatever time you want. A decision will change the result in -2,-1,0,1 or 2, points. What we can try, is repeat this 1000 times: Pick the decision (of all not picked yet) that will change the score for the best. This is easily implemented through just simulation. Complexity is `O(T^2)` where `T` is the number of choices.

I was typing this, and had some bugs. It took longer than usual to debug because it is not easy to know if an answer is correct or not. (This was the first Topcoder problem ever that allowed multiple correct answers to the same test case). Eventually, I found out that in two lines I had i where I meant j. Too bad, coding phase already ended. I tried the solution in the practice room after fixing it , and it passes although the execution time gets awfully close to 2 seconds .

class PieOrDolphin:
 def Distribute(self, choice1, choice2):
    choices = zip(choice1, choice2)
    n = 50  # values of choice1, choice2 go from 0 to 49, we can assume 50 people
    pie = [0] * n
    dolphin = [0] * n
    res = [ 3 ] * len(choices)
    for i in range(0, len(choices)):
        best = (3, (0,0), -1, 3)
        for (j, (a,b) ) in enumerate(choices):
            if res[j] == 3:
                # try (a,b) or (b,a) for choice:
                for (x,y,z) in ( (a,b,1), (b,a,2) ):
                    # calculate how the score would improve
                    p = abs(pie[x] - dolphin[x] + 1) -  abs(pie[x] - dolphin[x])
                    q = abs(pie[y] - dolphin[y] - 1) -  abs(pie[y] - dolphin[y])
                    best = min(best, (p+q, (x,y), j, z) )

        (x , (a,b), bi, t) = best
      # print (a,b),' would improve by ', x, ' index ',bi
        res[bi] = t
        pie[a] += 1
        dolphin[b] += 1
    return tuple(res)

So why is this correct? Well, no idea, but I thought it should be correct because , in theore, each decision is used in the best way ever. And each decision should reduce the effectiveness of at most one decision, in theory. I have nothing formal to prove.

I know that the real answer involves turning the thing into a graph and doing some proofs to show that it is easy. I think that this graph solution eventually reduces to this greedy. But no idea yet.

So?

I think it was a fine problem set, if a bit unusual (odd problem scores, flexible answers in div1 500).