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.
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)
my code is giving partially correct but I am not getting any testcase that is failing please help me
Blockquote
#include<bits/stdc++.h>
using namespace std;
/*
do not voilate rules
/
long long roots(long long sum)
{
return floor((float)(-1+sqrt(1+4sum))/2);
}
void fastio()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
long long c2(long long x)
{
return floor((x-1)*x)/2;
}
int main()
{
fastio();
long long t;//number of testcase
cin>>t;
while(t--)
{
long long int n;
cin>>n;
long long ans=0,x=0;
long long int sum=(n*(n+1))/2;
//cout<<"the sum is "<<sum<<endl;
if(sum%2!=0)
{
cout<<"0"<<endl;
}
else
{
x=roots(sum);
//cout<<"this is x "<<x<<endl;
ans=ans+(n-x);
//cout<<"this is ans "<<ans<<endl;
long long int sum2=(x*(x+1))/2;
//cout<<"this is sum"<<sum2<<endl;
if(sum2==sum/2)
ans=ans+c2(x)+c2(n-x);
cout<<ans<<endl;
}
}
}
this is my code but I am getting only partially correct answer
please help @rishup_nitdgp @cubefreak777 @jayant06 @alei
Hi,
I think i got the error. But before that let me suggest you one thing to not use long long for values not exceeding 1e+09. For this even unsigned long int will work. This unnecessary usage of larger data types makes the code run a bit slower. Check the constraints and the return value of the functions in order to decide for the same.
Coming back to the question, replace the return statement of roots function with:
long long roots(long long sum)
{
return (floor)((-1.0+sqrt(1.0+4.0*sum))/2.0);
}
i.e do the explicit type conversion at each step.
I hope this helps.
Thanks
This editorial is an essay 
the LOGIC shown in the editorial video is WRONG. the number of swaps will not be n-x in all cases. In a few cases yes i will be(for eg. 7) but for n=19, this will give the wrong answer, it will give answer as 6 but when you do it manually, the answer will come out to be 4. This is because my first swap will be (10,14) then (11,15), (12,16), (13,17) but when i try to (14,18) there won’t be any M such that sum of first M number is equal to the last N-M numbers. So the answer will be 4 in case of 19. I might be wrong but I am pretty confident.
2 Likes
Coz if the ‘set’ is much less, the difference between two sets cannot be compensated by swapping values!
Here my program shows TLE error. I cannot resolve this error
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. /
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
long n = sc.nextLong();
long res = 0;
long sum = (n(n+1))/2;
if(sum % 2 != 0){
System.out.println(res);
}
else{
long x = (long) ((-1.0 + Math.sqrt(1 + 4*sum))/2.0);
res = n-x;
if((x*x + x) == sum){
res += nC2(x) + nC2(n-x) ;
}
System.out.println(res);
}
}
} catch(Exception e){}
}
public static long nC2(long num){
return (num*num - num)/2;
}
}
yaah bro thank you so much appreciate it 