butterpaneer's blog

By butterpaneer, history, 3 weeks 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

»
3 weeks 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$$$.

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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$$$.

      • »
        »
        »
        »
        3 weeks 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

»
3 weeks 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).