Разбор Educational Codeforces Round 188

№	Пользователь	Рейтинг
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

№	Пользователь	Вклад
1	Qingyu	157
2	maspy	150
3	Um_nik	145
4	Errichto	139
5	adamant	136
6	maroonrk	134
7	DNR	133
7	nik_exists	133
9	AmShZ	130
10	Dominater069	129

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;             
        cout << s.find("RL") + 2 << endl;
    }
    return 0;
}

2204B - Правый максимум

Идея: fcspartakm

Разбор

Решение (BledDest)

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

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int mx = 0;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] >= mx) ans++;
        mx = max(mx, a[i]);
    }
    cout << ans << "\n";
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

2204C - Источник

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
long long getOne(long long a, long long m)
{
    return m / a;
}
 
long long getTwo(long long a, long long b, long long m)
{
    return m / lcm(a, b);    
}
 
long long getThree(long long a, long long b, long long c, long long m)
{
    return m / lcm(lcm(a, b), c);
}
 
long long get(long long a, long long b, long long c, long long m)
{
    long long c1 = getOne(a, m);
    long long c2 = getTwo(a, b, m) + getTwo(a, c, m);
    long long c3 = getThree(a, b, c, m);
    return (c1 - c2 + c3) * 6 + (c2 - 2 * c3) * 3 + c3 * 2;
}
 
void solve()
{
    long long a, b, c, m;
    cin >> a >> b >> c >> m;                                                                      
    cout << get(a, b, c, m) << " " << get(b, a, c, m) << " " << get(c, a, b, m) << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

2204D - Чередующийся путь

Идея: BledDest

Разбор

Решение (awoo)

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--){
		int n, m;
		cin >> n >> m;
		vector<vector<int>> g(n);
		forn(i, m){
			int v, u;
			cin >> v >> u;
			--v, --u;
			g[v].push_back(u);
			g[u].push_back(v);
		}
		vector<int> clr(n, -1);
		int ans = 0;
		forn(i, n) if (clr[i] == -1){
			queue<int> q;
			q.push(i);
			clr[i] = 0;
			vector<int> cnt(2);
			bool ok = true;
			while (!q.empty()){
				int v = q.front();
				q.pop();
				++cnt[clr[v]];
				for (int u : g[v]){
					if (clr[u] == clr[v])
						ok = false;
					else if (clr[u] == -1){
						clr[u] = clr[v] ^ 1;
						q.push(u);
					}
				}
			}
			if (ok) ans += max(cnt[0], cnt[1]);
		}
		cout << ans << '\n';
	}
	return 0;
}

2204E - Сумма цифр (и опять)

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
int f(int x)
{
    int res = 0;
    while(x != 0)
    {
        res += x % 10;
        x /= 10;
    }
    return res;
}
 
void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    if(n == 1)
    {
        cout << s << "\n";
        return;
    }
    vector<int> cnt(10);
    int sum_digits = 0;
    for(auto x : s) 
    {
        cnt[x - '0']++;
        sum_digits += x - '0';
    }
    for(int x = 1; x <= n * 9; x++)
    {
        int nx = x;
        string sx = to_string(nx);
        while(nx > 9)
        {
            nx = f(nx);
            sx += to_string(nx);    
        }
        //cout << x << " " << sx << endl;               
        vector<int> need_cnt(10);
        int sum_digits_x = 0;
        for(auto y : sx)
        {
            need_cnt[y - '0']++;
            sum_digits_x += y - '0';
        }
        bool can = true;
        for(int i = 0; i <= 9; i++)
            if(need_cnt[i] > cnt[i]) can = false;
        if(sum_digits - sum_digits_x != x)
            can = false;
        if(can)
        {
            string res = "";
            for(int i = 9; i >= 0; i--)
            {
                for(int j = 0; j < cnt[i] - need_cnt[i]; j++)
                    res.push_back(char('0' + i));
            }
            res += sx;
            cout << res << endl;
            return;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

2204F - Сумма дробей

Идея: adedalic

Разбор

Решение (adedalic)

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	fore(i, 0, sz(v)) {
		if(i) out << " ";
		out << v[i];
	}
	return out;
}
 
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
 
const int MOD = 998'244'353;
 
int add(int a, int b) {
	a += b;
	while (a >= MOD)
		a -= MOD;
	while (a < 0)
		a += MOD;
	return a;
}
int mul(int a, int b) {
	return a * 1ll * b % MOD;
}
int binPow(int a, int k) {
	int ans = 1;
	while (k > 0) {
		if (k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}
 
int n, m;
vector<int> a, k;
 
inline bool read() {
	if(!(cin >> n >> m))
		return false;
	a.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	k.resize(m);
	fore (i, 0, m)
		cin >> k[i];
	return true;
}
 
inline void solve() {
	vector<int> lf(n, -1), rg(n, n);
	vector<int> st;
	fore (i, 0, n) {
		while (!st.empty() && a[st.back()] > a[i])
			st.pop_back();
		if (!st.empty())
			lf[i] = st.back();
		st.push_back(i);
	}
	st.clear();
	for (int i = n - 1; i >= 0; i--) {
		while (!st.empty() && a[st.back()] >= a[i])
			st.pop_back();
		if (!st.empty())
			rg[i] = st.back();
		st.push_back(i);
	}
 
	int commonSum = 0;
	vector<int> la(m + 1), lk(m + 1), ra(m + 1), rk(m + 1);
 
	//[l, r)
	auto addSeg = [](vector<int> &pS, int l, int r, int val) {
		pS[l] = add(pS[l], val);
		pS[r] = add(pS[r], -val);
	};
 
	fore (i, 0, n) {
		int cnt = mul(i - lf[i], rg[i] - i);
		int rem = add(mul(i + 1, n - i), -cnt);
		int ia = binPow(a[i], MOD - 2);
		commonSum = add(commonSum, mul(rem, ia));
 
		int p = lower_bound(k.begin(), k.end(), a[i]) - k.begin();
		addSeg(la, 0, p, mul(cnt, ia));
		addSeg(lk, 0, p, mul(cnt, ia));
		addSeg(ra, p, m, cnt);
		addSeg(rk, p, m, mul(cnt, add(2, -a[i])));
	}
	fore (i, 0, m) {
		la[i + 1] = add(la[i + 1], la[i]);
		lk[i + 1] = add(lk[i + 1], lk[i]);
		ra[i + 1] = add(ra[i + 1], ra[i]);
		rk[i + 1] = add(rk[i + 1], rk[i]);
	}
 
	fore (i, 0, m) {
		int ans = commonSum;
		ans = add(ans, mul(add(la[i], ra[i]), k[i]));
		ans = add(ans, add(lk[i], rk[i]));
		cout << ans << '\n';
	}
}
 
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

2204G - Путь на поле

Идея: Roms

Разбор

Решение (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
 
const int K = 301;
 
using mat = vector<vector<int>>;
 
int n, m, mod, k;
 
int add(int x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
 
int mul(int x, int y) {
  return x * 1LL * y % mod;
}
 
unsigned long long aux[K][K];
 
mat mul(mat a, mat b) {
  mat b2(k, vector<int>(k));
  forn(x, k) forn(y, k) b2[x][y] = b[y][x];
  mat c(k, vector<int>(k));
  forn(x, k) forn(y, k) {
    aux[x][y] = 0;
    forn(z, k) {
      aux[x][y] += a[x][z] * 1ll * b2[y][z];
      if((z & 15) == 15)
        aux[x][y] %= mod;
    }
    c[x][y] = aux[x][y] % mod;
  }
  return c;
}
 
mat binpow(mat a, int b) {
  mat c(k, vector<int>(k));
  forn(i, k) c[i][i] = 1;
  while (b) {
    if (b & 1) c = mul(c, a);
    a = mul(a, a);
    b >>= 1;
  }
  return c;
}
 
int main() {
  cin >> n >> m >> mod;
  k = 2 * m + 1;
  mat a(k, vector<int>(k));
  a[k - 1][k - 1] = 1;
  forn(i, m) forn(f, 2) {
    for (int l = f ? 0 : i; l <= i; ++l) {
      for (int r = i; r < m; ++r) {
        a[i * 2 + f][k - 1] = add(a[i * 2 + f][k - 1], 1);
        for (int j = l; j <= r; ++j) {
          a[i * 2 + f][j * 2 + (j == l)] = add(a[i * 2 + f][j * 2 + (j == l)], 1);
        }
      }
    }
  }
  auto res = binpow(a, n);
  cout << res[1][k - 1] << endl;
}

#include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 998244353; int power(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } int inv(int x) { return power(x, MOD - 2); } int32_t main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; vector<int> a(n), k(m); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> k[i]; // Base: sum of sums of all subarrays int c = 0, base = 0; for (int i = 0; i < n; i++) { c = (c + (i + 1) % MOD * inv(a[i]) % MOD) % MOD; base = (base + c) % MOD; } // Monotonic stack to find contribution ranges vector<int> L(n), R(n); stack<int> st; for (int i = 0; i < n; i++) { while (!st.empty() && a[st.top()] > a[i]) st.pop(); L[i] = st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i = n - 1; i >= 0; i--) { while (!st.empty() && a[st.top()] >= a[i]) st.pop(); R[i] = st.empty() ? n : st.top(); st.push(i); } // Count subarrays where each value is minimum map<int, int> freq; for (int i = 0; i < n; i++) { int cnt = (i - L[i]) * (R[i] - i); freq[a[i]] += cnt; } vector<pair<int, int>> res(freq.begin(), freq.end()); int sz = res.size(); // Prefix: processed contribution (denominator → 1 then numerator) vector<int> prefGain(sz); vector<int> prefCount(sz); int sumGain = 0; int sumCount = 0; for (int i = 0; i < sz; i++) { int x = res[i].first; int cnt = res[i].second; int val = ((-(x - 1) % MOD + MOD) % MOD + (x - 1) * inv(x) % MOD) % MOD; sumGain = (sumGain + val * cnt % MOD) % MOD; prefGain[i] = sumGain; sumCount += cnt; prefCount[i] = sumCount; } // Suffix: sum of cnt * inv(x) vector<int> suffInv(sz); int sumInv = 0; for (int i = sz - 1; i >= 0; i--) { int x = res[i].first; int cnt = res[i].second; sumInv = (sumInv + cnt * inv(x) % MOD) % MOD; suffInv[i] = sumInv; } // Total number of subarrays int totalSubarrays = n * (n + 1) / 2; // Process queries for (int qi = 0; qi < m; qi++) { int K = k[qi]; if (K < res[0].first) { // All in k/x case int ans = (base + K % MOD * suffInv[0] % MOD) % MOD; cout << ans << '\n'; } else if (K > res.back().first) { // All fully reduced + numerator int ans = (base + totalSubarrays % MOD * (K % MOD) % MOD + prefGain.back()) % MOD; cout << ans << '\n'; } else { // Binary search split int l = 0, h = sz - 1, idx = 0; while (l <= h) { int mid = (l + h) / 2; if (res[mid].first <= K) { idx = mid; l = mid + 1; } else h = mid - 1; } int leftPart = (prefCount[idx] % MOD) * (K % MOD) % MOD; leftPart = (leftPart + prefGain[idx]) % MOD; int rightPart = 0; if (idx < sz - 1) { rightPart = (K % MOD) * suffInv[idx + 1] % MOD; } int ans = (base + leftPart + rightPart) % MOD; cout << ans << '\n'; } } return 0; }

#include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 998244353; int power(int a, int b) { int res = 1; while (b) { if (b & 1) res = (res * a) % MOD; a = (a * a) % MOD; b >>= 1; } return res; } int inv(int x) { return power(x, MOD - 2); } int32_t main() { ios::sync_with_stdio(false); cin.tie(NULL); int T = 1; //cin >> T; while (T--) { int n, m; cin >> n >> m; vector<int> a(n), k(m); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> k[i]; int c = 0LL, ans = 0LL; for (int i = 0; i < n; i++) { c = (c + (i + 1) * (inv(a[i]) % MOD)) % MOD; ans = (ans + c) % MOD; } vector<int> L(n), R(n); stack<int> st; for (int i = 0; i < n; i++) { while (!st.empty() && a[st.top()] > a[i]) st.pop(); L[i] = st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i = n - 1; i >= 0; i--) { while (!st.empty() && a[st.top()] >= a[i]) st.pop(); R[i] = st.empty() ? n : st.top(); st.push(i); } vector<pair<int,int>> res; map<int,int> mp; for (int i = 0; i < n; i++) { int cnt = (i - L[i]) * (R[i] - i); mp[a[i]] += cnt; } for (auto &p : mp) { res.push_back(p); } //up till heres just finding segments with min = whatever vector<int> pd(res.size()); //prefix gain (decr den to make frac = 1 then increase numerator) c = 0; vector<int> psac(res.size()); //number of subarrays with min<=x int pc = 0; for (int i = 0; i < (int)pd.size(); i++) { c = (c + ((-(res[i].first - 1) + ((res[i].first - 1) * inv(res[i].first) % MOD) + MOD) % MOD) * res[i].second) % MOD; pd[i] = c; pc += res[i].second; psac[i] += pc; } vector<int> sf(res.size()); //(number of subarrays with min = x)*x, suffix c = 0; for (int i = (int)sf.size() - 1; i >= 0; i--) { c = (c + inv(res[i].first) * (res[i].second) % MOD) % MOD; sf[i] = c; } for (int i = 0; i < m; i++) { if (k[i] < res[0].first) { cout << (ans + k[i] * sf[0]) % MOD << '\n'; } else if (k[i] > res.back().first) { cout << (ans + (n * (n + 1) / 2 % MOD) * k[i] % MOD + pd.back()) % MOD << '\n'; } else { int l = 0, h = (int)res.size() - 1; int idx = 0; while (l <= h) { int u = (l + h) / 2; if (res[u].first <= k[i]) { idx = u; l = u + 1; } else h = u - 1; } int f = ( ans + (psac[idx] * k[i] % MOD + pd[idx]) % MOD + ((idx < (int)res.size() - 1) ? (k[i] * sf[idx + 1] % MOD) : 0) ) % MOD; cout << f << '\n'; } } } return 0; }

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

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

adaptatron

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

← Rev. 2 →

+51

I created video editorial for Problem F. Sum of Fractions. I also created a practice contest where you can submit easy version of problem F along with some practice problems on similar ideas.

I added hints for all the problems on CF Step

→ Ответить

actualtsg

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

-7

Wow this editorial comment has more upvotes than the editorial blog itself 👍

shaurya_145a

I appreciate your work, Quite helpful!

OCDA

This is what I need

Munna

Thanks for this div3 contest. Also, the problem statement for problem D was terrible.

+37

derak

Yup! even the statement correction for D was pretty late.

expertaq

+43

for G. 300 * 300 * 300 * 30 is approximately 8.1 * 10^8, which is well beyond 3 * 10^8 operations, why does author set tight limits for matrix expo with 2m + 1 size? m could well have been 100, and m^3logn would have passed without much issues.

Badri41

-6

This problem tested matrix multiplication optimization tricks more unnecessarily or necessarily

doodoodakkadakka

Code

pls help with my solution on F. im trying to calculate gains over the base sum for every k. love you

heres my previous iteration of code. this doesnt even pass the first 20 tc the og comment is what jippity gave me after removing my template so you all could understand

cnt can be as large as $$$O(n^2)$$$ (from $$$(i - L[i]) * (R[i] - i)$$$)

So, val * cnt can overflow before the % MOD. Using $$$cnt \% MOD$$$ before multiplying keeps the product within range and preserves the result, since (val * cnt) % MOD == (val * (cnt % MOD)) % MOD.

Your updated submission now passes TC20, but fails on TC25 (due to the same bug, but in a different place). Hope you can fix it.

and what about the other one it wasnt passing even the first tc lol.

Median_72

Я был так близок к решению С. Просто я вместо того, чтобы посчитать кол-во дней, сразу начал умножать кол-во ягод на результаты деления, и как-то это складывать и вычитать

leetgoat_dot_dev

Thanks for the contest I enjoyed these problems! D and E were my favorites. (solved A-E)

lamducanh2005

B is pretty simple: track a max variable, count how many times it increases -> answer. Stack version works too (push when >= top), size of stack at the end is it ;)

CPP_Programming

the tasks were easier than I thought

Cacodyl

Statement for D could have been much better, but ok.

Serval

+31

Share a more natural solution of G with an $$$(m+1)\times (m+1)$$$ transition matrix.

First, the constraint that $$$(1, 1)$$$ should be covered by segments is equivalent to that of $$$(n, m)$$$ by symmetry. Thus, let $$$dp_{i,l,r}$$$ denote the number of ways to choose segments for the first $$$i$$$ rows where the segment for the $$$i$$$-th row is exactly $$$[l, r]$$$, without considering the constraint of $$$(1,1)$$$. Easy to write out the transition:

$$$ dp_{i,l,r} = 1 + \sum_{[a, b] \cap [l, r] \neq \emptyset} dp_{i-1, a, b} $$$

Note that $$$[a, b] \cap [l, r] = \emptyset$$$ iff either $$$b \lt l$$$ or $$$r \lt a$$$. Let the prefix sum and the suffix sum as

$$$ pre_{i,k} = \sum_{r\leq k} dp_{i,l,r}, \quad suf_{i,k} = \sum_{l\geq k} dp_{i,l,r} $$$

Then

$$$ dp_{i,l,r} = 1 + pre_{i-1,m} - pre_{i-1,l-1} - suf_{i-1,r+1} $$$

Summing up $$$dp$$$ by the definitions of $$$pre$$$ and $$$suf$$$ above gives the transitions between $$$pre_i, suf_i$$$ and $$$pre_{i-1}, suf_{i-1}$$$. Flipping the grid horizontally gives the bijection between ways to choose segments of $$$pre_{i,k}$$$ and that of $$$suf_{i,m-k+1}$$$, showing that they are equal. Thus, only $$$m+1$$$ states ($$$pre$$$ and a constant $$$1$$$) should be maintained. The final answer is $$$pre_{n,m} - pre_{n,m-1}$$$.

a_frog_named_yossy

← Rev. 6 →

~~I think G can be solved for $$$M\leq800$$$ . Not recommended.~~ (It seems like the solution above doesn't work for small modulos or non-prime modulos, so if only matrix multiplication is allowed, then $$$M\leq 500$$$ is doable.)

Also, what is the exact reason for the fact that BM doesn't work? What's the time complexity of BM?

Edit: the fastest solutions uses the Reed-Sloane algorithm (BM's extension to non-prime modulos). I guess the time complexity is $$$O(n^3)$$$ or simmilar.

YF_YUSUF

+13

Можно его ускорить следующим образом: давайте при перемножении матриц брать по модулю как можно реже

Почему просто ограничения на m не сделать меньше?

AksLolCoding

+11

Optimizations to E solution

I might argue that max suffix sum of digit is at most 70, not 71 because sum of digit = 999999 is not reachable from given problem constraint, so sum of digit 888889 is the worst case here with sum of suffix digit equal to 70: (8+8+8+8+8+9) + (4+9) + (1+3) + (4) = 70

My submisson checking only 71 possiblities without any precompute: 367072645 (62 ms)

And yes, in practice precompute is a bit slower than brute force in this case, I also has another submission that precompute all possible sum of digit too, and the result it's a bit slower (it uses >110 MB of memory): 367056743 (93 ms)

Maybe because my language is pure C (without plus-plus) so my runtime is faster than yours even with the same algorithm x)

AntennaeVY

10 дней назад, скрыть # ^ |

How do you know that in practice it's actually just $$$4!$$$ ?

perkybeep

how to find rating of ques?

https://clist.by

Find_it_out

I'm trying to understand problem G. If we run the code from the solution for m = 2, we get the matrix:

0 2 1 0 2

0 0 0 1 1

0 1 1 1 2

0 0 0 0 1

But I can't figure out why [1:1] is 2 and not 4. From state j=0 f=1 (these are 10 and 11 ), there are transitions: 10: 10, 11 11 : 10, 11 At j = 0, f=1. What am I missing?

well done

for Problem E ,there is a answer check for whitespace in the end of line.

ie '134 ' != '134' .. this caused me WA while practicing

I have rarely seen it on codeforces because my template always printed it, so I want to mention here

jhdfarrell_

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

in the tutorial of G: "that is, if the segments in adjacent rows are $$$[l_1,r_1]$$$ and $$$[l_2,r_2]$$$, we can only transition between them in column $$$j=min(l_1,l_2)$$$"

shouldn't this be $$$j=max(l_1,l_2)$$$?

ItayKarny

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

yap

34z12000

Hi! I've been trying to submit F on python lately and many times I faced TLE on test 25. I've tried to optimise it in different ways but still got TLE. From what I've gathered the only things that could possibly slow down my solution are sort and exponentiation modulo, but I'm more biased towards the second option. I'm a bit curious as why these things could possibly affect complexity so much?

VERITVS

← Rev. 3 →

For D, I think the problem should be phrased as “Call a vertex v beautiful if all not-necessarily-simple paths in original graph that start at v and that still exist after determining directions of each edge, are alternating in the resulting directed graph.” Because a path in original (undirected) graph could be a->b->a when there is only one edge (a,b). Then, no matter how you choose direction of (a,b), the path a->b->a will be missing an edge, and hence the path becomes invalid. But the problem doesn’t say how an invalid-after-direction path should affect the beauty of the vertices involved. I suppose one can figure out the intended meaning by studying examples, but still it confused me at first. Correct me if I’m missing something.

UPD: I understood the problem now and there is nothing wrong with the phrasing.

TLE_Breaker

Hello,

I would like to clarify that I did not copy or share my solution with anyone during the contest.

For problem 2204D, I solved it by modeling the problem as a bipartite graph check. I used a standard BFS/DFS-based coloring approach, where each node is assigned one of two colors and adjacent nodes are checked for conflicts.

Since bipartite checking is a very common and standard technique, I believe it is possible for independently written solutions to look very similar in structure and implementation.

My solution was written independently during the contest, and I did not use any external sources or public code-sharing platforms.

Please let me know if any further clarification is required.

Thank you.

[submission:2204D]

ipanforever

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

i think d bad and e veyyyyy good it dont said the breautiful v must has outdegree i just think all vertices in the connected components in a bipartite graph are breautiful the problem statement feels overly contrived and disconnected from the core algorithm, which is frustrating but the problem itself is well-designed! :)

DNR

Alternate solution for G:

The $$$r$$$-th row can be characterized by $$$2 \cdot m + 2$$$ variables, namely:

$$$x_r$$$ = total number of ways to arrive at this row with any segment.
$$$y_r = \sum_{q \leq r}{x_q}$$$ = total number of ways to arrive at some row till $$$r$$$. Note that the final answer is equal to $$$y_n$$$.
$$$p_{r, i}$$$ = number of ways to arrive at row $$$r$$$ with a segment that starts at $$$i$$$ ($$$1 \leq i \leq m$$$).
$$$s_{r, i}$$$ = number of ways to arrive at row $$$r$$$ with a segment that ends at $$$i$$$ ($$$1 \leq i \leq m$$$).

For the $$$r$$$-th row, all of these $$$(2 \cdot m + 2)$$$ variables can be expressed as linear combinations of the analogous $$$(2 \cdot m + 2)$$$ variables for row $$$(r - 1)$$$.

$$$p_{r, i} = (m - i + 1) \cdot x_{r - 1} + \sum_{1 \leq j \leq m} f(j)$$$ where $$$f(j) = (- (m - i + 1)) \cdot s_{r - 1, j}$$$ if $$$j \lt i$$$ and $$$f(j) = (-(j - i))\cdot p_{r - 1, j}$$$ for $$$j \geq i$$$.
$$$s_{r, i} = i \cdot x_{r - 1} + \sum_{1 \leq j \leq m} f(j)$$$ where $$$f(j) = (- (i - j)) \cdot s_{r - 1, j}$$$ if $$$j \leq i$$$ and $$$f(j) = (-i)\cdot p_{r - 1, j}$$$ for $$$j \gt i$$$.
$$$x_r = \sum{p_{r, i}}$$$
$$$y_r = y_{r - 1} + x_r$$$

And then we just plug this into a decent matrix multiplication implementation. We can reduce the number of variables to $$$m + 2$$$ but $$$2 \cdot m + 2$$$ passes.

milansuresh

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

The editorial for Spring was very well-written. Thank you, BledDest!

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