PROBLEM LINK:
Division 1
Division 2
Video Editorial
Author: Ritesh Gupta
Tester: Suchan Park
Editorialist: Ritesh Gupta
DIFFICULTY:
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()
}
