Scoring Consecutive Value Sets in a Matrix
National Olympiad — National round (2011 season)
Submission name: points.cpp
Problem summary
Score every row, column, and the two main diagonals by the lengths of their maximal sets of consecutive distinct values. Positions need not be consecutive; duplicate equal values do not extend a set.
Input
N followed by an N×N matrix.
Output
The total score.
Constraints
3 ≤ N ≤ 16; natural matrix values ≤ N². Row scores for run lengths 2,3,4,5,>5 are 10,40,70,100,150; add 10 for columns and 20 for diagonals.
Worked example
Input and output for the worked example discussed below.
Input
5 1 1 7 1 2 2 10 2 13 2 5 12 13 5 7 3 3 3 11 3 4 12 4 13 12
Output
360
Solution analysis
- Collect one line, sort it, and erase duplicate values. This turns a value set into increasing order without confusing equal repeated entries with a longer consecutive run.
- Scan maximal runs where each value is its predecessor plus one. Ignore runs of length 1. Look up the row score by run length, then add the line-type bonus 0,10,20. Never score shorter subruns inside one maximal run.
- For the row [11,6,14,8,12,5,13], the sets are {5,6}, {8}, {11,12,13,14}, so its score is 10+0+70=80. Apply the same calculation to every row and column and exactly the two corner-to-corner diagonals; the displayed full matrix totals 360.
Why it works
Sorting and deduplication preserve exactly the line’s set of values. Consecutive runs partition this set into precisely the maximal qualifying groups, so one lookup per run adds exactly the specified points. Processing all required lines once gives the total.
Watch out. Only the two principal diagonals count. Do not count duplicate values as additional consecutive numbers or score every subinterval of a longer run.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int score(vector<int>values,int bonus){
sort(values.begin(),values.end());
values.erase(unique(values.begin(),values.end()),values.end());
int answer=0;
for(int start=0;start<int(values.size());){
int end=start+1;
while(end<int(values.size())&&values[end]==values[end-1]+1){
end++;
}
int length=end-start;
if(length>=2){
// Score a maximal value run once, not each of its subruns.
int base=length>5?150:10+30*(length-2);
answer+=base+bonus;
}
start=end;
}
return answer;
}
int main(){
int size;
cin>>size;
vector<vector<int>>grid(size,vector<int>(size));
for(auto&row:grid){
for(int&value:row){
cin>>value;
}
}
int answer=0;
vector<int>diagonal;
vector<int>opposite;
for(int index=0;index<size;index++){
answer+=score(grid[index],0);
vector<int>column;
for(int row=0;row<size;row++){
column.push_back(grid[row][index]);
}
answer+=score(column,10);
diagonal.push_back(grid[index][index]);
opposite.push_back(grid[index][size-index-1]);
}
answer+=score(diagonal,20)+score(opposite,20);
cout<<answer<<'\n';
}