 # PROBLEM LINK:

Author: Ritesh Gupta
Tester: Suchan Park
Editorialist: Ritesh Gupta

EASY

# PREREQUISITES:

Number Theory, Math

# PROBLEM:

You are numbers from 1 to N lying in ascending order. You can do one swap operation in which you can select two distinct numbers from 1 to N and swap them. The swap is called good if numbers can be divided in two non-empty continuous parts such that both have the same sum.

# QUICK EXPLANATION:

• For the first subtask, you can try the brute force approach where you can try all possible pairs of swaps and check whether it is satisfying the given condition.
• Let suppose, it is initially possible to divide the numbers into two equal sum continuous parts. If M is such a number that sum from 1 to M is equal to sum from M+1 to N then the answer is only possible by swapping the numbers from the same group, i.e. swap any pair of numbers from 1 to M or M+1 to N.
• Else if no such valid M is there then we can say there should be X such that sum from 1 to X is less then sum from X+1 to N but sum from 1 to X+1 is greater then sum from X+2 to N. In this case, only possible good swaps are pairs of numbers in which the first number belongs to the first group and second from the second group.
• For the second subtask, we first look whether there exists any valid M or not. If YES then the answer would be simple math but NO then find some valid X and then for any one group try whether there exist some conjugate in another group using binary search.
• We can also see that number are 1 to N so, for some N, if there is no valid M then there should be vaid X such that 2*X > N. And we can also say that if for some Z (> X and \le N) there should be Y( \le X). So, answer for subtask three can be calculated easily.

# EXPLANATION:

Terms:

• N - Numbers given in ascending order.
• M - If it exists then it should be 1 < M < N and the sum of first M numbers is equal to sum from M+1 to N numbers.
• X - If it exists then it should be 1 < X < N and sum from 1 to X is less then sum from X+1 to N but sum from 1 to X+1 is greater then sum from X+2 to N.

Lemma:

• Both M and X can not be found for any given N.
• As M divides the numbers in two equal sum groups and X divides them in equal sum groups.
• 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 \le u < v \le M or M+1 \le u < v \le N.
• If we are swapping numbers from the same group i.e. either from 1 to M of from M+1 to N then value of M is kept preserve and these swaps are good but if we are doing inter swapping then it shift the value of M toward left (decrease) and we can easily show that 2*M -1 > N which implies that if we take the maximum value from the second group which is N in the first group, we are not able to give more than one greater value from the first group which is M. So, we are unable to shift M or after swapping, we don’t have any valid M.
• If some valid X is there then swapping numbers from the same group never be a good swap but if we can swap numbers from different groups then we can have some valid swap.
• By swapping numbers from the same group does not affect the value X which implies that there should not be any M exist after swap. If we swapping (u, v) such that u lies in first group and v in second group then it might be good swap as suppose sum of first X numbers is sum_X and rest is {sum_X}^’ then for each v we should find u such that u + {sum_X}^’ - sum_X = v.
• We can show that for any valid X, N < 2*X which implies that for each valid v from X+1 to N, there exists a u in first X numbers.
• We can say that {sum_X}^’ - sum_X < X+1 and 2*X > N. If v is X+1 then u should be X + 1 - {sum_X}^’ + sum_X (>= 1) and if v is N then u should be N - {sum_X}^’ + sum_X (<= X). As if there is a valid answer for X+1 and N then it all the numbers also have valid u.

Now, the problem can be solved easily.

# TIME COMPLEXITY:

TIME: O(T * log(N))
SPACE: O(1)

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>

#define int long long
#define endl "\n"
#define mod 1000000007

using namespace std;

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t;
cin >> t;

while(t--)
{
int m;
cin >> m;

if(m%4 == 1 || m%4 == 2)
cout << 0 << endl;
else
{
int cnt = m*(m+1);
cnt /= 4;

int n = sqrt(2*cnt) + 1;

while((n*(n+1))/2 > cnt)
n--;

cnt -= (n*(n+1))/2;

int ans = m-n;

if(cnt == 0)
ans += n*(n-1)/2 + (m-n)*(m-n-1)/2;

cout << ans << endl;
}
}
}
``````
Tester's Solution
``````// subtask 3
class CHFNSWAP_SUBTASK3 {
fun triangular (n: Long) = n*(n+1)/2
fun choose2 (n: Long) = triangular(n-1)

fun lbTriangular(target: Long): Long {
var low = 0L
var high = 1000000000L
var ret = -1L

while (low <= high) {
val mid = (low + high) / 2
val diff = triangular(mid) - target
if (diff <= 0L) {
ret = mid
low = mid+1
} else {
high = mid-1
}
}

require(triangular(ret) <= target)
require(triangular(ret+1) > target)

return ret
}

/*
93924
27510
*/

fun get(N: Long): Long {
if (triangular(N) % 2 == 1L) return 0L

var ans = 0L

val target = triangular(N) / 2
lbTriangular(target).let {
if (triangular(it) == target) {
ans += choose2(it) + choose2(N-it)
}
}

// maxOf(1, m+1-diff) <= minOf(m, N-diff) ?
// diff >= 1

// 아래 4개가 동시에 성립해야 함
// 1 <= m
// 1 <= N-(target - triangular(m))   iff triangular(m) >= target-(N-1)
// m+1-(target - triangular(m)) <= m iff triangular(m) <= target-1
// m+1-diff <= N-diff                iff m <= N-1
// 1 <= target - triangular(m)       iff triangular(m) <= target-1

val smallestM = maxOf(1, lbTriangular(target - (N-1) - 1) + 1)
val largestM = minOf(N-1, lbTriangular(target))
for (m in smallestM..largestM) {
val diff = target - m * (m+1)/2
ans += maxOf(minOf(m, N-diff) - maxOf(1, m+1-diff) + 1, 0L)
}
return ans
}
}

fun main(args: Array<String>) {
val br = java.io.BufferedReader(java.io.InputStreamReader(System.`in`), 32768 * 10)
val bw = java.io.BufferedWriter(java.io.OutputStreamWriter(System.`out`), 32768 * 10)

val solver = CHFNSWAP_SUBTASK3()

val T = br.readLine()!!.toInt()
require(T in 1..1000000)

for (_t in 0 until T) {
val N = br.readLine()!!.toLong()
require(N in 1..1000000000)
bw.write("\${solver.get(N)}\n")
}
bw.flush()
}
``````

## Video Editorial

17 Likes

Check out Screencast Tutorial for this problem: https://www.youtube.com/watch?v=xlMriamMbPo&list=PLz-fHCc6WaNJa2QJq7qULBBV0YOJunq75&index=4

Very much of an observation based problem. Thanks for this!

3 Likes
1 Like

Hey please help me out with my code I tried to find alternative to reduce time.But Time Limit is exceeding here in my code

import java.util.Scanner;
class Codechef {
public static void main (String[] args) throws java.lang.Exception
{
Scanner scan=new Scanner(System.in);
int t=scan.nextInt();
for(int i=0;i<t;i++) {
int n=scan.nextInt();
count(n);
}
scan.close();
}
public static void count(int n) {
int c=0;
int sum=n*(n+1)/2;
if(sum%2==0) {
int[] a=new int[n];
for(int p=0;p<n;p++) {
a[p]=p+1;
}
for(int j=0;j<n;j++) {
for(int k=j+1;k<n;k++){
int[] b=a.clone();
int temp=b[j];
b[j]=b[k];
b[k]=temp;
int u=0;
for(int w:b) {
u+=w;
if(u==sum/2) {
c+=1;
break ;
}else if(u>sum/2) {
break;
}
}
}
}
}
System.out.println©;
}
}
Hoping someone will surely help.

It is simple binary search problem… you can do it in O(logn) …there is one O(1) approach too

3 Likes

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 !

Thanks @sk_kh5037coder for the solution.It will be of great help for me. 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

Got TLE
https://www.codechef.com/viewsolution/37915951
Any help will be appereciated.

https://www.codechef.com/viewsolution/37844777 here’s my submission in java i would recommend using bufferedOutputStream. check this article - https://stackoverflow.com/questions/11823095/whats-the-fastest-way-to-output-a-string-to-system-out

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.

https://www.codechef.com/viewsolution/37905032

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