Share the Carolers’ Rolls Equally
Autumn Tournament (2013)
Submission name: kravaiche.cpp
Problem summary
Choose a nonempty subset of houses so that their total number of rolls is divisible by the number k of carolers. Print any valid house indices. A contiguous selection is allowed and is sufficient under k≤n.
Input
k n followed by n positive roll counts.
Output
Indices of a nonempty valid selection, or no kravaiche if no solution exists.
Constraints
1 ≤ k ≤ n ≤ 100000; 1 ≤ ai ≤ 100000.
Worked example
A valid selection for the original sample input; constructive outputs need not be unique.
Input
3 6 7 11 2 5 13 17
Output
1 2
Solution analysis
- Let prefix[i] be the sum of the first i counts modulo k, including prefix[0]=0. If two prefix remainders are equal, the sum between them is divisible by k because subtracting the prefixes cancels their common remainder.
- Remember the first index where each remainder appeared. Scan prefixes; as soon as a remainder repeats at indices left and right, the consecutive houses left+1 through right form a valid answer. The pigeonhole principle guarantees a repeat among the first k+1 prefixes, since there are only k remainder values and n≥k.
- For the displayed input, prefix remainders begin 0,1,0. Houses 1 and 2 contain 7+11=18 rolls, divisible by 3. This is a different valid selection from the original sample’s houses 2,3,4. No subset DP or exponential search is needed.
Why it works
Equal prefix remainders imply that their difference is a positive-length segment sum divisible by k. The k+1 prefixes through index k occupy only k possible remainder classes, so two must agree and produce a nonempty segment. Thus a valid answer always exists for the stated constraints, and the algorithm finds one.
Watch out. Initialize remainder zero at prefix index 0; otherwise a divisible prefix may be missed. A repeated remainder must use different indices, giving a nonempty selection. Print house indices, not their roll counts. The no-solution message is unreachable for valid k≤n inputs.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
int n;
cin>>k>>n;
vector<int>first(k,-1);
first[0]=0;
int remainder=0;
int left=-1;
int right=-1;
for(int index=1;index<=n;index++){
int rolls;
cin>>rolls;
remainder=(remainder+rolls)%k;
if(right==-1){
if(first[remainder]!=-1){
// Subtract the two prefixes with the same remainder.
left=first[remainder]+1;
right=index;
}
else{
first[remainder]=index;
}
}
}
if(right==-1){
cout<<"no kravaiche\n";
return 0;
}
for(int index=left;index<=right;index++){
if(index>left){
cout<<' ';
}
cout<<index;
}
cout<<'\n';
}