cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2022 · MediumPriority queue simulation

Alternating Chip Selection

National Olympiad — Regional round (2022 season)

Submission name: game.cpp

Solve in Editor →

Problem summary

Players alternate choosing a nonempty row; the other player takes its maximum chip. Choose the row whose maximum is smallest.

Source clarification. The statement omits tie-breaking. For rows[3,3] and[2,3], different tied row choices change totals. This implementation follows the released reference’s lowest-row-index convention; the literal prose does not uniquely specify all cases.

Input

Even N, then the N×N chip values.

Output

Ognyan’s total and Rosen’s total; Ognyan chooses the first row.

Constraints

2≤N≤200, N even; chip values1…100.

Worked example

Input and output for the worked example discussed below.

Input

2
1 3
2 4

Output

3 7

Solution analysis

  1. Sort every row descending, then put its current maximum and original row index in a min-heap. The smallest heap entry is the next selected row.
  2. The chip goes to the opponent of the row selector. Remove it, advance that row’s pointer, and replace its heap entry unless the row is empty.
  3. In the sample removals are3,1,4,2. Rosen receives3+4=7 and Ognyan1+2=3. Tied maxima follow the released reference’s lowest-row-index convention, disclosed below.

Why it works

The heap contains exactly one maximum per nonempty row, so its minimum implements each required greedy choice. Updating only that row preserves the invariant and alternating receivers gives the totals.

Complexity: O(N²logN) time and O(N²) space, including sorting and N² heap updates.

Watch out. The first chip belongs to Rosen. Empty rows leave the heap; equal row maxima require the disclosed tie rule.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<utility>
#include<algorithm>
using namespace std;
// The heap contains exactly one maximum per nonempty row, so its minimum implements each required greedy
// choice.
int main(){
    int n;
    cin>>n;
    vector<vector<int>>a(n,vector<int>(n));
    using Entry=pair<int,int>;
    priority_queue<Entry,vector<Entry>,greater<Entry>>pending;
    for(int r=0;r<n;r++){
        for(int&x:a[r]){
            cin>>x;
        }
        sort(a[r].begin(),a[r].end(),greater<int>());
        pending.push({a[r][0],r});
    }
    vector<int>next(n,0);
    long long score[2]={0,0};
    for(int turn=0;turn<n*n;turn++){
        auto[value,row]=pending.top();
        pending.pop();
        score[turn%2==0?1:0]+=value;
        next[row]++;
        if(next[row]<n){
            pending.push({a[row][next[row]],row});
        }
    }
    cout<<score[0]<<' '<<score[1]<<'\n';
}

Source: Arena Olimpiici ↗