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