Разбор Educational Codeforces Round 177

Спасибо за участие! Надеюсь задачи вам понравились.

2086A - Варенье из морошки

Разбор

Решение(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 - Большой массив и отрезки

Идея: FelixArg

Разбор

Решение(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 - Исчезающая перестановка

Идея: FelixArg

Разбор

Решение(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 - Четная строка

Идея: FelixArg

Разбор

Решение(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 - Зебристость чисел

Идея: FelixArg

Разбор

Решение(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();
	}
}

Решение(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 - Онлайн палиндром

Идея: Valentin_E

Разбор

Решение(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();
}

Решение(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; }

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

Показать архивные | Написать комментарий?

not_insync

18 месяцев назад, скрыть # |

+27

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

→ Ответить

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

18 месяцев назад, скрыть # ^ |

-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

17 месяцев назад, скрыть # ^ |

D1500

Kavi

8 месяцев назад, скрыть # ^ |

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://codeforces.me/contest/2086/submission/313808229.

Arthis

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 solution for B. Just use a suffix and calculate how many "full arrays" you need infront of that suffix so that the the sum is larger than or equal to X. Code: https://codeforces.me/contest/2086/submission/314026288

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://codeforces.me/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

17 месяцев назад, скрыть # |

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$$$).

sushant4599

10 месяцев назад, скрыть # |

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

8 месяцев назад, скрыть # |

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?

__masao__

3 месяца назад, скрыть # |

My approach for problem D:

so let's say we have a grp of similar character with size x > 1 then all these characters will be on the even indices or odd indices(all of them) , so what we can do is we can handle odd and even indices seperatly so the permutations of the odd side are (fact[(n+1)/2]/(x)) , where x is the product of factorials of group size for each character at odd position , and indeed we can find similar for the even indices which is (fact[n/2])/(y), where y has the similar meaning to x but for the even indices , now the answer for the problem will be (odd_part*even_part)*(cnt), and also rememver that we are doing everything under modulo so there may be inverse also,

now let's talk about the "cnt" that i have written , cnt refers to the number of exchanges that you can do between the odd and even indices , say there is a group of size 4 on odd side and there are two groups of size 2 on the even side then you can simply exchange them between odd and even part, so now how do we calculate cnt?, basically it is the same as counting the subsequences that have sum n/2, because all the c_i's at even positions have a sum equal to n/2, so we can count the number of subsequences in O(2^(26)) , ik TLE is waiting for me because test case <= 1e4....

I just want to know whether this approach is correct or not??

Here is my code

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

#define int long long
#define all(v) v.begin(),v.end()
#define sz(x) (int)x.size()
#define INF LLONG_MAX



int M = 998244353;

vector<int> fact((int)5e5+1);

int subs_cnt(int idx,int sum,int target,vector<int> &c){
    if(sum > target) return 0;

    if(idx == sz(c)){
        if(sum == target) return 1;
        return 0;
    }

    sum += c[idx];
    int take = subs_cnt(idx+1,sum,target,c);
    sum -= c[idx];
    int notTake = subs_cnt(idx+1,sum,target,c);

    return take+notTake;
}

int modInverse(int x,int n){
   int res = 1;
   while(n > 0){
    if(n%2 == 1){
        res = (res*(x%M))%M;
    }

    x = ((x%M)*(x%M))%M;
    n /=2;
   }

   return res;
}

void solve() {
    vector<int> freq(26);
    vector<int> c;
    int x = 1;

    int mex = 0;

    for(int i = 0;i<26;i++){
        cin >> freq[i];
        x = x*fact[freq[i]]%M;
        mex = max(mex,2*(freq[i]-1)+1);
        if(freq[i] != 0){
            c.push_back(freq[i]);
        }
    }


    int n = accumulate(all(freq),0LL);

    if(n == 0){
        cout<<0<<"\n";
        return;
    }

    if(mex > n){
        cout<<0<<"\n";
        return;
    }

    //count the number of subsequences whose sum is n/2
    int cnt = subs_cnt(0,0,n/2,c);

    int ans = ((fact[(n+1)/2]*fact[n/2]%M)*(modInverse(x,M-2)%M)*cnt%M)%M;

    cout<<ans<<"\n";
}

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

    fact[0] = 1;
    fact[1] = 1;

    for(int i = 2;i<=(int)5e5;i++){
        fact[i] = i*fact[i-1]%M;
    }

    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

№	Пользователь	Рейтинг
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

№	Пользователь	Вклад
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	143
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	maroonrk	133
9	BledDest	132
10	qwexd	129

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