Same problems

Build topological order backwards (meaning reverse graph and apply greedy)

I would've swapped 500 and 250 personally :P

First, you can throw away any penalty token with value > $$$2*D$$$. This leaves at most 12 penalty tokens. Use a mask over those tokens.

Let $$$dp(mask)$$$ be the required expected value if we only had tokens which are activated in the mask. For each possible value of the roll i.e. for every value $$$v$$$ in the range $$$[2,2*D]$$$, try all possible ways of getting sum equal to $$$v$$$ (You can precalc those, each way is a mask of tokens). A way that uses tokens of the mask $$$x$$$ is valid if $$$x&mask = x$$$. Over all valid ways, find the one that has the minimum value of $$$dp(mask - x)$$$. add to $$$dp[mask]$$$ that minimum multiplied by the probability of rolling $$$v$$$.

Problem K. There is editorial online.

We don't care about numbers > 12 anyway. Let mask represent the numbers we haven't eliminated yet. For each state, we just try out every possible rolls, and try every possible ways to make a move with this roll.

let dp[mask]=the answer we get considering only the tokens corresponding to this mask.

For calculating dp[mask], we iterate through all the sum s[2,2d] and go to all the submask possible after removing sum s from this mask. We take the dp[submask] which gives the minimum answer for this sum s. If for a sum s, we can't make a transition to any other submask, then we consider the current sum remaining in this mask. So we get for each sum s, the minimum possible answer we can form.

After this we can calculate the answer for dp[mask] by taking expected value of sum s for all s from [2,2d].

Div1 1000 is a very interesting problem :)

First, since we need to flip every vertex at least once, the closed walk should be spanned all $$$N$$$ vertices. Second, suppose there is an edge between $$$v_1$$$ and $$$v_2$$$, and we go from $$$v_1 \rightarrow v_2$$$, going by $$$v_1 \rightarrow v_2 \rightarrow v_1 \rightarrow v_2$$$ makes "extra flip" of color of vertex $$$v_1$$$ and $$$v_2$$$. We define such move "anti-shortcut of $$$v_1 \rightarrow v_2$$$".

Now, let's suppose that the given graph is a tree. There is a unique closed walk of length $$$2N-2$$$, which passes each edge twice. When we walk in the determined closed walk, the color of vertex $$$i$$$ will be black if $$$deg(i)$$$ is even, otherwise it will be white.

Since the sum of degree of each vertices is even, if the graph size $$$N$$$ is even, there will be even number of vertices which will be white. Now let's choose two white vertices $$$w_1$$$ and $$$w_2$$$ and do anti-shortcut for all edge of direct path between $$$w_1$$$ and $$$w_2$$$. The maximum possible length of the closed walk will be $$$4N$$$.

The last problem is if $$$N$$$ is odd. If there is an odd cycle, going around it will make all vertices on cycle flipped. So, the parity of number of white vertices will change! Thus, we can solve in this pattern with maxium length $$$4N + N = 5N$$$.

If $$$N$$$ is odd and the graph is bipartite... there's no way to complete the game. That's because the length of closed walk will be even because of bipartiteness of graph, but the length of closed walk "should be" odd because we need to flip vertices odd times.

Notice that we can invert the colours of any two vertices $$$a$$$ and $$$b$$$ with a cycle $$$a \rightarrow \ldots \rightarrow b \rightarrow \ldots \rightarrow a$$$. We can also use the root as vertex $$$a$$$. The only problem can be when everything except the root becomes black — then we need one odd-length cycle (so the only impossible case is bipartite graph, odd $$$N$$$). This way, we can get a solution with many edges.

Now we can reduce the number of edges — if an edge $$$u-v$$$ is used $$$x$$$ times in the direction $$$u \rightarrow v$$$ and $$$y$$$ times in $$$v \rightarrow u$$$, where $$$x, y \gt 2$$$, we can reduce $$$x$$$ and $$$y$$$ both by $$$2$$$. The above approach gave us $$$|x-y| \le 1$$$, so this will result in either $$$x=y \le 2$$$ or $$$x \le 2, y \le 3$$$, which is $$$\le 5M$$$ moves. Next, all except at most one of these edges (in the odd cycle) can be from a DFS spanning tree. That actually gives at most $$$5N$$$ moves (details skipped).

Finally, when we know how many times each edge is used, we can bruteforce an Eulerian cycle on them.

But it's true that only around 1/3 of people are solving Div1 500, despite around 2/3 of people are solving Div1 250. If you'd turn 500 to 250, it will be "DesperateForces" which is only enjoyable to high-rated coders :)

I think Div1 500 is the problem which the solution is easy to come up with higher rated coders, and also implementation is easy, and that's why many high-rated coders got more than 450.00 points, but for blues and lower-yellows, coming up with such accurate greedy algorithm is difficult, when the problem comes to be not a typical greedy pattern.

So, problemset where I submit everything in 45/75 mins and ~40 users submit everything in time is on the hard side (some solutions failed, but that should be mainly attributed to weak samples)? K