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
