Proficient.
Put your skills to the test.

Problem summary

Given A of length n with values1..m, and B of length m with values1..n, find a nonempty subsequence of each having the same sum. Any solution is accepted. The algorithm below finds contiguous subsequences, which also qualify.

Source clarification. The linear-time repeated-difference argument follows the official editorial: https://infos.infosbg.com/files/Contests/ETI/2021/B/analyses/B23_Sss_analysis.docx

Constraints

1≤n,m≤1000000;1≤A[i]≤m;1≤B[j]≤n; a solution is guaranteed.

Worked example

Original statement input with a different valid pair of equal-sum subsequences.

5
2 3 3 2 3
3
4 5 5

2
2 3
1
1

Solution analysis

1. Keep nonempty prefixes of the two arrays and their difference d=sumA−sumB. If d<0, append the next A element; if d>0, append the next B element. If d=0, the two prefixes already solve the problem.
2. After every step, −n<d<m because each newly appended element is bounded by the opposite array length. Record the prefix lengths at the first occurrence of each difference. If the same difference occurs again, subtract the two prefix states: the newly added A and B blocks have equal sums.
3. The two extracted blocks are nonempty because their elements are positive. For A=[2,3,3,2,3] and B=[4,5,5], the prefix difference1 occurs after lengths(2,1) and(4,2). Their differences select A indices2,3 and B index1, each summing to5. The bounded differences guarantee a match before an unavailable next element is needed.

Why it works

Equal prefix differences imply equal sums between the corresponding prefix endpoints. Positivity implies both extracted blocks are nonempty. To prove termination, suppose A is exhausted while the difference is negative. There would be n distinct negative-difference states, one before each A extension or the failed final extension, but only n−1 possible negative values in(−n,0); two states must repeat. The symmetric argument applies to exhausting B. Thus zero or a repeated difference is found first.

Watch out. Indices in the original problem are0-based. Store both prefix lengths for a difference, not only its sum. The bound on element values is essential to the termination argument. Do not return the two empty prefixes as a 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 n,m;
    cin>>n;
    vector<int>a(n);
    for(int&value:a){
        cin>>value;
    }
    cin>>m;
    vector<int>b(m);
    for(int&value:b){
        cin>>value;
    }
    vector<int>firstA(n+m,-1);
    vector<int>firstB(n+m,-1);
    int usedA=1;
    int usedB=1;
    int difference=a[0]-b[0];
    int beginA=0;
    int beginB=0;
    while(difference!=0){
        int slot=difference+n;
        if(firstA[slot]!=-1){
            beginA=firstA[slot];
            beginB=firstB[slot];
            break;
        }
        firstA[slot]=usedA;
        firstB[slot]=usedB;
        // Append to the prefix with the smaller sum.
        if(difference<0){
            difference+=a[usedA++];
        }
        else{
            difference-=b[usedB++];
        }
    }
    cout<<usedA-beginA<<'\n';
    for(int i=beginA;i<usedA;i++){
        if(i>beginA){
            cout<<' ';
        }
        cout<<i;
    }
    cout<<'\n'<<usedB-beginB<<'\n';
    for(int i=beginB;i<usedB;i++){
        if(i>beginB){
            cout<<' ';
        }
        cout<<i;
    }
    cout<<'\n';
}