Breakun's blog

By Breakun, 3 months ago, ,

I participated in this year's Facebook Hacker Cup and have enjoyed all the problems so far. The only problem I couldn't solve during the contest was the last problem of Round 2 named "Seafood" (link). Facebook always uploads solutions right after the contest, which I'm thankful for, so I checked the solution for that problem. However, I couldn't see why the solution works just from their description. Maybe I'm not thinking through it enough, but I found it hard to justify their approach in mathematical rigor. So I picked up key ideas from their description and filled out the details. I'm writing this for myself, and it turns out to be more complicated than I thought but I hope this helps some folks out there. If you have any simpler solution/description I'm happy to know.

Here is a short synopsis of the problem. You start at position $0$ of a number line and move around. There are clams and rocks on the number line. Each clam/rock have distinct positive coordinates and also its own strength as a number. When you are on a position where a clam is placed, you can take the clam immediately and you can hold multiple clams at a time. When you are on a position where a rock is placed, you can use the rock to break open any clam you have with lesser strength. Your goal is to open all the clams in minimum distance moved (or determine that you can't). You should do this in quasilinear time over the number of clams+rocks.

My attempt (You can skip this)
Solution
Source Code

• +62

By Breakun, 5 years ago, ,

I'm preparing a local programming contest for my university. It turns out that Polygon development system is the perfect tool for this kind of job, and I want to use the system in real contest too. The problem is that during the contest, participants are not allowed to access internet. I'm afraid to use PC^2 system because of several reasons:

• No multiple input files: All input files should be concentrated to one file
• No checker. Actually it's possible to use a checker, but one has to write judgement in XML format or run the checker manually (I'm not 100% sure about it).
• It's hard to configure the system
• Sometimes the system clogs up judge computer's memory. Two years before we had to reset the whole system because computer couldn't handle too much memory load.

Maybe I misused the PC^2 system, but still I'd strongly prefer Polygon/Gym system. Can I use it while keeping every participants away from the internet(maybe except for contest page)? Participants' PC are connected to a main router. I'm really a noob when it comes to system configuring/networking stuff, so any kind answer will be appreciated. If there's another judgement system that is easy to use, you can suggest it too.

• +14

By Breakun, 6 years ago, ,

First of all, sorry for being late :( I was quite depressed because of the server's chronic breakdown during the contest. Also, all the records for Round #233 was gone after the black day, so I thought not many people will be interested in the solution. I should have been more responsible for this. I really want to apologize for people who have been waiting for this editorial.

During the contest, the only one user who solved this problem was: Petr. The contest was extended by 30 minutes, and if I remember correctly, he submitted the correct solution at about 2:25. So, congratulations to him!

Now let me explain the solution. Let us start with the case when there is no hole. Given any permutation, I will prove that it takes only at most two seconds to sort it completely. Since every permutation can be decomposed into disjoint cycles (link), we only need to take care of each decomposed cycle. That is, we only need to sort a cycle of arbitrary length in two steps.

Let's make a table of 3 rows and n columns. The first row will constitute the original, unsorted permutation. For each column, the next column will form the permutation after one second. The last column will be the sorted permutation. The following depicts the case where n = 5 and the permutation is a full cycle.

2 3 4 5 1
? ? ? ? ?
1 2 3 4 5


Now we have to show that we can fill the second column properly. Let's just fill the first number in the second column randomly, say 4, and see what happens.

2 3 4 5 1
4 ? ? ? ?
1 2 3 4 5


Because 4 replaces 2 in the second column, 2 replaces 4 and we are forced to put 2 below the 4 in first column.

2 3 4 5 1
4 ? 2 ? ?
1 2 3 4 5


Likewise, 3 replaces 2 in the third column, so we should put 3 above 2 in the third column.

2 3 4 5 1
4 3 2 ? ?
1 2 3 4 5


Repeating the process will finally give a complete, valid answer.

2 3 4 5 1
4 3 2 1 5
1 2 3 4 5


Like the example above, filling the first number in the second column by any number will give a unique and valid answer. I won't prove it formally, but by experimenting with different examples you can see it indeed works :) So now we know that (i) any permutation can be sorted in 2 seconds and, additionally, (ii) if the permutation is a cycle, there are exactly n ways of doing it. Now let us see what happens if two disjoint cycles interact with each other. Try to fill the tables below and figure out what happens. First one is a disjoint union of cycles of length 4 and 5. Second one is a union of cycles of length 4 and 4.

2 3 4 5 1 7 8 9 6      2 3 4 1 6 7 8 5
8 ? ? ? ? ? ? ? ?      8 ? ? ? ? ? ? ?
1 2 3 4 5 6 7 8 9      1 2 3 4 5 6 7 8


By experimenting, you will see that if two disjoint cycles A and B interact (to be precise, when an element in A swaps place with another element in B), (i) the size of A and B are equal and in that case (ii) the number of ways to achieve a complete assignment for elements of A and B is exactly the size of A (or B). I won't prove it, but it can be done formally if one wishes to.

Now we have the solution when there is no hole: decompose the permutation into disjoint cycles. Assume there are exactly ci cycles of length li for each i. Let a[c, l] be the number of ways to sort c cycles of length l completely. Then the answer will be , basically because only cycles of same length interact.

To sort c cycles of length l, we can pair some of the cycles to interact with each other. Then each pair and unpaired cycle will contribute multiplicative factor l to the answer. Now we can derive a recursive formula for a[c, l]. Just take a cycle C and decide if it will be paired to different cycle or not. For the first case, C contributes multiplicative factor l and we can decide on the rest of c - 1 cycles, so there are total of l·a[c - 1, l] ways. For the second case, we have c - 1 ways to pair C with the other cycle, then the pair contributes factor l and we can decide on the remaining c - 2 cycles. This contributes l·(c - 1)·a[c - 2, l]. Adding up will give us the recursive formula.

a[c, l] = l·a[c - 1, l] + l·(c - 1)·a[c - 2, l]

(I'm trying my best to explain the idea, but for this part i'm not quite satisfied with it. Ask or message me if you want more clear explanation)

I will write the rest of the editorial tomorrow (my English is bad so it's quite hard to write), but I hope that this draft version will be helpful to you.

• Update

It's almost been a year since I updated this editorial. I have nothing to say but that I was lazy... However, for the sake of completeness, I'll sketch up the rest of the solution.

Computing every a[c, l] can be done in reasonable time: cl will be at most n / l and there will be total of values of a[c, l] to compute using the recursive formula above. Given a permutation, we can count the number of cycles cl of length l for each l and compute a[cl, l]. Since two cycles of different length cannot interact, the number of ways to sort the whole permutation will be the multiplication of a[cl, l]'s over all l.

Finally, we have to deal with k ≤ 12 holes. The crucial observation is that with holes, the permutation decomposes into cycles and paths. Filling the holes will group the paths to disjoint cycles. Considering every 12! possible ways will give TLE. But if we note that the order of paths in a same group does not make a change in cycle's length, we can actually deploy a bitmask DP to consider all possible way to partition at most 12 paths. Just multiply some constant to each partition and sum over (I'll skip the details).