Problem statement
Link : https://codeforces.com/contest/1476/problem/D
Gist
There are $n$ cities, connected by one directional roads (L or R). If you move from one city to it's neighbouring city, then the direction of the roads reverses. Find the number of unique cities visitable from each city.
$1 \leq t \leq 10^4$
$1 \leq n \leq 3 \times 10^5$
Solution
Let's say that the current world is the normal world. If you move one time then all the roads are reversed, then we would have a "reversed" world.
Inference 1 : Even and odd moves affecting output world
If I am at city A, and I take odd number of moves to reach city B. Then if at A I was in the normal world, then at B I would be in the reversed world. But if I take even number of moves to reach city B, then I would be in the normal world.
We can create two DPs here : Ldp and Rdp.
Ldp[i] will have two values, 0 -> Number of cities visited, and reached city i while ending in a normal world. 1 -> Number of cities visited, and reached city i while ending in a reversed world. Note that Ldp will only consider reaching the city i from it's left.
Similarly, Rdp[i] will also have two values, 0 -> Number of cities visited, and reached city i while ending in a normal world. 1 -> Number of cities visited, and reached city i while ending in a reversed world. Note that Rdp will only consider reaching the city i from it's right.
Inference 2 : To end up in a normal world, the previous world should be reversed.
If I want to end up in a normal world, then the previous state should be a reversed world - because in one step, the reversed world will become the normal world.
Therefore to calculate $Ldp[i][0]$ we can use $Ldp[i-1][1]$ and check whether the road joining them is L in the normal world. This is because in the reversed world this L will be a R, therefore you can go from $i-1$ to $i$. If yes, then $Ldp[i][0] = Ldp[i-1][1] + 1$ otherwise it will be zero.
Similarly to calculate $Ldp[i][1]$ we can use $Ldp[i-1][0]$ and check whether the rod joining them is R in the normal world - because $Ldp[i-1][0]$ suggests that it's a normal world.
We do the similar thing to find $Rdp$.
Now for each city $i$ we have $Ldp[i][0]$, $Ldp[i][1]$, $Rdp[i][0]$ and $Rdp[i][1]$. We need to find a way to combine these to find our answer.
Inference 3 : $Ldp$ is an arrow from left to city $i$ and $Rdp$ is an arrow from right to left to city $i$
We can see $Ldp$ and $Rdp$ as arrows *towards* the city $i$ - so they can't just be added without thought.
Inference 4 : Even length paths between two cities are bi-directional
Consider that A->B<-C->D<-E
The reverse world is A<-B->C<-D->E
You can go from A -> B, then B->C, then C->D then D->E
Similarly, you can go from E->D, then D->C then C->B and then B->A
Inference 5 : Reverse of even length paths is useless
A->B<-C is useful
A<-B->C has no use
Inference 6 : Reverse of odd paths are useful
A->B<-C->D
A<-B->C<-D
Both of these are useful. Just the direction changes
Inference 7 : If I reach a place in odd steps, from a normal world, then it will be a reversed world at that place
A->B<-C->D
A -> B (reversed world)
B -> C (normal world)
C -> D (reversed world)
Inference 8 : Normal world even + anything works
If $Ldp[i][0]$ and $Rdp[i][0]$ both are even:
We can simply add $Ldp[i][0]$ and $Rdp[i][0]$ because we can reverse one of the arrows,
So initially it's -><- and I can reverse one arrow with no repercussions ->-> which makes a path, therefore I can add them.
Similarly, let's say one of these arrows is of odd length and the other of even length, then -><-. The even length arrow can be reversed to get ->-> OR <-<- depending upon which arrow was of even length. Again we can just add.
Inference 9 : Odd + Odd in a normal world also works
If $Ldp[i][0]$ and $Rdp[i][0]$ both are odd, then too we can add them.
Initially it looks like -><-.
If I use one arrow to reach $i$ then since the length is odd, the world becomes a reversed world. But the second arrow is an <- arrow in a normal world. Therefore we can reverse it in a reversed world. So this becomes ->-> which again is valid.
Inference 10 : We don't need to check $Ldp[i][1]$ and $Rdp[i][1]$
This is because the endings are inside reversed worlds. But if there is a path, then that would have been covered under the normal world checks because each path has cities which will be in a normal world and some cities which will be in the reversed world.
Working submission : https://codeforces.com/contest/1476/submission/308874075
