Codeforces Round #273 English Editorial (UnfinishedC is available now!)
Difference between en10 and en11, changed 1,355 character(s)
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://codeforces.com/blog/entry/14307#comment-192751).↵

**UDP2:** Problem C is now available!↵

A &mdash; 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 &mdash; 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 &mdash; Table Decorations↵
=====================↵
Unfinished...[user:spiderbatman,2015-06-17] has a great idea for this problem. You can read his comment [here](http://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, a, a and sort them in ascending order. We'll now have a <= a <= a.↵

There's two case:↵

- 2*(a+a) <= a. In this case, we can take a sets of (0, 2, 2) and a sets of (1, 2, 2), so the answer is a+a.↵

- 2*(a+a) > a. In this case, we can continuously take a set of two balloon from a and a balloon from max(a, a) until a point that a <= max(a, a). At this point, max(a, a)-a <= 1, and since max(a, a) - min(a, a)  <= 1 too, max(a, a, a) - min(a, a, a) <= 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+a+a) mod 3 doesn't change, so there will be at most (a+a+a) mod 3 balloons wasted. We go back to the beginning now. The answer is (a+a+a) div 3.↵

**My solution:** [submission:11614150]↵

_Complexity: O(1)_

D &mdash; 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 &mdash; Wavy numbers↵
================↵

Unfinished...

History

Revisions Rev. Lang. By When Δ Comment
en14 xuanquang1999 2015-06-27 16:28:57 5 Tiny change: 'ng. We’ll f[ih, ' -> 'ng. We’ll call f[ih, '
en13 xuanquang1999 2015-06-27 16:27:56 4 Tiny change: 'ossible (0, 1, 2) group l' -> 'ossible (1, 1, 1) group l'
en12 xuanquang1999 2015-06-27 16:26:34 8
en11 xuanquang1999 2015-06-17 06:50:25 1355 Tiny change: '], a). At this po' -
en10 xuanquang1999 2015-06-17 04:52:15 4 Tiny change: 'orce to fill this valu' -> 'orce to find this valu'
en9 xuanquang1999 2015-06-17 04:51:44 2 Tiny change: '1))/ 2.\nFirst, w' -> '1))/ 2`.\n\nFirst, w'
en8 xuanquang1999 2015-06-17 04:40:16 8
en7 xuanquang1999 2015-06-17 04:36:51 67
en6 xuanquang1999 2015-06-17 04:34:48 4 Tiny change: ' read.\n\nUDP: Actually,' -> ' read.\n\n**UDP:** Actually,'
en5 xuanquang1999 2015-06-17 04:34:29 190
en4 xuanquang1999 2015-06-17 03:58:14 2 Tiny change: ' formed.\nFor the ' -> ' formed.\n\nFor the '
en3 xuanquang1999 2015-06-16 18:02:39 4
en2 xuanquang1999 2015-06-16 18:01:56 2 Tiny change: 'nfinished.\n' -> 'nfinished...\n'
en1 xuanquang1999 2015-06-16 18:01:26 3562 Initial revision (published)