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
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
long long in c++) to avoid overflow.
My solution: 11607784
C — Table Decorations
The order of the balloons isn't important, so instead or
b, we'll call them
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
(1, 0, 2)and
(0, 1, 2), so the answer is
2*(a+a) > a. In this case, we can continuously take a set of two balloon from
aand 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) <= 1too,
max(a, a, a) - min(a, a, a) <= 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+a+a) mod 3doesn't change, so there will be at most
(a+a+a) mod 3balloons wasted. We go back to the beginning now. The answer is
(a+a+a) div 3.
My solution: 11614150
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
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.
f[ih, ir], there’s two way to reach it:
ihred 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].
ihgreen 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
E — Wavy numbers