Thank you for participating in #25!
104743A - Make All Elements 0 by Yugandhar_Master:
There is no need to take segments, we can go with whole array.
If all elements are equal to $$$0$$$, we don't need to do anything, so the answer is $$$0$$$.
If there is any bit $$$\leq k$$$ which is set to $$$0$$$ for all $$$a_i$$$, then answer will be $$$1$$$.
If $$$k$$$ is $$$1$$$, then answer is $$$−1$$$, in all other cases answer is $$$2$$$.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
int t;
cin>>t;
while(t--){
int n,x;
cin>>n>>x;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
int cnt=count(a.begin(),a.end(),0);
if(cnt==n) cout<<0<<endl;
else if(x==1){
for(int i=0;i<n;i++) a[i]=a[i]&1;
int cnt=count(a.begin(),a.end(),0);
if(cnt==n) cout<<1<<endl;
else cout<<-1<<endl;
}
else{
bool ok=false;
for(int i=0;i<31;i++){
int cnt=0;
for(int j=0;j<n;j++){
if((a[j]&(1<<i))==0) cnt++;
}
if(cnt==n && x>=(1<<i)){
ok=true;
break;
}
}
if(ok) cout<<1<<endl;
else cout<<2<<endl;
}
}
}
104743B - Array Construction by wuhudsm:
If $$$n=1$$$, then the answer is YES if and only if $$$x=y$$$.
Otherwise, we consider each binary bit of $$$x$$$ and $$$y$$$.
If there is any bit which is set to $$$0$$$ in $$$x$$$ and to $$$1$$$ in $$$y$$$, then the answer is NO.
Let $$$c$$$ be the number of bits set to $$$1$$$ in $$$x$$$ and to $$$0$$$ in $$$y$$$. There can be at most $$$2^c$$$ different elements in $$$a$$$. So just check if $$$n \leq 2^c$$$.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n,x,y;
int main()
{
//freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&x,&y);
if(n==1) printf("%s\n",(x==y)?"YES":"NO");
else
{
int flg=1,sz=1;
for(int i=0;i<30;i++)
{
int bx=((x&(1<<i))!=0),by=((y&(1<<i))!=0);
if((!bx)&&by) flg=0;
else if(bx&&(!by)) sz<<=1;
}
if(n>sz) flg=0;
printf("%s\n",flg?"YES":"NO");
}
}
//fclose(stdin);
return 0;
}
104743C - Prefix MEX Problem by pavlekn:
Let $$$p_0$$$ be the first occurrence of $$$0$$$. It's not hard to find that $$$a_{p_0}$$$ cannot be increased, since in order to make $$$a_{p_0} > 0$$$, $$$a_i = 0$$$ should exist for $$$i < p_0$$$. So, we cannot make any $$$a_i = 0$$$, for $$$i > p_0$$$, because MEX($$$a_0, a1, \ldots, a{i-1}$$$) $$$\ge 1$$$. However, we can apply operations for $$$i = p_0, p_0 - 1, \ldots, 2, 1$$$, obtaining $$$a_i = 0$$$, for each $$$i \in [1, p_0]$$$.
After that, let's find the first occurrence of $$$1$$$ — $$$p_1$$$. (If there are no $$$1$$$s in the sequence, let $$$p_1 = n$$$). Similarly, we can apply operations for each $$$i = p_1, p_1 - 1, \ldots p_0 + 1$$$, where $$$a_i \le 1$$$, obtaining $$$a_i = min(a_i, 1)$$$, for each $$$i \in [p_0, p_1]$$$.
Increasing the value, we repeat the process, while $$$[1, p_0] \cup [p_0, p_1] \cup \ldots \cup [p_{k-1}, p_k] \ne [1, n]$$$.
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int cur = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == cur) {
++cur;
}
a[i] = min(a[i], cur);
}
for (auto el : a) {
cout << el << " ";
}
cout << endl;
}
return 0;
}
104743D1 - Prefix XOR Problem(Easy Version) and 104743D2 - Prefix XOR Problem(Hard Version) by pavlekn:
Let's find an $$$i$$$ such that $$$a_i \ne b_i$$$. If $$$a_1 \oplus \ldots a_{i - 1} = 1$$$, then we can flip $$$a_i$$$ straightaway. Otherwise, let $$$cnt$$$ be the number of indices $$$j$$$ such that $$$a_j = 1, j < i$$$. If $$$cnt = 0$$$, then we cannot flip $$$a_j$$$ for all $$$1 \le j \le i$$$, so the answer is $$$-1$$$. So now $$$cnt \ge 2$$$. Let $$$j_2$$$ be the second position for which $$$a_{j_2} = 1$$$. Let's flip $$$a_{j_2}$$$, then flip $$$a_i$$$ and once again flip $$$a_{j_2}$$$. Since for every $$$i$$$ such that $$$a_i \ne b_i$$$, we apply at most $$$3$$$ operations, there are at most $$$3 \cdot n$$$ operations in total.
Let $$$i_1, i_2, \ldots, i_k$$$ be the indices that we need to flip in $$$a$$$. Let's iterate over them in increasing order and flip indices that we can ($$$cnt$$$ should be odd). After that, we know that for all remaining indices, corresponding $$$cnt$$$ is even. We can make corresponding $$$cnt$$$s odd by flipping the second occurrence of $$$1$$$ in $$$a$$$ — $$$j_2$$$, then we can flip all remaining $$$i_1, i_2, \ldots, i_k$$$ in reverse order, and finally flip $$$a_{j_2}$$$ back.
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
int n;
cin >> n;
string a, b;
cin >> a;
cin >> b;
vector<int> ans;
vector<int> ones;
int fl = true;
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) {
if (ones.empty()) {
fl = false;
break;
}
int k = (int)ones.size();
if (k % 2 == 1) {
ans.push_back(i);
} else {
ans.push_back(ones[1]);
ans.push_back(i);
ans.push_back(ones[1]);
}
}
if (b[i] == '1') {
ones.push_back(i);
}
}
if (!fl) {
cout << -1 << endl;
continue;
}
cout << ans.size() << endl;
for (auto el : ans) {
cout << el + 1 << " ";
}
cout << endl;
}
return 0;
}
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
int a[N],b[N];
char s[N],t[N];
int check()
{
int ca=0,cb=0;
for(int i=1;i<=n;i++) ca+=a[i],cb+=b[i];
if(!ca) return cb!=0;
for(int i=1;i<=n;i++)
{
if(a[i]) return (!b[i]);
else if(b[i]) return 1;
}
}
int main()
{
//freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%s%s",&n,s,t);
for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
for(int i=1;i<=n;i++) b[i]=t[i-1]-'0';
if(check())
{
printf("-1\n");
continue;
}
int p=INF,x=0;
vector<int> ans;
for(int i=1;i<=n;i++)
{
if(a[i])
{
p=i+1;
break;
}
}
if(p<=n)
{
for(int i=1;i<=n;i++)
{
x^=a[i];
if((a[i]!=b[i])&&x==b[i]&&i>p)
{
ans.push_back(i);
x^=1;a[i]^=1;
}
}
a[p]^=1;ans.push_back(p);
for(int i=n;i>=p;i--) if(a[i]^b[i]) ans.push_back(i);
}
printf("%d\n",ans.size());
if(!ans.size()) printf("\n");
for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
}
//fclose(stdin);
return 0;
}
104743E - Range Modulo Queries by Ashutosh.Singh:
For $$$i$$$ in range $$$1\le l \le r \le n$$$,
$$$a_i \bmod m = b_i$$$
$$$\Rightarrow (a_i-b_i) \bmod m =0$$$
$$$\Rightarrow m \text{ divides } (a_i-b_i)$$$
Therefore, the biggest possible value of $$$m$$$ is gcd of all $$$(a_i-b_i)$$$ $$$(l \le i \le r)$$$ (except when $$$gcd=0$$$, then $$$m$$$ can be arbitrarily large).
But we need the smallest value of $$$m$$$, so we will find the smallest factor of $$$m$$$ strictly greater than all $$$b_i$$$ $$$(l \le i \le r)$$$.
To efficiently answer the queries, we can use some data structures like segment tree or sparse table to find the range gcd of $$$(a_i-b_i)$$$ in range and also to find the maximum value of $$$b_i$$$ in the range.
We will also need to do some precomputation for finding the factors of the gcd we obtained. Then, we can do binary search over the factors, to find the smallest factor strictly greater than the maximum value of $$$b_i$$$ in the range.
We will print -1 when we are unable to find any such $$$m$$$, like when $$$(a_i-b_i)$$$ is negative for some $$$i$$$ in or no factor of $$$gcd$$$ is strictly greater than the maximum value of $$$b_i$$$ in the range.
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
const int N=1000001;
vector<vector<int>>divisors(N);
void init_sparse_max(vector<int>&a,vector<vector<int>>&dp){
int n=a.size();
for(int i=0;i<n;i++){
dp[i][0]=a[i];
}
for(int j=1;j<30;j++){
for(int i=0;i+(1LL<<j)-1<n;i++){
dp[i][j]=max(dp[i][j-1],dp[i+(1LL<<(j-1))][j-1]);
}
}
}
void init_sparse_gcd(vector<int>&a,vector<vector<int>>&dp){
int n=a.size();
for(int i=0;i<n;i++){
dp[i][0]=a[i];
}
for(int j=1;j<30;j++){
for(int i=0;i+(1LL<<j)-1<n;i++){
dp[i][j]=__gcd(dp[i][j-1],dp[i+(1LL<<(j-1))][j-1]);
}
}
}
int query_max(int l,int r,vector<vector<int>>&dp){
int j=log2(r-l+1);
int ans=max(dp[l][j],dp[r-(1LL<<j)+1][j]);
return ans;
}
int query_gcd(int l,int r,vector<vector<int>>&dp){
int j=log2(r-l+1);
int ans=__gcd(dp[l][j],dp[r-(1LL<<j)+1][j]);
return ans;
}
void solve(){
int n,q;
cin>>n>>q;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
vector<int>b(n);
for(int i=0;i<n;i++){
cin>>b[i];
}
vector<vector<int>>sparse_max(n,vector<int>(30));
init_sparse_max(b,sparse_max);
vector<int>c(n);
set<int>st;
for(int i=0;i<n;i++){
c[i]=a[i]-b[i];
if(c[i]<0){
st.insert(i);
}
}
vector<vector<int>>sparse_gcd(n,vector<int>(30));
init_sparse_gcd(c,sparse_gcd);
while(q--){
int l,r;
cin>>l>>r;
l--;r--;
auto it=st.lower_bound(l);
if(it!=st.end() && *it<=r){
cout<<-1<<endl;
continue;
}
int m=query_gcd(l,r,sparse_gcd);
int maxi=query_max(l,r,sparse_max);
int index=upper_bound(divisors[m].begin(),divisors[m].end(),maxi)-divisors[m].begin();
if(index!=(int)divisors[m].size()){
cout<<divisors[m][index]<<endl;
}else{
cout<<-1<<endl;
}
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
for(int i=1;i<=1000000;i++){
for(int j=i;j<=1000000;j+=i){
divisors[j].push_back(i);
}
}
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
104743F - Yet Another Tree Problem by aryanc403:
Soon...
Soon...
Very interesting contest <3
In editorial for A: How in all other cases answer is 2?
By choosing 2 different bit positions which are <=K in all elements.
Nice problems. Time Limit is too tight for python on E. Range Modulo Queries.
Easy Solution for the Easy Version of D.
Let x be the place in a where the first on bit appears in a, similarly let y be the place in b where the first on bit appears in b. If x is not equal to y, then the answer is NO.
This is just because, we can't change the first on bit in a ever.
Otherwise ( x = y ), remove all the 1's after x in a, we can do this starting from just to the right of x. And then add all the 1's from right to left, if b[i] = 1.
In the first case, the number of on bits to the left (prefix) are 2 so the prefix-xor will be 0. In the second case, the number of on bits to the left (prefix) is only 1 so the prefix-xor will be 1.
This solution uses at most 2n operations. We are done.
this is passing hard version also
I had made this test case during the contest :
If algorithm is run on this one, it will give 4 operations.
Maybe the test cases (all of them) are generated using random, so all 1's is a rare case.
my code is giving MLE
Use
intinstead ofllIn problem B, could sb give me an example plz?:)
sry I got some simple mistake in my code... when using bitwise operation, I forgot to adding "()" and got unexpected results.
For Problem E I tried to submit I'm getting TLE at test-case-7 or test-case-11.
Also i'm using segment tree implementation from atcoder-library. Need help how to get AC?
231010905
Ashutosh.Singh
Update: Got it replaced endl with \n worked.
hehe
In problem D Is the given string always consisting by 0 or 1 ?
You are given two binary strings so the answer is yes
What's the solution for problem F?
aryanc403