butterpaneer's blog

can anyone help me with this submission? like what case or condition am i missing here?
By butterpaneer, history, 5 months ago, In English

this is my submission

i am getting WA in test 3, probably missing some case that i did not include in my code, but i am unable to find what case i am missing (i am missing brain ofc but what else).

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you misunderstood the statement, you don't need the number of ways to make $$$c \equiv k \mod 998244353$$$, you need the number of ways to maximize $$$c$$$. Since the number of ways is big (not the maximum value of $$$c$$$), you want that number $$$\mod 998244353$$$.

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah but like even if i do only (number of way to maximize c) % MOD

    like here:

    const ll MOD = 998244353;
void solve(){
    int n;
    cin>>n;
    ll c =0,temp=0,sum =0,count1=1,count2=1;
    vector<ll>arr(n);
    vector<ll>sum_array(n);
    ll minimum_c = INT32_MAX;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        temp += arr[i]; 
        if(minimum_c > temp){
            minimum_c = temp;
        }
        sum_array[i] = temp;
        if(temp>=0){
            count1 = (count1 * 2) % MOD;
        }
    }
    for(int i=0;i<n;i++){
        if(sum_array[i]==minimum_c && minimum_c != 0){
            count2 = (count2 * 2) % MOD;
        }
    }
    int index;
    for(int i=0;i<n;i++){
        if(sum_array[i]==minimum_c && minimum_c != 0){
            index = i;
        }
    }
    for(int i=index+1;i<n;i++){
        if(sum_array[i]<0){
            count1 = (count1 * 2) % MOD;
        }
    }
    ll res = (count1 * max((ll)1,(count2-1)))%MOD;
    cout<<res<<'\n';
}

    the number of ways to maximize c depends on count1 and count2, so i am doing % MOD to them only. and isn't, the number of ways to make c=k is equal to the number of ways to maximize c? like k is the maximum value right?

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Ok, I found a failing testcase:

      $$$n = 2$$$

      $$$arr_0 = -1, arr_1 = 0$$$

      Your code outputs $$$3$$$, but the answer is $$$2$$$.

      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        how is it 2,

        like here k is 1;

        and we have 3 ways;

        1st : c = c+arr0 = -1 , c = |c+arr1| = 1

        2nd : c = |c+arr0| = 1 , c = c+arr1 = 1

        3rd : c = |c+arr0| = 1 , c = |c+arr1| = 1;

        there are 3 unique ways to maximize c

        → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by butterpaneer (previous revision, new revision, compare).

→ Reply