I understood. Thanks a ton.
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 .
Can anyone please tell me how for N=20 Answer is
not 6
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
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
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
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?
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
can anyone help me to figure out where I was wrong,
my solution link:
https://www.codechef.com/viewsolution/37549925
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 ?
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?
#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.
You used int, so integer overflow
correct solution for your approach–> CodeChef: Practical coding for everyone
1 Like
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?
3 Likes
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.