What is a good way to solve the following:

In the grid below, choose one value from each row such that no column is used more than once; the sum of the choices must be maximized. Number of rows <= 1500.

  A B C D
e 5 8
f 3 9 2
g 1 9 6 4 

Working down the rows, notice that each row is left with two options, as the rest are removed by the choices made before.

Addendum

Using Psychologist's answer, we create dp grid with exactly the same structure as the input grid. Each entry means "after this row, what's the maximum so far with this column still available".

(1) First row is reversed

  A B C D        dp A B C D
e 5 8             e 8 5
f 3 9 2           f ? ? ?
g 1 9 6 4         g ? ? ? ?

(2) Each dp cell before the end of the row means the last cell in the input array's row is used.

  A B C D        dp A  B C  D
e 5 8             e 8  5
f 3 9 2           f 10 7 ?    // 8(dp) + 2(a), 5(dp) + 2(a)
g 1 9 6 4         g ?  ? ?  ?

(3) With the dp cell at the end, we need to try taking each other cell to get the best.

  A B C D        dp A  B  C  D
e 5 8             e 8  5
f 3 9 2           f 10 7 14   // 8(dp) + 3(a) vs. 5(dp) + 9(a)
g 1 9 6 4         g ?  ? ?  ?

(4) Finishing up

   A B C D       dp A  B  C  D
 e 5 8            e 8  5
 f 3 9 2          f 10 7  14
 g 1 9 6 4        g 14 11 18 20  // 10 + 4, 7 + 4, 14 + 4, (10+1 vs 7+9 vs 14+6)

The solution is then the best value in the bottom row. And thanks for showing me the right way.

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

Greetings,

I'm wondering, what happens to your rating if you register for a contest but then make zero submissions (and score a 0)?

Appreciated, Derek