Monday, April 21, 2014

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.


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


d07RiV said...

Hey you're that Vexorian from wc3c? I started doing topcoder recently and was surprised to see you here.

Anyway for second problem, graph is the first thing that comes to mind, we need to orient all the edges such that the sum of differences of incoming and outgoing edges is the smallest; what I did is remove all the cycles (since we can just orient the edges along them, achieving 0 difference), so we end up with a tree, for which the answer is easily found with a DFS.

Xellos said...

What's nonsensical about a 1D cake? (Or rather, a cake that's long and can be cut just parallel to its length?) As long as N isn't infinite...


xenny said...

Hey vexorian, I got to learn Euler Totient function, thanks to the cake problem and the concept of 'yield' in Python, thanks to your editorial. I wish you were part of GCJ as well as TCO this year. Both events seem incomplete without you.

Catalin Stefan Tiseanu said...

The PieAndDolphin problem could also be solved using a MaxFlow - MinCost solution (albeit a bit over the top for a 500).

We can model the problem as a bipartite graph where in the left side we have the days and in the right we have the programmers.

For each day i we add an edge to programmer1[i] and programmer2[i].
We can reframe the problem to 'For each day, which of the programmers gets the dolphin in order to minimize the cost defined as in the problem ?'

Obviously, this solution will compute a valid assignment of dolphins / pies, although it's not clear how to optimize for the cost.

Let us define for each programmer p, tot(p) = total number of days this programmers is involved in (aka his degree in the graph).
Let us defined dolphins(p) = how many dolphins does this programmer receive ?
Notice the tot(p) - dolphins(p) gives us the number of pie's received by p.

Therefore, his cost is abs((tot(p) - dolphins(p)) - dolphins(p)) = abs(tot(p) - 2 * dolphins(p)).
Then the total cost for the problem can be defined as sum after p in [0, 49] of abs( tot(p) - 2 * dolphins(p)).

Since tot(p) is fixed for each programmer, the only variable in the cost is dolphins(p), which is tied to our MaxflowMincost formulation (good :).

The tricky part is that for each programmer, his cost function is unimodal in the number of dolphins (first decreasing, than increasing).
Had it been ascending, setting the costs would have been trivial.

However, notice that the cost for a programmer starts at tot(p) for 0 dolphins. As the number of dolphins he receives goes up, the cost decreases by 2, UNTIL we reach # of dolphins = tot(p) / 2, after which is starts to increase by 2 again (there is a special case for tot(p) odd, I'll let that as an exercise to the reader).

Therefore, we can set the cost on the edge for each programmer (right hand side in the bipartite graph) to the sink as follows:
* the first tot(p) / 2 edge have a cost of -2
* the remaining edges have a cost of +2

Now, the last thing to remark is that any MaxflowMincost implementation which supports multiple edges will choose the (-2) weight edges at the beginning, and only when it runs out of them will it choose the +2 edges, thereby computing the cost in the correct manner.


vexorian said...

Hey thank you for the kind words. Sorry for taking this long to reply, I had some bugs that made disqus stop notifying me by email.