Codeforces Round 856 (Div. 2) Editorial

#	User	Rating
1	Benq	3783
2	jiangly	3772
3	tourist	3706
4	maroonrk	3609
5	Um_nik	3591
6	fantasy	3526
7	ko_osaga	3500
8	inaFSTream	3477
9	cnnfls_csy	3427
10	zh0ukangyang	3423

#	User	Contrib.
1	Um_nik	185
2	awoo	182
3	nor	172
4	-is-this-fft-	170
5	adamant	169
6	maroonrk	165
7	antontrygubO_o	160
8	SecondThread	159
9	dario2994	152
9	kostka	152

Thanks for participating in the round! I hope you enjoyed the problems!

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		int n; cin >> n;
		vector <string> long_subs;
		for(int i = 0; i < 2 * n - 2; i++){
			string s; 
			cin >> s;
			if((int)s.size() == n - 1){
				long_subs.push_back(s);
			}
		}
		reverse(long_subs[1].begin(), long_subs[1].end());
		if(long_subs[0] == long_subs[1]){
			cout<<"YES\n";
		}else{
			cout<<"NO\n";
		}
	}
	
	return 0;
}

Feedback

1794B - Not Dividing

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		int n; cin >> n;
		vector <int> a(n);
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		for(int i = 0; i < n; i++){
			if(a[i] == 1){
				a[i]++;
			}
		}
		for(int i = 1; i < n; i++){
			if(a[i] % a[i - 1] == 0){
				a[i]++;
			}
		}
		for(auto i : a){
			cout << i << " ";
		}
		cout << "\n";
	}
	return 0;
}

Additional comment

Feedback

1794C - Scoring Subsequences

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		int n; cin >> n;
		vector <int> a(n);
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		vector<int> res;
		for(int i = 0; i < n; i++){
			int l = 1, r = i + 1;
			while(l <= r){
				int m = (l + r) / 2;
				if(a[i - m + 1] >= m){
					l = m + 1;
				}else{
					r = m - 1;
				}
			}
			res.push_back(r);
		}
		for(auto i : res){
			cout << i << " ";
		}
		cout<<"\n";
	}
	return 0;
}

Feedback

1794D - Counting Factorizations

Solution

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const ll MOD = 998244353;
 
//checks if n is prime
bool is_prime(ll n){
	if(n == 1){
		return false;
	}
	for(ll i = 2; i * i <= n; i++){
		if(n %i == 0){
			return false;
		}
	}
	return true;
}
 
//computes b ** e % MOD
ll fast_pow(ll b, ll e){
	ll res = 1;
	while(e > 0){
		if(e % 2 == 1){
			res = res * b % MOD;
		}
		b = b * b % MOD;
		e /= 2;
	}
	return res;
}
 
vector<pair<ll, ll>> primes;
 
const int MAXN = 5050;
 
ll dp[MAXN][MAXN];
 
ll fact[MAXN], fact_inv[MAXN];
 
ll f(ll x, ll y){
	ll &res = dp[x][y];
	if(res >= 0){
		return res;
	}
	if(x == (int)primes.size()){
		return res = (y == 0);
	}
	res = fact_inv[primes[x].second] * f(x + 1, y) % MOD;
	if(y > 0){
		res = (res + fact_inv[primes[x].second - 1] * f(x + 1, y - 1)) % MOD;	
	}
	return res;
}
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//reading the input
	int n; cin >> n;
	vector<ll> a(2 * n);
	for(int i = 0; i < 2 * n; i++){
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	//compressed version of a, pairs {value, #occurrences}
	vector<pair<ll, ll>> a_comp;
	for(int i = 0; i < 2 * n; i++){
		if(a_comp.size() == 0u || a_comp.back().first != a[i]){
			a_comp.push_back({a[i], 1});
		}else{
			a_comp.back().second++;
		}
	}
	//computing factorials and inverses
	fact[0] = 1;
	for(ll i = 1; i < MAXN; i++){
		fact[i] = fact[i-1] * i % MOD;
	}
	fact_inv[0] = 1;
	for(ll i = 0; i < MAXN; i++){
		fact_inv[i] = fast_pow(fact[i], MOD - 2);
	}
	//adding only primes for the dp
	for(auto i : a_comp){
		if(is_prime(i.first)){
			primes.push_back(i);
		}
	}
	memset(dp, -1, sizeof(dp));
	ll res = f(0, n);
	//we have to consider the contribution of non-primes too!
	for(auto i : a_comp){
		if(!is_prime(i.first)){
			res = res * fact_inv[i.second] % MOD;
		}
	}
	res = res * fact[n] % MOD;
	cout << res << "\n";
	return 0;
}

Additional comment

Feedback

1794E - Labeling the Tree with Distances

Solution

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN = 200005;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
 
//Hashing stuff
const ll MOD[3] = {999727999, 1070777777, 1000000007};
ll B[3];
 
vector<ll> shift(vector<ll> h, ll val = 0){
	for(int k = 0; k < 3; k++){
		h[k] = (h[k] * B[k] + val) % MOD[k];
	}
	return h;
}
 
vector<ll> add(vector<ll> a, vector<ll> b){
	vector<ll> res(3);
	for(int k = 0; k < 3; k++){
		res[k] = (a[k] + b[k]) % MOD[k];
	}
	return res;
}
 
vector<ll> sub(vector<ll> a, vector<ll> b){
	vector<ll> res(3);
	for(int k = 0; k < 3; k++){
		res[k] = (a[k] - b[k] + MOD[k]) % MOD[k];
	}
	return res;
}
 
//Tree stuff
vector<int> g[MAXN];
 
bool vis[MAXN];
int parent[MAXN];
vector<ll> dp[MAXN], dp2[MAXN];
 
void dfs(int x){
	vis[x] = true;
	for(auto i : g[x]){
		if(!vis[i]){
			parent[i] = x;
			dfs(i);
			dp[x] = add(dp[x], shift(dp[i]));
		}
	}
	dp[x] = add(dp[x], {1, 1, 1});
}
 
void dfs2(int x){
	if(x != 0){
		dp2[x] = sub(dp[parent[x]], shift(dp[x]));
		dp2[x] = add(dp2[x], shift(dp2[parent[x]]));
	}
	for(auto i : g[x]){
		if(i != parent[x]){
			dfs2(i);
		}
	}
}
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int k = 0; k < 3; k++){
		B[k] = rng() % MOD[k];
	}
	//reading the input
	int n; cin >> n;
	vector<int> occurrences(n);
	for(int i = 0; i < n - 1; i++){
		int a; cin >> a;
		occurrences[a]++;
	}
	for(int i = 0; i < n - 1; i++){
		int u, v; cin >> u >> v;
		u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	//calculating possible list hashes
	vector<vector<ll>> list_hashes;
	vector<ll> h = {0, 0, 0};
	for(int i = n - 1; i >= 0; i--){
		h = shift(h, occurrences[i]);
	}
	vector<ll> extra = {1, 1, 1};
	for(int i = 0; i < n; i++){
		list_hashes.push_back(add(h, extra));
		extra = shift(extra);
	}
	//calculating possible tree hashes
	for(int i = 0; i < n; i++){
		dp[i] = {0, 0, 0};
		dp2[i] = {0, 0, 0};
	}
	parent[0] = -1;
	dfs(0);
	dfs2(0);
	vector<pair<vector<ll>, int>> tree_hashes;
	for(int i = 0; i < n; i++){
		if(i == 0){
			tree_hashes.push_back({dp[i], i});
		}else{
			tree_hashes.push_back({add(dp[i], shift(dp2[i])), i});
		}
	}
	//calculting the answer
	sort(list_hashes.begin(), list_hashes.end());
	sort(tree_hashes.begin(), tree_hashes.end());
	vector<int> res;
	int pos = 0;
	for(auto lh : list_hashes){
		while(pos < n && tree_hashes[pos].first < lh){
			pos++;
		}
		while(pos < n && tree_hashes[pos].first == lh){
			res.push_back(tree_hashes[pos].second);
			pos++;
		}
	}
	sort(res.begin(), res.end());
	cout << res.size() << "\n";
	for(auto i : res){
		cout << i + 1 << " ";
	}
	cout << "\n";
	return 0;
}

Feedback

define ll long long

bool isPalindrome(string S) { string P = S; reverse(P.begin(),P.end()); if (S == P) return true; else return false; }

int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

ll t; cin>>t; while(t--) { ll n; cin >> n; vector<string>svec; string s; for(ll i=0; i<2*n-2; i++) { cin >> s; if(s.size() == n-1) { svec.push_back(s); } } string res = svec[0] + svec[1]; if (isPalindrome(res)) cout << "YES\n"; else cout << "NO\n"; } return 0;

}

int function(vector<int>& a, int k, int n) { vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0)); int currSum = 0; for(int j = 1; j <= n; j++) { dp[1][j] = a[j - 1]; currSum += dp[1][j]; } for(int i = 2; i <= k; i++) { int tempSum = 0; for(int j = 1; j <= n; j++) { currSum -= dp[i - 1][j]; dp[i][j] = a[j - 1] * currSum; tempSum += dp[i][j]; } currSum = tempSum; } return currSum; }

int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<string> v(2*n - 2); for (int i = 0; i < 2*n - 2; i++) { cin >> v[i]; } bool ok = true; for (int i = 0; i < 2*n - 2; i++) { if (v[i].size() == n-1) { string rev = v[i]; reverse(rev.begin(), rev.end()); if (find(v.begin(), v.end(), rev) == v.end()) { ok = false; break; } } } if (ok) cout << "YES\n"; else cout << "NO\n"; } return 0; }

Your code here... for (ll i = 1; i < n; i++) { if (arr[i] % arr[i - 1] == 0) { if(arr[i-1]==1){ arr[i-1]++; if(arr[i]%arr[i-1]==0) arr[i]++; } else{ arr[i]++; } } }

Comments (132)

Write comment?

Bhj2001

3 weeks ago, # |

+41

E was doable :/

→ Reply

Tutis

← Rev. 2 →

Why don't we need to check if the remaining distance is not too far away in problem E? (nvm got it)

vinayak_7989

3 weeks ago, # ^ |

Please share the explanation

It could only be wrong in case of a collision, which gives a probability of at most $$$\dfrac{N}{MOD}$$$ of it being wrong for a single vertex, using two hashes solves this.

Dontony

O(n) solution for problem C. https://codeforces.com/contest/1794/submission/196020227

ayush_tiwari26

I did using 2 pointer in O(N) and O(1) extra space

prayas123

+27

C can be done in O(N) using two pointers.

MuhammadSawalhy

The two-pointers technique is an easier and more intuitive solution.

IanISam

You could actually just use greedy for C using a pq. Add the new element at each prefix and while the lowest element in the given series is less than the size of the array, you will remove it. 196022463. Very easy implementation.

drdilyor

+14

Even simpler solution using queue: 196042147

bestial-42-centroids

This is literally the same solution as the two pointers (and it works for exactly the same reasons).

But as the array is sorted you don't need the priority queue.

Oh, I didn’t even realize the array was sorted lul.

GH1hatem

true

geppoz

o(N) with no pointer, just record end-positions: https://codeforces.com/contest/1794/submission/196067881

n_k101

can someone explain in problem B why can't we iterate from right to left basically how addition form left to right is making sure correct answer and not right to left

← Rev. 3 →

Because the constraint is from left to right

Let me explain, draw the elements of the array from left to right in increasing order of the indices. For each i, add a directed edge from the i-th element to the (i+1)-th element. As you can see, the value of the i-th element is constraining the value of the (i+1)-th element to be not divisible.

If you wanted to fix the issues by starting from right, then it would change a[i+1] for it not to be divisible by a[i] but then when you change a[i] for it not to be divisible by a[i-1], the fact that the value of a[i] changed might make a[i+1] divisible by a[i].

While if you do it from left to right, the changes you do on the (i+1)-th value will not affect the values from 0 to i

Jady

Amazing to see so many solutions for C!

whymihere

2 weeks ago, # ^ |

My Code using 2 pointers

#include <stdio.h>
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        int n; scanf("%d", &n);
        int a[n]; 
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        int ptr = 0;
        for(int i = 0; i < n; i++) {
            while(a[ptr] < i - ptr + 1) ptr++;
            printf("%d ", i - ptr  + 1);
        }
        printf("\n");
    }
    return 0;
}

Mayank2707

Nice Contest

satyam_kant

As always good contest and good quality questions.

Raito_Yagami

Great problems (even though I did pretty bad)

iamatester

You are so close to expert. Bad luck this time, better luck next time!

Nahid_Faraji

Anya

Killer_Instinct

O(N) solution for div2 C. Basically if a[i] = j, then for all k from i to i+a[i]-1, this index i will be the "bottleneck" i.e. our max length score will be k-i+1. We can iterate on i and maintain 2 pointers to avoid overlaps.

196049334

TrainGod

+32

Somehow I always assumed that hashing based solutions will never work on codeforces, now feeling stupid :/

areke

You can always choose the modulo randomly to defend against hacks

SirRembocodina

Just use two hashes

Morisz10

composite modulo can be a problem if you have to do modular inverse, and I don't know an easy way of choosing a random prime

quilir

https://codeforces.com/blog/entry/50984?#comment-348756

aryanc403

We can tweak Errichto algorithm in the above comment to generate a uniformly random prime.

Just choose a random no in range and check if it's prime. If it isn't, keep choosing another random no in the range.

A range of length N has $$$N/logN$$$ primes so that this algorithm will end after $$$O(logN)$$$ iterations, and this will be a uniformly generated prime no.

Errichto

+24

I agree.

Disclaimer though: after generating a random prime, the computations modulo that prime are very slow. Do it only in CF, where you can be hacked. Otherwise, using a constant modulo is faster.

Pimienta27

To check if a number k is a prime number is not O(1) i think; then, to generate a random prime this way will be at least a little more than O(logn)

Edit: Is there a way for checking primmality in O(1)?

Noble_Mushtak

Instead of choosing the modulo randomly, you could also choose the base as a random integer from the interval $$$[0, MOD-1]$$$, which is what they do in the editorial.

Kilo_5723

+44

This round needs an extra problem F.

dzhi

+15

Less than 20 people in Div 2 solved E, less than 10 people in Div 2 solved E with 10+ minutes left.

I won't say that this isn't a good round or the last problem isn't interesting, but for most Div.2 rounds these numbers would be 1 or 0.

+43

A problem F that is usually solved by 1 or 0 people in Div 2 satisfies the desire of unofficial participants from Div 1 but will be ignored by most Div 2 participants during the contest, as if it never existed. Maybe I will have a different view/desire once become more advanced, but currently feel such F will add more stress and intimidation, at least during the contest.

ScarletS

See this.

Thanks for the strong tests. I got lots of WA and had a chance to fix them.

Yet another DP problem that I can't solve within the contest time. :(

MouadWillBeExpert

O(n) Solution for C ( https://codeforces.com/contest/1794/submission/196044456 ) PS: I know that i could have only used two pointers without adding a useless memory for the deque!

PurpleCrayon

+91

I solved E by adding heuristics until I got AC. I challenge anyone to hack my solution: 196038364.

Here is what my solution does:

For each node

Find the value that must be added to the array (by calculating the sum of distances from each node — the sum of the values in the array). Make sure that distance is $$$[0, n-1]$$$. Add that missing element.
Check if the number of nodes with distance $$$0$$$, $$$1$$$, and $$$2$$$ are correct.
Check if the maximum value in the array is equal to the maximum distance from the node to any other node (can be done by just checking the endpoints of the diameter of the tree).

If at the end, there are $$$\leq 200$$$ candidates, check all of them individually. Otherwise, check any one of them. If that node is good, every candidate is good, otherwise they are all bad.

← Rev. 6 →

+23

Spoiler

The blog I'm talking about

marc2825

(Including the speed of posting the editorial,) what a great contest!

I liked these problems (especially C & D) because their implementation will be quite simple if we could find out the essence.

Also the number of problems was just nice for a rated participant (like me) to solve them all in time (though I couldn’t solve E).

aditya.wairkar123

← Rev. 4 →

There are 2 strings of length n-1 , and you can't try both direction on one of them. Example: if the original string is "CCCAC" , you will find the strings "CCCA" and "CCAC", and appending "C" to the second, you will find a palindrome => wrong answer

Yeah understood. Thanks a lot!

nilay__patel

O(n) solution for problem C ==> https://codeforces.com/contest/1794/submission/196041871

tfg

+16

How to calculate the probability of a hash failing for hashes like problem E?

jeroenodb

+13

I did the same as the editorial with $$$5$$$ hashes, with $$$P = 10^9 + 7$$$ and $$$5$$$ randomized bases. With a polynomial hash like this the chance of a collision is basically the same as the chance that for an arbitrary polynomial of degree $$$n$$$, if you evaluate at a uniformly random $$$x$$$ that it is equal to $$$0\mod P$$$. A polynomial $$$\mod P$$$ has at most $$$n$$$ roots (if $$$P$$$ is prime). So the chance of a false positive for one hash is $$$n/P$$$. In this problem we actually check equality for $$$n^2$$$ pairs implicitly. So this means that the final probability of failure on one test with $$$5$$$ hashes is $$$ \leq 1 - (1 - (n/P)^5)^{n^2} \approx 1.3 \times 10^{-8}$$$. But seeing that solutions with fewer hashes also passed I think in general the $$$n/P$$$ is a big overestimate.

+10

Are you sure that a polynomial mod P of degree n has at most n roots? That doesn't seem trivial to me. Also about the N^2 thing, if the values of b^e mod P are different, you're left with only 1 candidate per vertex after hashing once. That whole N^2 thing seems different from what I have in mind but it might be just different solutions.

+20

I think it's true for polynomials in arbitrary fields. The proof relies on the fact that if you have a root of a polynomial, then you can write the polynomial $$$f(x) = (x- \texttt{root}) \times g(x)$$$, where $$$g(x)$$$ has degree $$$1$$$ less. By induction you can easily see it that the maximum number of roots is $$$n$$$.

Nice. I was afraid of things not working as usual because x^(P-1) == x^0.

Assume the answer for a testcase should be 0. Then for your answer on the testcase to be wrong, it only has to happen once, that any of the hashes of the $$$n$$$ rooted trees coincides with any of the hashes of $$${ H+b^k, \text{for}\ 0 \leq k <n }$$$ (using editorial notation). So these are two (multi)sets of $$$n$$$ items, for each of the $$$n^2$$$ pairs, you are basically subtracting the corresponding polynomials, evaluating the polynomials at random points, and hoping that the result is not $$$0$$$, because then you mistakenly output some number of good roots $$$>0$$$.

Lagrange's theorem says that

https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory) this? I see no relation.

no, this: https://proofwiki.org/wiki/Lagrange%27s_Theorem_(Number_Theory)

Lain

Formal statement for arbitrary fields — Schwartz-Zippel Lemma

Dragonado

+11

D can be solved in $$$O(n\log n)$$$ time using convolution + D&C. My submission.

Edit: Time complexity is not $$$O(n\log n)$$$. It is $$$O(n \log^2n)$$$.

Can you provide resources about these topics, please? What is D&C?

_enzo

Divide and Conquer I suppose

Convolution is multiplying two polynomials using FFT. D&C is Divide and Conquer. They are very standard topics, you can Google them.

+46

Isn't it $$$O(n \log^2(n))$$$?

Oops, my bad. You are right.

r4kit1czheng

Can you please explain further why fft and D&C come into play here?

Since $$$c^{'}_i = c_i-1 \text{ or } c_i \implies \frac{c_i!}{c^{'}_i!} = c_i \text{ or } 1$$$

We want to calculate sum of $$$\frac{1}{c^{'}_1! \cdot c^{'}_2! \dots c^{'}_t!}$$$

Let us multiply and divide the summation by $$$(c_1!\cdot c_2! \dots c_t!)$$$
We get $$$\frac{(c_1!\cdot c_2! \dots c_t!)}{(c_1!\cdot c_2! \dots c_t!)} \cdot \sum \frac{1}{c^{'}_1! \cdot c^{'}_2! \dots c^{'}_t!} = \frac{1}{(c_1!\cdot c_2! \dots c_t!)} \cdot [\sum (c_{i_1}\cdot c_{i_2} \dots c_{i_n})]$$$ where $$$c^{'}_{i_j} = c_{i_j}-1$$$

So now we want to select $$$n$$$ elements from {$$$c_1, c_2, \dots, c_t$$$}, calculate its product, and then sum it over all ways of choosing $$$n$$$ such elements.
To do that consider the polynomial $$$f = (1 + c_1 x)\cdot(1 + c_2 x) \dots (1 + c_t x)$$$. The coefficient of $$$x^n$$$ in this polynomial is exactly the value we are trying to calculate.

Multiplying two polynomials of length $$$k$$$ can be done in $$$O(k \log k)$$$ time using FFT. But here we have $$$O(n)$$$ polynomials. So if we just keep multiplying from left-to-right it will take $$$O(n^2 \log n)$$$ time. One solution is to use a priority queue and keep multiplying the smallest two polynomials in the product.

The other solution is to use divide and conquer. Recursively calculate the product of the first $$$\lceil\frac{t}{2}\rceil$$$ polynomials and the last $$$\lfloor \frac{t}{2} \rfloor$$$ polynomials. Both polynomials are of size at most $$$n$$$. Now use FFT to calculate product of the left-half and right-half in $$$O(n \log n)$$$. Overall time complexity can be proved to be $$$O(n \log^2 n)$$$

ankan.nayak.1412

-31

I think Problem A can be done more easily & efficiently just by adding the biggest suffix & biggest prefix,then we can just check if it's palindrome or not, I did it this way....

include<bits/stdc++.h>

using namespace std;

-14

btw can some one tell me where did the hashtag(#) go ,how to paste code properly

chuka231

Simple loop and if condition check solves C in O(n) time.

196053649

deadcoder123

how u arrived at this one , plz give some hints

I did observations from my local test case experiments. Whenever ans++, following condotion must met.

int len = 1;
		RREP(i, n) {
			if (i>1) {
				if (a[i - len] >= len + 1) len++;
			}
			cout << len << " ";
		}

vaaven

Proof of $$$\frac{3}{2}n$$$ operations in problem B.

Proof

DockingBlade

Could some explain the reasoning behind the dp in question D?

You can watch my video analysis: https://www.youtube.com/watch?v=jFSUQmxCoUI

kvcodereaper

Nice explanation

Thallium54

+26

I think E can be solved without the $$$dp2$$$ array: let the hash of the current root be $$$cur$$$, then the hash for its child $$$u$$$ is $$$(cur - b \cdot dp_u) \cdot b + dp_u$$$, code: 196075156.

ahmedzaidi2002

can anyone tell me how did my c, solution worked in the given constraint, shouldn't it give tle as i guess it's O(n^2). my submission 196046823 what i did instead of binary search, i did linear O(n) in the while loop. it still worked, but why?

procoderomk

Because for each iteration of the 'forloop', if you notice carefully the 'while loop' is running at most once. So at the end it is a O(n) solution

Sylvester_

yours start pointers is not doing same work again and again it is simply start's where it was left previous after updations.

Adith082

B.NOT DIVIDING VIDEO EDITORIAL LINK : https://youtu.be/HOXFgH_5Nus

HAPPY CODING

Can Anyone Pls Tell My Code Fails on 2nd Test Case 196087709

WaisKamal

Assume the original string is "abaa", so that the longest prefix is "aba" and the longest suffix is "baa". Reverse the longest prefix "aba" and you get "aba". You have to compare it to the longest suffix ("baa"), but you are comparing it to both "aba" and "baa". Hence the WA.

Oh thanks brother for this

izhang

+40

It seems that the author's solution for E has been hacked... https://codeforces.com/contest/1794/hacks/894254

MateoCV

+49

I should have chosen a non-hackable solution to publish in the editorial. It is fixed now.

drexdelta1

HOW TO SOLVE PROBLEM D with N = 10^5 ?

xox0

Following the same setup as the editorial, we need to find the sum of all the terms of the form $$$\frac{1}{c'_1!c'_2!c'_3!...}$$$, where $$$c_i$$$ is the frequency of the ith prime and $$$c'_i$$$ is the frequency after we've chosen the bases. Let's look at this problem another way, let's look at the polynomial $$$P(x) = (\frac{1}{c_1!}+\frac{1}{(c_1-1)!}x) * (\frac{1}{c_2!}+\frac{1}{(c_2-1)!}x) * ...$$$
or in other words $$$P(x) = \Pi_{allprimes} (\frac{1}{c_i!}+\frac{1}{(c_i-1)!}x)$$$
The coefficient of $$$x^n$$$ in this polynomial represents choosing the $$$x$$$ term $$$n$$$ times and the constant term the rest of the times, which is exactly what we want to do, we want to choose the prime as a base $$$n$$$ times. So if we choose our coefficients properly, this essentially gives us our answer. To calculate $$$P(x)$$$ you can use FFT (actually NTT) and Divide and Conquer to do it in $$$O(nlog^2(n))$$$

Submission

ayush002024

another opportunity to feel ashamed....!!

strange14

Problem E — I am getting WA on TC 178, I used the same base and mod as that in the editorial. Can someone help? My submission : 196096531

That was the previous editorial solution. Check the new one.

O(N) and O(1) extra space solution to C using 2 pointers https://codeforces.com/contest/1794/submission/196040502

IfG2

Problem-A -- "i i io i"- why there is no output for this? Can someone help?

ExpertHunter

Hashing strategy in problem E is very nice. I want to say thanks to the author for being a reason to learn this strategy.

Ishaan_23

This code is giving random output on TC 6 pls help https://codeforces.com/contest/1794/submission/196113923

atharv_tiwari

Just had to correct the size of the dp array.
The max value of n is 2022, but the max number of input elements is (n * 2), i.e., 4044. And since the value of the array elements can be up to 10^6, it is possible that we have 4044 distinct primes in the input.
Thus, changing the size of the array to [4045][4045] made the code pass: 196195253

Thank you, i shouldn't have missed that. :)

That's alright mate, happens sometimes :-)

shashank290604

can any one please explain how in problem A this is true , Observe that there are exactly two strings of length n−1 ** (one prefix and one suffix). We will call them x** ** and y** . Then, s ** is a palindrome if and only if rev(x)=y** ,

-15

IN PROBLEM B: CAN ANY ONE EXPLAIN WHY MY CODE DIDN'T WORKED:

196123474

moonpay

if(( arr[i]%arr[i-1]==0) ){

#define r(i,n) for(int i=1;i<=n;i++)

i = n then arr[n] but len(arr) = n !!

kakashi_01_11

https://codeforces.com/blog/entry/113556#comments

ag_007

Not able to figure out why i am getting correct ans in test 5 but WA in test 9 for problem D.

I have used a bottom-up dp.

could someone please help, my code

i_emerge16

Problem D is nice!

Magdy_Sedra

Can anyone help me make sense of something in problem E?

This submission got Wrong answer : https://codeforces.com/contest/1794/submission/196157777 but this one got Accepted : https://codeforces.com/contest/1794/submission/196160146

The only difference between them is that they have different primes numbers. I thought that the cause is a collision but i used the prime numbers of the judge's solution on the one that got wrong answer so the occurrence of collision doesn't make sense.

I would appreciate if anyone can help me understand the cause of that.

Edit: Hacked. but i still know why my code is wrong if someone can help?

Collision. Use 3+ mods and/or random bases to avoid hacks.

A_G

+29

I'll provide my generator for generating hacks on E, if anyone else wants to do more (and I know for certain that there are a lot more hackable solutions out there). Look for solutions that use some fixed pairs of base and modulo and place them in the pairs variable in the code. There were a few special cases that required another idea to hack but I won't describe the details unless requested.

Generator

import random

def conv(a, b):
    """
    Compute product of a and b as polynomials
    """
    c = [0]*(len(a)+len(b)-1)
    for i in range(len(a)):
        for j in range(len(b)):
            c[i+j] += a[i]*b[j]
    return c

def eval(poly, x):
    return sum(poly[i]*x**i for i in range(len(poly)))

def get_poly(x, mod):
    """
    Given integer x, return a nonzero polynomial P such that P(x) is a
    multiple of mod for mod on the order of 10^9.

    This algorithm fails in some specific cases but should be fine for typical
    values used for hashing. Adjust l and mx as necessary.
    """
    l = 10
    mx = 7
    res_to_tuple = {}
    while 1:
        coeffs = [random.randint(0, mx) for _ in range(l)]
        res = eval(coeffs, x)%mod
        if res in res_to_tuple:
            if coeffs == res_to_tuple[res]:
                continue
            return [coeffs[i]-res_to_tuple[res][i] for i in range(l)]
        res_to_tuple[res] = coeffs


# List pairs (base, mod) used in the hash
pairs = [
        (200003, 1e9+7),
        (200003, 998244353),
        (200003, 1070777777),
        ]

# Convert to ints (so you can write 1e9+7 instead of int(1e9+7))
for i in range(len(pairs)):
    x, y = pairs[i]
    pairs[i] = (int(x), int(y))

p = [1, -1]
for x, mod in pairs:
    p = conv(p, get_poly(x, mod))
if p[0] < 0:
    for i in range(len(p)):
        p[i] = -p[i]

S = sum(abs(x) for x in p)
# Number of vertices in the construction is about S/2
if S > int(4e5):
    print("FAIL", p, S)
    exit(0)
elif S > int(2e4):
    # output is too large to be pasted directly, use a generator instead
    print(p)
    exit(0)

# Print the test case given p
a = [max(x+1, 1) for x in p]
for i in range(len(p)):
    p[i] = a[i]-p[i]

p = p[1:]
edges = []
n = 1
for x in p:
    for i in range(x):
        edges.append((n, n+i+1))
    n += x
print(n)
a[0] -= 1
l = []
for i in range(len(a)):
    l += [i]*a[i]
print(*l)
for u, v in edges:
    print(u, v)

golions

Can you explain how this generator works?

+28

For simplicity, consider a version of the problem where instead of $$$n-1$$$ distances being given, all $$$n$$$ distances are given. It's pretty similar when it comes to hacking. A solution takes the following form: pick some $$$r$$$ and $$$p$$$, and mark a vertex $$$v$$$ as good if

$$$\displaystyle\sum_{u=1}^{n}r^{d(u, v)}\equiv \displaystyle\sum_{i=0}^{n-1}r^{a_i}\pmod{p}$$$

where $$$d(u, v)$$$ is the distance from $$$u$$$ to $$$v$$$.

We'll try to make vertex $$$1$$$ a false positive. Let $$$P$$$ be the polynomial defined by

$$$P(x)=\displaystyle\sum_{u=1}^{n}x^{d(1, u)}-\displaystyle\sum_{i=0}^{n-1}x^{a_i}.$$$

Then we should make it so that $P$ is not identically zero, yet $$$P(r)\equiv 0\pmod{p}$$$. Additionally, $$$P(1)=n-n=0$$$.

There are pretty much no further constraints on the polynomials $$$P$$$ we can use now, aside from the coefficients not being too large so that the number of vertices is at most $$$2\cdot 10^5$$$. For example, if we have the polynomial $$$P(x)=-10+13x-3x^2$$$, then we can write it as a difference

$$$P(x) = (1+13x+x^2)-(11+4x^2)$$$

which means a graph with $15$ vertices where $$$13$$$ vertices are at distance $$$1$$$ from $$$1$$$, one vertex is at distance $$$2$$$, and the wrong distances consist of $$$11$$$ zeroes and $$$4$$$ twos. The graph is easy to construct from here. (For the actual version of the problem, just delete one copy of $$$0$$$.)

To construct the polynomial, note that we can first find a polynomial with $$$P(r)=0\pmod{p}$$$ and then multiply it by $$$(x-1)$$$ to have $$$P(1)=0$$$. With $$$p$$$ on the order of $$$10^9$$$, we can use a birthday paradox approach. Generate random polynomials with small coefficients and check the residues $$$P(r) \pmod{p}$$$ until you find a collision $$$P_1(r)\equiv P_2(r)$$$ where $$$P_1\neq P_2$$$. Then we can use $$$P=P_1-P_2$$$ as our polynomial. Assuming the residues are uniformly random, this should take about $$$\sqrt{p}$$$ tries which is fine.

To handle multiple hashes $$$(r_i, p_i)$$$, find a polynomial for each pair and then multiply them together. This works because if $$$P_i(r_i) \equiv 0 \pmod{p_i}$$$ then any multiple of $$$P_i$$$ also satisfies the same property. At some point the product polynomial's coefficients are too large but I was able to hack 5 hashes pretty easily.

12 days ago, # ^ |

Wow, this is really cool — thanks for the detailed explanation!

SunnyYuan

C is a nice problem.

tvermaashutosh

One can use this $$$DP$$$ method to find the sum of the product of all $$$k$$$ sized subsets out of an array of $$$n$$$ numbers.

Once_I_Liked_AGirl

Can somebody help me on problem D,this is my submission 196227451,thanks!

I make a mistake and su.ccessfully solve D now,haha.

plus_minus_delta

In problem D, my code is giving correct output on all small test cases. But it is failing on large test cases. I am getting 'WA on Test 5' verdict. Please someone help me in correcting my code. Submission Link — https://codeforces.com/contest/1794/submission/196218425

You seem to have accidentally declared N to be 2002 instead of 2022.
Changing just that made the code pass: 196296912

Thanks.

prabhavdobhal45

C by fenwick link

vitosevski

I had the same solution, but changing elements in the array filled with zeroes and then calculating the prefix sums at the end was enough. It works in $$$O(n)$$$.

dot1209

I'm stuck on problem A. I tried using the following code to find two substrings of length n-1 and check if one of them is equal to its reverse, but it didn't pass the test. Can someone help me

Sinocchi

it fails for string "bba" (sequence b b a bb ba)

10 days ago, # ^ |

Thanks :)

snacache

Has anyone found a way (or, is it possible) to solve problem E without hashing or heuristics?

I really like the hashing approach, but I'm just curious about alternative solutions :)

alexvim

Need for any advice about DP solution for C.
My idea was calculating
dp[i] = max(dp[i-1], a[i], dp[i-1]*a[i]/(state[i-1]+1))
where dp is maximal score for prefix a[0..i] and state is maximal cost for this prefix.
state[i] is being calculated according to dp choice (see code).
What did I wrong? Thanks for any help :)
https://codeforces.com/contest/1794/submission/196045900

ankush_86

Can anyone explain the concept in C problem?

ravi_code66

This is my solution for problem B can anyone tell me why it doesnot work. I think its correct but i am getting wrong answer on test 2.Please help me i am a newbie.