Hello everyone. I have noticed the absence of round 273's editorial, so I decided to write one. This is the first time I write an editorial, so hope everyone like this!↵
↵
I didn't know how to solve C and E yet, so it would be appreciated if someone help me with these problems.↵
↵
Also, how to use LaTex in codeforces? I want to use this so my editorial would be more clear to read.↵
↵
**UDP:** Actually, there's a (well-hidden) tutorial for this round, but it's written in Russian (with a English version using google translate in comment section). If you can read Russian, [click here](http://mirror.codeforces.com/blog/entry/14307#comment-192751).↵
↵
**UDP2:** Problem C is now available!↵
↵
A — Initial Bet↵
===============↵
Since the coin only pass from this player to other player, the coins sum of all player won’t change in the game. That mean, we’ll have `5*b = c1+c2+c3+c4+c5`. We’ll put `sum = c1+c2+c3+c4+c5`. So, if `sum is divisible by b`, the answer will be `sum/b`. Otherwise, the answer doesn’t exist.↵
↵
Be careful with the case `0 0 0 0 0` too, since `b > 0`, answer doesn’t exist in this case.↵
↵
**My solution:** [submission:11607374]↵
↵
**_Complexity: O(1)**_↵
↵
↵
B — Random Teams↵
================↵
If a team have `a` participants, there will be `a*(a-1)/2` pairs of friends formed.↵
↵
For the minimum case, the participants should be unionly – distributed in all the team. More precisely, each team should not have more than one contestant compared to other team. Suppose we’ve already had `n div m` contestant in each team, we’ll have `n mod m` contestant left, we now should give each contestant left in first `n mod m` teams.↵
↵
For example, with the test `8 3`, we’ll first give all team 8 div 3 = 2 contestants, the result now is `2 2 2`. We’ll have 8 mod 3 = 2 contestants left, we should each contestant in the first and the second team, so the final result is: `3 3 2`.↵
↵
The maximum case is more simple, we should give only give one contestant in first `m-1` teams, and give the last team all the contestant left. For example with above test, the result is `1 1 6`.↵
↵
Since number of the contestant in one team can be 10^9, the maximum numbers of pairs formed can be 10^18, so we should use `int64` (`long long` in c++) to avoid overflow.↵
↵
**My solution:** [submission:11607784]↵
↵
**_Complexity: O(1)**_↵
↵
C — Table Decorations↵
=====================↵
Unfinished...[user:spiderbatman,2015-06-17] has a great idea for this problem. You can read his comment [here](http://mirror.codeforces.com/blog/entry/14282?#comment-192710).↵
↵
The order of the balloons isn't important, so instead or `r`, `g`, `b`, we'll call them `a[0]`, `a[1]`, `a[2]` and sort them in ascending order. We'll now have `a[0] <= a[1] <= a[2]`.↵
↵
There's two case:↵
↵
- `2*(a[0]+a[1]) <= a[2]`. In this case, we can take `a[0]` sets of `(0, 2, 2)` and `a[1]` sets of `(1, 2, 2)`, so the answer is `a[0]+a[1]`.↵
↵
- `2*(a[0]+a[1]) > a[2]`. In this case, we can continuously take a set of two balloon from `a[2]` and a balloon from `max(a[0], a[1])` until a point that `a[2] <= max(a[0], a[1])`. At this point, `max(a[0], a[1])-a[2] <= 1`, and since `max(a[0], a[1]) - min(a[0], a[1]) <= 1` too, `max(a[0], a[1], a[2]) - min(a[0], a[1], a[2]) <= 1`. All we have to do left is take all possible `(0, 1, 2)` group left. Since we only take the balloons in group of 3, `(a[0]+a[1]+a[2]) mod 3` doesn't change, so there will be at most `(a[0]+a[1]+a[2]) mod 3` balloons wasted. We go back to the beginning now. The answer is `(a[0]+a[1]+a[2]) div 3`.↵
↵
**My solution:** [submission:11614150]↵
↵
_Complexity: O(1)_↵
↵
D — Red-Green Towers↵
====================↵
For more convenient, we’ll call a function `trinum(x) = (x*(x+1))/ 2`, which is also the number of blocks needed to build a tower with height `x`.↵
↵
First, we’ll find h, the maximum height possible of the tower. We know that `h <= trinum(l+r)`. Since `(l+r) <= 2*10^5`, `h <= 631`, so we can just use a brute-force to find this value.↵
↵
Now, the main part of this problem, which can be solved by using dynamic programming. We’ll `f[ih, ir]` the number of towers that have height `ih`, can be built from `ir` red block and `trinum(ih)-ir` green blocks. ↵
↵
For each `f[ih, ir]`, there’s two way to reach it:↵
↵
- Add `ih` red block. This can only be done if `ih <= ir <= min(r, trinum(ih))`. In this case, `f[ih, ir] = f[ih, ir] + f[ih-1, ir-ih]`.↵
↵
- Add `ih` green block. This can only be done if `max(0, trinum(ih)-g) <= ir <= min(r, trinum(ih-1))`. In this case, `f[ih, ir] = f[ih, ir] + f[ih-1, ir-ih]`.↵
↵
The answer to this problem is sum of all `f[h, ir]` with `0 <= ir <= r`.↵
↵
We will probably get MLE now...↵
↵
**MLE solution:** [submission:11600887]↵
↵
How to improve the memory used? We'll see that all `f[ih]` can only be affected by `f[ih-1]`, so we'll used two one-dimension arrays to store the result instead of a two-dimension array. The solution should get accepted now.↵
↵
**Accepted solution:** [submission:11600930]↵
↵
**_Complexity: O(r*sqrt(l+r))**_↵
↵
↵
E — Wavy numbers↵
================↵
↵
Unfinished...↵
↵
I didn't know how to solve C and E yet, so it would be appreciated if someone help me with these problems.↵
↵
Also, how to use LaTex in codeforces? I want to use this so my editorial would be more clear to read.↵
↵
**UDP:** Actually, there's a (well-hidden) tutorial for this round, but it's written in Russian (with a English version using google translate in comment section). If you can read Russian, [click here](http://mirror.codeforces.com/blog/entry/14307#comment-192751).↵
↵
**UDP2:** Problem C is now available!↵
↵
A — Initial Bet↵
===============↵
Since the coin only pass from this player to other player, the coins sum of all player won’t change in the game. That mean, we’ll have `5*b = c1+c2+c3+c4+c5`. We’ll put `sum = c1+c2+c3+c4+c5`. So, if `sum is divisible by b`, the answer will be `sum/b`. Otherwise, the answer doesn’t exist.↵
↵
Be careful with the case `0 0 0 0 0` too, since `b > 0`, answer doesn’t exist in this case.↵
↵
**My solution:** [submission:11607374]↵
↵
↵
↵
B — Random Teams↵
================↵
If a team have `a` participants, there will be `a*(a-1)/2` pairs of friends formed.↵
↵
For the minimum case, the participants should be unionly – distributed in all the team. More precisely, each team should not have more than one contestant compared to other team. Suppose we’ve already had `n div m` contestant in each team, we’ll have `n mod m` contestant left, we now should give each contestant left in first `n mod m` teams.↵
↵
For example, with the test `8 3`, we’ll first give all team 8 div 3 = 2 contestants, the result now is `2 2 2`. We’ll have 8 mod 3 = 2 contestants left, we should each contestant in the first and the second team, so the final result is: `3 3 2`.↵
↵
The maximum case is more simple, we should give only give one contestant in first `m-1` teams, and give the last team all the contestant left. For example with above test, the result is `1 1 6`.↵
↵
Since number of the contestant in one team can be 10^9, the maximum numbers of pairs formed can be 10^18, so we should use `int64` (`long long` in c++) to avoid overflow.↵
↵
**My solution:** [submission:11607784]↵
↵
↵
C — Table Decorations↵
=====================↵
↵
The order of the balloons isn't important, so instead or `r`, `g`, `b`, we'll call them `a[0]`, `a[1]`, `a[2]` and sort them in ascending order. We'll now have `a[0] <= a[1] <= a[2]`.↵
↵
There's two case:↵
↵
- `2*(a[0]+a[1]) <= a[2]`. In this case, we can take `a[0]` sets of `(0, 2, 2)` and `a[1]` sets of `(1, 2, 2)`, so the answer is `a[0]+a[1]`.↵
↵
- `2*(a[0]+a[1]) > a[2]`. In this case, we can continuously take a set of two balloon from `a[2]` and a balloon from `max(a[0], a[1])` until a point that `a[2] <= max(a[0], a[1])`. At this point, `max(a[0], a[1])-a[2] <= 1`, and since `max(a[0], a[1]) - min(a[0], a[1]) <= 1` too, `max(a[0], a[1], a[2]) - min(a[0], a[1], a[2]) <= 1`. All we have to do left is take all possible `(0, 1, 2)` group left. Since we only take the balloons in group of 3, `(a[0]+a[1]+a[2]) mod 3` doesn't change, so there will be at most `(a[0]+a[1]+a[2]) mod 3` balloons wasted. We go back to the beginning now. The answer is `(a[0]+a[1]+a[2]) div 3`.↵
↵
**My solution:** [submission:11614150]↵
↵
_Complexity: O(1)_↵
↵
D — Red-Green Towers↵
====================↵
For more convenient, we’ll call a function `trinum(x) = (x*(x+1))/ 2`, which is also the number of blocks needed to build a tower with height `x`.↵
↵
First, we’ll find h, the maximum height possible of the tower. We know that `h <= trinum(l+r)`. Since `(l+r) <= 2*10^5`, `h <= 631`, so we can just use a brute-force to find this value.↵
↵
Now, the main part of this problem, which can be solved by using dynamic programming. We’ll `f[ih, ir]` the number of towers that have height `ih`, can be built from `ir` red block and `trinum(ih)-ir` green blocks. ↵
↵
For each `f[ih, ir]`, there’s two way to reach it:↵
↵
- Add `ih` red block. This can only be done if `ih <= ir <= min(r, trinum(ih))`. In this case, `f[ih, ir] = f[ih, ir] + f[ih-1, ir-ih]`.↵
↵
- Add `ih` green block. This can only be done if `max(0, trinum(ih)-g) <= ir <= min(r, trinum(ih-1))`. In this case, `f[ih, ir] = f[ih, ir] + f[ih-1, ir-ih]`.↵
↵
The answer to this problem is sum of all `f[h, ir]` with `0 <= ir <= r`.↵
↵
We will probably get MLE now...↵
↵
**MLE solution:** [submission:11600887]↵
↵
How to improve the memory used? We'll see that all `f[ih]` can only be affected by `f[ih-1]`, so we'll used two one-dimension arrays to store the result instead of a two-dimension array. The solution should get accepted now.↵
↵
**Accepted solution:** [submission:11600930]↵
↵
↵
↵
E — Wavy numbers↵
================↵
↵
Unfinished...
