This post is in reference to CodeForces

Stadium and Games.

Let’s look at a subset of inputs, and see what shakes out.

N.B. From problem description

– Phase 1: total of halves removed

– Phase 2 input: number of teams minus phase one

– Phase 2 output: phase-2-input * ( phase-2-input — 1 )/2

x (binary) phase-1 phase-2-input
1 (1b) = 0 1
3 (11b) = 0 3
5 (101b) = 0 5
7 (111b) = 0 7
9 (1001b) = 0 9
11 (1111b) = 0 11
x (binary) phase-1 phase-2-input
2 (10b) = 1 1
6 (110b) = 3 3
10 (1010b) = 5 5
14 (1110b) = 7 7
18 (10010b) = 9 9
22 (11110b) = 11 11
...
x (binary) phase-1 phase-2-input
8 (1000b) = 7 1
24 (11000b) = 21 3
40 (101000b) = 35 5
56 (111000b) = 49 7
72 (1001000b) = 63 9
88 (1111000b) = 77 11

First, notice the phase-2-input in each case: it’s strictly increasing. And phase-2-output (on this strictly increasing input) is strictly increasing. And phase 1 is strictly increasing too. Therefore, it’s safe to say that the total result on any series of inputs having the same number of ending-zeroes is strictly increasing.

This means we can perform a binary search on each group of partitioned inputs, for the given result. So, explicitly:

– Series 0: 1, 3, 5, 7… with no zeroes attached to the back

– Series 1: 1, 3, 5, 7… with 1 zero attached (yielding 2, 6, 10…)

– Series 2: 1, 3, 5, 7… with 2 zeroes attached

– etc.

Also notice that *any* number is part of *exactly one* series: if it ends in 1 zero it’s in series 1, ends in 14 zeroes it’s in series 14, etc. Therefore, all possible answers are searched.

(Also, notice the phase-1 to phase-2-input ratio in each series is the same. This is useful during implementation.)

With that, here it is in git and below:

*Related*