zxqfl's blog

By zxqfl, history, 9 years ago, In English

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(n3). 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 46 = 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 time, so the algorithm is .

I think this algorithm is actually O(n2) 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(n3): there are n2 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 . 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 a0, ..., an - 1 be the chance of K being equal to 0, ..., n - 1. Let b be Bob's expected score. Then:

a0 + ... + ai ≤ i / n
ai ≥ 0
b ≥ a0v0 + ... + aivi + ai + 1vi + ... + an - 1vi

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.

  • Vote: I like it
  • +32
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Not sure what is wrong with my math typesetting. The plaintext is here: http://pastebin.com/vBqHwCB4

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is 5 nested for loops / DFS supposed to pass for div1 easy? The only solutions I saw that passed were in this form.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Can you find a counterexample?

    I think these solutions are generally correct because they run in time on every graph where the answer is no. So if you want to make them TLE then the answer must be yes, which means they will terminate early.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    From the point of view of someone who coded that without knowing the possible no cases, here's a proof that it should run in time:

    Look at the first 4 vertices in the nested for-loops, say they are a,b,c and d.

    (a,b) is an edge, (c,d) is an edge, so ignoring the restriction that b and c are connected, you already have only edges^2 possibilities for the 4 vertices, which is small enough.

    Of course, if a fifth vertex is found by the dfs/nested loops, you can immediately terminate and return Yay!, which is why I assumed you'd never find a fifth vertex.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

come up with a similar solution with you in DIV1 med, but there are too many corner cases, could you explain more?