Proficient.
Put your skills to the test.

Problem summary

Choose the longest consecutive run of bags whose total candy count for every type has the same parity: either all even or all odd. Break ties by earliest starting bag.

Constraints

2 ≤ N ≤ 2000; 2 ≤ K ≤ 1000; total candies per bag < 10^9; a valid nonempty run exists.

Worked example

An independently prepared example for this explanation.

6 4
9 3 1 15
10 12 9 13
11 12 2 10
3 6 12 2
4 8 11 8
6 13 7 11

3 2

Solution analysis

1. Store the prefix parity vector after each bag. The parity vector of a run is the XOR of its two boundary prefix vectors.
2. A run is valid when its boundary vectors are equal or complementary. Normalize each prefix by XORing all its bits with its first bit. Equal normalized vectors mean exactly those two cases. Store the earliest index of every normalized vector in an ordered map.
3. In the example, bags 3 and 4 sum to 14,18,14,12, all even. Their boundary prefix vectors have the same normalized key, producing length two starting at bag 3. Earliest stored indices maximize length for each ending position.

Why it works

Two binary vectors have the same normalization if and only if their XOR is constant across all coordinates. This constant vector is exactly an all-even or all-odd run. For every end position, the earliest prefix with its key gives the longest valid run ending there; comparing all ends and tie-breaking finds the required global result.

Watch out. Do not require each bag individually to satisfy the parity rule. Include the empty prefix at index zero and retain only earliest indices.

An independently written complete program with standard headers.

#include<iostream>
#include<map>
#include<string>
#include<vector>
// Algorithm: Store the prefix parity vector after each bag.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int>parity(k,0);
    map<string,int>earliest;
    earliest[string(k,'0')]=0;
    int bestStart=1,bestLength=0;
    for(int bag=1;bag<=n;++bag){
        for(int type=0;type<k;++type){
            int count;
            cin>>count;
            parity[type]^=count&1;
        }
        string key(k,'0');
        for(int type=0;type<k;++type){
            key[type]+=parity[type]^parity[0];
        }
        auto inserted=earliest.emplace(key,bag);
        int previous=inserted.first->second;
        int length=bag-previous;
        int start=previous+1;
        if(length>bestLength||(length==bestLength&&start<bestStart)){
            bestLength=length;
            bestStart=start;
        }
    }
    cout<<bestStart<<' '<<bestLength<<'\n';
}