[A-Staircase](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/A)<br>↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]↵
↵
<spoiler summary="Tutorial">↵
The answer contains such elements $a_i$ that $a_i+1=1$ since Chutki starts counting $1,2,3...$ again. Also add to the answer the last element $a_n$.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)↵
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)↵
#define prii pair <int,int>↵
#define PB push_back↵
#define S second↵
#define F first↵
#define B begin()↵
#define E end()↵
using namespace std;↵
↵
/*......................................................................*/↵
↵
void solve(){↵
int n;cin>>n;↵
int arr[n+1];vector <int> vec;int p=0;↵
lop(i,0,n,1){↵
cin>>arr[i];↵
if (arr[i]>p)p=arr[i];↵
else {↵
vec.PB(p);p=1;↵
}↵
}vec.PB(p);↵
cout<<vec.size()<<"\n";↵
lop (i,0,vec.size(),1)cout<<vec[i]<<" ";↵
}↵
int32_t main(){↵
int t;t=1;↵
//cin>>t;↵
while (t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
n=int(input())↵
a=list(map(int,input().split()))↵
ans=[]↵
for i in range(n-1):↵
if a[i+1]==1:↵
ans.append(a[i])↵
ans.append(a[-1])↵
print(len(ans))↵
print(*ans)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[B-XOR It](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/B)<br>↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]<br><br>↵
↵
<spoiler summary="Tutorial">↵
The XOR of two consecutive numbers will always be of the form $2^{x}-1$(trivial) for some $x>=0$<br>↵
So we can convert the given number $n$ in this form for some value $x$<br>↵
Thus, $2^{x}+1=n$<br>↵
$x$ will be equal to $log_2(n+1)$<br>↵
So now as we require the minimum possible value of $M$, it will be $(2^{x-1}-1)$.<br>↵
The answer will be $-1$ for $n$ which is not of this form $2^{x}-1$↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
from math import log2↵
for _ in range(int(input())):↵
n=int(input())↵
k=log2(n+1)↵
if k%1==0:↵
k=int(k)↵
print(2**(k-1)-1)↵
else:↵
print(-1)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[C-Sum with Twist](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/C)<br>↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]<br><br>↵
↵
<spoiler summary="Tutorial">↵
To approach this question you should know about divisor properties<br>↵
Only perfect square have the property to have odd number of divisor {why ? Think about it}<br>↵
so the condition $(p+q)\%2=0$ to be satisfied one number should be a perfect square and other should be a non-perfect square. Now you need to minimize the difference between those two numbers. To minimize the difference between those two number you should look for a number nearby half of the given number. {In practice look for the perfect square less than $n/2$ and perfect square greater then $n/2$ where $n$ is the given number, now check which have minimum difference keeping in mind only one number can be a perfect square i.e., both the numbers should not be a perfect square}.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)↵
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)↵
#define prii pair <int,int>↵
#define PB push_back↵
#define S second↵
#define F first↵
#define B begin()↵
#define E end()↵
using namespace std;↵
↵
/*......................................................................*/↵
↵
void solve(){↵
int n;cin>>n;↵
int ans=1e18;int a=-1,b=-1;↵
↵
int r=sqrt(n/2);↵
lop (i,-1,2,1){↵
int re=r+i;↵
int df=n-re*re;//cout<<re<<" "<<i<<" "<<df<<"\n";↵
int z=sqrt(df);↵
if (z*z==df or df<0 or re<=0)continue;↵
//cout<<re<<" "<<df<<" "<<abs(re*re-df)<<"\n";↵
if (ans>abs(re*re-df)){↵
ans=abs(re*re-df);↵
a=re*re;b=df;↵
}↵
}↵
↵
if (a==-1){↵
cout<<a<<"\n";return;↵
}↵
else {↵
cout<<min(a,b)<<" "<<max(a,b)<<"\n";↵
}↵
}↵
int32_t main(){↵
int t;↵
cin>>t;↵
while (t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
from math import sqrt,floor,ceil↵
from sys import stdin,stdout↵
input=stdin.readline↵
for _ in range(int(input())):↵
a = int(input())↵
b=-1;c=-1;curr=10**15↵
res=floor(sqrt(a//2))↵
for i in range(-1,2):↵
new=res+i↵
diff=a-new**2↵
if diff>0 and sqrt(diff)%1==0:↵
continue↵
if curr>abs(diff-new**2):↵
curr=abs(diff-new**2)↵
c=diff;b=new**2↵
if b>0 and c>0:↵
print(min(b,c),max(b,c))↵
else:↵
print(-1)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[D-XOR It, once again](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/D)<br>↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]<br><br>↵
↵
<spoiler summary="Tutorial">↵
We will find the value of K by finding its separate bits in binary representation.<br>Maximum number of bits present in $K$ can be 40 {think why!}.<br>↵
For $i^{th}$ bit, if $x$ elements have this bit ON, implies $N - x$ elements have this bit OFF.<br>↵
-> If this bit is ON in $K$ , then its contribution in final sum is $(N-x)*2^{i}$<br>↵
-> If this bit is OFF in $K$, then its contribution in final sum is $x*2^{i}$<br>↵
If $(N-x)>x$, then this bit will be OFF in K , otherwise this bit will be ON in K.<br><br>↵
Hence, greedily we can find the value of K.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
from sys import stdin,stdout↵
input=stdin.readline↵
for _ in range(int(input())):↵
n = int(input())↵
a = list(map(int, input().split()))↵
bits = [0 for i in range(40)]↵
for x in a:↵
for j in range(40):↵
bits[j]+=(x>>j & 1)↵
ans=0↵
for i in range(40):↵
if (n-bits[i])<bits[i]:↵
ans+=(1<<i)↵
stdout.write(str(ans)+'\n')↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)↵
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)↵
#define prii pair <int,int>↵
#define PB push_back↵
#define S second↵
#define F first↵
#define B begin()↵
#define E end()↵
using namespace std;↵
↵
/*......................................................................*/↵
↵
void solve(){↵
int n;cin>>n;↵
int arr[64];memset(arr,0,sizeof(arr));↵
lop (i,0,n,1){↵
int a;scanf("%lld",&a);↵
string st=bitset<64>(a).to_string();int sz=st.size();↵
rlop (j,sz,0,1){↵
if (st[j]=='1'){↵
arr[sz-1-j]++;↵
}↵
}↵
}↵
int ans=0;int r=1;↵
lop (i,0,64,1){↵
int p=arr[i];↵
if (2*p>n){↵
ans+=r;↵
}↵
r=2*r;↵
}↵
cout<<ans<<"\n";↵
}↵
int32_t main(){↵
int t;↵
cin>>t;↵
while (t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[E-Is Sum Really Easy?](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/E)<br>↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]<br><br>↵
↵
<spoiler summary="Tutorial">↵
Well this problem is a modified and bit complicated version of problem C<br>↵
To approach this question you should know about Sieve of Eratosthenes↵
You can do this question without Sieve of Eratosthenes if you can some how find all the primes number till $10^{5}$ and store them. To fulfill the condition $p+(q\%2)=3$ you should know that there can be only two way to do this first you can take $p=2$ and chose $q$ to be odd, for $p$ to be equal to $2$ the number should be a prime number (only prime number have two divisors) and choose a perfect square so q will be odd<br>, second you can take $p=3$ and choose $q$ to be even. For $p$ to be equal to $3$ the number must be a square of a prime number i.e, $(4,9,25)$ {$16$ is not a square of a prime number so it can’t be considered}.<br>↵
Now chose any non perfect square number to make $q$ even. To implement the above idea you can simply brute force the solution i.e., check all the number which satisfy the above condition and for that you can make store all the prime number upto $10^{5}$ and their square and then check for all of them.<br> ↵
{If you read the question and this editorial too, then I would like to know your opinionabout this question ;) }↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)↵
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)↵
#define prii pair <int,int>↵
#define PB push_back↵
#define S second↵
#define F first↵
#define B begin()↵
#define E end()↵
using namespace std;↵
↵
/*......................................................................*/↵
int dk[100007];vector <int> prime,sqr;↵
void sieve(){↵
lop (i,2,100007,1){↵
if (dk[i]==0){↵
lop (j,i*i,100007,i){↵
dk[j]=1;↵
}↵
prime.PB(i);↵
sqr.PB(i*i);↵
}↵
}↵
}↵
void solve(){↵
int n;cin>>n;↵
int ans=1e9;int a=-1;int b=-1;↵
lop (i,0,prime.size(),1){↵
if (prime[i]>=n)break;↵
int df=n-prime[i];↵
int z=sqrt(df);↵
if (z*z!=df)continue;↵
if (ans>abs(prime[i]-df)){↵
ans=abs(prime[i]-df);↵
a=prime[i];↵
b=df;↵
}↵
}↵
lop (i,0,sqr.size(),1){↵
if (sqr[i]>=n)break;↵
int df=n-sqr[i];↵
int z=sqrt(df);↵
if (z*z==df)continue;↵
if (ans>abs(df-sqr[i])){↵
ans=abs(df-sqr[i]);↵
a=sqr[i];b=df;↵
}↵
}↵
if (a==-1){↵
cout<<-1<<"\n";return ;↵
}↵
cout<<min(a,b)<<" "<<max(a,b)<<"\n";↵
}↵
int32_t main(){↵
int t;sieve();↵
cin>>t;↵
while (t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]↵
↵
<spoiler summary="Tutorial">↵
The answer contains such elements $a_i$ that $a_i+1=1$ since Chutki starts counting $1,2,3...$ again. Also add to the answer the last element $a_n$.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)↵
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)↵
#define prii pair <int,int>↵
#define PB push_back↵
#define S second↵
#define F first↵
#define B begin()↵
#define E end()↵
using namespace std;↵
↵
/*......................................................................*/↵
↵
void solve(){↵
int n;cin>>n;↵
int arr[n+1];vector <int> vec;int p=0;↵
lop(i,0,n,1){↵
cin>>arr[i];↵
if (arr[i]>p)p=arr[i];↵
else {↵
vec.PB(p);p=1;↵
}↵
}vec.PB(p);↵
cout<<vec.size()<<"\n";↵
lop (i,0,vec.size(),1)cout<<vec[i]<<" ";↵
}↵
int32_t main(){↵
int t;t=1;↵
//cin>>t;↵
while (t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
n=int(input())↵
a=list(map(int,input().split()))↵
ans=[]↵
for i in range(n-1):↵
if a[i+1]==1:↵
ans.append(a[i])↵
ans.append(a[-1])↵
print(len(ans))↵
print(*ans)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[B-XOR It](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/B)<br>↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]<br><br>↵
↵
<spoiler summary="Tutorial">↵
The XOR of two consecutive numbers will always be of the form $2^{x}-1$(trivial) for some $x>=0$<br>↵
So we can convert the given number $n$ in this form for some value $x$<br>↵
Thus, $2^{x}+1=n$<br>↵
$x$ will be equal to $log_2(n+1)$<br>↵
So now as we require the minimum possible value of $M$, it will be $(2^{x-1}-1)$.<br>↵
The answer will be $-1$ for $n$ which is not of this form $2^{x}-1$↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
from math import log2↵
for _ in range(int(input())):↵
n=int(input())↵
k=log2(n+1)↵
if k%1==0:↵
k=int(k)↵
print(2**(k-1)-1)↵
else:↵
print(-1)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[C-Sum with Twist](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/C)<br>↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]<br><br>↵
↵
<spoiler summary="Tutorial">↵
To approach this question you should know about divisor properties<br>↵
Only perfect square have the property to have odd number of divisor {why ? Think about it}<br>↵
so the condition $(p+q)\%2=0$ to be satisfied one number should be a perfect square and other should be a non-perfect square. Now you need to minimize the difference between those two numbers. To minimize the difference between those two number you should look for a number nearby half of the given number. {In practice look for the perfect square less than $n/2$ and perfect square greater then $n/2$ where $n$ is the given number, now check which have minimum difference keeping in mind only one number can be a perfect square i.e., both the numbers should not be a perfect square}.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)↵
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)↵
#define prii pair <int,int>↵
#define PB push_back↵
#define S second↵
#define F first↵
#define B begin()↵
#define E end()↵
using namespace std;↵
↵
/*......................................................................*/↵
↵
void solve(){↵
int n;cin>>n;↵
int ans=1e18;int a=-1,b=-1;↵
↵
int r=sqrt(n/2);↵
lop (i,-1,2,1){↵
int re=r+i;↵
int df=n-re*re;//cout<<re<<" "<<i<<" "<<df<<"\n";↵
int z=sqrt(df);↵
if (z*z==df or df<0 or re<=0)continue;↵
//cout<<re<<" "<<df<<" "<<abs(re*re-df)<<"\n";↵
if (ans>abs(re*re-df)){↵
ans=abs(re*re-df);↵
a=re*re;b=df;↵
}↵
}↵
↵
if (a==-1){↵
cout<<a<<"\n";return;↵
}↵
else {↵
cout<<min(a,b)<<" "<<max(a,b)<<"\n";↵
}↵
}↵
int32_t main(){↵
int t;↵
cin>>t;↵
while (t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
from math import sqrt,floor,ceil↵
from sys import stdin,stdout↵
input=stdin.readline↵
for _ in range(int(input())):↵
a = int(input())↵
b=-1;c=-1;curr=10**15↵
res=floor(sqrt(a//2))↵
for i in range(-1,2):↵
new=res+i↵
diff=a-new**2↵
if diff>0 and sqrt(diff)%1==0:↵
continue↵
if curr>abs(diff-new**2):↵
curr=abs(diff-new**2)↵
c=diff;b=new**2↵
if b>0 and c>0:↵
print(min(b,c),max(b,c))↵
else:↵
print(-1)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[D-XOR It, once again](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/D)<br>↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]<br><br>↵
↵
<spoiler summary="Tutorial">↵
We will find the value of K by finding its separate bits in binary representation.<br>Maximum number of bits present in $K$ can be 40 {think why!}.<br>↵
For $i^{th}$ bit, if $x$ elements have this bit ON, implies $N - x$ elements have this bit OFF.<br>↵
-> If this bit is ON in $K$ , then its contribution in final sum is $(N-x)*2^{i}$<br>↵
-> If this bit is OFF in $K$, then its contribution in final sum is $x*2^{i}$<br>↵
If $(N-x)>x$, then this bit will be OFF in K , otherwise this bit will be ON in K.<br><br>↵
Hence, greedily we can find the value of K.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
from sys import stdin,stdout↵
input=stdin.readline↵
for _ in range(int(input())):↵
n = int(input())↵
a = list(map(int, input().split()))↵
bits = [0 for i in range(40)]↵
for x in a:↵
for j in range(40):↵
bits[j]+=(x>>j & 1)↵
ans=0↵
for i in range(40):↵
if (n-bits[i])<bits[i]:↵
ans+=(1<<i)↵
stdout.write(str(ans)+'\n')↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)↵
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)↵
#define prii pair <int,int>↵
#define PB push_back↵
#define S second↵
#define F first↵
#define B begin()↵
#define E end()↵
using namespace std;↵
↵
/*......................................................................*/↵
↵
void solve(){↵
int n;cin>>n;↵
int arr[64];memset(arr,0,sizeof(arr));↵
lop (i,0,n,1){↵
int a;scanf("%lld",&a);↵
string st=bitset<64>(a).to_string();int sz=st.size();↵
rlop (j,sz,0,1){↵
if (st[j]=='1'){↵
arr[sz-1-j]++;↵
}↵
}↵
}↵
int ans=0;int r=1;↵
lop (i,0,64,1){↵
int p=arr[i];↵
if (2*p>n){↵
ans+=r;↵
}↵
r=2*r;↵
}↵
cout<<ans<<"\n";↵
}↵
int32_t main(){↵
int t;↵
cin>>t;↵
while (t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[E-Is Sum Really Easy?](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/E)<br>↵
Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07]<br><br>↵
↵
<spoiler summary="Tutorial">↵
Well this problem is a modified and bit complicated version of problem C<br>↵
To approach this question you should know about Sieve of Eratosthenes↵
You can do this question without Sieve of Eratosthenes if you can some how find all the primes number till $10^{5}$ and store them. To fulfill the condition $p+(q\%2)=3$ you should know that there can be only two way to do this first you can take $p=2$ and chose $q$ to be odd, for $p$ to be equal to $2$ the number should be a prime number (only prime number have two divisors) and choose a perfect square so q will be odd<br>, second you can take $p=3$ and choose $q$ to be even. For $p$ to be equal to $3$ the number must be a square of a prime number i.e, $(4,9,25)$ {$16$ is not a square of a prime number so it can’t be considered}.<br>↵
Now chose any non perfect square number to make $q$ even. To implement the above idea you can simply brute force the solution i.e., check all the number which satisfy the above condition and for that you can make store all the prime number upto $10^{5}$ and their square and then check for all of them.<br> ↵
{If you read the question and this editorial too, then I would like to know your opinionabout this question ;) }↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)↵
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)↵
#define prii pair <int,int>↵
#define PB push_back↵
#define S second↵
#define F first↵
#define B begin()↵
#define E end()↵
using namespace std;↵
↵
/*......................................................................*/↵
int dk[100007];vector <int> prime,sqr;↵
void sieve(){↵
lop (i,2,100007,1){↵
if (dk[i]==0){↵
lop (j,i*i,100007,i){↵
dk[j]=1;↵
}↵
prime.PB(i);↵
sqr.PB(i*i);↵
}↵
}↵
}↵
void solve(){↵
int n;cin>>n;↵
int ans=1e9;int a=-1;int b=-1;↵
lop (i,0,prime.size(),1){↵
if (prime[i]>=n)break;↵
int df=n-prime[i];↵
int z=sqrt(df);↵
if (z*z!=df)continue;↵
if (ans>abs(prime[i]-df)){↵
ans=abs(prime[i]-df);↵
a=prime[i];↵
b=df;↵
}↵
}↵
lop (i,0,sqr.size(),1){↵
if (sqr[i]>=n)break;↵
int df=n-sqr[i];↵
int z=sqrt(df);↵
if (z*z==df)continue;↵
if (ans>abs(df-sqr[i])){↵
ans=abs(df-sqr[i]);↵
a=sqr[i];b=df;↵
}↵
}↵
if (a==-1){↵
cout<<-1<<"\n";return ;↵
}↵
cout<<min(a,b)<<" "<<max(a,b)<<"\n";↵
}↵
int32_t main(){↵
int t;sieve();↵
cin>>t;↵
while (t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
