# | User | Rating |
---|---|---|
1 | tourist | 3757 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
5 | nor | 154 |
5 | maroonrk | 154 |
7 | -is-this-fft- | 152 |
8 | Petr | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
+3
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 |
0
Yeah, I saw. But I wonder if there isn't a nicer way. |
0
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? |
+3
Actually, not sure if this is convex... It still should solve in $$$O(N^2)$$$... |
+3
Yes |
+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. |
0
Auto comment: topic has been updated by NaimSS (previous revision, new revision, compare). |
+47
Go Brazil! |
+3
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). |
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 |
+25
You guys deserve it! Best of luck at IOI! |
+18
Yes |
+26
MatheusLealV, NaimSS, tdas, Latin America, Brazil, UNICAMP |
0
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 |
0
Oh. Now It makes sense. Ty |
+10
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)? |
0
OK! thanks |
0
How to become a participant in this group? |
0
How to take part in the contest? Seems like I'm not allowed to register |
On
imtinanjibon →
wrong answer on codeforces compiler but in my pc gives correct answer., 4 years ago
+6
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 |
+5
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... |
Name |
---|