SQRDSUB - Editorial

editorial
, , , ,
22

@ssrivastava990 i have absolutely followed your approach…Please tell me where i am wrong.
thanks in advance …

23

No, it is integer overflow issue. You have declared n as int and you are calculating n*(n+1)/2, which will be an int, even if you assign it to long long type variable.

1 Like
24

Now what is wrong in this solution?

https://www.codechef.com/viewsolution/31851753

25

Thank you :innocent:@hackslash_123 .I thought casting n*(n+1)/2 with ll int will solve that problem.But that was not the case.

26

Try for array [-2].

1 Like
27

@hackslash_123 I just cannot express my gratitude enough to you…Thanks you thank you very much…

28

My solution O(n) using simple approach :
int pos_zero = -1,pos_two = -1;
//sum will be sum + 1 for every valid single element like 0,1
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
dp[i] = i; sum += 1; pos_zero = i;
}
else if (a[i] == 1) {
if (i == 0)dp[i] = 0;
else {
if (a[i - 1] % 2 != 0 or a[i - 1] == 0)dp[i] = dp[i - 1] + 1;
else dp[i] = dp[i - 1];
}
sum += 1;
}
else if (a[i] == 2) {
dp[i] = max(pos_zero, pos_two);
(dp[i] != -1) ? dp[i]++ : dp[i] = 0;
pos_two = i;
}
sum += dp[i];
}
printf("%lld\n", sum);

29

Actually it’s not. It’s running (K x (N-K)) times, where K is the sliding window in range [2…N].

It’s not even NxLog(N), my bad.

What do you think?

30

thanks

31

can you please send the test cases as i was unable to find the mistake in my code! it worked for almost all the sets but the last 2 showed wrong answer!

32

Hi so I am quite new to competitive programming, just wanted to know why brute force approach was giving a wrong answer in sub tasks, i wanted to know which cases my approach could not detect. I know it was a n^2 complexity, but i just want to know which test cases was the code failing for
here is the code, it would be really helpful if someone debugged it thanks

33

can you tell what’s wrong in this approach, done the same as explained in editorial except I have not converted the values of array to 0,1 and 2 and done directly instead.

35

please help me finding bug in this code

36

I used a more direct approach.

Loop for each number i. In each pass, add the number of good subsequences ending at this i.

As we go through the loop, maintain the positions of (a) the last even number index_even, and (b) the last multiple of 4 index_four.

If the current i is odd, add the number of subsequences beginning since the last even number.

If the current i is a multiple of four, remember it as both a multiple of 4 and as an even number.

Else the current number is even. Set last multiple of 4 to the previous even number, if any.

If there has been a multiple of 4, add the number of subsequences from the start which include this multiple of 4 = (index_four + 1).

37

I’ve been trying this problem for days and after knowing the logic I still couldn’t able to get the AC.
I made a test Case generator and put my algorithm and tester’s solution in it. Even after thousands of test cases my algo is producing the same output as the tester solution but when I’m submitting the code I get WA. (except 2 test cases 2, 5)
Which means I’m doing some silly mistake. Please help me.
while taking input of numbers I changed them,
if(num[i]%4 == 0) num[i] = 16;
else num[i] = num[i]%8;
My approach :

  1. I’ve counted all the odd numbers and also if any sub array has odd as its product. A sub Array can only have odd as its product if its been multiplied by odd numbers only.(right?)
  2. next, I’ve counted all the number divisible by 4 or number of sub array which is divisible by 4.
    then I add them both.
    PS: sorry for my bad english.
    Solution file
    CodeChef: Practical coding for everyone
38

i am getting wrong answer in sub task 2( 3,4,5) and not in 6 can anybody help me with this (CodeChef: Practical coding for everyone)

39

//easy solution
//** aman**/
#include<bits/stdc++.h>
#define ll long long
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll fun(vector &v,ll n){
ll sum=0;
ll cnt=0;
unordered_map<ll,ll> m;
for(ll i=0;i<n;i++){
sum+=v[i];
if(sum==1)cnt++;
cnt+=m[sum-1];
m[sum]++;
}
return cnt;
}
int main(){
ios;
ll t;cin>>t;
while(t–){
ll n;cin>>n;
ll x;
vector v;
for(ll i=0;i<n;i++){
cin>>x;
if(x%4==0)v.push_back(2);
else if(x%2==0)v.push_back(1);
else v.push_back(0);
}
//cout<<fun(v,n)<<endl;
ll ans=n*(n+1)/2-fun(v,n);
cout<<ans<<endl;
}
}

41

can yo please share the test cases for this problem

42

hereis my code for the challenge but it’s returning TLE, can any body had a better optimized code/idea?

43

can anyone point out the mistake i have done in my submission to squared subsequences problem
[CodeChef: Practical coding for everyone]
@vijju123