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.

**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:** 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:** 11607784

*Complexity: O(1)*

# C — Table Decorations

spiderbatman has a great idea for this problem. You can read his comment here.

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`(1, 0, 2)`

and`a[1]`

sets of`(0, 1, 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`(1, 1, 1)`

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:** 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 call `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:** 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:** 11600930

*Complexity: O(r*sqrt(l+r))*

# E — Wavy numbers

Unfinished...

Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).In problem C, I think you actually mean a[0] sets of (1, 0, 2) and a[1] sets of (0, 1, 2)

Thanks for pointing that out. I'll fix it right now.

Isn't it a[0] sets of (0, 0, 2) and a[1] sets of (1, 1, 2) or am I misinterpreting the convention used ?

Thank you for the editorial :)

Hello all, I was trying to understand the solution of this problem.

http://codeforces.com/contest/478/problem/D

Can someone please explain their recursion? I read a couple of solutions but I am not able to figure out the reasoning. It would be very helpful of someone to point out what I am missing. I am sharing the link below.

http://codeforces.com/contest/478/submission/14321778

Testcase 11 for prob C

Input 500000000 1000000000 500000000 Jury's answer 666666666

Please explain(theoretically) ,how to arrive at this solution for the given input?

Thanks for this couldn't find an official editorial for this round

For Problem D, I was trying to prove that it is always possible to build to a tower of height of height

h, given enough blocks (i.e;r+g≥h(h+ 1) / 2). Here is the proof for this that I came across : https://abitofcs.blogspot.com/2014/10/a-bit-of-cf-codeforces-round-273-div-2.htmlMany thanks for C.

In the solution for question 478C — Table Decorations

Take

`r = 3, g = 7, b = 8`

=>`a[0] = 3, a[1] = 7, a[2] = 8`

. Since`2*(a[0]+a[1]) > a[2]`

, we follow case 2.Start removing 2 balloons from a[2] and 1 balloon from

`max(a[0], a[1])`

till`a[2] <= max(a[0], a[1])`

. Therefore, after a single iteration, we get`a[0] = 3, a[1] = 6, a[2] = 6`

. This does not satisfy the condition`max(a[0], a[1]) - min(a[0], a[1]) <= 1`

.Can anyone tell me where am I going wrong, or is there a problem with the solution?

I was wondering about that part too.In the solution by spiderbatman quoted above, after a[2] <= max(a[0], a[1]), we subtract 2 from max(a[0], a[1], a[2]) and 1 from second_max(a[0], a[1], a[2]). (a[0], a[1], a[2]) = (3,6,6), (3,5,4), (3,3,3), (1,2,3), (1,1,1). In the case of (1,1,1), we use all the colors and get (0,0,0).