Krypton31's blog

Help needed in CSES Subarray Sums ||
By Krypton31, history, 3 years ago, In English

Can you please help me see my mistake, in Subarray Sums || It gives WA for 2 cases. 


int main(){
  FastIO;
  int n;
  ll x;
  cin>>n>>x;
  ll a[n];
  ll prefix[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
    prefix[i] = a[i];
    if(i>0) prefix[i]+=prefix[i-1];
  }
  map<ll,ll>cache;
  int cnt =0;
  for(int i =0;i<n;i++){
    cache[prefix[i]]+=1;
    if(prefix[i]==x and cache[0]==0) cnt+=1;
    else cnt+=cache[prefix[i]-x];
  }
  cout<<cnt;
  return 0;
}
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I modified this part of the code and got accepted. 

map<ll,ll>cache;
cache[0] = 1; 
  int cnt = 0;
  for(int i=0;i<n;i++){
    int need = x - prefix[i];
    cnt += cache[-need]; // Notice the minus right there
    cache[prefix[i]]++;
    //cache[prefix[i]]+=1;
    //if(prefix[i]==x and cache[0]==0) cnt+=1;
    //else cnt+=cache[prefix[i]-x];
  }
  cout<<cnt;
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    also why — sign tho, what difference does it make and I get that you added 0 for prefix(i)=x so what is wrong with the if condition of mine, plz help?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Your code will fail for testcases like these 5 100 100 100 100 100 100 because cache[0] = 0 initially so everytime after the first 100 we will add 1 to the ans due to if condition. So initially cache[0] should be made 1 and if condition should be removed. cache[prefix[i]]+=1; should be done at the end of the loop so as to manage testcases like 5 0 0 0 0 0 0 and cnt should be made ll.

      int main(){
  int n;
  ll x;
  cin>>n>>x;
  ll a[n];
  ll prefix[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
    prefix[i] = a[i];
    if(i>0) prefix[i]+=prefix[i-1];
  }
  map<ll,ll>cache;
  cache[0] = 1;
  ll cnt =0;
  for(int i =0;i<n;i++){
    cnt+=cache[prefix[i]-x];
 
    cache[prefix[i]]+=1;
  }
  cout<<cnt;
  return 0;
}
      → Reply