SQRDSUB - Editorial

editorial
, , , ,
65

CodeChef: Practical coding for everyone is the link to my code.

66

Yes, it is yielding a wrong answer despite passing the given test case . Can anyone tell me why is it so? The logic applied seems to be correct .

67

my approach is same as yours . but only got WA please have a look.

#include <bits/stdc++.h>
using namespace std;
long long int um(int a[], int n, int sum)
{
unordered_map<long long int,long long int> pum;
long long int res = 0;
long long int cum = 0;
for (int i = 0; i < n; i++) {
cum += a[i];
if (cum == sum)
res++;
if (pum.find(cum - sum) != pum.end())
res += (pum[cum - sum]);
pum[cum]++;
}
return res;
}

int main()
{
int t ;
scanf("%d",&t);
while(tā€“){
int n,i;
scanf("%d",&n);
int a[n],b[n];
for (i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++){
if (a[i]%4==0)
b[i]=2;
else if(a[i]%2==0)
b[i]=1;
else if(a[i]%2==1)
b[i]=0;
else
b[i]=3; }
long long int k,m=(n*(n+1)/2);
k=m-um(b,n,1);
printf("%lld\n",k);
}
return 0;
}

68

please look at my solution , Donā€™t know why it giving WA .
https://www.codechef.com/viewsolution/31565416

69

thanks

70

please address @abhishek855 and/or @jackiefer doubts. my issue is the same

72

I think automatic typecast is the problem.
Initialise the count as count = n*(n+1)/(long long)2;

Also the right count and left count product to be subtracted as
count -= (lcount+(long long)1)*(rcount+(long long)1);

Hope it helps :slight_smile:

73

I am attaching my code here
Can anyone tell what is the problem as I am getting AC in 1 subtest and WA in all others

#include<bits/stdc++.h>

using namespace std;

int n,i,pos2=-1,pos4=-1,pos0=-1;
long long int aa,ans=0;
int ab[100010];

int check0(int p1, int p2 ,int p3)
{
if(p3>=p1 && p3>=p2)
return 0;
return 1;
}
int main()
{
int t;
cin>>t;

while(t!=0)
{   
    ans=0;
    cin>>n;

    for(i=0;i<n;i++)
    {
        cin>>aa;
        aa=abs(aa);
        if(aa & 1)
        ab[i]=1;
        else if(!(aa%4) && aa!=0)
        ab[i]=4;        
        else if( aa!=0 )
        ab[i]=2;
        else
        ab[i]=0;        
    }
    pos0=-1;
    pos2=-1;
    pos4=-1;
    for(i=0;i<n;i++)
    {
        if(ab[i]==1)
        {
            ans+=(i-max(pos2,pos0));
        }
        else if(ab[i]==4)
        {
            ans+=(i-pos0);
            pos2=-1;
            pos4=i;
        }
        else if( ab[i]==2 )
        {

            if(check0(pos2,pos4,pos0)==0)
            pos2=i;
            else
            ans+=(max(pos2,pos4)-pos0);
            pos2=i;
        }
        else if(ab[i]==0)
        {
            pos0=i;
        }
    }
    
    cout<<ans<<" \n";
     
    t--;
}
return 0;

}

Solution_ 31533543 _ CodeChef - Google Chrome 21-04-2020 11_56_38 (2)
Solution_ 31533543 _ CodeChef - Google Chrome 21-04-2020 11_56_38 (2)1920Ɨ820 49.2 KB

1 Like
74

@arftdipto because we assign odd number by 0 and even by 1. and the only subsequence that canā€™t be represented as difference of two integer is odd * even = even . So when 1 + 0 = 1 . there is a sub sequence of odd and even which will result in odd .
we canā€™t have sum 1 + 2 . Because 1(even with mod 4 == 2) + 2(even with mod 4 == 0 ) will result in a number that can be represented as difference of two integer. We are trying to get answer conversely so we canā€™t take that .

75

@coastaldemigod you program works only for the test case having array of odd numbers . I had the same AC in test case 5 . I figured it out It was failing for other cases . Try Editorialistā€™s approach to get AC in all.

1 Like
76

typecast unsigned long long int to all the variables.

77

Can anyone help me understand why my code with unsigned long long int works and not long long int

AC

WA

1 Like
78

Thanks bro :slight_smile:

But I couldnā€™t understand the reason behind it .

79

Can you please elaborate on this answer += seen[sum-k]

80

There is Video made by errichto on this.

1 Like
81

Got it. Thanks bro!

82

I also want to know .