Auto comment: topic has been updated by MofK (previous revision, new revision, compare).

tourist didnt participate in the contest yet he first solved H. ig there is some mistake

unprovedforces

D should not appear

What are the more elegant solutions to G? Is it possible to explain without formulas and latex?

Not a tester, but I found my solution to G satisfying, so I'll write it up below:

Sort the balls in order of position. We express the answer as $$$\sum_{i = 1}^n p_i e_i$$$, where $$$p_i$$$ is the probability that ball $$$i$$$ is the last ball remaining and $$$e_i$$$ is the expected time it will take for there to be only ball remaining conditional on the last ball being ball $$$i$$$.

Let $$$d_i$$$ be the distance between ball $$$i$$$ and the ball immediately before ball $$$i$$$, which we will call $$$b_i$$$. Note that the probability that ball $$$i$$$ is the last one remaining is equal to the probability that ball $$$i$$$ overtakes ball $$$b_i$$$ before $$$b_i$$$ overtakes $$$i$$$. Let $$$d_i$$$ be the distance from $$$b_i$$$ to $$$i$$$. Then we claim that $$$p_i = d_i / m$$$. The general idea is that when we move ball $$$i$$$, the value $$$d_i$$$ increases by $$$1$$$, while when we move $$$b_i$$$, $$$d_i$$$ decreases by $$$1$$$. Moving any other ball will not affect $$$d_i$$$. Thus, with each move of ball $$$i$$$ or $$$b_i$$$, $$$d_i$$$ is equally likely to increase or decrease by $$$1$$$, and we want to find the probability that $$$d_i$$$ reaches $$$m$$$ before it reaches $$$0$$$. This is a well-known result (try to prove it if you haven't seen it before!), establishing $$$p_i = d_i / m$$$.

Now we compute $$$e_i$$$. Let $$$f(x)$$$ be the expected number of times either ball $$$i$$$ or ball $$$b_i$$$ moves before ball $$$i$$$ is the only one remaining, conditional on ball $$$i$$$ being the last one left in the end, conditional on $$$d_i = x$$$. Then, when $$$d_i = x$$$ for $$$0 < x < m$$$, we have a $$$1/2$$$ chance of moving to $$$d_i = x+1$$$ and a $$$1/2$$$ chance of moving to $$$d_i = x-1.$$$ However, the probability that ball $$$i$$$ is the last one left becomes $$$\frac{x+1}{m}$$$ and $$$\frac{x-1}{m}$$$ in the two cases. Thus, the probability that we move to $$$d_i = x+1$$$ conditional on ball $$$i$$$ being the last one left is

This gives

We can prove that $f(x) = \frac{2x+1}{3} + f(x+1),$ and with $$$f(m) = 0$$$, we can compute the value of $$$f(x)$$$ for any $$$x$$$ efficiently. Then, for a given $$$d_i$$$, we have $$$e_i = \frac{n f(d_i)}{2},$$$ since in expectation we use $$$f(d_i)$$$ moves of ball $$$i$$$ and the ball immediately before $$$i$$$, and each turn we have a $$$\frac{2}{n}$$$ chance of using such a move. (Note that it's fine to assume that whether or not we use one of these two balls each round is independent from the number of turns it takes to finish the process, since using any other ball will not affect $$$d_i$$$.)

We can then sum up $$$\frac{n p_i f(d_i)}{2}$$$ to finish the problem.

I'm not sure this will be particularly comprehensible, so feel free to post questions below and I can try to answer them.

I think it's super important in G to note that $$$g(0)=0$$$ is a choice one needs to make since once a $$$0$$$ comes along in $$$d$$$, you normally need to take it out. It is then crucial that even if you temporarily kept it in (just for the computation of $$$h$$$), under our assumption of how $$$f$$$ looks like, $$$f(d_1\ldots d_k, 0, d_{k+1}\ldots d_{m-1})=f(d_1\ldots d_{m-1})$$$.

My solution to G:

We can note the game ends when ball $$$i$$$ reaches ball $$$i-1$$$ for any $$$i$$$. Clearly only one of these events happens and picking the other balls doesn't change anything in the distance between $$$i$$$ and $$$i-1$$$ so we can solve $$$n$$$ games that only have balls $$$i$$$ and $$$i-1$$$ separately. Our final answer is sum of (probability ball i overtakes i-1) * (expected time) for all subgames.

The problem with only two balls is known as "gambler's ruin": to solve for the expected time, you can write the markov chain equations relating the expected time in terms of the distance $$$d$$$ between the balls and solve them, but also the final result of $$$E_d = \frac13 (m^2 - d^2)$$$ is well-known and can be found online.

Is there any way to solve D without mathematics?

I'm curious about the meaning of the number 60 in D. Was there any other intended solution or was the number just there to deceive people?

how was abababa...baba for 10^6 characters not part of pretests for E https://mirror.codeforces.com/contest/1951/submission/255334003

Can someone explain why p1 = n — k + 1 in D? It's like out of nowhere for me.

For problem E,

Nevertheless, we tried our hardest to make sure dumber "solutions" won't pass.

Unfortunately, my dumber solution has passed. Just for 100 random positions I checked if I partitioned the string into 2 at that position, are those strings not palindrome?

In the tutorial of the problem D the authors incorrectly opened brackets, so we should check the inequality $$$2k > n + 1$$$ instead of $$$2k > n - 1$$$.

MofK ⇒ p1q−p1−2q ≥ 2 this should be -2. Please change this ...

I: I wonder whether there's a solution that provably runs in time. If $$$F(n,m)\propto n^2m$$$ when Dinic is used, then $$$m\cdot \log W\cdot n\cdot F(n+m, n+m)$$$ could be very large (maybe on the order of $$$10^{12}$$$).

Also, the time limit is rather tight, depending on the implementation. I tried submitting two different solutions, both using AtCoder's flow template and running in the intended time complexity. The slower one is 2.5x slower, and runs just under the time limit. 255377849 255377303

(and when I used my own Dinic template in the slower solution, it TLEd due to constant factor. guess I need to rewrite it :P)

It seems like explanation for D contains a mistake. How is this transition possible? ⇒p1q−p1−2q≥2 shouldn’t it be -2 in this inequality’s right hand side?

Awesome round

I had a solution to H that didn't involve binary search. 255380772

First, precompute for each subtree a list of the values within the subtree sorted from greatest to least. This takes $$$O(k2^k)$$$ time.

Then for each $$$t$$$, go bottom-up starting from the nodes at depth $$$t$$$. Compute for each subtree and each $$$k'$$$ in the range $$$[0, depth(\text{subtree root})]$$$ the quantity $$$dp[\text{subtree root}][k']$$$, which we define to be the maximum value $$$m$$$ for which Alice can win the subtree if she can replace $$$k'$$$ nodes in the subtree with $$$\infty$$$. For a node at depth less than $$$t$$$ with children $$$c_1$$$ and $$$c_2$$$, this is possible if there are at least $$$2^{t-depth(\text{subtree root})}-k'$$$ values in the subtree at least $$$m$$$ and there are non-negative integers $$$k_1'$$$ and $$$k_2'$$$ such that $$$dp[c_1][k_1']\ge m$$$, $$$dp[c_2][k_2']\ge m$$$, and $$$k_1'+k_2'=k'+1$$$. Computing the DP values can be done in $$$O(t2^t)$$$ time for a single $$$t$$$.

The overall time complexity is $$$O(k2^k)$$$, though the constant factor is quite poor.

I was fully confused at problem D.

.

Why is brute forcing partitions of 2 considered a dumb solution? :facepalm:

Problem E. For those who got the intuition of dividing the string in two parts but were not able to implement or think of an algo during the contest for problem E. we could just use manacher's algorithm and then we can try to divide the string in two parts at any index i for which 0...i is non palindrome and i+1...n is also non palindrome that works in O(n).I remember in contest div2 934 D there was this question which can also be solved using manacher's algo ... Upsolving or just looking at the idea helps in improving. Unpopular opinion

we dont have a solution for E in 3 cases

1 — all chars are the same 2 — chars are alternating and the string length is odd 3 — all chars are the same except for the middle char and the string length is odd (aaabaaa)

if none of these constraints is satisfied we always print the string if its not palindrome otherwise we take the first 2 chars in the first partition and the rest of the chars in the second partition if the first string is still a palindrome we take the third char from the second partition and insert it into the first partition and so on until the first string length reaches 4 then its never a palindrome after

greedy solution here 255354790

D is a little bad, just a problem for guess.

I never thought D would be so concise. My attention has always been focused on 60.

can someone please explain why DP approach fails at C for everyday a for loop can be used from 1 to maximum allowed tickets..

whats wrong with that?

I think D is easier than B, i kept debugging B for an hour lol.

constructforces

:(

I think you can easily solve problem G if you have solved 1349D - Slime and Biscuits or 951F - Company Acquisitions before and understand the content related to potential functions.

The contest is just trash.

guessforces

Why do people hate D so much? I'm personally okay with the problem

Thank you for fast editorial

contest is so bad :v it will be better if it does not have much trick like that

Midway doing B, i stared at the numbers, saw 727 and suddenly "WHEN YOU SEE IT" came out of my mouth. My favorite beatmap so far, thanks MofK and Kuroni for that one.

Alternative solution to problem E:

First eliminate the case where $$$s = a...a$$$ and $$$s = abab...aba$$$ since they don't have solution.

Then consider find first character $$$s_t$$$ ($$$s_t \neq s_1$$$) and cut off $$$s[1, t]$$$, obviously this is not a palindrome. If we keep doing it until we can't, the rest of the string is either empty or $$$s = a...a$$$.

For the first case, we are done. For the second, consider merge this string back to the last partition we make, if it is still an palindrome, it would be like $$$s = a...aba...a$$$, then just try to merge one more time, if it is still an palindrome, it would be like $$$s = a...aba...aba...a$$$, in such case, just cut this string into half and both of them won't be palindrome.

Can anyone share their intuition for C? I completely messed up my contest because I took way too long to figure C out, I was able to get AC only after I figured out the proper mathematical proof. I initially was able to figure out that we need to select $$$\lceil\frac{k}{m}\rceil$$$ days with minimum prices, but I couldn't figure out how to distribute the $$$k$$$ tickets among those days.

Initially, I came up with an idea that I can buy $$$k\mod{m}$$$ tickets on the first day and $$$m$$$ on the rest of the days because I felt that buying more tickets earlier isn't good as it'll increase the cost, it passed samples but I got WA on pretest 2. Then for a long time I couldn't really figure out how to fix this, later when I came up with the mathematical proof I realized that the $$$k\mod{m}$$$ tickets should be assigned to the largest one among the $$$\lceil\frac{k}{m}\rceil$$$ smallest elements.

I think most people wouldn't have come up with the mathematical proof for this problem, so how does one get this intuition?