Can you please share the code in Java?
No i can in c++
here is my c++ code
#include <bits/stdc++.h>
#define whatis(x) cout << #x << " is " << x << endl;
#define whatis2(x, y) cout << #x << " is " << x << " and " << #y << " is " << y << endl;
#define whatis3(x, y, z) cout << #x << " is " << x << " and " << #y << " is " << y < < " and " << #z << " is " << z << endl;
#define MOD 1000000007
#define IOS \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//function to return sum of n elements
unsigned long long sum(ull n) {
ull a = n;
ull b = n+1;
if(a%2==0){
a = a/2;
}
else{
b = b/2;
}
ull res = a*b;
return res;
}
//Takes log n time to find the first number whose sum is smaller than equal to total sum/2;
ull findindex(ull n) {
ull target = (ull)sum(n) / 2;
ull l = 1;
ull r = n;
while (l < r) {
if ((l+1)== r) {
break;
}
ull m = (l + r) / 2;
ull curr = (ull)sum(m);
//if the sum of m which is the middle number is equal to the sum of the target return m
if (curr == target) {
return m;
}
if (curr < target) {
l = m;
} else {
r = m;
}
}
if(sum(r)<target) return r;
else return l;
}
ull findstart(ull target, ull end, ull n) {
ull l = 1;
ull r = end;
while (l < r) {
if ((l + 1) == r) {
break;
}
ull m = (l + r) / 2;
if (target - (ull)sum(m) > n) {
l = m;
}else if (target - (ull)sum(m) <= n) {
r = m;
}
}
if((ull)sum(r) < target) return r;
else return l;
return l;
}
int main() {
IOS;
long long t;
cin >> t;
while (t--) {
ull n;
cin >> n;
ull s = sum(n);
if(s%2!=0){
cout<<0<<"\n";
continue;
}
ull target = sum(n) / 2;
ull rend = findindex(n);
ull rbegin = findstart(target, rend, n);
ull ans = 0;
ull f = rend - rbegin;
for (ull i = rbegin; i <= rend; i++) {
ull diff = target - sum(i);
ull lower = 1 + diff;
if(lower<=i){
lower = i+1;
}
ull upper = i + diff;
if(upper > n){
upper = n;
}
ans+=(upper-lower) + 1;
if(diff==0){
ans+=sum(i-1);
ans+=sum(n-i-1);
}
}
cout<<ans<<"\n";
}
return 0;
}
1 Like
Felt more like september math challenge this time xD, nice problemset btw
1 Like
I code basically in Java , still thanks for the help.It will help me to develop logic.Thanks a lot !
my solution
#include<iostream>
#include<math.h>
//Done by vaibhavgadag
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
typedef long long int ll;
using namespace std;
int main()
{
fastio;
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll sum=((n)*(n+1))/2;
if(sum%2==0)
{
ll x=(sqrt(1+4*sum)-1)/2;
ll y=n-x;
if(sum/2==(y*(2*n-y+1))/2)
{
cout<<ll((y*(y-1))/2+((n-y)*(n-y-1))/2+y)<<endl;
}
else
{
cout<<y<<endl;
}
}
else
{
cout<<0<<endl;
}
}
return 0;
}
can anyone help me, how can I short the code or maybe reduce time complexity
Note that my solution has been executed in 1.92 sec AC 
Here is my observation based code…
//Author:- Rahul Arya
#include<bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define w(x) ll x; cin>>x; while(x--)
#define ll long long int
int main(){
fio
ll n,k,s,c,e; double r;
w(t)
{
cin>>n; c=0; r=0;
k=n*(n+1)/2;
if(k%2!=0)
cout<<"0\n";
else
{
r=sqrt(1+2*(n*n+n)); e=sqrt(1+2*(n*n+n));
c=n-(e-1)/2; s=r;
if(r-s==0)
{
c=c*(c-1)/2+(n-c-1)*(n-c)/2+c;
}
cout<<c<<"\n";
}
}
}time complexity of your code is O(1)(you cannot achieve less than that) as for the time is concerned it may be because of heavy math operations like sqrt, division , multiplication on large dataset
CodeChef: Practical coding for everyone here’s my submission in java i would recommend using bufferedOutputStream. check this article - java - What's the fastest way to output a string to system out? - Stack Overflow
What is the problem with my solution? It passed only test case 1.
I have done it in O(1) (probably) using roots of quadratic equation. To deal with the precision errors in sqrt, I have used sqrtl (1.0L*)) also. Kindly help.
You have to use ll instead of int for n.
Thanks.
Why is there only a single value of X for which nice swaps are possible ?
Please provide some intuition or proof
2 Likes
O(1) huh? Can you please elaborate how finding the square root of a number takes place in O(1) ?
3 Likes
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
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).
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.
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
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