B. Network Packet Ordering
Author: Derianto Kusuma
(link to problem B)
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.