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 takea[0]
sets of(0, 2, 2)
anda[1]
sets of(1, 2, 2)
, so the answer isa[0]+a[1]
.2*(a[0]+a[1]) > a[2]
. In this case, we can continuously take a set of two balloon froma[2]
and a balloon frommax(a[0], a[1])
until a point thata[2] <= max(a[0], a[1])
. At this point,max(a[0], a[1])-a[2] <= 1
, and sincemax(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: 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 ifih <= 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 ifmax(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...