TurnOnLamps editorial

This is the one other interesting problem in the match. Remember I solved this problem during the match and even wrote a quick explanation already? It is interesting, I knew there was a greedy, but I didn't know if I was going to prove it, so I proposed me to write the editorial about the same dynamic programming approach. Interestingly, while I was writing that explanation, I could see through the problem and notice the idea nad proof for the greedy approach. It is not the first time that the process of writing an explanation for a problem teaches me more about the problem than just trying to solve it. For this reason, there are times I consider it very (VERY) seriously to write explanations for problems at the same time as I am participating in the contest.

I should finally be done with this SRM 583 editorial soon. The other problems are all implementation ones (I fear the explanations will end up boring and tedious). Then I have to write the editorial for round 3B. This job is becoming a busy one.

TurnOnLamps

We have a trees. There are lamps in each of its edges. Some are on, some are off. In a single step, you pick two vertexes and toggle the lamps between the two vertexes. There is a list of important edges that must end with a turned-on lamp (state = 1). Return the minimum number of simple paths you need to pick.

Number of paths and parity

The city is a tree and there are important edges (roads) and unimportant ones. Whenever we pick a pair of vertexes, all the lamps in the simple path between them are toggled. An important edge that starts with a turned-on lamp has to belong to an even number of picked simple paths. If instead, the important edge starts with a turned-off lamp, then it has to be picked an odd number of times. To simplify, we can say that unimportant edges can be picked an even or odd number of times. So we just need to minimize the number of paths we pick following the requirement of the parity of the number of times each edge is picked.

At most once

Since the problem depends on the parity of the number of times we use each edge, let us try to see what happens after we make that decision for each edge. For each edge `(u,v)`, decide the number of times it is picked in a path. Then we try to think of the paths that follow this rule. This is the time where we find out something interesting. Imagine an edge is used two times, by two separate paths:

Since the edge is used twice, its state is not affected at the end. The trick is to notice that those two paths would alter the states in the same way as the following two paths:

And in this case, the edge in question is not visited at all. We can generalize this idea further, it is never necessary to pick the same edge more than once, whenever that happens, we can find an equivalent combination of paths that have the same effect.

Exactly once

We cannot pick an edge more than once, but there are edges that we must pick at least once (Important edges that start with a state equal to 0). Then we have to pick them exactly once. There are other edges that must be picked an even number of times (important edges with initial state equal to 1), since 2 or more picks are not allowed, we must pick these edges zero times - don't pick them at all.

Greedy approach

All important edges with lamp state = 0 must be picked exactly once, we just need to minimize the number of paths that include them. The paths must not include any important edge with lamp state = 1.

There are `O(n^2)` total simple paths in the tree. We can just find each valid one of them. For each path, count the number of important edges with state = 0 that it contains. Then we can just pick the path with the largest amount of important edges it changes and make the change. This approach is optimal because any remaining important edge with lamp state = 0 will have to be changed eventually anyway. Making the changes in the path, can only make other paths unable to be picked in the future, if the other paths share at least one important edge with state = 0 with the largest path. If they do, however, we will always be unable to pick a smaller path that will contain the remnants of the path that is now unable to be picked. Thus the decision can only decrease and never increase the total number of used paths.

Finding the paths

The step to find the simple path between two vertices in the tree is a implementation challenge of its own. Since it is a tree, there is only one simple path and we can use any graph search like a Depth-first search (DFS). We just need to count the number of important edges afterwards.