Codeforces Round 943 (Div. 3) Editorial

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

We thank everyone who participated in the round.

1968A - Maximize?

Hint 1

Hint 2

Hint 3

Solution

Implementation

#include<iostream>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int x;
		cin>>x;
		cout<<x-1<<"\n";
	}
}

Rate the problem

1968B - Prefiquence

Author: FBI

Hint 1

Solution

Implementation

#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";
	}
}

Rate the problem

1968C - Assembly via Remainders

Author: SashaT9

Hint 1

Hint 2

Hint 3

Solution

Implementation

#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";
	}
}

Rate the problem

1968D - Permutation Game

Author: FBI

Hint 1

Hint 2

Solution

Implementation

#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");
	}
}

Rate the problem

1968E - Cells Arrangement

Author: SashaT9

Hint 1

Hint 2

Hint 3

Solution

Implementation

#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";
	}
}

Rate the problem

1968F - Equal XOR Segments

Author: SashaT9

Hint 1

Hint 2

Hint 3

Hint 4

Solution

Implementation

#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";
	}
}

Rate the problem

1968G1 - Division + LCP (easy version)

Author: SashaT9

Hint 1

Hint 2

Solution

Implementation

#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";
	}
}

Rate the problem

1968G2 - Division + LCP (hard version)

Author: SashaT9

Hint 1

Hint 2

Solution

Implementation

#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";
	}
}

Rate the problem

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct Hash { int n; string s; const ll p = 31; ll mod = uniform_int_distribution<int>((int)(1e9+7), (int)(1e9+1e8))(rng); vector<ll> pw, hash; Hash(string _s) : s(_s) { n = s.size(); pw.resize(n+1); hash.resize(n+1); pw[0] = 1; for(int i=1; i<=n; i++) pw[i] = (pw[i-1] * p) % mod; hash[0] = s[0] - 'a' + 1; for(int i=1; i<n; i++) hash[i] = (hash[i-1] + pw[i] * (s[i] - 'a' + 1)) % mod; } ll getHash(int l, int r) { return (hash[r] - (l ? hash[l-1] : 0) + mod) % mod; } bool equal(int l1, int r1, int l2, int r2) { if(r1 - l1 != r2 - l2) return 0; if(l1 > l2) swap(l1, l2), swap(r1, r2); return (pw[l2-l1] * getHash(l1, r1) % mod) == getHash(l2, r2); } bool isPal(int l, int r) { return equal(l, r, n-1-r, n-1-l); } };

while(q--){ int l,r; cin>>l>>r; if(a[r] == a[l-1]){ cout<<"YES"<<endl;continue; } int x = *lower_bound(mp[a[r]].begin(), mp[a[r]].end(), l); int y = *lower_bound(mp[0].begin(), mp[0].end(), x+1); if(y<r && y>x && x>=l)cout<<"YES"<<endl; else cout<<"NO"<<endl; }

void solve(){ int t; cin>>t; while(t--){ int n; cin >>n; vector<int> x(n+1); for(int i=2 ; i<n+1 ; ++i) cin >>x[i]; vector<int> a(n+1,1); for(int i=2 ; i<n+1 ; ++i){ if(a[i-1]<=x[i]){ a[i-1] = a[i-1]*(x[i]/a[i-1] + 1); a[i] = a[i-1] + x[i]; } else if(a[i-1]>x[i]){ a[i] = a[i-1] + x[i]; } debug(a) } //debug(a) for(int i=1 ; i<=n ; ++i) cout << a[i] << " "; cout << nline; } } Your code here...

Комментарии (164)

Написать комментарий?

WakuWakuWaku

8 месяцев назад, # |

← Rev. 2 →

any good resources or blogs to explain Z-function?

→ Ответить

SashaT9

8 месяцев назад, # ^ |

+28

Here or here

SNX03

This is KMP but literally the same thing that was required for G1/G2.

Spoiler

nskybytskyi

usaco.guide

Matrosk1n

+15

codeforces edu

AkiLotus

CSES CP book has a dedicated chapter (Advanced topics -> String algorithms -> Z-algorithm) for this topic, and personally I find its explanation really friendly.

tbquan08hanoi

I was thinking too complex at the problem D

same.

so do I

LOL same

Me too!

I also lies in the same category. :")

xyw_6

Good way to express!

Jackduy

7 месяцев назад, # ^ |

the same bro

RED_Falcon

Can someone make clear how did the first question really work, I mean I thought about doing it in the same way as you've explained but I saw that some of the test cases doesn't work by that implementation on the test cases 1000 => 750 and on some other test cases, how please???

HeteroTuring

It says to print out any possible(maintaining the statement) value of y. so printing out 750 or 500 or even 999 will be allowed in this case.

Oh yeah it worked thanks bro

wjranger

Should Problem B be just a 2 pointer problem with a time complexity of O(min(a, b))?

FBI

Yeah,that is one of the possible solutions. However, it is easier to explain the dp solution)

ismailfateen

There exists an $$$\mathcal{O}(n \log^2 n) $$$ solution with a very good constant factor for G2, reply to this if interested.

hxano

I just thought of one too. Does it involve sorting and parallel binary search?

sam571128

You don't need any of that. You could simulate what you do in G1 with a set/segment tree by iterating over the lengths, and it works. The time complexity came from harmonic series and the log from DS.

thanhdno

There also exists an O(n log n) solution using DSU.

Not sure what “parallel binary search” means, but it is nested binary search. I don't sort anything.

Basically, we still have our nice $$$z$$$ function, however, we will also store an RMQ which can get the maximum value of $$$z_i$$$ for all $$$i$$$ in a range $$$[l, r]$$$.

Let's precompute the value $$$mx_i = \text{maximum number of disjoint substrings with length } i, \text{which are all equal to the prefix of length } i$$$

If we want to check if $$$k$$$ disjoint substrings are possible with $$$\text{LCP}$$$ $$$l$$$, we just check if $$$mx_{l} \ge k$$$.

Now the problem is the computation of $$$mx$$$.

For length $$$i$$$, there can be at most $$$\frac{n}{i}$$$ disjoint substrings with that length. Let's use the fact that $$$\sum_{i=1}^{n}\frac{n}{i}=\mathcal{O}(n \log n)$$$.

Using our RMQ, we can, instead of calculating $$$mx_i$$$ in linear time in the length, we can calculate it in $$$\mathcal{O}(mx_i \log n)$$$, simply binary search on the next $$$j$$$ such that $$$z_j \ge i$$$ (here, we binary search and use a sparse table to get this next $$$j$$$ in $$$\mathcal{O}(\log n)$$$, alternatively, you can walk on a segment tree in $$$\mathcal{O}(\log n)$$$).

The complexity of this computation is $$$\sum_{i=1}^{n}mx_i\cdot \log n = \log n \sum_{i=1}^{n} mx_i \le \log n \sum_{i=1}^{n}\frac{n}{i}=\mathcal{O}(n \log^2 n)$$$

NexTopper

In G2 for every l <= i <= r, I used binary search and memorized answer for mid. Solution

Yes, that is my AC submission after the contest. I was able to show a loose upper bound (not in terms of $$$n$$$, but more like the maximum possible number of operations).

FlashVS

8 дней назад, # ^ |

My code is almost exactly similar to yours, but it is getting tle on tc 13, could you take a look at it please?

296358703

misteg168

RMQ is quite overcomplicated, I just used a set 259230125

codex47

Can somebody tell how to do G1 using KMP? I don't know KMP well enough to manipulate it.

ASHWANTH_K

← Rev. 3 →

+10

FOR G2: answer f(x) is decreasing function, so i just modified simple binary search solution for G1, by just changing the upperlimit as previous answer.
Code: 259245908
I am not able to prove this tho... please help me.

nflight11

Thanks for your brilliant problems! Round was fun enough to spend full competition time just solving the problem.

VaibhavPal99

Can anyone explain why Sasha is the winner in the second test of problem D?

Riyad_Hossain

k -> 8; pb — 2; ps — 10 path -> 3 1 4 5 2 7 8 10 6 9 score-> 5 10 5 1 3 7 10 15 4 3

If both play optimally: Bodya sticks to his current position. Score -> k*score[i] -> 10*8 -> 80 Sasha moves the highest score possible and sticks there. Score -> 3+4+7+10*(15*4) -> 84

Thus, Sasha is the winner. I hope you understand:)

Yes, thanks for the explanation.

Can someone please tell me what's the rating of problem D? I'm asking because the rating is not updated on the problem tag.

clist said it was 1349 at the time I wrote this comment. I personally would say it might be around 1200-1300.

Around 1300

rushi_mungse

For B: Optimise Answer

void solve() {
    int n, m; cin >> n >> m;
    string a, b; cin >> a >> b;
    
    int j = 0;
    for(int i = 0; i < m; i++) {
        if(a[j] == b[i]) j++; 
    }

    cout << j << endl;
}

formidablechief27

Made video editorials for C,D,E for whoever wants to refer

C : https://www.youtube.com/watch?v=oEx5rR4wAKw

D : https://www.youtube.com/watch?v=XBUN4LwolEM

E : https://www.youtube.com/watch?v=DObsk_Rlhg8

language => Hindi

DeaphetS

In problem F, my submission 259182179 has been hacked. But I resubmit it and got AC... Could anyone tell me why???

alex17.12

Testset hasn't been updated yet, all AC solutions will be retested during some hours with updated tests

Six_Seconds

Your resubmission will soon give WA verdict after system testing. In current System's all testcases are those that were during the contest [where u got AC]. Now, all the testcases that could hack other's solution, will be added in the System testcases[including the testcase that could hack ur F no. solution] and System test will run again. Then, u will get a different verdict.

djm03178

Uphacked as per your wish :) now it should be automatically added to the tests already.

:((((((((((

btw, is other solutions (259304100 and 259314753) hackable?

259304100: Probably yes 259314753: No

It's all about smashing unordered_map, you can check the generator I used once system test is done.

thx a lot :D

fine... new submission has been uphacked :(

i should use map replace unordered_map

vstiff

G1/G2 can be solved without any fancy algorithms as in my rust solution in C++ too: 259314092

My G1 C++ submission was the same but it was hacked

This? You should implement it more carefuly, look at Complexity section for string +=

Maybe

nguyenkhangninh99

CAN YOU explain how it works

Count number of non-overlapping occurrences of prefix of length lcp in s. Then binary search lcp, then cache it, then find ans for every k in $$$[l..r]$$$.

andre_rei

-7

I also solved G1 without using any string algorithm during the contest, but after main tests I got TLE :(

cwz2024

And TLE in main test:(

We may use kmp or hash or other algorithm to search a substring in $$$O(n+m)$$$ time, and a simple brute force can become $$$O(nm)$$$ in the worst cases.

Yes, the built-in find in c++ is too slow for it.

Yes. Also, what is funny is that your solution that passes on G2, doesn't pass on G1. They probably forgot to add the same test case on G2 and no one hacked it.

I assumed G2 includes all tests from G1, but then checked it on G1 and finally got my TLE :)

Interesting that Rust uses Two-way matching and passes easily. The same algorithm is said to be used in std::strstr, I tried it: 259358346 and it doesn't even pass G2.

Vladosiya

Just bc G1 had TL 2sec when G2 had 3sec. I'll remember this for next contests :(

That's not the root cause, for sure. G2 AC in 1.7sec: 259346859 (while doing much more work) and exactly same code TLEs in G1: 259347015

I think it's ok that simpler problems have lower time limit.

Doesn't kmp takes overlapping patterns into consideration as well? How to remove that?

SiRBruce

+17

Is this solution for G2 hackable? Using two heurestics:

1) Memoising the value of cnt calculated in f(mid)

2) Since the answer always decreases on increasing k, keeping the value of hi from previous k(not setting it to n again).

Not able to proove it's time complexity.

+27

I have done the same thing, and I was able to prove the complexity to some extent. It's easy to see that my code is $$$\mathcal{O(n\cdot\text{number of distinct values of } mid})$$$.

First let's assume $$$l=1$$$ and $$$r=n$$$, the binary search ranges are $$$[1,n],[1,\frac{n}{2}],\dots,[1,\frac{n}{n}]$$$.

The main observation is this, the range $$$(\frac{n}{2},n]$$$ is exposed to $$$1$$$ binary search, the range $$$(\frac{n}{3},\frac{n}{2}]$$$ is exposed to $$$2$$$ binary searches. Similarly, the range $$$(\frac{n}{i},\frac{n}{i-1}]$$$ is exposed to $$$i-1$$$ binary searches.

It is clear that with this, we have a very loose upper bound of $$$O(n\cdot\sum_{i=2}^{n}\min((i-1)\cdot\log(n), \frac{n}{i-1}-\frac{n}{i})$$$. However, as i said, this is very loose, as the sum $$$\sum_{i=2}^{n}(i-1)\cdot\log(n)$$$ is quite a bit more than $$$n\cdot\log(n)$$$ (the total number of checks).

We can make this tighter.

Let's consider the ranges $$$1$$$ by $$$1$$$, first we have the range $$$(\frac{n}{2}, n]$$$. We have $$$2$$$ cases, the first case is that $$$\log(n)$$$ is smaller than the range, in which case (for the sake of an upper bound), we should assume that we take all the $$$\log(n)$$$ checks from that range, becuase we will never see that range again, so it is best to take as much as we can from that range, hence decreasing the number of times the other ranges can be chosen by $$$\log(n)$$$.

However, if the range length is less than $$$\log(n)$$$, then all the next ranges are also smaller than $$$\log(n)$$$. So in fact, a better upper bound is $$$\mathcal{O(n\cdot\sum_{i=2}^{n}\min(\log(n),\frac{n}{i-1}-\frac{n}{i}))}$$$, this value is $$$733800000 \approx 7\times 10^8$$$ for $$$n=2\cdot 10^5$$$.

el_tunel

The point where the minimum changes from $$$\lg n$$$ to $$$n/(i-1)-n/i$$$ will be $$$i\approx i_0=\sqrt{n/\lg n}$$$, so this analysis gives a runtime bound proportional to around $$$n\cdot ((n/i_0)+(\lg n)\cdot i_0)=2 n \sqrt{n \lg n}$$$.

thunder_fart

Can someone please explain D as why greedy works. like can't a player stay at position for more than 1 time and then move to next one to get best answer. Its's confusing to think that he will move only by staying once or either staying all rest of left moves on that positions.

Won't it also depend on array A's elements as to loose some chances in low points in pursuit of bigger points to get maximum answer.

i still can't get how greedy gets right answer

Zaid_Al_Habbal

If you move from your current position cur to another position nxt then It should be a[nxt]>a[cur], else it's optimal to stay at your current position.

I hope you understand.

Yeah I get it now. I was stuck on dp approach making it complex and wasn't able to think greedy.

Thanks

xu_zhihao

-16

第四题出的太好了

Noobish_Monk

For G2 there is also solution using the problem:

-we can deactivate an element

-we need to find the closest active element to the right

That can be done using dsu

Then we'll increase lcp. When we increase it by one, we deactivate elements, so we're left only with elements with $$$z_i \ge curLCP$$$ where $$$z_i$$$ is z-function.

To find maximum $$$k$$$ that can achieve at least $$$curLCP$$$ we will start at the beginning and then jump to the next active element of $$$i + curLCP$$$. Since the answer for $$$curLCP$$$ is at most $$$\frac{n}{curLCP}$$$, $$$O(ans)$$$ solution works in $$$O(n log n)$$$, and dsu gives us either $$$\alpha(n)$$$ or $$$log n$$$

Interesting solution, do you have the code example?

259187296 for example

What's nice about this task is that there so many different interesting solutions

https://mirror.codeforces.com/contest/1968/submission/259227872

avighnakc

In G2, shouldn't the time complexity of the case when $$$k > \sqrt{n}$$$ be $$$\mathcal{O}(n \sqrt{n})$$$? (the editorial says it's $$$\mathcal{O}(n \sqrt{n} \log{n})$$$)

ando

I agree. The total complexity is ($$$n\sqrt{n}\ logn$$$), but when $$$k>n$$$,it works in ($$$n\sqrt{n}$$$).

Thanks, fixed:)

GlydonNeedsDedication

-8

approx. rating of G2? 2100+ right?

clist said 2266 as I typed this.

+11

That usually means 2000-2100

Bnahmad15

For G2 I had a similar idea to use the fact that the answer only changes a few times and I calculated the answer for each segment with new n/l.

However, this got WA, not sure why, so I replaced it with an O(n*log^2(n)) (please someone correct me if I'm wrong).

You first binary search for the leftmost index with an answer less than the last one.

Here's the submission 259255876

It TLE'd on the general test. :(

shouldn't O(N log^2 (N)) <= O(N sqrt(N))

I'll try analyzing the complexity and if someone can correct me...

1- Calculating the Z function is done in O(N)

2- Then there's the check which is also O(N)

3- Both binary searches are log(N)

4- is there a sqrt(N) I'm missing maybe?

My friend had an $$$O(n \log^2{n})$$$ solution that ACed (which I believe uses a similar idea to your $$$n/l$$$ thing), if you wanna check that out.

I don't quite understand tbh. if you could explain it to me please... unforgettablepl

unforgettablepl

In my code, the calc function is pretty much the same as the check function in your code. The got variable in your code stores the maximal k such that the answer is >= len. In my code, the calc function returns the got variable. Now I make an array called ans where ans[i] = maximal k such that the answer is >= i using this function. For answering queries I just binary search over this answer array.

RegenFallen

+20

Use hash to check whether two string equal again.

And be hacked again (((

VMaksimoski008

I used hashing too, but I wasn't hacked since I used mersenne twister to randomly select mod for hashing.

cseshamim47

Can you share your hashing template?

Here you go.

Also be aware that the function isPal only works if the to the string is appended its reverse.

For example, let's say we will call isPal for the string s = "cabad".

To chech is substring from "aba" is palindrome, you have to initialize the hashing structure with the string "cabaddabac"

Does this line returns a prime number?

ll mod = uniform_int_distribution<int>((int)(1e9+7), (int)(1e9+1e8))(rng);

No. It return random integer in the range $$$[10^9+7, 1.1*10^9]$$$.

The mod doesn't need to be a prime number.

Thank you my friend.

noomaK

Why such tight constraints on G2, $$$n \leq 2\cdot 10^5$$$ when the intended time complexity is $$$O(n\sqrt{n}log(n))$$$??

arash.

There is (in my opinion) easier $$$O(n log^{2}n)$$$ solutions too.

PedroBigMan

Hey,

G2 is solvable in O(NlogNlogN): checking the maximum number of intervals one can separate in such that the common prefix has length at least k is doable in O(N/k logN) if we store the valid indices with Z[i]>=k in a set.
Can someone understand why the solution to F gives TLE if we use unordered_map<int,vector > instead of map<int,vector >? My solution using unordered_map was TLEd in the main tests, and the official solution has the same issue when we use unordered_map. This seems unintuitive as we never use the key ordering.

Thanks!

For the 2nd point, I think even from the main tests have some exploits on unordered_map to cause enough hash collisions for $$$\mathcal{O}(n)$$$ access. It's been a common exploit for quite a while, and it's due to hash table's nature itself, as long as its hashing could be reverse engineered.

tickbird

now I get it

Is there any tutorial for that Z function used in G1?

989

Edu

Is it this? https://cp-algorithms.com/string/z-function.html

coder0687

Can anyone refer me more problems like E?

omsincoconut

Check out constructive algorithms

of what range?

Range? I’m not sure what you mean.

Problem rating like 1600-1700?

There’s a wide range of difficulty for constructive algorithms, so I’m not sure what to suggest. Just choose the difficulty range you would normally do, I suppose?

Okay, sure Btw thanks

nassjes

why do we usually use a segment tree for finding xor on segments and not just how it was described in the problem f? or we just do this only when elements don't change?

Correct. We can do prefix XOR to evaluate range XOR in case that there are no updates (That is, no change). But if there are updates, then we use a Fenwick or segment tree.

polsage

how can we use segment tree pls tell??

In the same way how it is used for sums, but you change each node to store the XOR of the interval instead.

ohk got it, thanks

ClosetNarcissist

I think there's an error in the editorial for problem F. It says "we may find the largest t <= r" but it should be t < r since if t == r then the segment [t+1, r] would not make sense. I tried a solution with this change in mind and it got AC. 259369531

IhBa_

Looks like I have to practice more to recognize patterns in problems like in E!

calmpsychopath

For Problem C, if we want to find the lexicographically smallest sequence $$$a_1, a_2, a_3, ..., a_n$$$ what would be the approach?

Belal_Abouraya

Anyone has an idea why this one gets TLE https://mirror.codeforces.com/contest/1968/submission/259216131 ? it is exactly the same complexity as the editorial solution.

nipun753

On problem F i am not convinced with the solution , can anyone provide with a better approach here , because i see the statement that

Observation: any division on more than k>3 segments can be reduced to at most 3 segments. Doesn't hold the biequivalence , that if the segment can be divided into atmost 3 segments then it can be divided into k segments

The equivalence is not needed, we simply require that k > 1.

We are only required to show an injection in one direction. I think we can't show bijection here, because it is not always true, that we may divide from $$$3$$$ segments up to $$$k$$$.

v_i_sh_a_l

Easy observation solution for E. Put two dots at (1,1) and (n,n) One dot at (2,1). and the remaining(n-3) on the first row starting from the third column. The intuition behind this is to get all possible Distances for N >= 4. To get all distance I first choose (1,1) and (n,n) which gives distances 0 and 2*n-2. then put one at (1,2) to get the distance of 1 and 2*n-1. We can get the remaining in pairs if we put them on the first row. for ex- (1,3) will give distance 2 and 2*n. and so on for (1,4), (1,5) ... .

karna001

could someone please explain the bfs solution for problem D, also what will be maximum number of steps to reach a cycle in a permutation of length n where we move from a random number x in permutation to permutation[x] 1 indexing similalry moving forward

yariss

In a permutation of length n, the max number of steps to reach a cycle is always n.

example : 4 3 1 2

Here, whatever starting position you had, you will need to perform 4 moves to end up at the starting position

for 3 2 1 and if you are at 3 you go to p(3) that is 1 and then p(1) that is 3 it took only two steps right

Kanishk_0012

I have a general doubt, on how to build a constructive approach + thinking in problems like E. I generally find it difficult to find a pattern. So in general what should be my approach while tackling such problems. (Ig having the right intuition at the beginning is very important.) If possible please do suggest me something on this :)

DeadlyFe

(Disclaimer) I haven't solved E since lack of time. I think everyone has it since there is no generalisation in such problems :) What I find helpful for myself is to look into the properties of data structures and operations used in problems. For example, it's clear u can get max Manhattan distance by putting cells into corners. It gives u unique combination and also a range of all possible distances. Than u can see, that putting cells into the lines/diagonals gives u lots of other combinations since u have more unique values in the formula. The hardest part is to notice that u lack some values in the range and how to adjust it. I would say that examples in the problem allow u to reverse engineer the idea of leaving one empty column and putting 2 cells into one.

Another example is a task C where solution based on one property of modular arithmetic. Tutorial used one property, I used similar one (a mod b = a b > a), which allowed me to take as ai just xi if condition is satisfied and if not i still took ai as xi only with an adjustment of ai-1 by ai-2 as many times as needed.

dr.owl

← Rev. 4 →

problem E as per the tutorial: 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)

but I guess if total x manhattan distances exist then we only get x-1 , how to prove we can get max x-1 distances only ?

if I am wrong please correct me

SashaT9 Please help !!

ohh I understand, we get all the distances both even and odd except in the case of 2,3.

Ryuu7

Could you please explain the idea behind problem E solution? I am not quite sure

First, try to find all possible distances, Try to put all the pieces diagonally, see what distances are covered, and then what happens if you move a piece. What distances are covered now?

There are other ways like placing in the first row and last column, you can try to find these patterns also.

we have only a single clue what distances we can cover, and if all, then how? If not, how do you cover max number of distances?

Thanks. Got it :)

theGreyHound

In problem F, what is wrong in the following logic: (Here a represents the prefix xor array and mp is mp[xor] = vector)

You need to look for the sum a[l - 1], not 0.
The result of the second call to lower_bound() may not be dereferenceable.
You don't have to check whether $$$y>x$$$ or $$$x\ge l$$$, since these things are automatically true.

Kenshi01

Why is O(nlogn) approach exceeding time limit in B question? Normally O(nlogn) works with n<2x10^5 and time limit = 2 sec.

(i tried to write a solution using upper bound 259169919)

You are using upper_bound incorrectly: the way set is structured isn't linear, thus it will make your command $$$\mathcal{O}(n)$$$.

Instead, use the class method built for set, something like this:

auto x1 = ons.upper_bound(lst);

auto x2 = zrs.upper_bound(lst);

thanks for the help

WrongAtTestCase1

How else can G1 be solved ?

ScitusSnake

Binary Search on Prefiquence felt more intuitive. https://mirror.codeforces.com/contest/1968/submission/259543727

Could someone tell me what is wrong with my submission https://mirror.codeforces.com/contest/1968/submission/259550793

keerthanyadav23

are there any problems similar to F

JonathanSS

Can someone please explain to me the solution for problem D cause, I can't understand the editorial clearly

ishrak26

Let me explain my idea:

Let $$$f_s(p)$$$ be the total score of a player when he starts at the position $$$s$$$, always moves from his current position until he reaches $$$p$$$, and after reaching $$$p$$$, always stays at his current position. Bodya and Sasha's maximum score will be $$$\max_{1 \le i \le n}{f_{P_B}(i)}$$$ and $$$\max_{1 \le i \le n}{f_{P_S}(i)}$$$ respectively.

This claim is correct because, a player will always move from his current position only when there lies some better position with higher $$$a_x$$$, somewhere in the future along the path of his $$$k$$$ moves. Now we will prove why it is always better for him to move now instead of staying at the current position for some turns and then move.

If his current position is $$$x$$$, and he decides to stay at $$$x$$$ for some (one or more) turns, and then move to $$$p_x$$$, there are the following three cases:

$$$a_x < a_{p_x}$$$: It is obviously better to move to $$$p_x$$$ immediately and not waste turns at $$$x$$$ with lower score.
$$$a_x = a_{p_x}$$$: Staying and moving doesn't really differ here. So there is no loss in moving.
$$$a_x > a_{p_x}$$$: When he moves after some turns, he moves definitely in the hope of reaching some position $$$y$$$ from $$$p_x$$$ (through one or several moves in between) where $$$a_x < a_y$$$. So it is always better to spend these turns at the position $$$y$$$ than wasting them on $$$x$$$.

So the optimal move for a player will be — some number of moves (possibly zero), followed by some number of stays (possibly zero), until he completes his $$$k$$$ turns. So we basically iterate over his final position to know the maximum possible score.

For all $$$1 \le i \le n$$$, $$$f_s(i)$$$ can be calculated in $$$O(n)$$$ by keeping track of how many turns it takes to reach $$$i$$$ starting at $$$s$$$ and the total score obtained along the path.

So overall running time of the solution is $$$O(n)$$$.

You can check my submission for better understanding: 259185280.

Thank you for your explanation

Why my solution is failing for G1? I have used the same idea stated in the editorial but instead of z-function, I have used rolling-hash. My Code

About the problem F , I have a question. According to the formula $$$X ^ X ^ X = X$$$ , why reduce k to three , instead of further reduce one? Could help me ?

$$$one$$$ subarray is not allowed in the problem.

Thank you for your reply! I actually forget the detail ， $$$k > 1$$$.

andrewtt

I implemented the solution described by the editorial for G2 during contest but got TLE...

https://mirror.codeforces.com/contest/1968/submission/259238179

I am posting this so late because I was trying to upsolve with a smarter solution, but couldn't come up with one. It's pretty frustrating that my approach was correct but failed because of the constant factor.

GaiaKing

for f what is the different between "--lower_bound(id[a[l-1]].begin(),id[a[l-1]].end(),r)" and "lower_bound(id[a[l-1]].begin(),id[a[l-1]].end(),r — 1)"

You don't find lower_bound $$$>=$$$ in the first case instead you find the first value that is $$$<$$$ $$$r$$$

thx bro

anbxmw

I don't get why simple binary search doesn't work on G1. Can anyone explain? Why my code gets WA on 3 test? https://pastebin.com/SnQmt9qk

haku-_-

7 месяцев назад, # |

problem D was awesome.

can you suggest more problems like that one?!

kevin_Durant_

Good tutorial, thanks! But I want to ask that In problem F, why we should do mp[0].push_back(0) ?

Sabbir.Hasan

For G2: I would be glad if any one help understand why author's O(n√n log(n) ) solution is passing where n=2e5 and time limit 3s.

kir_tan22

Can somebody help me with Problem D submission ? i seem stuck here. 260790899

NamanJ_1

Can someone please tell what mistake am I doing in G1 ?

https://mirror.codeforces.com/contest/1968/submission/260861542

Fork512Hz

G2 卡常厳しすぎ！！ (Constant factor for G2 too tight!)

I implemented the solution described in the editorial, with KMP instead of Z-function, but all my submissions ended up TLE41 (261016696) and I couldn't get the log^2 solution right.

By dividing the submission into $$$>\sqrt{n}$$$ and $$$\le\sqrt{n}$$$ parts I found my solution would finish in 3.2 seconds and I tried my best to squeeze in but still couldn't.

Could anyone help me optimize the constant factor further, or is KMP unable to pass?

BTW I don't think a $$$2e5$$$ data range for a $$$O(n\sqrt{n}\log n)$$$ intended solution is quite appropriate.

tushar_joshi

if we divide the first part into < root(N / log(N)) and > root(N * log(N)) we can have a time complexity of n * root(n * log(n)). Maybe you can try this.

In G2 I submitted 2 solutions one wit time complexity O(N * sqrt(N) * log(n)) and other with O(N * sqrt(N * log(N))). The former solution passed whereas the later gave TLE. Does anyone have any idea why this is happening?

Former solution: https://mirror.codeforces.com/contest/1968/submission/261653053

Latter solution: https://mirror.codeforces.com/contest/1968/submission/261652536

rajnishism

what is the need of permutation in the problem D

__Legacy__

E was too easy to be E

bansalarpan4

6 месяцев назад, # |

hi i have employed pretty much same logic as given in editorial in problem C , but in reverse sense but it is not giving right output for last test case (1 5) can u help what is wrong with it

mikacy

any idea why does this get tle?

https://mirror.codeforces.com/contest/1968/submission/268508103

AksLolCoding

3 месяца назад, # |

G2 can be easily solved with z-function in O(nlogn^2). We find the maximal k for each answer i in increasing order. Use ordered set to maintain list of all indices in z-function that are greater than or equal to i and binary search for each next index. This allows us to binary search for each answer. Code

Блог пользователя SashaT9