We thank everyone who participated in the round.
Author: SashaT9
Try to find the upper bound of $$$\gcd(x,y)+y$$$.
$$$\gcd(x,y)+y=\gcd(x-y,y)+y$$$.
$$$\gcd(x,y)+y\le x$$$. Try to find such $$$y$$$, that $$$\gcd(x,y)+y=x$$$?
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int x;
cin>>x;
cout<<x-1<<"\n";
}
}
Author: FBI
Try to check for every $$$k$$$ if the prefix of $$$a$$$ of length $$$k$$$ is a subsequence of $$$b$$$.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
vector<char>a(n+1),b(m+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
vector<int>dp(m+1);
dp[1]=(a[1]==b[1]?1:0);
for(int i=2;i<=m;i++){
if(dp[i-1]!=n && b[i]==a[dp[i-1]+1]){
dp[i]=dp[i-1]+1;
}else{
dp[i]=dp[i-1];
}
}
cout<<dp[m]<<"\n";
}
}
1968C - Assembly via Remainders
Author: SashaT9
Why constraints are small?
Try to think about increacing $$$a_1,\dots,a_n$$$.
$$$((a + b)\bmod a) = b$$$ for $$$0\le b < a$$$.
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int S=1000;
cout<<S<<" ";
for(int i=2;i<=n;i++){
int x;
cin>>x;
S+=x;
cout<<S<<" ";
}
cout<<"\n";
}
}
Author: FBI
Consider a cycle of the permutation.
When it is optimal to stay on the same place till the end of the game?
#include<bits/stdc++.h>
using namespace std;
long long score(vector<int>&p,vector<int>&a,int s,int k){
int n=p.size();
long long mx=0,cur=0;
vector<bool>vis(n);
while(!vis[s]&&k>0){
vis[s]=1;
mx=max(mx,cur+1ll*k*a[s]);
cur+=a[s];
k--;
s=p[s];
}
return mx;
}
int main(){
int t;
cin>>t;
while(t--){
int n,k,s1,s2;
cin>>n>>k>>s1>>s2;
vector<int>p(n),a(n);
for(auto&e:p){
cin>>e;
e--;
}
for(auto&e:a){
cin>>e;
}
long long A=score(p,a,s1-1,k),B=score(p,a,s2-1,k);
cout<<(A>B?"Bodya\n":A<B?"Sasha\n":"Draw\n");
}
}
Author: SashaT9
What is the maximal possible size of $$$\mathcal{H}$$$?
Can you always get that size for $$$n\geq 4$$$?
Consider odd and even distances independently.
Let us find an interesting pattern for $$$n\geq 4$$$.
Can you generalize the pattern? We put $$$n-2$$$ cells on the main diagonal. Then put two cells at $$$(n-1,n)$$$ and $$$(n,n)$$$.
But why does it work? Interesting fact, that in such way we generate all possible Manhattan distances. Odd distances are generated between cells from the main diagonal and $$$(n-1,n)$$$. Even distances are generated between cells from the main diagonal and $$$(n,n)$$$.
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n-2;i++){
cout<<i<<' '<<i<<"\n";
}
cout<<n-1<<' '<<n<<"\n"<<n<<' '<<n<<"\n";
}
}
Author: SashaT9
Is it useful to divide the segment into more than three segments?
Use the fact, that $$$x\oplus x=0$$$ and $$$x\oplus x\oplus x=x$$$.
When you can divide the segment into $$$2$$$ parts?
When can you divide the segment into $$$3$$$ parts?
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N];
int main(){
int t;
cin>>t;
while(t--){
int n,q;
cin>>n>>q;
map<int,vector<int>>id;
id[0].push_back(0);
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]^=a[i-1];
id[a[i]].push_back(i);
}
while(q--){
int l,r;
cin>>l>>r;
if(a[r]==a[l-1]){
cout<<"YES\n";
continue;
}
int pL=*--lower_bound(id[a[l-1]].begin(),id[a[l-1]].end(),r);
int pR=*lower_bound(id[a[r]].begin(),id[a[r]].end(),l);
cout<<(pL>pR?"YES\n":"NO\n");
}
if(t)cout << "\n";
}
}
1968G1 - Division + LCP (easy version)
Author: SashaT9
Binary search.
How to check if two strings are equal?
#include<bits/stdc++.h>
using namespace std;
vector<int>Zfunc(string& str){
int n=str.size();
vector<int>z(n);
int l=0,r=0;
for(int i=1;i<n;i++){
if(i<=r){
z[i]=min(r-i+1,z[i-l]);
}
while(i+z[i]<n&&str[z[i]]==str[i+z[i]]){
z[i]++;
}
if(i+z[i]-1>r){
l=i;
r=i+z[i]-1;
}
}
return z;
}
int f(vector<int>&z,int len){
int n=z.size();
int cnt=1;
for(int i=len;i<n;){
if(z[i]>=len){
cnt++;
i+=len;
}else{
i++;
}
}
return cnt;
}
int main(){
int t;
cin>>t;
while(t--){
int n,k;
string s;
cin>>n>>k>>k>>s;
vector<int>z=Zfunc(s);
int l=0,r=n+1;
while(r-l>1){
int mid=(l+r)/2;
if(f(z,mid)>=k){
l=mid;
}else{
r=mid;
}
}
cout<<l<<"\n";
}
}
1968G2 - Division + LCP (hard version)
Author: SashaT9
Consider the general case: $$$L=1$$$ and $$$R=n$$$.
You must find the answer for each $$$k$$$ in the range $$$[1,n]$$$. Consider the cases $$$k\le \sqrt{n}$$$ and $$$k\geq \sqrt{n}$$$.
#include<bits/stdc++.h>
using namespace std;
vector<int>Zfunc(string& str){
int n=str.size();
vector<int>z(n);
int l=0,r=0;
for(int i=1;i<n;i++){
if(i<=r){
z[i]=min(r-i+1,z[i-l]);
}
while(i+z[i]<n&&str[z[i]]==str[i+z[i]]){
z[i]++;
}
if(i+z[i]-1>r){
l=i;
r=i+z[i]-1;
}
}
return z;
}
int f(vector<int>&z,int len){
int n=z.size();
int cnt=1;
for(int i=len;i<n;){
if(z[i]>=len){
cnt++;
i+=len;
}else{
i++;
}
}
return cnt;
}
int main(){
int t;
cin>>t;
while(t--){
int n,L,R;
string s;
cin>>n>>L>>R>>s;
vector<int>z=Zfunc(s);
const int E=ceil(sqrt(n));
vector<int>ans(n+1);
for(int k=1;k<=E;k++){
int l=0,r=n+1;
while(r-l>1){
int mid=(l+r)/2;
if(f(z,mid)>=k){
l=mid;
}else{
r=mid;
}
}
ans[k]=l;
}
for(int len=1;len<=E;len++){
int k=1;
for(int i=len;i<n;){
if(z[i]>=len){
k++;
i+=len;
}else{
i++;
}
}
ans[k]=max(ans[k],len);
}
for(int i=n-1;i>=1;i--){
ans[i]=max(ans[i],ans[i+1]);
}
for(int i=L;i<=R;i++){
cout<<ans[i]<<' ';
}
cout<<"\n";
}
}