Comments

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
+3

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

On Mysterious109Help with a problem, 11 months ago
+3

Yes

On Mysterious109Help with a problem, 11 months ago
+12

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](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)) 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
0

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
+18

Yes

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

Fixed. Sorry about that

+18

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

https://mirror.codeforces.com/contest/478/submission/81478816

https://mirror.codeforces.com/contest/1307/problem/F

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

-29

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.

+20

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