am I the only one who solved this using binary search

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

For the 2nd lemma, Let’s say the sequence is 1,2, … M-1, M, M+1, M+2, …, N

where Sum of elements from 1 to M (say x) = Sum of elements from M+1 to N (say y).

If we swap 1 and M+1, then sequence is M+1, 2, … M-1, M, 1, M+2, … , N

Still the sequence can be divided into two equal sum subarrays M+1, 2, … M-1 being the first half and M, 1, M+2, … , N being second half.

Proof:

left half sum = x - 1 + (M+1) - M = x

right half sum = y - (M+1) + 1 + M = y

Since x = y, then x- M = y - M.

Please correct me if I am wrong but with this being said, when an array can be divided in two equal subarrays, then also we can choose 1 element from left half and 1 from right half of M(equilibrium point)

@rishup_nitdgp can you please clarify my doubt

i have seen the editorial video made by codechef.

i have understood the concept and the implementation.

but i have certain doubts

what is the difference between long,long long, long int,long long int and what is long double?i have tried google it but the answers which i have got confused me.

second in the work function in the implementation it is clear that shree dhar acharya formula is used but in the formula there is + and - both but in the implementation why we have ignored -?

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()

{

int t;

cin>>t;

while(t–)

{

double n;

cin>>n;

long long sum = (n*(n+1))/2;

double count = 0;

if(sum%2!=0)

cout<<0<<endl;

else

{

double root = (-1+sqrt(1+4*sum))/(2);
double r1 = floor(root);
count = n - r1;
if(r1==root)
{
double add = (count*(count-1))/2;

count+=add;

add = (r1*(r1-1))/2;

count+=add;

```
}
cout<<count<<endl;
}
}
```

}

My code is passing all tasks of subtask 2 except one. I cannot think of a testcase where my code fails. Please suggest me some test cases that my code might be failing at.

Thanks in advance

According to the solution there is only one valid X for swaps to take place. But in this testcase:

12

Here two valid X are possible : X=8, X=7

1 2 3 4 5 6 7 8 | 9 10 11 12 -> swaps (8,11),(7,10),(6,9) sum here is 36: 42 (|diff| = 6 =>/2= 3 (+3,-3 achievable )

1 2 3 4 5 6 7 | 8 9 10 11 12 -> swaps (1,12) sum here is 28: 50 (|diff|=22 =>/2=11(+11,-11 achievable)

can anyone explain why the solution has considered only one valid X?

Same thing is happening with me too. Although, I don’t know the exact test case, but the test case sequence(1, 2, …, n) can be divided in two equal sum subarrays initially.

**This ain’t giving AC for 2 test cases**

import math

def xc2(x):

return int((x*(x-1))/2)t = int(input())

for _ in range(t):

n = int(input())

sum1 = int((n*(n+1))/2)

if(sum1%2 == 1):

print(0)

else:

ans = 0

x = ((1+4*sum1)**0.5-1)/2.0

ans += n-math.floor(x)

if(math.floor(x)==math.ceil(x)):

ans += xc2(x) + xc2(n-x)

print(ans)