1476D - Journey

Tags :

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

 919D - Substrings

 Link : https://codeforces.com/contest/919/problem/D

Thought process

 

It is given inside the problem statement that if the value is arbitrarily large, output -1 instead. The total value can be arbitrarily large only in a single case - When there are one or more cycles present inside the graph.

So firstly, we need to run a cycle detection on the graph, and if there is one present, we can output -1.

If there is no cycle, then we need to think further. Let's think about local and global minimas. Can a local minima be used inside a global minima (this is the question we ask while solving DP problems too).

In this case, can the answer of a child node, be used for a parent node?

Let's see -

Let's say we have the graph:

6 5
abcaab
1 2
1 3
2 4
2 5
3 6

The answer in this case is clear - It's 2. We can either go $1 \rightarrow 2 \rightarrow 4$ or $1 \rightarrow 2 \rightarrow 5$. In both the cases, the two a's will have the maximum count.

Now let's say we only see the node 2 and it's children. Then the answer is 1, and it can be 'a' or 'b'. But in order to use this data in the parent, we need to have information of both of these stored, so that the parent can use them.

What we can simply do, is that at each node, we keep the maximum count of each letter. So at 2, we keep maxCount[a] = 1, and maxCount[b] = 1. Similarly, in 3, maxCount[b] = 1 maxCount[c] = 1

We can use a simple DFS here, and when we are coming up, from the children, we can keep the maximum of each character inside the parent's max character count map. We then will want to add the parent's character to the max count.

We can then take the maximum of each character, and that would be the answer.

My submission : https://codeforces.com/contest/919/submission/220805757

1684D - Traps

#codeforces

Question link : https://codeforces.com/problemset/problem/1684/D

Crux

Let’s say we instantaneously get a damage of \(n - i\) when some trap is skipped (instead of addition to the damage done by the traps after this trap as bonus).

But this has an issue right? Let’s say we skip a trap, add \(n-i\) and later we skip another trap. In that case, this trap didn’t give the additional bonus damage, so the current skipped trap’s damage will decrease to \(n-i-1\). So how are we dealing with that?

We are not. So let’s say we skip \(k\) traps. For the first trap skipped, we instantaneously added a damage of \(n-i\) (where \(i\) is the position of the skipped trap). Since there are \(k-1\) traps after this one, it means that we would actually have a damage of \(n - i - (k - 1)\). But we are taking \(n-i\). So we have \(k-1\) more damage here. Similarly, for the second trap \(n - i_{2}\) would be considered, which is \(k-2\) more than intended.

If we continue in this manner, we would have : \(k - 1 + k - 2 + ... + 1 = \frac{k \times (k - 1)} {2}\) more damage, than the actual value.

Let’s say we are comparing different permutations of traps to be skipped. If we just consider \(n-i\) values instead of \(n - 1 - (k - j)\) values (where \(k - j\) is the number of traps after the current traps), then in all cases, the sum would be \(k \times (k - 1) / 2\) more than the actual value.

So we can just depend upon the \(n - i\) increase in damage, and a decrease in damage by \(a_{i}\) (because the trap is being skipped).

So we create another array : \(b_i = a_i - (n - i)\), which points to the reduction in damage because of skipping the \(i^{th}\) trap. We sort this, and find k largest values.

Then we reduce the sum of these from the total sum. Then we also remove \(k \times (k - 1) / 2\) from the total, and that is the answer we are looking for.