CHFNSWAP - Editorial

editorial
, , , , , ,
24

O(1) huh? Can you please elaborate how finding the square root of a number takes place in O(1) ?

3 Likes
25

Thanks. That helped pass many more cases. Can you please tell why because n<=10^9 was given in the constraints?
Also, still it wasn’t able to pass all test cases. Below is the link to updated submission.
https://www.codechef.com/viewsolution/37923429

26

Change all int to ll see this
https://www.codechef.com/viewsolution/37924034

for calculation of ct you were multiplying to number whose ranges were (10^9) which makes it a range of result (10^18).

27

Can someone explain me the proof in the Lemma.

If some valid M is there then only valid swaps are possible by swapping into the same group element, i.e. any pair (u,v) is good only if either 1≤u<v≤M or M+1≤u<v≤N.

28

Very strict time limit. Sad to see that the code which passes in 0.09 using fast i/o, won’t pass in 2 secs without fast i/o.

1 Like
29

We can also conclude for zero output n by checking
if(n%4==0 || (n+1)%4==0)
if the above condition does not satisfy then the output should straight away be zero. no need to check the sum for all n terms. This is just an alternate way of looking at this case. I believe that this gives a more logical understanding of how the first n numbers sum up to give an even or an odd sum.

https://www.codechef.com/viewsolution/37926679
Check out this solution for more details

30

I understood. Thanks a ton.

31

The sum of first set ie 1 to M will always get increased on swap while that of the second set decrease so we have to find a threshold , ie point where sum of first set is just less than second one so we can make a good swap
ex- N=11 (1 ,2,3,4,5,6,7,8,9,10,11) sum till 8 is 36 and that of remaining is 30 so this point is (X+1) ,
your X should be number before it such that : sum of 1 to X is less than that of X+1 to N
thus your point is 7 .

32

Can anyone please tell me how for N=20 Answer is
not 6

33

The answer cannot be 6. Now it depends how you are counting the nice swaps.
N=20 is a special case in a way that the sum of first 14 terms of the series i.e from 1 to 14 =105 is equal to the sum of last 6 terms i.e from 15 to 20 =105. i.e in its natural order the there exist 2 parts such that the sum of first 14(i.e M) terms is equal to the sum of last 6(i.e N-M) terms.Now any two terms within these two parts is a nice swap. So the total number of swaps is nC2 + (n-x)C2.

Secondly, this case also includes a partition such that the sum of first 13 terms is less than 105 and the sum of last seven terms is greater than 105 (where 105 is sum/2). Since this is the same as the case of any non-special number where the number of nice-swaps is equal to (N-X) given the
X is the pivot element (14 in this case). A pivot X is chosen such that the sum of first X terms is less than or equal to sum/2 and sum of the rest of the terms is greater than sum/2. And moreover X has to be the closest possible number to sum/2.

So the total number of nice swaps is:
(N-X) + nC2 + (n-x)C2

I hope I explained it all you needed.

You can check out this code for more details
https://www.codechef.com/viewsolution/37926679

2 Likes
34

Kindly someone explain for the value N = 16.
I think its 3 instead of 5.
@uhateme @add

35

I used the same logic ,but during the competition my test case 18 showed TLE every time , after the contest ended , I submitted the same code again and now all my test cases are passed

Check my code and the time taken
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
long long int n;
cin>>n;
long long int sum= (n*(n+1))/2;
if(sum%2)
cout<<0<<“\n”;
else
{
long long int s1=0;
long long int pos = sqrt(1+4sum);
pos–; pos/=2;
s1 = pos(pos+1)/2;
long long int answer=0;
if(s1==sum/2)
answer+= ((pos*(pos-1))/2)+(((n-pos)*(n-pos-1))/2);
answer+= n-pos;
cout<<answer<<“\n”;
}
}
}

Link of solution during contest - CodeChef: Practical coding for everyone
Link of solution after contest - CodeChef: Practical coding for everyone

36

https://www.codechef.com/viewsolution/37576955
it is my solution can you tell me whats wrong with my code it is passing sub task 1 and 2 except the first test case and giving tle for 3
my concept is tsum is total sum and i m calculating sum(initially 0) backwards till the moment it is greater than the half of tsum and the count of all such numbers which are contributing to sum is the ans

37

pls someone can tell me for n=7 what is X SUMx and SUMx’ and u and v to satisfy this condition u+SUMx’-SUMx=v?

38

My solution is O(T) as I solved directly without a binary search, but did have a square-root for each test. Even so I could only get within the time limit in C# by using fast input and fast output.

1 Like
39

can anyone help me to figure out where I was wrong,

my solution link:
https://www.codechef.com/viewsolution/37549925

40

why can’t you make a swap if first set is much less than the second ?
why should first set be “just less” than the second set ?

41

I was getting WA with this solution:
https://www.codechef.com/viewsolution/37781040
even though my approach was correct I was using long double for storing ans.
but after the contest when i tried to figure out , and i used long long to store the answer
I got AC
https://www.codechef.com/viewsolution/37934878
can anyone tell me why that happened?

42

#include
#include
using namespace std;

long func(int n);

int main() {

int T;
int n;

cin>>T;

while (T--)
{
    cin>>n;
    cout <<func(n);
    cout<<"\n";
}
return 0;

}

long func(int n)
{
unsigned long long sum, xsum;
unsigned long a,b,c,y;
int x;

//get sum of 1....n
sum = ((n * (n+1))/2);

if (sum%2)
  return 0;


// get pivot element 1,....x, x+1....n
x = (((sqrt(1.0+(4*sum))) - 1.0)/2.0);
//x = (((sqrt((1.0 + 2*(n*n+n)))) - 1.0)/2.0);

//get sum of 1......x
xsum = ((x * (x+1))/2);

y = n-x;

if ((2*xsum) == sum)
{
    a = ((x * (x-1))/2);
    b = ((y * (y-1))/2);
    
    return (a + b + y);
}

return y;

}

Anything wrong I did here. Not all test cases are passing.

43

You used int, so integer overflow

correct solution for your approach–> CodeChef: Practical coding for everyone

1 Like