Hunting the Submarine
National Olympiad — National round (2021 season)
Submission name: submarine.cpp
Problem summary
Generate a firing plan covering every initial zone, direction and integer speed from 1 through K on a circle of d zones, within times 0 through 10d−1. Fewer shots earn a higher score. This is an output-only task.
Input
Offline generator input: d K from one released input file.
Output
N, followed by N distinct-time pairs time zone; save as submarine.xx.out and submit output files in a ZIP.
Constraints
1 ≤ d,K ≤ 60; 0 ≤ time < 10d; 0 ≤ zone < d.
Worked example
The official example is a nonunique witness; the generator prints a valid three-shot alternative.
Input
3 1
Output
4 0 0 1 2 3 2 4 0
Solution analysis
- Reduce signed speeds modulo d and remove duplicate speeds. There are at most d² distinct trajectories (initial zone, residue speed). Maintain only trajectories not already hit by a previous shot. At each time count how many survivors occupy each zone, fire at the zone with the highest count, and remove the trajectories hit.
- This greedy generator always finishes inside the permitted horizon. If R trajectories remain, some zone contains at least R/d of them. One shot leaves at most R(1−1/d); after 10d shots fewer than d²e^(−10)<1 survive for d≤60. For d=1 the first shot immediately finishes.
- The official example is a valid four-shot plan for d=3,K=1; this generator deterministically finds the three-shot plan (0,0),(1,0),(2,0). Output need not match the official witness. This algorithm guarantees coverage, but does not minimize the number of shots and does not guarantee the maximum score. The score for a valid test is 10*min(authorShots/yourShots,1)^3.
Why it works
The enumerated trajectories represent every possible submarine because motion depends only on its initial zone and signed speed modulo d. Removing a trajectory only after a coincident shot preserves exactly the set of uncovered possibilities. The averaging argument decreases that set to zero before the time limit. Consequently every possible submarine is hit, and each chosen time is distinct and in range.
Watch out. Do not submit the generator as an ordinary accepted program: the contest takes ZIP files named submarine.xx.out. Validate all signed velocities, avoid repeated times, and distinguish coverage from score optimization.
Commented C++17 solution
Offline output-file generator. Run with each released submarine.xx.in, redirect to submarine.xx.out, validate the plan, then ZIP the outputs. It guarantees valid coverage but not optimal shots or full score.
#include<iostream>
#include<vector>
#include<utility>
// Algorithm: Reduce signed speeds modulo d and remove duplicate speeds.
using namespace std;
int main(){
int zones,maximum;
cin>>zones>>maximum;
vector<bool>used(zones);
vector<pair<int,int>>alive;
for(int speed=1;speed<=maximum;++speed){
used[speed%zones]=true;
used[(zones-speed%zones)%zones]=true;
}
for(int speed=0;speed<zones;++speed){
if(used[speed]){
for(int start=0;start<zones;++start){
alive.push_back({start,speed});
}
}
}
vector<pair<int,int>>shots;
for(int time=0;!alive.empty()&&time<10*zones;++time){
vector<int>count(zones);
for(auto submarine:alive){
++count[(submarine.first+submarine.second*time)%zones];
}
int target=0;
for(int zone=1;zone<zones;++zone){
if(count[zone]>count[target]){
target=zone;
}
}
shots.push_back({time,target});
vector<pair<int,int>>remaining;
for(auto submarine:alive){
if((submarine.first+submarine.second*time)%zones!=target){
remaining.push_back(submarine);
}
}
alive.swap(remaining);
}
cout<<shots.size()<<'\n';
for(auto shot:shots){
cout<<shot.first<<' '<<shot.second<<'\n';
}
}