### xuanquang1999's blog

By xuanquang1999, history, 6 years ago,

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...

• +11

 » 6 years ago, # |   0 Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).
 » 6 years ago, # |   0 Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).
 » 6 years ago, # |   0 Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).
 » 6 years ago, # |   +5 In problem C, I think you actually mean a[0] sets of (1, 0, 2) and a[1] sets of (0, 1, 2)
•  » » 6 years ago, # ^ |   0 Thanks for pointing that out. I'll fix it right now.
•  » » » 3 years ago, # ^ |   0 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 ?
 » 6 years ago, # |   0 Thank you for the editorial :)
 » 6 years ago, # |   +1 Hello all, I was trying to understand the solution of this problem.http://codeforces.com/contest/478/problem/DCan 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
 » 5 years ago, # |   0 Testcase 11 for prob CInput 500000000 1000000000 500000000 Jury's answer 666666666Please explain(theoretically) ,how to arrive at this solution for the given input?
 » 4 years ago, # |   +3 Thanks for this couldn't find an official editorial for this round
 » 4 years ago, # | ← Rev. 2 →   0 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.html
 » 3 years ago, # |   0 Many thanks for C.
 » 2 years ago, # | ← Rev. 2 →   0 In the solution for question 478C — Table DecorationsTake 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?
•  » » 7 weeks ago, # ^ |   0 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).