SRM 682 Unofficial Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Div2 Easy

The size of the input string is small, so we can iterate over all the substrings and find the largest substring consisting of the characters A, C, G, and T. The complexity of this approach is O(n³). You could solve it in O(n) using the two-pointers method.

Div2 Medium

I claim that the answer will always have at most 6 characters. There are at most n substrings of length 6 of a string of length n. The length of the input string is at most 2000. But there are 4⁶ = 4096 possible DNA sequences of length 6, so at least one of them isn't contained in the string.

That means that we can afford to iterate over all possible answers, in increasing order of length. We will try at most 2000 + 1024 + 256 + 16 + 4 strings, and checking each string will take $\text{[math]}$ time, so the algorithm is $\text{[math]}$ .

I think this algorithm is actually O(n²) because it is hard to induce worst-case behaviour in the string-checking algorithm, but I haven't proved it.

Div2 Hard

We will use dynamic programming. The state is: suppose we are at position i in the string, we have j changes available, and the robot is currently at (0, 0). Then, we iterate over how many moves it will take for the robot to return to (0, 0). If we know it will take x moves, then it's computationally easy to find the minimum number of changes to make this happen: suppose that if we made no changes, the robot would end up at distance d. Then by making d / 2 changes we can ensure that the robot reaches cell (0, 0).

The complexity is O(n³): there are n² states and each state has n possible transitions.

Div1 Easy

There are a few ways to solve this problem.

One way is this: not hard to code, but difficult to prove. It turns out there are only 3 cases where the answer is no. Here they are, crudely drawn in paint.NET by yours truly about 20 minutes ago:

So, you could manually check these cases.

You are probably interested in a provable solution. We can use the following lemma:

In any graph of n vertices where every vertex has degree at least d, there is a simple path of length min(n - 1, 2d).

This is pretty hard, so I asked someone else to prove it. Here is a proof written by my friend Sina Abbasi:

Take the longest path P in the graph, suppose it is length L. Out of the vertices not in P, take the one v which is connected to a vertex closest to one of the endpoints of P (distance measured on path). Suppose this distance is a>=1. Then each vertex not in P can only be connected to L-2a possible vertices, but it can't be connected to two consecutive ones on the path otherwise there's a longer path, so L/2-a. So if we take the subgraph H by removing P, each vertex has degree at least d+a-L/2. Now follow one end of P until you get to the vertex v is connected to, then follow a path from v for as long as you can outside of P. By a greedy argument this path has length at least L-a+d+a-(L)/2 = (L)/2 +d. Since L was maximal we get d <=L/2 which implies the desired result. I don't know if I did the calculations are completely correct but I think this idea gives the desired bound.

Anyway, once we have this lemma you can reduce the leaves (just mark the remaining vertex with the associated path length). Then you're left with a graph, and if it has a lot of vertices then the answer is immediately yes. Otherwise, there aren't very many vertices left, so you can brute force.

Div1 Medium

The answer is $\text{[math]}$ . Wait, that fails the sample case with a cycle of length 4. We have to subtract 1 if there is a vertex on the cycle with exactly 2 neighbours.

This is actually just the maximum connected dominating set problem asked on a pseudotree. Problem authors are getting lazy these days.

Div1 Hard

Challenge phase ends in 5 minutes as I write this so let's make this quick. Let's pretend Bob knows the probability distribution, and the game show picked the worst-case distribution knowing that Bob would know it. The answer to this problem will be the same as the answer to the given problem. Wait, what?

https://en.wikipedia.org/wiki/Minimax_theorem

So, we've switched the problem. How does this make it easier?

Let a₀, ..., a_n - 1 be the chance of K being equal to 0, ..., n - 1. Let b be Bob's expected score. Then:

$\text{[math]}$ a₀ + ... + a_i ≤ i / n a_i ≥ 0 b ≥ a_0v₀ + ... + a_iv_i + a_i + 1v_i + ... + a_n - 1v_i

We can find the minimal value of b with the simplex algorithm.

There's also a solution using binary search that the round tester created. It is pretty cool, but I am not confident that I can explain it.