CHFNSWAP - Editorial

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+4sum))/(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?

1 Like

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)