### B. Network Packet Ordering

Author: Derianto Kusuma

This write-up is written by Felix Halim.

The art of solving problems quickly is by gathering as much hints as possible. The most valuable hints are usually come from the input range. If you are a veteran, the first thing you should notice is that D is no more than 100. It suggests something (just like problem G, you should notice that r is no more than 100). Also, if you are a veteran, when you see questions like “number of ways”, the first thing that should come to your mind is: dynamic programming, and you would be right!

Without much thinking, the dynamic programming states can be found easily:

number_of_ways = dp[i][j]

Where i is the ith packet from New York that is about to arrive to Dublin, and j is the jth packet from Jakarta that is about to arrive to Dublin.

To transition between one state to another state, you need to make this observation:
– if bj – ai is bigger than D then there is only ONE possiblity: packet ai must arrive before bj.
– if ai – bj is bigger than D then there is only ONE possiblity: packet bj must arrive before ai.
– if bj – ai is less than D then it is possible for packet bj to arrive before ai.
– if ai – bj is less than D then it is possible for packet ai to arrive before bj.

Then, we just need to code it. The easiest is using recursion with memoization:

```INPUT S input string   L = 0, R = 0, P = 1 i = 1, j = S.length() ans = 0   while i <= j L = L * P + S[i] R = R + S[j] * P P = P * x # x is some large prime number if L = R AND i < j ans = ans + 2 L = 0, R = 0, P = 1 i = i + 1 j = j - 1   if P <> 1 ans = ans + 1   return ans```

Of course this solution will not work because memo[i][j] can be as large as 50,000 * 50,000. That requries more than 2GB memory which is infeasible.

This is when the small range of D (< 100) comes into play for optimization. We can reduce the second dimension by storing the delta instead of the actual value of j. Like this:

``` int delta = a[i] - b[j] + 100; assert(delta >= 0 && delta <= 200); int &ret = memo[i][delta];```

Then you only need to allocate memo[50,000] which only consumes less than 10MB memory, and you will get accepted.

### 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?