Educational Codeforces Round 177 Editorial

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	158
2	adamant	152
3	Proof_by_QED	146
3	Um_nik	146
5	Dominater069	144
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

Thank you for participating! I hope you enjoyed the problems.

2086A - Cloudberry Jam

Tutorial

Solution (Galina_Basalova)

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << n * 2 << "\n";
    }
    return 0;
}

2086B - Large Array and Segments

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    int n, k, x;
    cin >> n >> k >> x;
    vector<int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }

    if (accumulate(a.begin(), a.end(), 0ll) * k < x){
        cout << 0 << '\n';
        return;
    }

    int l = 1, r = n * k;
    while(l <= r){
        int m = l + (r - l) / 2;
        int cnt_a = (n * k - m + 1) / n;
        int suff = (n * k - m + 1) % n;
        int sum = cnt_a * accumulate(a.begin(), a.end(), 0ll);
        for (int i = n - suff; i < n; i++){
            sum += a[i];
        }
        if (sum < x){
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }

    cout << r << '\n';
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin >> t;
	while(t--){
	    solve();
	}
}

2086C - Disappearing Permutation

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++){
        cin >> p[i];
        p[i]--;
    }

    set<int> X;
    for (int i = 0; i < n; i++){
        int d;
        cin >> d;
        d--;
        while(!X.contains(d)){
            X.insert(d);
            d = p[d];
        }
        cout << X.size() << ' ';
    } 
    cout << endl;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	while(t--){
	    solve();
	}
}

2086D - Even String

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
const int MOD = 998'244'353;
 
int bpow(int x, int p){
	int res = 1;
	while(p){
		if (p % 2){
			res = (res * x) % MOD;
		}
		p >>= 1;
		x = (x * x) % MOD;
	}
	return res;
}
 
int fact(int x){
	int res = 1;
	for (int i = 1; i <= x; i++){
		res = (res * i) % MOD;
	}
	return res;
}
 
void solve(){
	vector<int> c(26);
	for (int i = 0; i < 26; i++){
		cin >> c[i];
	}
 
	int s = accumulate(c.begin(), c.end(), 0ll);
	
	vector<int> dp(s + 1);
	dp[0] = 1;
 
	for (int i = 0; i < 26; i++){
		if (c[i] == 0){
			continue;
		}
		for (int j = s; j >= 0; j--){
			if (j + c[i] <= s){
				dp[j + c[i]] = (dp[j + c[i]] + dp[j]) % MOD;
			}
		}
	}
 
	int ans = dp[s / 2] * fact(s / 2) % MOD * fact((s + 1) / 2) % MOD;
	for (int i = 0; i < 26; i++){
		ans = (ans * bpow(fact(c[i]), MOD - 2)) % MOD;
	}
 
	cout << ans << '\n';
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

2086E - Zebra-like Numbers

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include<bits/stdc++.h>
using namespace std;
 
long long dp[40][120][2][2];
 
void count(vector<int>& num){
	int m = num.size();
	memset(dp, 0, sizeof(dp));
 
	dp[0][0][1][0] = 1;
	for (int i = 0; i < m; i++){
		for (int j = 0; j < 3 * m + 2; j++){
			for (int k = 0; k < 4; k++){
				if (j + k >= 3 * m + 2){
					break;
				}
				if (num[i] == k){
					dp[i + 1][j + k][1][0] += dp[i][j][1][0];
					dp[i + 1][j + k][0][0] += dp[i][j][0][0];
					if (k == 0){
						dp[i + 1][j + k][1][1] += dp[i][j][1][1];
						dp[i + 1][j + k][0][1] += dp[i][j][0][1];
					}
				}
				else if (num[i] > k){
					dp[i + 1][j + k][0][0] += dp[i][j][0][0];
					dp[i + 1][j + k][0][0] += dp[i][j][1][0];
					if (k == 0){
						dp[i + 1][j + k][0][1] += dp[i][j][0][1];
						dp[i + 1][j + k][0][1] += dp[i][j][1][1];
					}
				}
				else{
					dp[i + 1][j + k][0][0] += dp[i][j][0][0];
					if (k == 0){
						dp[i + 1][j + k][0][1] += dp[i][j][0][1];
					}
				}
			}
			if (j + 4 < 3 * m + 2){
				if (num[i] == 4){
					dp[i + 1][j + 4][1][1] += dp[i][j][1][0];
					dp[i + 1][j + 4][0][1] += dp[i][j][0][0];				
				}
				else{
					dp[i + 1][j + 4][0][1] += dp[i][j][0][0];					
				}
			}
		}
	}
}
 
void solve(){
	long long l, r, k;
	cin >> l >> r >> k;
	l--;
	if (k >= 90){
		cout << 0 << '\n';
		return;
	}
 
	vector<long long> zeb;
	long long cur = 0;
	for (int i = 0; i < 60; i += 2){
		cur ^= (1ll << i);
		zeb.emplace_back(cur);
	}
	int m = zeb.size();
 
	vector<int> num_l;
	for (int i = m - 1; i >= 0; i--){
		int cnt = 0;
		while(l >= zeb[i]){
			cnt++;
			l -= zeb[i];
		}
		num_l.emplace_back(cnt);
	}
 
	vector<int> num_r;
	for (int i = m - 1; i >= 0; i--){
		int cnt = 0;
		while(r >= zeb[i]){
			cnt++;
			r -= zeb[i];
		}
		num_r.emplace_back(cnt);
	}
 
	count(num_r);
	long long ans = dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];
	count(num_l);
	ans -= dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];
	cout << ans << '\n';
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin >> t;
	while(t--){
	    solve();
	}
}

Solution (BledDest)

#include <bits/stdc++.h>
using namespace std;
 
vector<long long> z;
 
void precalc()
{
    z = {1ll};
    while(z.back() < 1e18)
        z.push_back(4 * z.back() + 1);
}
 
map<pair<long long, long long>, long long> dp;
 
long long get(long long r, long long x)
{
    if(dp.count(make_pair(r, x))) return dp[make_pair(r, x)];
    long long& d = dp[make_pair(r, x)];
    if(x > 4 * z.size()) return d = 0;
    if(x < 0) return d = 0;
    if(r == 0) return d = 0;
    if(r == 1)
    {
        if(x == 0) return d = 1;
        return d = 0;
    }
    auto it = lower_bound(z.begin(), z.end(), r);
    --it;
    long long y = *it;
    return d = get(y, x) + get(r - y, x - 1);
}
 
int main() 
{
    precalc();
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        long long l, r, x;
        cin >> l >> r >> x;
        cout << get(r + 1, x) - get(l, x) << endl;
    }
}

2086F - Online Palindrome

Idea: Valentin_E

Tutorial

Solution (FelixArg)

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
bool is_palindrom(const string& s){
    int n = s.size();
    for (int i = 0; i < n / 2; i++){
        if (s[i] != s[n - i - 1]){
            return false;
        }
    }
    return true;
}
 
bool check_pattern(const string& s){
    int n = s.size();
    char a = 'a', b = 'b';
    int cnt_a = 0, cnt_b = 0;
    for (int i = 0; i < n; i++){
        if (s[i] == a){
            cnt_a++;
        }
        else{
            cnt_b++;
        }
    }
    if (cnt_a % 2 == 1){
        swap(cnt_a, cnt_b);
        swap(a, b);
    }
    if (s[n / 2] != b){
        return false;
    }
    if (!is_palindrom(s)){
        return false;
    }
 
    cnt_b--;
    cnt_a /= 2;
    cnt_b /= 2;
 
    if (cnt_a > cnt_b){
        swap(cnt_a, cnt_b);
        swap(a, b);
    }
 
    if (s[0] == a){
        cnt_a--;
    }
    else{
        cnt_b--;
    }
 
    for (int i = 1; i < n / 2; i++){
        if (s[i] == s[i - 1]){
            if (cnt_a == 0){
                return true;
            }
            return false;
        }
        if (s[i] == a){
            cnt_a--;
        }
        else{
            cnt_b--;
        }
    }
 
    return true;
}
 
pair<int, int> find_valid_move_odd(string s){
    int n = s.size();
    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++){
            swap(s[i], s[j]);
            if (check_pattern(s)){
                return {i, j};
            }
            swap(s[i], s[j]);
        }
    }
    return {-1, -1};
}
 
pair<int, int> find_valid_move_even(string s){
    int n = s.size();
    for (int i = n - 1; i >= 0; i--){
        for (int j = 0; j <= i; j++){
            if (s[i] == s[j] && i != j){
                continue;
            }
            if (i == j && i != n - 1){
                continue;
            }
            swap(s[i], s[j]);
            int cnt = 0;
            s += 'a';
            for (int k = n; k >= 0; k--){
                for (int l = 0; l <= k; l++){
                    if (s[k] == s[l] && k != l){
                        continue;
                    }
                    if (k == l && k != n){
                        continue;
                    }                
                    swap(s[k], s[l]);
                    if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){
                        cnt++;
                        swap(s[k], s[l]);
                        break;
                    }
                    swap(s[k], s[l]);
                }
                if (cnt == 1){
                    break;
                }
            }
            s.pop_back();
            if (cnt == 1){
                s += 'b';
                for (int k = n; k >= 0; k--){
                    for (int l = 0; l <= k; l++){
                        if (s[k] == s[l] && k != l){
                            continue;
                        }
                        if (k == l && k != n){
                            continue;
                        }   
                        swap(s[k], s[l]);
                        if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){
                            return {i, j};
                        }
                        swap(s[k], s[l]);
                    }
                }
                s.pop_back();
            }
            swap(s[i], s[j]);
        }
    }
    return {-1, -1};
}
 
void solve(){
    string t = "";
    while(1){
        char ch;
        cin >> ch;
        if (ch == '0'){
            break;
        }
 
        t += ch;
 
        if (t.size() % 2 == 1){
            auto [l, r] = find_valid_move_odd(t);
            swap(t[l], t[r]);
            cout << l + 1 << ' ' << r + 1 << endl;
        }
        else{
            auto [l, r] = find_valid_move_even(t);
            swap(t[l], t[r]);
            cout << l + 1 << ' ' << r + 1 << endl;
        }
    }
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}

Solution (awoo)

#include <bits/stdc++.h>
using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 
const int N = 100;
 
bool dp[N][N];
pair<int, int> nxt[N][N][2];
bitset<N> cur;
bitset<N> form[N][N];
 
int main(){
	forn(i, N) forn(j, N) dp[i][j] = (i + j) % 2;
	for (int len = 1; len < N; len += 2){
		forn(x, len + 1){
			int y = len - x;
			int nx = x, ny = y;
			int i = 0;
			while (nx > 1 || ny > 1){
				if (nx > 1){
					nx -= 2;
					++i;
				}
				if (ny > 1){
					form[x][y][i] = form[x][y][len - i - 1] = 1;
					ny -= 2;
					++i;
				}
			}
			if (ny > 0){
				form[x][y][i] = 1;
			}
		}
	}
	for (int len = N - 3; len >= 1; len -= 2){
		forn(x, len + 1){
			int y = len - x;
			cur = form[x][y];
			forn(c, 2){
				cur[len] = c;
				bool found = false;
				forn(l, len + 1){
					forn(r, l + 1){
						if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
						bool ok = true;
						forn(d, 2){
							cur[len + 1] = d;
							int nx = x + (c == 0) + (d == 0);
							int ny = y + (c == 1) + (d == 1);
							if ((cur ^ form[nx][ny]).count() > 2){
								ok = false;
								break;
							}
						}
						if (ok){
							found = true;
							nxt[x][y][c] = {l, r};
						}
						if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
						if (found) break;
					}
					if (found) break;
				}
				if (!found){
					dp[x][y] = false;
					break;
				}
			}
		}
	}
	string s;
	cur.reset();
	for (int i = 0;; ++i){
		cin >> s;
		if (s == "0") break;
		int c = s[0] - 'a';
		int py = cur.count(), px = i - py;
		cur[i] = c;
		int nx = px + (c == 0), ny = py + (c == 1);
		int l = -1, r = -1;
		if (i % 2 == 1){
			auto res = nxt[px][py][c];
			if (res.first != res.second){
				l = res.first;
				r = res.second;
			}
		}
		else{
			assert(dp[nx][ny]);
			bitset<N> dif = cur ^ form[nx][ny];
			assert(dif.count() <= 2);
			if (dif.count() == 2){
				l = dif._Find_first();
				r = dif._Find_next(l);
			}
		}
		if (l == -1){
			cout << 0 << " " << 0 << endl;
		}
		else{
			cout << l + 1 << " " << r + 1 << endl;
			if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
		}
	}
}

void solve() { ll n, k, x; cin >> n >> k >> x; vector < int > a(n); REP(i, n) cin >> a[i]; ll sum = accumulate(all(a), 0ll); ll temp = sum; ll ans = 0; for (int i = 0; i < n; i++) { ll cnt = 1; ll val = x - temp; cnt += max(0ll,val / sum); if (val % sum != 0 && val>=0) cnt++; ans += max(0ll, k - cnt + 1); temp -= a[i]; } cout << ans << endl; }

#include <bits/stdc++.h> #define ll long long int #define For(i, N) for(i = 0; i < N; i++) #define FOR(i, K, N) for(i = K; i <= N; ++i) #define v vector #define vl vector<ll> #define vp vector<pair<ll, ll>> using namespace std; void solve() { ll N, K, X; cin >> N >> K >> X; ll i; vl A(N); For(i, N) { cin >> A[i]; } vl suff(N); ll sum = 0; for(i = N-1; i >= 0; i--) { sum += A[i]; suff[i] = sum; } ll ans = 0; For(i, N) { ll num = max(X - suff[i], (ll)0); num = num/sum + (num%sum != 0 ? 1 : 0); ans += max(K-num, (ll)0); } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll T = 1; cin >> T; while(T--) { solve(); } return 0; }

Comments (41)

Show archived | Write comment?

not_insync

13 months ago, hide # |

+27

for E: To prove when Greedy works for the coin problem in O(N ^ 3)

→ Reply

FelixArg

← Rev. 4 →

+15

Before the round, I asked chatGPT to rate the difficulty of the problems, and this is what came out:

A: 800
B: 1700 pog
C: 1200
D: 1900
E: 2100
F: 1600 pog

What do you think?

lequoctran181

13 months ago, hide # ^ |

-9

You mean F instead of G, right? 1600 for the problem is really underestimated, but amazing task there!

Yes, it's F now, we just had another F that we decided to remove

yeetholmes619

D is a very standard problem so I think 1700 would be better.

DespicableFan

D1500

Kavi

3 months ago, hide # ^ |

B can't be 1700 , B required just mathematical observation, & this is how we can do it in 0(n) TC per testcases // code ~~~~~

Spoiler

... ll n,k,x; cin>>n>>k>>x; iv(a,n);

ll sum=0;
    f(i,n) sum+=a[i];

    ll y= (x-1)/sum;
    ll rem=k-y;
    ll suffixsum=y*sum;
    ll extra=0;
    if(rem>=1){
        for(int i=n-1; i>=0 ; i--){
            suffixsum+=a[i];
            if((suffixsum) >=x){
                extra=i+1;
                break;
            }
        }
    }
    rem--;
    ll ans=0;
    if(rem>=1){
        ans+=(n*rem);
    }
    ans+=extra;
    cout<<ans<<nline;

~~~~~

wasif2397

can someone explain the combinatorics part of D in an easier way?

MEDAAA

Let us see another problem How many ways to arrange the word "mississippi"? Now, you have $$$11!$$$ possible permutations. However, there are repeated characters in "miiiisssspp" ,for example, if all similar letters are swapped there is no change. So, you need to put into consideration the frequence of every letter so you need to divide by $$$4!$$$ twice and $$$2!$$$.

Similarly, in our problem after the dp now you can split the string into two parts even and odd since they are independent and the number of ways is as discussed above.

NotAnArtist

Basically , there are dp[odd] ways of constructing the string.

Now if all elements were unique in this construction the number of formations would be dp[odd]! , similarly we can calculate for even as well.

Now we know that all elements are not unique as there are repeated elements as well so we use the formula (n!/k!) which gives us the number of unique formations that are possible.(here k means the number of elements which are repeated) This will result in (odd!*even!)/(freq of each element)!

H_a_r_M_i_t

This is similar to counting the number of distinct permutations of a multiset with $$$n$$$ elements, where:

$$$n_1$$$ elements are of type $$$1$$$, $$$n_2$$$ elements are of type $$$2$$$, $$$\dots$$$, $$$n_k$$$ elements are of type $$$k$$$, and $$$n_1 + n_2 + \cdots + n_k = n$$$.

We choose positions step by step: First, $$$ \binom{n}{n_1} = \frac{n!}{n_1!(n - n_1)!} $$$, then $$$ \binom{n - n_1}{n_2} = \frac{(n - n_1)!}{n_2!(n - n_1 - n_2)!} $$$, and so on.

Multiplying all: $$$ \binom{n}{n_1} \binom{n - n_1}{n_2} \cdots = \frac{n!}{n_1!(n - n_1)!} \cdot \frac{(n - n_1)!}{n_2!(n - n_1 - n_2)!} \cdots $$$

All intermediate factorials cancel out, and we get: $$$ \boxed{\frac{n!}{n_1! n_2! \cdots n_k!}} $$$

Enryue

O(n) solution for B

DonutMaster

My O(N) solution for B:

employed

FelixArg you got any idea which problems gpt o3 mini high solves before proposing the contest , also which problems are they

+21

Yeap, I checked which problems can be solved by o3-mini-high, it turned out that all but F :(

I think it's because in almost all problem statements were highly formalized, and the problems themselves are more educational than in regular div2.

Now GPT is very good at solving problems, and authors have to either mess up statements or put up with it.

I believe that contests are created to enjoy solving problems without help, not to chase high rankings by all available methods, including unfair use of GPT.

028

← Rev. 5 →

Can someone explain why the following approach does not work for E:

Zebra numbers are numbers of the form 111...111 in base 4. This is equivalent to $$$\frac{4^p - 1}{3}$$$ for some $$$p \gt 0$$$. This implies that for a number $$$x$$$ to have a zebra value of $$$k$$$, it is necessary and sufficient that sum of the digits in the base 4 representation of $$$3x + k$$$ must be equal to $$$k$$$. We can set $$$L = 3l + k$$$ and $$$R = 3 r + k$$$. We define our dp to find all numbers less than a number $$$X$$$ which have a zebra value of $$$k$$$ as follows:

$$$dp[pos][sum][tight]=\sum_{i = 0}^{tight?X[pos]:3} dp[pos + 1][sum + i][tight \& [i = X[pos]]]$$$

With

$$$dp[|X|][sum][tight] = [sum = k]$$$

Note that in the implementation, we must be sure that the final digit is zero, as we cannot have $p = 0$ since $$$\frac{4^p - 1}{3}$$$ would be equal to $$$0$$$. Subtracting the dp value for $$$X = L - 1$$$ from $$$X = R$$$ should give the correct result, but it does not. Can anyone point out the flaw in my reasoning?

Tsaminamina

I had the same approach and the flaw here is that you can take each zebra upto 4 times. Eg answer for (4^m-1)/3-1 is 4. So base 4 doesn't quite work. I don't have a fix for this yet.

That makes sense, thanks.

Negationist

Note: D can be solve with meet in the middle, which, while slower for this problem, passes no matter what the constraint on the sum of the number of characters is.

Erering

Isnt the meet in the middle solution

n*26 choose 13 +

n* 26 choose 12 +

n* 26 choose 11 etc which tles?

← Rev. 2 →

Meet in the middle is 2^(n/2), where n is the number of elements (and a log factor if you are lazy though there are many ways to avoid it here tbh, not that it's needed), per test case. So the complexity is O(2^(n/2)t) which is about 2^13*10^4 in the worst case, which is pretty comfortably passing there. Link: https://mirror.codeforces.com/contest/2086/submission/313808229.

Arthis

12 months ago, hide # ^ |

Nice solution! Is applying meet in the middle to no of letters (26) is a common technique? I never thought about that before.

laplace_daemonium

← Rev. 3 →

In problem D we should divide not by the product of the elements of vector c, but by the product of the factorials of the elements of this vector. (In tutorial part. Code solution is ok)

Just add factorials to formulas

Thanks, fixed now

Baraa-Ahmed

+19

I solved D — Even String problem using a different approach.

The key observation is that every character in the string must be placed either in even or odd indices. This allows us to reduce the problem to a standard "pick-or-leave" DP problem.

Let $$$dp[i][j]$$$ represent the number of ways to arrange the last $$$i$$$ characters such that there are $$$j$$$ remaining even indices.

Since each character must be placed entirely in either even or odd positions, we don't need to track the number of remaining odd indices in the state—it's implicitly determined. So, let $$$k$$$ be the number of remaining odd indices.

The transition becomes: $$$dp[i][j] = dp[i + 1][j - c[i]] * C(j, c[i]) + dp[i + 1][j] * C(k, c[i])$$$, where $$$c[i]$$$ is the count of character $$$i$$$ and $$$C(a, b)$$$ denotes "$$$a$$$ choose $$$b$$$". The idea is simple: if we decide to place character $$$i$$$ in the even indices, we have $$$C(j, c[i])$$$ ways to do it using $$$j$$$ available even positions; similarly, if we place it in the odd indices, we have $$$C(k, c[i])$$$ ways using $$$k$$$ odd positions. We multiply these counts with the respective DP values to accumulate the number of valid configurations.

My solution Code

-7

Speedforces handled A, B, C — D tried, but got speedforced too!

Sul_A.

Alternate solution for D:

Let $$$dp(i, j, k)$$$ be the number of strings you can make from the first $$$i$$$ letters if there are $$$j$$$ even positions and $$$k$$$ odd positions. Then:

$$$dp(i, j, k) = dp(i-1, j - c[i], k) \cdot \binom{j}{c[i]} + dp(i-1, j, k - c[i]) \cdot \binom{k}{c[i]}$$$

We can optimize this by realizing that $j+k = c[1] + c[2] + ... + c[i]$. So we can drop the $$$k$$$.

Code: 313882724

Ashar-Usmani

FelixArg the editorial is not attached to the contest problems.

Nogaybica

thanks for the round! perfect problems

There's an easier way to solve problem B. Just use a suffix and see how many "full arrays" you need infront of that suffix so that the sum is larger than or equal to X. Code: https://mirror.codeforces.com/contest/2086/submission/314026288

_ScoobYDOo

Can we solve C using graphs? If YES, then how? Can someone share sol?

WSD33

Yes. I solved C with dsu. I think dsu is also a kind of graph. code

ritchie_s

damn....can you elaborate how did you get to know that you have to solve this via graph ??

Help will be much appreciated !!!

It's a classic trick I have seen.

abcsumits

c: https://www.youtube.com/watch?v=lq7fLWNFfGo&t=5s

Sanae

I want to explain the brute force for F.

In the tutorial of F,it said "however, deriving them manually is quite complicated, as there are many situations."

But I consider this problem as a perfect chance to practice case work:

Do the first three letters by case work.

First, whether $$$s_1$$$ is 'a' or 'b' doesn't matter.

We can just record the longest 'ababab' prefix and the value of $$$s_{mid}$$$ ,and do case work. Do two letters $$$x,y$$$ once.

p=1; p is odd number ;p is even number
$$$s_1=s_{mid}$$$,$$$s_1\neq s_{mid}$$$
$$$p=mid-1$$$,$$$p\neq mid-1$$$
$$$x=a$$$,$$$x=b$$$
$$$y=a$$$,$$$y=b$$$

In the $$$p=1$$$,we don't care $$$p=mid-1$$$.

As in the code,there is $$$2\times 2 \times 2+2\times 2\times 2\times 2\times 2=40$$$ cases,handle them one by one and get c++ code in 15kb.

I highly recommend you to read code, and I'm glad you to find my mistakes.

lightmon

12 months ago, hide # |

Cannot understand why If the greedy algorithm works for all numbers less than y , then in the decomposition of the number y , there must be at least one number zi−1 .

BledDest

Suppose the greedy algorithm works for all numbers less than $$$y$$$, but not for $$$y$$$. Then, the partition of $$$y$$$ should start with some number $$$z_j$$$ such that $$$j \lt i$$$. If $$$j = i-1$$$, case closed.

Otherwise, the partition of $$$y$$$ consists of the number $$$z_j$$$ and the partition of $$$(y - z_j)$$$ such that $$$z_j \le z_{i-2}$$$. Since $$$y \ge z_i$$$, it means that $$$y - z_j \ge z_{i-1}$$$. So, the greedy partition of $$$(y-z_j)$$$, which is optimal by our assumption, starts with either $$$z_i$$$ (then $$$y$$$ can also be greedily partitioned) or $$$z_{i-1}$$$ (then $$$z_{i-1}$$$ is included in the optimal partition of $$$y$$$).

Henry2

8 months ago, hide # |

I had a problem in the Problem F.

How to prove that we could add two characters in any cases, when I could not find the general cases by my hand. In other words, why could brute-force find the method necessarily?

sushant4599

5 months ago, hide # |

Problem D, could also be solved using MEET-IN-THE-MIDDLE, with a TC = $$$O(2^{14} + n/2 )$$$
As, we can brute force on first 13 characters, within reasonable time constraints, then we are left with just some standard MITM algo. implementation, where we take "i" even from first set and find the complementary part from the other, and apply the combinatorial formula, and add it to our answer.

Here's my code : submission

harshXshinchan

3 months ago, hide # |

Why in the second problem author have taken r = n*k fixed, can't it change for some other x where a subarray from between the b array be selected?

FelixArg's blog