Problem C3 from IMO13 shortlist (AoPS link):

Given an undirected graph. You can perform these 2 operations, one at a time:

1. Remove a vertex with odd degree.

2. Double the graph: for each u, create a copy u'; create edge (u', v') if there is edge (u, v); create edge (u, u') for all u.

Prove that there exists a sequence of these 2 operations such that after performing it, the graph will have no edge.

There's this greedy solution that seems to work really well, that is to remove the odd vertex with largest degree until there's no more odd vertices, then double the graph, then do the same over and over again.

It seems to work for all graphs with <= 7 vertices and for random large graphs. Moreover, the number of operations needed doesn't exceed 3N for all graphs I tested on.

Is it possible to prove that it will work for all graphs? And if it does, what is the upper bound of the number of operations?

Thank in advance.

Statement summary:

Given a string S of length N and an array L of size K. You need to find the shortest substring of S which contains K disjointed palindromes substring of size L[1], L[2]...L[K] in any order.

For example: if

S = aaappbbccccdrrr.

L = {4, 2, 3}.

Then the answer is 10 (the substring bbccccdrrr, aaappbbcccc satisfies too, but its length is 11).

Constraint:

• N ≤ 10⁵.

• K ≤ 13.

The best I can come up with is O(NK.2^K) which iterate over all position in S, consider it as the beginning of the substring and then DP with bitmask to find the end of the substring. Of course this won't fit in the TL.

I wonder if there exist some observation which will reduce the numbers of beginning position, or there is an entirely different approach that will fit in the TL.

Thanks in advanced.

Given an array A of size N. You have to perform K operations. Each operation is:

• Create a new element equal to the current number of elements.

• Decrease other elements by 1.

• Any element that is decreased to 0 will be removed.

• After that, sort the new array.

Example:

8311 -  > 742 -  > 6331 -  > 5422.

You need to find what the array will be after K operations.

Contraints:

• 1 ≤ Ai

• sum(Ai) ≤ 100

• K ≤ 10⁹.

I feel like this's gonna be a cycle detection problem. I've tested a few cases and I see that the cycle length is quite short. But I have no idea what the upperbound will be.

It'd be great if someone can help me prove an upperbound for this, or give me a testcase where the cycle length is large.

Thanks in advance !