You can also achieve $$$O(sqrtN)$$$ using burnside lemma, by grouping terms by $$$gcd(n,k)$$$, which gives precisely the formula pointed out on wikipedia.

About incorporating a classical problem with higher constraints, I see no issue depending on the purpose of the contest. I actually added a version of it to my internal college contest: link

Yeah, I saw. But I wonder if there isn't a nicer way.

Nice! This seems to be from a series of weekly classes. Do you happen to have the link where I can access all of them?

On Mysterious109Help with a problem, 11 months ago

Actually, not sure if this is convex... It still should solve in $$$O(N^2)$$$...

On Mysterious109Help with a problem, 11 months ago


On Mysterious109Help with a problem, 11 months ago

I was thinking $$$dp[v][k][f] =$$$ min cost if you have to pick $$$k$$$ vertices from the subtree of $$$v$$$, and $$$f$$$ is 1 if you have to go all the way back to the root $$$v$$$ after getting the $$$k$$$ specials and $$$0$$$ if not.

Then we could solve this with a convolution on tree (similar to this problem): $$$dp[v][a + b][0] = min(dp[v][a][0] + dp[to][b][0])$$$ and $$$dp[v][a+b][1] = min(dp[v][a][1] + dp[to][b][0], dp[v][a][0] + dp[to][b][1])$$$.

This seems to be like a (min,+) convolution, which can be solved faster in this case since the $$$dp$$$ is convex, similary to this other problem, by mainting the difference $$$dp[v][a] - dp[v][a-1]$$$ and using small to large to merge this difference arrays.

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

Go Brazil!

This seems O(NlogN), or rather O(RlogR). You are basically summing $$$\sum_{x=l}^{r} (r/x) = r \sum_{x=l}^{r} \frac{1}{x}$$$. This is known as the [harmonic Sum]( and it grows in O(logN). For it to be O(loglogN) you would need to only iterate over the primes, as $$$\sum \frac{1}{p}$$$ growns in O(loglogN) (reference).

On vaavenCodeforces Round #852 Editorial, 16 months ago

It is a implicit restriction, due to the limit on N this case has no valid solution. I agree that this is misleading... maybe they didn't make it clear to avoid giving a hint

You guys deserve it! Best of luck at IOI!

On FattyLovesMangoesHow to solve this?, 22 months ago


MatheusLealV, NaimSS, tdas, Latin America, Brazil, UNICAMP

Fixed. Sorry about that


It could be solved in O(N + M) to. Binary search is not necessary, one could just "simulate". In case someone is interested: code

Oh. Now It makes sense. Ty

In problem G why can we ignore the initial order of chests and sort? I was thinking on a case like 4 40 400 400 600 and k=1. Where can I put the mimic so that the answer gives 330 (as it does with the editorial solution)?

OK! thanks

How to become a participant in this group?

How to take part in the contest? Seems like I'm not allowed to register

Maybe is because of the way your computer rounds doubles. I tried to put a + 0.5 to round it up and it passed the test 4 (but still got TLE). There can be another errors, since factorials with n = 1e9 can cause overflow

Does this problem really has 3200 rating? Seems like too much


Semi-rating or rejudging after taking out who had something wrong sounds like a better ideia than rooling back all the ratings. Only a small amount got stuck in div1E I suppose.


Can't just fix the rating of those negatively affected? Me and many others didn't suffer from those mistakes...