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.