Stadium and Games

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:

Leave a Reply

Your email address will not be published. Required fields are marked *