It will look terrifying soon enough :D

OK I'll take a stab at showing my thought process. I got it accepted.. after the contest naturally :-(

Let n = |s|
Because n <= 300, the worst we can shoot for is O(n^3)
So we can't do a recurrence based on a function like:
f(x,y,p,c) = max claps,
........if robot is at (x,y), and
........at position p in the program, and
........c allowed changes are remaining

Because that would be O(n^4), even worse since x,y can be -300..300 (yes, yes it's still O(n^4).. you know what I mean).

So I tried for a recurrence based on this:
f(p,c) = max claps if robot is at the origin, and
........the program is at position p in the program, and
........c changes are remaining.
With that definition of f, we want to know f(0, changesAllowed).

Basically the problem boils down to, what is the maximum number of contiguous substrings we can split up "s" into, such that each substring returns robot to (0,0).

To know f(p,c) consider a substring of the program from [p..q]. The robot is at (0,0) now and suppose with "t" changes we can make that substring return the robot to (0,0). Then we can check 1+f(q+1,c-t).

Thus we can check

result=0;
for (q = p; q < n; q++)
    if (s[p..q] can be returned to origin with t changes && t <= c)
        result = max(result, 1+f(q+1, c-t));

With memoization, this recurrence has n^2 states. If you can do the loop in O(n) then the runtime is enough. To do the loop in O(n) you need to be able to compute the vertical/horizontal delta of the program substring s[p..q] in O(1) time, which can be done with some precomputed arrays or, as I later saw some smarter people do, just by keeping track of the count of U,D,L,R chars as you iterate the above loop.

I got everything above in the contest except I couldn't nail down the condition in the if() statement above, which is the actual movement logic of the blasted robot with the allowed changes. First, the substring s[p..q] needs to be even in length. Second, by adding up the U,D,L,R in s[p..q] then |U-D|+|L-R| is the manhattan distance M of the robot from the origin. To bring him back to the origin, you need to be able to change at least M/2 characters, so finally, you need (|U-D|+|L-R|)/2 <= c in order to continue the recurrence with this q.

To see this last part, consider that any string like "DL" can be turned into either "RL" or "DU", i.e. by changing half the letters we can bring him back to (0,0).

Sorry, I don't know how to write short.

Make a depth-first search for each starting node and try to reach a depth of 4. Obviously you have to remember the nodes of your current path, so that you don't visit a node twice.

I solved it this way:

If there were n-1 edges, check if the diameter of the tree is >= 4

If there were n edges, delete each edge one by one and check diameter

Else, if there are more than n edges there will always be a path of length 4

There are simpler solutions .-. I completely overthought the problem

It's called color coding. Let k = 5.

(1) Assign one of k "colors" uniformly at random to each vertex. (2) Check if there is a simple path of length k with distinct colors (it can be solved in O(2^k * E) using a simple bitmask DP) (3) Repeat the above process sufficient number of times.

In each iteration, the probability of success is k! / (k^k) ~ 1 / e^k, so we need to repeat it O(e^k) times. In total the problem can be solved in O((2e)^k * E).

You need to choose a pair of edges (a, b) and (c, d) such that b and c are adjacent and there is an edge from a to some vertex e such that e != b, e != c, e != d. If the degree of a is greater than 3, it's always possible, otherwise check all neighbours of a.

The solution with bitsets: let's iterate over (x, y) the second and the fourth vertices. Now we can check if they have common vertex by ANDing their bitsets (g[x] & g[y]).count() > 0. And the last thing that we should check that the degrees of vertices x, y are at least 2. The only bad case that we should not count when degree[x] = degree[y] = (g[x] & g[y]).count() = 2.

Another approach: there are K edges (K <= 2000), so you can compute all 3-point segments in O(K^2). Each segment is like this:

(End node 1) — (Mid node) — (End node 2).

For each segment, I had to check if there is a segment such that [end node 1 or 2] is end point, but the other nodes are different from original.

Iterating over segments vector, I computed how many times node x is end and node y appears (used count[N][N]). Also, saved how many times node x is end (used freq[N]). After that, just checked for each segment if freq[end_1] >= count[end_1][mid] + count[end_1][end_2]. Note '>=' is because original segment was counted twice.

I just wrote five nested loops which clearly have a coding-deep-at-night look. They perform just like the simple recursive search mentioned above. The complexity is perhaps O(n²) on a connected graph: the graphs for which the answer is :( are very restricted, and otherwise, an answer is easy to find.

Interesting. After finding the first bug why didn't you correct it instead of searching for a bug in the second problem?

Is this one fine?