Stadium and Games problem description

Greetings,

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:

#include <iostream>
#include <vector>
#include <time.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;
typedef unsigned long uint32;
typedef long int32;
typedef unsigned long long uint64;
typedef long long int64;

#define INF64 0x8000000000000000LL
#define INF64_SQRT 3037000000LL

#define MAX_N 1000000000000000000LL // from problem description

int main( void )
{
	uint64 target = 0;
	cin >> target;

	vector<uint64> results;

	for ( uint64 series_ix = 0;; series_ix++ ) {
		uint64 series_first = (1LL << series_ix);
		if ( series_first > MAX_N ) break;

		/**
		 * Watch for overflow:
		 * - p2_input will be squared
		 * - p2_input will be multiplied by p1_to_p2_ratio
		 */
		uint64 p1_to_p2_ratio = series_first - 1;
		uint64 max_p2_input = INF64_SQRT;
		if ( p1_to_p2_ratio > 0 ) {
			max_p2_input = min(max_p2_input, INF64 / p1_to_p2_ratio);
		}

		/**
		 * Each series gives results strictly increasing, so on each do a binary search.
		 *
		 * Index is mapped from ix=>1, 2, 3... to p2_input=>1, 3, 5...
		 */
		uint64 lo = 1;
		uint64 hi = (max_p2_input + 1) / 2;
		while ( lo <= hi ) {
			uint64 mid = lo + (( hi - lo ) / 2);
			uint64 p2_input = (mid * 2) - 1;

			uint64 p2 = p2_input * ((p2_input - 1) / 2); // or `* (p2_input >> 1LL);`

			uint64 p1 = p1_to_p2_ratio * p2_input;
			uint64 result = p1 + p2;
			if ( result == target ) {
				results.push_back(p2_input << series_ix);
				break;
			}
			else if ( result < target ) {
				lo = mid + 1;
			}
			else {
				hi = mid - 1;
			}
		}
	}

	sort(results.begin(), results.end());
	if ( results.empty() ) {
		cout << -1;
	}
	else {
		for ( uint32 i = 0; i < results.size(); i++ ) {
			cout << results[i] << endl;
		}
	}

	return 0;
}

I hope this helps, Derek Illchuk