Nov 082013
 

I. Coins on a Ring

Author: Winardi Kurniawan
(link to problem I)

This is my next favorite problem after problem E in this contest. It has a cute solution and it’s HARD to get it right once you went wrong. Felix Halim is one of the victim. He got so many Wrong Answer attempts when he tried to solve this problem (I think he was a bit hasty when he tried to solve this). I gave him a feedback on which case his solution failed for each attempt and he “fixed” his code (patchwork). From a simple short solution, his code grew into a hundred lines because of this patchwork. In his flight from USA to Singapore, he had time to rethink the problem carefully and found the correct solution. The next day, he sent me his completely new (short) solution and got accepted in one hit.

Notice that there will always be an optimal solution by moving coins (if necessary) without crossing each other, thus to simplify things, let’s assume the coins’ position are sorted.

There are mainly two approach to solve this problem. Both approaches have O(M lg M) time complexity.

Greedy Approach
First, let’s try to “fix” the position of the 1st coins, i.e. do not move this coin from its position. Then, move all other coins to their correct position relative to the 1st coin (the correct position of all coins can be determined by N, M and the position of the 1st coin). Calculate the moving distance for each coin; let negative value means moving the coin counter clockwise and positive value means moving the coin clockwise; let these collection of distances (of all coins) be D. The cost of this arrangement is simply the maximum over absolute values of all distances in D. At this point, we have a feasible solution, but not necessarily an optimal one.

Now, observe what happened to D if we move the 1st coin 1 slot in clockwise direction and correct the position of all other coins. You will notice that all values in D will be increased by 1. The same thing happened if we move the 1st coin 1 slot in counter clockwise direction, all values in D will be decreased by 1. If we generalized this, then we will realize that the value of D will be increased/decreased by K if we move the 1st coin K slots in clockwise or counter clockwise direction.

To find the optimal solution, we have to reduce the highest absolute value of all distances in D; in other words, we want the lowest negative value and the highest positive value have absolute values which are close to each other. This can be achieved simply by calculating the distance between those two extremes and divide it by two (ceil up), i.e. ANS = (HI – LO + 1) / 2.

Bisection/Binary-Search Approach
If we can determine whether the equidistant configuration can be achieved by moving coins at most K distance, then we can do a binary search to find the smallest feasible K which corresponds to the answer. Fortunately, there is a way to do that.

Start by not moving the 1st coin and process all (sorted) coins one by one. When we process ith coin, move the coin to its correct position; if it can’t (due to K) then we should “move” all previous coins such that the ith coin can be moved to its new correct position. Observe that to “move” all previous coins, we only need to know the two extreme values, the largest counter clockwise moves (negative values) and the largest clockwise moves (positive value). If we cannot “move” all previous coins when we need to, then the equidistant configuration cannot be achieved by K.

My solution used the greedy approach, while Risan suggested the binary-search approach. It seems both approaches are used by teams in the contest.


  12 Responses to “ACM-ICPC 2013 Jakarta – Problems and Analysis”

  1. are you sure there isn’t mod operation ?

    and this : j = j + 1, why it isn’t j = j-1 ?

    • Ah, you’re right, it should be j =j – 1 (updated).

      MOD operation is not needed, What we really need is whether a two substrings have a same hash value or not, not the hash value itself. There are only addition and multiplication operators, so overflowing the result doesn’t matter.

  2. ^that comment above is for pasti pas

  3. Halo Mr. Suhendry.
    Saya ingin sekali bisa berkompetisi di ACM ICPC. Saya Mahasiswa tingkat 2 di salah satu perguruan tinggi di bandung. Tapi skill koding saya tidak terlalu bagus. algoritma sorting saja masih bingung. Gimana ya kiat nya untuk belajar algoritma yg baik dan benar agar bisa nanti suatu saat ke ACM ICPC?

  4. How to determine which prime number should be used? I tried some prime numbers and the result is not as expected.

    • (Problem F). Just use large prime number (larger is better, its chance to collide is smaller). I used 1000003 and it’s fine.

      • I have implemented it and submitted on Live Archive, but got WA 😀
        Is there something wrong with my implementation? Could you please check it? http://pastebin.com/ECJX9yEa

      • I didn’t read your code, but it failed the first sample input: PASTIPAS.

        • Yes and it works if I do MOD operation, but still WA on Live Archive. Does your solution with above algorithm still work on LA? Maybe you/others have added more test cases to break that hash function? Or my implementation wrong?

        • I’m the one who send the data to LA and I’m pretty sure LA’s admin was quite busy to do any changes on the dataset.

          BTW, I’ve just noticed an error in F’s pseudocode. There is one line which is wrong. Try to figure that out! 🙂

          hint: pay attention to the rolling hash (when you do the multiplication with prime number); you might want to check other resources on rolling hash.

  5. ^ problem F Pasti Pas!

  6. Problem H can be solved by Dynamic Programming,here I find two states,one is index of the current question,another is wrong answers used/left so far, and then minimize the answer. But this solution does not work,though sample test case gives correct output. I saw another boolean state in some accepted codes in HUST, which tries both minimizing and maximizing. Can you please explain why another state is needed here?

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)