1498C - Planar reflections

Problem

We have a set of $n$ 2D planes. A particle comes from the left, and goes through all the planes. Initially it has power $k$. When this particle touches a plane, another particle with power $k-1$ is created, but in the reverse direction.

Find the total number of particles created in this process.

Note that the created particles can create more particles as they themselves hit the planes.
 

Solution

As soon as a particle hits a plane, we know that a new particle with $k-1$ power will be created in the reverse direction. And the initial particle itself will carry on, with the same power $k$.

Note that the new particle now can touch the planes that were before (on the left of) the initial particle - therefore this particle should have knowledge on how many planes are on the left of it, and how many on the right.

Note that left + right will always be $n$, therefore we can just keep track of the number of particles on the left, and the right ones will be $n - left$.

So to represent the state of a particle, we can say that there are $left$ particles to the left of it, and it has $k$ power, and it's going in the direction $dir$, which can be left or right.

We can create a memoization based DP, where we save outputs for these values in a map.

The key of the map will be $\{left, \{k, dir\}\}$  which will be represented by `pair<long long, pair<long long, long long>>` . (Even though $dir$ can be 0 / 1 I have used a `long long` here)

This map will output the total number of particles created because of this particle.

Now we can create a simple recursion based on the original statement.

$$ getDp(left, k, dir) = getDp(left, k - 1, 1 - dir) + getDp(left + 1, k, dir) $$
 Here the first item in RHS is the new particle created going in the reverse direction with 1 less power, and the second item is the original particle which now has one less plane to see.

This is pretty much the logic to the problem.

The interesting part is in the implementation itself.

I tried to submit the solution 6 times - let's iterate on each of the submission, and see how we improved it until an AC.

Implementations

Submission 1 : 1:* DP

Link : https://codeforces.com/contest/1498/submission/278463113

The DP in this case was not the one mentioned above. Instead it was different.

As a particle goes through multiple planes, with power $k$, it will create particles of power $k-1$ in the reverse direction for each such plane.

So I created the DP around that with

If the particle is going in the right direction:

$$ getDp(left, right, k, direction) = 1 + \sum _{i = 1}^{right} getDp(left + i - 1, right - i + 1, k - 1, 1 - direction)$$

If the particle is going in the left direction:

$$ getDp(left, right, k, direction) = 1 + \sum _{i = 1}^{left} getDp(left - i + 1, right + i - 1, k - 1, 1 - direction)$$

The time complexity of this is *high* (what exactly and why?) therefore this easily gave me TLE

On time complexity of the above recursion

It's basically something like $O(right \times left \times right \times ...\text{k times})$
Since $O(right) = O(left) = O(n)$, the upper bound of this is $O(n^k)$.

But let's look into the total number of items possible inside DP. That is $O(left) \times O(right) \times O(k) \times 2 = 10^3 \times 10^3 \times 10^3 \times 2 = 2 \times 10^9$

But note that $left + right = n$ always, therefore there can be only $10^3$ valid combinations of left and right (ex : both left and right can not be 1)

Therefore a tighter bound on the number of items would be then $2 \times 10^6$

Which means the total number of possible states is within limits. But the number of times these states are accessed is high. (Basically one state inside the DP is accessed multiple times, leading to a high time complexity)

Submission 2 : 1:2 DP

Link : https://codeforces.com/contest/1498/submission/278717744

In this case, I improved upon by using a DP that had a lower time complexity. Basically similar to the one as used in the description, but note that I was still using a $right$ attribute which was actually not required. At this point I started to get a WA (wrong answer) instead of a TLE.
 

Time complexity of the new recursion

Earlier we had a n-ary tree, and now a binary one, with height = $O(n)$ or $O(k)$. Total number of nodes then are $2^{O(n)} = 2 ^ {10^3}$ which is lower than the time complexity of $n^k$ mentioned above.

Note that we are memoizing the answers so actually it's not $2^{10^3}$, as unique states are again $2 \times 10^6$ only. The *number* of times a state is accessed is reduced as compared to the first submission.
 

Submission 3 : MOD

Link : https://codeforces.com/contest/1498/submission/278717889

I realized that I was not MODing the answer. After adding that, I again started to get TLEs

Submission 4 : Removing $right$

Link : https://codeforces.com/contest/1498/submission/279037448

I realized that $right$ is not actually required in the DP, so I removed it, and used only $left$.

Earlier I was getting a TLE in TC 3, and not I was getting a TLE in TC 25, so this was an improvement
 

Exact improvements after removing the concept of `right`

I think the item size inside the map reduced, and that might have lead to some constant improvement in querying of the map.

As mentioned here : https://stackoverflow.com/a/22607155/5345646, https://stackoverflow.com/a/1843264/5345646

During searching inside the map (which in c++ is a red black tree), we compare the keys. Bigger the key, larger the time it will take to do this comparison - though it will always be a constant proportional to the key size.
 

Submission 5 : Emphasis on the reverse key

Link : https://codeforces.com/contest/1498/submission/279275375

So the key = $\{left, k, direction\}$ should give the same output for $\{n - left, k, 1 - direction\}$ because it's basically the same situation but in the reverse direction.

I tried to save this reverse key as well inside the DP when we calculate the main key, but that caused MLEs.
 

Submission 6 : Total removal of the reverse key concept

Link : https://codeforces.com/contest/1498/submission/279275427

As soon as I removed the concept of $reverseKey$ totally, the submission was accepted. This might not be because of asymptotic improvements, but instead because of constant improvements - because we are no longer making `count` calls on a `Map` which is $O(log\text{ } n)$. In this case if $n$ is large enough, this is going to take time. 

 

How much impactful was $reverseKey$?

In this case, as soon as we removed reverse key, we removed both items from the map, and queries to the map. Removing items from the map, improves the query performance for the remaining cases, if the number of items are large. Also, removing queries directly impacts the time complexity.