Codeforces Round 903 (Div. 3) Editorial

Tutorial

Solution

def solve():
    n, m = map(int, input().split())
    x = input()
    s = input()
    for i in range(6):
        if s in x:
            print(i)
            return
        x += x
    print(-1)


for _ in range(int(input())):
    solve()

1881B - Three Threadlets

Idea: Gornak40

Tutorial

Solution

for _ in range(int(input())):
    a, b, c = sorted(map(int, input().split()))
    if a == b and b == c:
        print('YES')
    elif b % a == 0 and c % a == 0 and (b // a - 1) + (c // a - 1) <= 3:
        print('YES')
    else:
        print('NO')

1881C - Perfect Square

Idea: myav, MikeMirzayanov, Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>
#define all(arr) arr.begin(), arr.end()

using namespace std;

const int MAXN = 1010;

int n;
string A[MAXN];

int solve() {
    int ans = 0;
    for (int i = 0; i * 2 < n; ++i)
        for (int j = 0; j * 2 < n; ++j) {
            vector<char> M {A[i][j], A[n - 1 - j][i], A[n - 1 - i][n - 1 - j], A[j][n - 1 - i]};
            char c = *max_element(all(M));
            for(char e: M)
                ans += c - e;
        }
    return ans;
}

int main() {
    int t; cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> A[i];
        cout << solve() << endl;
    }
}

1881D - Divide and Equalize

Idea: myav

Tutorial

Solution

#include<bits/stdc++.h>
using namespace std;
const int maxv = 1000000;

void add_divs(int x, map<int, int>&divs){
    int i = 2;
    while(i * i <= x){
        while (x % i == 0){
            divs[i]++;
            x /= i;
        }
        i++;
    }
    if(x > 1) divs[x]++;
}

bool solve(){
    int n;
    cin >> n;
    vector<int>a(n);
    map<int, int> divs;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        add_divs(a[i], divs);
    }
    for(auto e: divs){
        if(e.second % n != 0) return false;
    }
    return true;
}

int main(){
    int t;
    cin >> t;
    while(t--) {
        cout << (solve() ? "YES" : "NO") << "\n";
    }
}

1881E - Block Sequence

Idea: MikeMirzayanov

Tutorial

Solution

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    dp = [n + 1] * n

    def get(pos):
        if pos > n:
            return n + 1
        if pos == n:
            return 0
        return dp[pos]

    dp[-1] = 1
    for i in range(n - 2, -1, -1):
        dp[i] = min(dp[i + 1] + 1, get(i + a[i] + 1))
    print(dp[0])


for _ in range(int(input())):
    solve()

1881F - Minimum Maximum Distance

Idea: ibraevdmitriy

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> g;

void dfs(int v, int p, vector<int> &d){
	if(p != -1) d[v] = d[p] + 1;
	for(int u: g[v]){
		if(u != p){
			dfs(u, v, d);
		}
	}
}

int main(){
    int t;
	cin>>t;
	while(t--){
	    int k;
		cin>>n>>k;
		g.assign(n, vector<int>(0));
		vector<int> marked(k);
		for(int &e: marked) cin >> e, --e;
		for(int i=1;i<n;i++){
			int u, v;
			cin >> u >> v;
			--u, --v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		if(k==1){
			cout<<0<<"\n";
			continue;
		}
		vector<int> d1(n);
		dfs(marked[0], -1, d1);
		int mx = marked[0];
		for(int e: marked){
		    if(d1[e] > d1[mx]) mx = e;
		}
		vector<int> d2(n);
		dfs(mx, -1, d2);
		mx = marked[0];
		for(int e: marked){
		    if(d2[e] > d2[mx]) mx = e;
		}
		cout << (d2[mx] + 1) / 2 << "\n";
	}
	return 0;
}

1881G - Anya and the Mysterious String

Idea: Gornak40

Tutorial

Solution

#include <iostream>
#include <string>
#include <set>
#include <cstring>
#define int long long

using namespace std;

const int L = 26;
const int MAXN = 200200;

int n, m;
string s;
set<int> M2, M3;
int fen[MAXN];

void fenadd(int i, int x) {
	x = (x % L + L) % L;
	for (; i < n; i |= (i + 1))
		fen[i] = (fen[i] + x) % L;
}

int fenget(int i) {
	int ans = 0;
	for (; i >= 0; i = (i & (i + 1)) - 1)
		ans = (ans + fen[i]) % L;
	return ans;
}

void relax(int l, int r) {
	l = max(l, 0LL);
	r = min(r, n);
	for (int i = l; i + 1 < r; ++i) {
		int c1 = fenget(i);
		int c2 = fenget(i + 1);

		if (c1 == c2) M2.insert(i);
		else M2.erase(i);

		if (i + 2 >= r) continue;

		int c3 = fenget(i + 2);
		if (c1 == c3) M3.insert(i);
		else M3.erase(i);
	}
}

void build() {
	M2.clear();
	M3.clear();
	memset(fen, 0, n * sizeof(int));
	fenadd(0, s[0] - 'a');
	for (int i = 1; i < n; ++i) {
		fenadd(i, s[i] - s[i - 1] + L);
	}
	for (int i = 0; i + 1 < n; ++i) {
		if (s[i] == s[i + 1]) M2.insert(i);
		if (i + 2 < n && s[i] == s[i + 2]) M3.insert(i);
	}
}

void update(int l, int r, int x) {
	fenadd(l, x);
	relax(l - 5, l + 5);
	fenadd(r, L - x);
	relax(r - 5, r + 5);
}

bool query(int l, int r) {
	auto it = M2.lower_bound(l);
	if (it != M2.end() && *it + 1 < r) return false;
	it = M3.lower_bound(l);
	if (it != M3.end() && *it + 2 < r) return false;
	return true;
}

signed main() {
	int t; cin >> t;
	while (t--) {
		cin >> n >> m >> s;
		build();
		while (m--) {
			int tp, l, r; cin >> tp >> l >> r, --l;
			if (tp == 1) {
				int x; cin >> x;
				update(l, r, x);
			} else {
				cout << (query(l, r) ? "YES" : "NO") << '\n';
			}
		}
	}
}

if(!distante.empty() && (distante.back()).second == vecin) { if(distante.size() >= 2) { int poz = distante.size() - 2; dfs2(nod, vecin, max(dist, distante[poz].first) + 1); } else dfs2(nod, vecin, dist + 1); } else if(!distante.empty()) dfs2(nod, vecin, max(distante.back().first, dist) + 1); else dfs2(nod, vecin, dist + 1);

Comments (88)

Show archived | Write comment?

asdasdqwer

3 years ago, hide # |

+12

I just have a question: Why is the algorithm for F correct? What's the intuition behind it?

→ Reply

Kareem_Elgoker

3 years ago, hide # ^ |

Its like diameter of the tree and you want to get a point in the middle of it you can say as a centroid

Yes, I know, but we essentially don't care about which nodes are marked and which ones are not.

robostac

Assume the tree is rooted at a marked node. If you are at the deepest marked node on a branch and move further down that branch it will increase the distances to all marked nodes by 1 (meaning the value of that node will be greater than the marked node you came from). You can therefore remove any nodes past the deepest marked node on each branch. From this it follows that you have a tree where all the leaves are marked and at that point it's the standard algorithm for finding the largest distance from a leaf.

JSR1

can't we do it with rerooting?

ohmygodtosbryantooorz

← Rev. 2 →

I actually did it with rerooting, with lazy segment tree. You can check out my submission 227869909 .

DeletedUser2343

There is no need for a lazy segment tree to do the rerooting.

chinesedfan

← Rev. 5 →

My rerooting with prefix and suffix sum. It is really a bit too more complicated, so I missed the first AK in div 3 (got AC after the contest 12min later, because of a little afraid of TLE by NodeJS). https://mirror.codeforces.com/contest/1881/submission/227927645

The first DFS will calculate 3 kinds of values,

dp[u], the max length from u to a marked node under u's subtree
prefix[u][j], the max length from u to a marked node under u's [0,j] children's subtree
suffix[u][j], the max length from u to a marked node under u's [j,] children's subtree

The second DFS is rerooting. For each u, its answer can be calculated by two parts,

dp[u], to nodes under u's subtree
out, to nodes not under u's subtree

When rerooting from u to v, out is updated by 3 parts. All of them should increase 1 if necessary.

u's out
u itself
max(prefix[u][j-1], suffix[u][j+1]), with v is u's jth child

Hope above can help you improve understanding of rerooting, even this problem is not the best application to be solved.

stefdasca

F can also be done in a similar fashion to Tree Distances —

Submission for Tree Distances

Solution for CF: 227871270

Cipher07

Exactly! Problem F can be considered as the special case of this one. 227869702 Here's mine with a slightly different approach.

fREaK092

21 month(s) ago, hide # ^ |

Can you please explain this part in your code

Yes, this code is one of my older ones where I used Romanian names for various variables

distance = distances, an array which stores for each vertex the maximum distances to leaves vecin = next node (literal translation is neighbor) nod = node

Basically if you have at least two children, you don't want to visit the same path which gave you the best answer, I have a video where I explain this in more detail.

cookieeee

278260829

can you please help why this solution of mine fails. I tried to implement the method explained in your video

Sahil_32

+17

"the author is lazy"

Pretty obvious from the way this editorial is written

helloworld1102

For problem 1881F - Minimum Maximum Distance , can someone please tell the proof why it is always true to consider the longest distance between the labelled vertex and then divide it by 2 then take ceil of it.

After considering some examples it becomes somehow convincing but not very intutive about why that condition will always be true.

HexShift

+11

Define $$$dist(i,j)$$$ as the distance between node $$$i$$$ and node $$$j$$$.

Assume that there are $$$3$$$ labelled vertices $$$a,b,c$$$ and $$$(a,b)$$$ is the pair that creates longest distance from two labelled vertices. To find the node position that makes the minimum value of maximum distance to either $$$a$$$ or $$$b$$$, ofc we choose the node (call this node $$$d$$$) that resides in the middle of the path from $$$a$$$ to $$$b$$$ (since if without loss of generality we assume $$$dist(d,a) \leq dist(d,b)$$$, then $$$dist(d,b) = \bigg\lceil\frac{dist(a,b)}{2}\bigg\rceil$$$ is the maximum from both and this is the min value of $$$dist(d,b)$$$).

Now, suppose $$$dist(d,c) \gt \max(dist(d,a),dist(d,b))$$$. Then, the longest distance from two labelled vertices must be the pair $$$(c,a)$$$ or $$$(c,b)$$$ (since $$$dist(d,c)+dist(d,b) \gt dist(d,a)+dist(d,b)$$$ and $$$dist(d,c)+dist(d,a) \gt dist(d,b)+dist(d,a)$$$) which results in contradiction.

123gjweq2

-12

C was the coolest one and it's not even close

NeoYL

bruh I felt that G was much more interesting than all the problems(despite me tryping 11 attempts to AC G)

Shivu

Starters were bad(ABC) but the main course was good(DEF) but i am not able to understand the bill(editorial)

tru, i dont really enjoy ABC this round. DE was kinda meh for me. FG was quite interesting to play around with

Vardanverma96

2 years ago, hide # ^ |

can you explain to me why in E we are updating dp[i] as

dp[i]=min(dp[i+1]+1,dp[i+a[i]+1]) and not as

dp[i]=min(dp[i+1]+1,dp[i+a[i]+1+j]+j) for all j st i+a[i]+1+j<n indexing from 0.

← Rev. 3 →

Depends on how you define your DP. My design was that dp[i] = minimum removals I can have after considering all the values from [i, n — 1].

Case 1: We don't take the current index.

That means that we will need to remove this index. So, dp[i] = min(dp[i], dp[i + 1] + 1).

Case 2: Take the current block.

That means that we will need to remove all the values from [i, i + a[i] + 1]. So, dp[i] = min(dp[i], dp[i + a[i] + 1]). Need to make sure it is not out of bound. You can only end up at i + a[i] + 1, nowhere else.

I am saying that when you take the current block, it means you will take a[i] number of elements with you and then consider the next block. So I am saying that we pop some more values before taking the a[i] values and it can land us an even better solution. Thats y i am checking for all j possible

Fluoresce

Task D

If we assumed 1s can calculate 10^8 times, but in the worst condition(all a are equal to 999983), it will judge near 2000(t)*10^4(n)*10^3 times. Would it TLE?

I am a novice and thank you for your generous advice and point out my mistakes.

No, because the sum of n over all testcases does not exceed 10^4. So it's 10^4*10^3.

oh,oh i misundertand it!thanks

Ahmed--Mohsen

https://ideone.com/lyUPEZ

problem F c++ BFS code: why RTE on test 3 ???

← Rev. 9 →

Ok let me show some potential improvements of your code:

Why you are wrong: You missed out the corner case (n=1) where deg[1]=0 meaning your "start" is undefined and therefore shows runtime error. Meanwhile, the solution is wrong(after I tested it with the fixed code).

Data Structures used: You dont need to push the k values into a set instead use a boolean vector or smt. set requires O(nlogn) which means you will waste precious time if you are using set.

Your code checks if the root is in the set and the adjacent elements as well, you can generalise it by putting it after int node=q.front(); q.pop(); if(bla bla bla) mdis.push_back(...). You can save some lines of code.

You can try learning how to write functions such as function<void(int)> bfs=[&](int root){ code here}; this allows you to write the function inside your main fucntion where you dont need to pass all the arrays and stuff. You can access it inside the function. This should save you some implementation time as well.

Your code is not very clean (for a guy like me), therefore hard to read. I saw some parts of the code that has strange spacing. I used to be a template monster with around 400 lines of templates, but I find it hard to debug if I write a code with lots of shortforms(for some reason). I recommend spending sometime either looking at other people's code and learning a neater way of writing it. I'm not pinelizing you, just giving some personal suggestions

Neater and fixed code(although it is wrong): Sorry that I deleted the front part of your code.

code is here: https://ideone.com/fN9WEY

Abracadaber

I lost the top 150 due to hacking task D :(

i3mr125

same got TLe . because i am too dum dum and used frequency array instead of a map

now instead of + 40 delta its a negative delta :(

the predictor showed me +140, and 136 was missing before blue, but now only +50. And it would also be my best result on codeforces

sad :( now we learned something from this silly mistake at least.

Pirate_King

there's a predictor ?

xboy

this is a better one imo

https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn

chromate00

You don't really need the map. You just need a way to make the rollback/reset $$$O(1)$$$ amortized. This could be done by storing what was updated in a separate stack/queue/whatever.

yes, but is it easier than just using map? In fact, if I had received a tle during the contest, I would have quickly rewritten everything on the map and what happened would not have happened.

At least it's easier than rewriting, I should tell you. It's basically just stk.push_back(k) whenever you update index $$$k$$$, and while(!stk.empty()){arr[stk.back()]=0;stk.pop_back()} for the reset.

MostafaO4o

https://mirror.codeforces.com/contest/1881/submission/228412567 is this reset considered o(1)? as i didn't use stack to remember what i pushed and i didn't get TLE

No, but the number of primes is not too big. Try finding out the value of $$$(\text{number of primes below }10^5) \times 2000$$$

Simple and insightful Video Editorials for A-E.

embetapbay

← Rev. 4 →

Why is my code for incorrect? I feel like it closely resembles the intended idea. It's prob D. Please help me My code

VolodiaHeizenberg

I suppose in the end of the function "check" you should add max1 = max(max1, a) as it could be still the biggest prime number

yes, i did it in my code.

Well, the everything I have done is just change array to map and it worked...

https://mirror.codeforces.com/contest/1881/submission/228020694

whyyyyyy ? :(

memset doesn't work how you think (the size is in bytes, so you only reset 1/8th of the array). Having said that using the correct length will cause a TLE.

Well, interesting. So in this case should we just use vector instead of array?

Nah, it doesn't work too. Well, therefore is there any solution without using map? I take it there isn't.

227869532 i found jiangly's code.

i solved it without maps https://mirror.codeforces.com/contest/1881/submission/228412567 but i hardcoded the prime count to 10power6 (i think i could counted it using seive)

can someone explain to me why map would be better?

because in 1 test case, you must check for 79000 primes. And with map, you simply need to check the prime factors. I think that

not_ahmed_hamed

For F, It's always better to re-construct the tree like this.

Tree

It's related to tree diameter (I guess there's no formal proof but this blog will help Blog)

Flash-

Can anyone please explain how does D solution works? Can't able understand how counting frequency of prime divisors gives our answer.

myav

Let's use two ideas:

1) Every number can be represented as a product of prime numbers (= prime divisors). This is known as factorization.

2) If two numbers are equal, they have the same set of prime divisors.

So, the operation in the problem allows you to "take" one prime divisor from a[i] and "give" it to a[j].

If, after doing this operation several times, we can rearrange the divisors so that every number in the array has the same set of divisors, then the answer is YES.

To check that this is possible, we can simply count the number of occurrences of each divisor in the products.

For example, consider test case 4:

30 50 27 20

30 = 2 * 3 * 5

50 = 2 * 5 * 5

27 = 3 * 3 * 3

20 = 2 * 2 * 5

We have four occurrences of "5", four occurrences of "3" and four occurrences of "2". By doing the operation several times, we can turn each number into 2*3*5.

Thanks! Understood

Typed_SIGTERM

Only AC 1 problem... f**k me

youll get better

noobiesAG

If someone prefers video explanations or interested in knowing how to think in a live contest or reach to a particular solution.
Here is my live Screencast of solving problems [A -> E] (with detailed commentary in Hindi language).

Can G solved with sqrt-decomposition?, I'm getting WA2 Code

I think it shoud be fine, WA means your code has some errors not TLE. But im pretty sure if your code has a large constant factor with sqrt-decomposition, your code might TLE

Yup I know, I just wanted tye TLE verdict not the WA one to make sure that my idea is correct.

Erm i also got many wa2(you can see from my submissions) I had many WA2 because I even pushed l into my valid answers when s[l-2]==s[l] but actually its invalid. If l is in the set meaning s[l]==s[l+2]. So check if your program has valid answers correctly. Also similarly for r with r+1 and r+2. r-1 with r+1.

It's TLE now, the solution was right but I forgot a case $$$(i+1,i-1)$$$ when jumping by $$$sqrt$$$ size 228099350

kar2003

the editorial is short and to the point!!

sirvi_26

alaa.A

Problem F solutions are based on the tree diameter, It takes some greedy proofs but in the end you can convert the problem to a direct tree diameter problem. Here's a blog

Folka

Any one Feels that this contest was not for Div.3 ?

It seems to be Harder :(

brownfox2k6

How do I solve 1881G - Anya and the Mysterious String with Segment tree using Lazy propogation? This is what I've done 227967016, I haven't used Lazy propogation and it's TLE. Thank you in advance.

_bidhayak

Why this code doesn't work for problem D?

code

 int n;cin>>n;
   int a[n];
   ll l=1;
   forn(i,n){
    cin>>a[i];
    l*=a[i];
   }
   ll rl=ll(pow(l,1/n));//taking n-th power
   if(ll(pow(rl,n))!=l){cout<<"NO"<<endl;}
   else cout<<"YES"<<endl;

The product of the whole input is in the order of $$$O(A^n)$$$ which is at most $$$10^{60000}$$$ :unamused:

No, product of every integer input per test case would be (10^10). correct me if I'm wrong.

No man that's the sum not the product 💀💀💀

JustJie

LOL True

Sekhar

I feel it was really a nice contest for anyone starting out on cp in the sense that it offers a good mix of adhoc and dsa

Go8

f can be solved using dp Let define d(v) as the max distance from vertex v to a labeled vertex in its subtree and define g(v) as the max distance from vertex v to a labeled vertex which is not in the subtree of v then d(v)=max(d(child of v)+1), g(v)=max(g(parent of v)+1,d(sibling of v) + 2) then f(v)=max(d(v),g(v))

adarsh.kumariitbhu

can u plz explain the intuition and the process as well as the implementation...plzz !!

SNX03

F is similar to

Tree Distances I

The only change is to fix the end points of the diameter as RED nodes.

I did rerooting for F, would've gotten top 100 or something but I had to have a typo that I didn't see

1021839

I have two nicer(?) solutions than the official ones.

B: Suppose everything has length $$$l$$$ in the end. Then $$$l \mid A$$$, $$$l \mid B$$$, $$$l \mid C$$$ (proof: run the splitting apart in reverse). This is also sufficient, and uses $$$\frac{A}{l} + \frac{B}{l} + \frac{C}{l} - 3$$$ operations. The number of operations is minimised when $$$l$$$ is maximum, so $$$l := \gcd(A, B, C)$$$; to solve the problem just check if the minimum is at most 3. 228383697

(I saw a lot of people at the top of unofficial standings iterating over $$$(A + B + C) / l$$$ and testing each of them using this condition; it's quite strange to me that they didn't use GCD instead...)

G: There is no need for Fenwick trees or segment trees, you can check palindromes using just the difference array (and maintain bad positions using std::set as in the tutorial). 228383431

Hayan

Can someone Please help me with the problem F . My code 228434471 is giving wrong answer at Test 4.

shorya1835

Problem G with sets and vectors is also possible submission

Kusoul

Can anybody can tell me whether my solution in F can use when it have the edge-weight?Can it be called DP?228766385

Can someone explain what does this mean ~ Notice that palindromes do not appear or disappear inside a segment, but they can appear or disappear at its boundaries

dino_merlin

2 years ago, hide # |

G can also be solved only with segment tree. In each node we keep track of the first two characters in the interval as well as the last two (or just one character if its a leaf). Then when we merge two intervals we just keep check if a palindrome is formed at the edges. Updates can also be handled very simply by just applying the shift operation to the characters we keep track of. AC with this idea: https://mirror.codeforces.com/contest/1881/submission/240931303

dp[i]=min(dp[i+1]+1,dp[i+a[i]+1+j]+j) for all j st i+a[i]+1+j<n indexing from 0

Marlboro

22 months ago, hide # |

can some body explain d part

divya8080

11 months ago, hide # |

editorial not loading for F problem

showing "Unable to parse markup [type=CF_MATHJAX]"

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	jiangly	3631
4	Kevin114514	3574
5	maroonrk	3521
6	strapple	3515
7	Radewoosh	3461
8	tourist	3428
9	turmax	3378
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

Vladosiya's blog