Home Archive Trending Tags Category Friends About Me
KarL05/Aiyiyi's Blog
Blog
Tony Wu
Archive Trending Tags Category Friends About Me
Proudly published with Hexo
Theme Journal. by Makito
© 2025 KarL05/Aiyiyi's Blog
Codeforces Global Round 28
  folder 笔记Notes label 信竞OI

Codeforces Global Round 28 Notes

A. Kevin and Combination Lock

Op 1 is more difficult so try to relate Op 1 with Op 2. After Op 1 the number is still the same mod 11 and mod 3, so Op 1 is just doing Op 2 multiple times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#ifdef DEBUG
#include"bits/dbg.h"
#else
#define dbg(...)
#endif

#include"bits/stdc++.h"
#define int long long
#define P pair<int,int>
#define x first
#define y second
using namespace std;

void solve () {
    int n; cin >> n;
    if (n%33 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

B. Kevin and Permutation

Try to place a "1" that affect the most subarrays. This can be done by placing "1" at position \(k\). Then do this process recursively, that is, try to place a "2" that affect the most subarrays. So "2" should be placed at position \(2k\). This process continues.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#ifdef DEBUG
#include"bits/dbg.h"
#else
#define dbg(...)
#endif

#include"bits/stdc++.h"
#define int long long
#define P pair<int,int>
#define fi first
#define se second
using namespace std;

const int maxn = 1e5+5;

void solve () {
    int n, k;
    cin >> n >> k;
    int R = n;
    int L = 1;
    for (int i=1;i<=n;i++) {
        if (i%k == 0) cout << L++ << " ";
        else cout << R-- << " ";
    }
    cout << endl;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

C Kevin and Binary Strings

It's important to note that \(n \leq 5000\). Observe that the length of \(x\) and \(y\) should be long in \(x \oplus y\) to have the minimum number of leading zeros. WLOG, should \(x\) just be \(s\)? Well just let \(y\) to be the smallest possible string, then clearly \(x \oplus y\) has the same length as \(s\), and this cannot be done by choosing any shorter \(x\)s, so \(x = s\).

For \(y\), we just have to iterate through all the possible substrings, but checking is quite hard and even if possible will take time complexity like \(O(n^3)\). What I did is that I considered \(t = s \oplus (2^{\inf}-1)\). We try to find a substring of \(s\) that matches the suffix of \(t\). When clearly its not really possible but we can still match the first few characters of the suffix of \(t\).

So I considered substrings of \(s\) starting from a specific character. Up to a certain point, the answer grows, then the answer decreases. We just have to find this changing point, which is just the next different character. A bit more formally find the next position in \(t\) such that its different from the current character. The length of the substring is the same as the length of the suffix of \(t\) from that point, and its optimal because its the best match for \(t\).

Then we only have \(n\) strings, just sort.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#ifdef DEBUG
#include"bits/dbg.h"
#else
#define dbg(...)
#endif

#include"bits/stdc++.h"
#define int long long
#define P pair<int,int>
#define fi first
#define se second
using namespace std;

vector<pair<string, P>> v;

void solve () {
    v.clear();
    string s; cin >> s;
    int n = s.size();
    s = "#"+s;
    int p0 = -1;
    int p1 = -1;
    string sp = s;
    sp[1] = '0';
    v.push_back({sp, {1, 1}});
    for (int i=n;i>=1;i--) {
        if (s[i] == '0') {
            if (p1 == -1) {
                p0 = i;
                continue;
            }
            string t = s;
            for (int j=p1;j<=n;j++) {
                if (s[j] == s[j-p1+i]) t[j] = '0';
                else t[j] = '1';
            }
            v.push_back({t, {i, n-p1+i}});
            p0 = i;
        }
        if (s[i] == '1') {
            if (p0 == -1) {
                p1 = i;
                continue;
            }
            string t = s;
            for (int j=p0;j<=n;j++) {
                if (s[j] == s[j-p0+i]) t[j] = '0';
                else t[j] = '1';
            }
            v.push_back({t, {i, n-p0+i}});
            p1 = i;
        }
    }
    sort(v.begin(),v.end());
    P ans = v.back().second;
    cout << 1 << " " << n << " " << ans.fi << " " << ans.se << endl;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

D Kevin and Competition Memories

Start with small \(k\)s. I find out that the \(b_i\) that is just larger than Kevin is clearly the worst problem. Because almost everyone knows how to solve except Kevin. More generally speaking, only the problem that is just larger than Kevin's rating matters.

Consider the case where we give up no problems, that the worst problem must be selected and contribute to the final answer. Now, since in this problem set only the worst problem matters, just take the next few worse problems.

Now let's go back to the case where we can give up problems, sort the problems in ascending rating and give up the problems from the problem that is just larger than Kevin's rating. Then group the problems in this way: let say group size is \(k\). Sort the problem in how bad the problem is (how many people knew to solve except Kevin), if Kevin can solve, then = 0. Choose 1...k, k+1 .... 2k and etc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#ifdef DEBUG
#include"bits/dbg.h"
#else
#define dbg(...)
#endif

#include"bits/stdc++.h"
#define int long long
#define P pair<int,int>
#define fi first
#define se second
using namespace std;

const int maxn = 3e5+5;
int a[maxn];
int b[maxn];
int v[maxn];
int kevin;
int n, m;

void solve () {
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=m;i++) cin >> b[i];
    kevin = a[1];
    sort(a+1, a+n+1);
    sort(b+1, b+m+1);
    for (int i=1;i<=m;i++) {
        v[i] = lower_bound(a+1, a+n+1, b[i])-a-1;
        v[i] = n-v[i];
        if (b[i] <= kevin) v[i] = 0;
    }
    dbg(v);
    int pos = upper_bound(b+1, b+m+1, kevin)-b;
    dbg(b[pos]);
    for (int k=1;k<=m;k++) {
        int ans = m/k;
        int x = m-m/k*k;
        for (int i=pos+x;i<=m;i+=k) {
            ans += v[i];
        }
        cout << ans << " ";
    }
    cout << endl;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

E Kevin and Bipartite Graph

Nothing much I can do except for guessing the answer. I guessed \(n \leq m\), but doesn't work. I guessed \(2n \leq m\), but doesn't work because \(n = 2\), \(m = 4\) is a counter example. So logically try \(n = 2\) and \(m = 3\) and yes there is a solution by just creating 2 zig zags.

1
2
3
4
Left side = 1,2,3,4
Right side = 1,2,3
Color 1: R1->12 R2->23 R3->34 
Color 2: R1->34 R2->41 R3->12

Just follow this construction so basically:

1
2
3
Color 1: 12 23 34 45 56 .....
Color 2: 34 45 56 67 78 .....
Color 3: 45 56 67 78 89 .....

Clearly each color has no loops. This problem is really confusing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#ifdef DEBUG
#include"bits/dbg.h"
#else
#define dbg(...)
#endif

#include"bits/stdc++.h"
#define int long long
#define P pair<int,int>
#define fi first
#define se second
using namespace std;

const int maxn = 2005;
int E[maxn][maxn];

void solve () {
    int n, m;
    cin >> n >> m;
    if (m >= n+n) {
        cout << "NO" << endl;
    }
    else {
        cout << "YES" << endl;
        for (int i=1;i<=m;i++) {
            int col = 0;
            for (int j=0;j<n+n;j+=2) {
                col++;
                int id1 = (i+j)%(n+n)+1;
                int id2 = (i+j+1)%(n+n)+1;
                E[id1][i] = col;
                E[id2][i] = col;
            }
        }
        for (int i=1;i<=n+n;i++) {
            for (int j=1;j<=m;j++) {
                cout << E[i][j] << " ";
            }
            cout << endl;
        }
    }
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

F Kevin and Math Class

This is quite a good problem. At first I tried to analyze array \(a\) but nothing worked. I just observed that only the maximum value matter. Also, I observed that the answer is at most \(70\). But not very useful. Then I tried to analysis the ceiling function at its still doesn't work well because even if I change the ceiling function to pure division I still can't solve.

So the only thing left that I can do something on is \(b\) and I realized that quite lately. I think there are some "optimal" ranges that are just better than some other ranges. I can't really characterize this, but I think there are only \(O(n)\) of them instead of \(O(n^2)\) which is easier to deal with. Then I observe that the optimal ranges never intersect. This reminded me of cartesian tree. Then the problem is just DP on the cartesian tree.

Some important stuff to store during DP: maximum number in the range, number of operation, and index. Well maximum number is \(1e18\) size so cannot be the index, and recall that answer is at most \(70\), now DP is natural.

Well I think this problem should be optimized to \((n\log n)\) by some sort of binary search because the min-max convolution clearly only has \(O(n)\) meaningful operations. But I don't really know how to implement so I kept optimizing and eventually made it through will some interesting optimizations with two logs.

Luckily I forgot how to write cartesian tree but I remember segment tree so I did that.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#ifdef DEBUG
#include"bits/dbg.h"
#else
#define dbg(...)
#endif

#include"bits/stdc++.h"
#define int long long
#define P pair<int,int>
#define fi first
#define se second
using namespace std;

const int maxn = 2e5+5;
const int maxc = 64;
int a[maxn];
int b[maxn];
int n;
int L[maxn];
int R[maxn];

int read () { 
	int x = 0;
	char c = getchar();
	while (c<'0'||c>'9') {
		c = getchar();
	}
	while (c>='0'&&c<='9') {
		x = x*10+c-'0';
		c = getchar();
	}
	return x;
}


struct node {
    int l;
    int r;
    P v;
};
node t[4*maxn];

void pushup (int p) {
    t[p].v = min(t[p+p].v, t[p+p+1].v);
}

void build (int p, int l, int r) {
    t[p].l = l;
    t[p].r = r;
    if (l == r) {
        t[p].v = {b[l], l};
        return;
    }
    int mid = (l+r)/2;
    build(p+p, l, mid);
    build(p+p+1, mid+1, r);
    pushup(p);
}

P query (int p, int ql, int qr) {
    if (ql <= t[p].l && t[p].r <= qr) {
        return t[p].v;
    }
    int mid = (t[p].l+t[p].r)/2;
    P ans = {1e18, -1};
    if (ql <= mid) ans = min(ans, query(p+p, ql, qr));
    if (mid < qr) ans = min(ans, query(p+p+1, ql, qr));
    return ans;
}

void catesian (int l, int r) {
    int p = query(1, l, r).se;
    if (l <= p-1) {
        L[p] = query(1, l, p-1).se;
        catesian(l, p-1);
    }
    if (p+1 <= r) {
        R[p] = query(1, p+1, r).se;
        catesian(p+1, r);
    }
}

int dp[maxn][maxc+1];

int c (int x, int y) {
    return x/y + (x%y != 0);
}


void DFS (int u) {
    if (L[u]) DFS(L[u]);
    if (R[u]) DFS(R[u]);
    for (int i=0;i<=maxc;i++) {
        dp[u][i] = 1e18;
    }
    for (int i=0;i<=maxc;i++) {
        for (int j=0;i+j<=maxc;j++) {
            dp[u][i+j] = min(dp[u][i+j], max({dp[L[u]][i], dp[R[u]][j], a[u]}));
            if (!dp[R[u]][j]) break;
            if (dp[R[u]][j] < dp[L[u]][i]) break;
        }
        if (!dp[L[u]][i]) break;
    }
    for (int i=1;i<=maxc;i++) {
        dp[u][i] = min(dp[u][i], c(dp[u][i-1], b[u]));
    }
} 

void solve () {
    n = read();
    for (int i=1;i<=n;i++) a[i] = read();
    for (int i=1;i<=n;i++) {
        L[i] = R[i] = 0;
        b[i] = read();
    }
    build(1, 1, n);
    catesian(1, n);
    int rt = query(1, 1, n).se;
    DFS(rt);
    for (int i=0;i<=maxc;i++) {
        if (dp[rt][i] == 1) {
            printf("%lld\n", i);
            return;
        }
    }
}

signed main () {
    int t = read();
    while (t--) solve();
}

G Kevin and Matrices

This problem is quite hard. I didn't make much progress initially so I start with cases like 1xn, 2x2, 2xn, etc. For the 1xn case, it's always true. For the 2xn case, let row 1 be \(a\) and row 2 be \(b\). Equation can be simplified to \(\min(\max a, \max b)\). WLOG, let \(\max a \leq \max b\). Observe that RHS \(\leq \max a\), because each column is compared against an element of \(a\) that is at most \(\max a\). So we eventually realize that LHS \(\geq\) RHS. This can be extended to a more general case. Key Observation: LHS = RHS.

Now lets fix \(A\), where A = LHS = RHS, and fix the position of A (lets say there is only this single A that satisfy the equation for simplicity). We have to put [1...A] in the row and [A...v] in the column. The other vacant positions can be placed arbitrarily.

Now consider the case with multiple \(A\)s that is row maximum and col minimum (lets call this kind of \(A\) a key \(A\)). Draw out these rows and cols, and observe that the intersection of these rows and cols are also key \(A\)s. Basically the key \(A\)s form a submatrix. Now we can see that this is similar to inclusion-exclusion, where we can easily find things \(\geq\) something and its crucial to remove repeats.

So fix \(r\), rows for this sub-matrix, and fix \(c\), cols, and fix \(A\). Do some math and apply in-ex. The issue is that the in-ex coefficient is hard to decide. \((-1)^{rc}\) doesn't make sense because for example in the 2x2 case matrix (2,2)(2,2) is {1x1}4-{1x2}4+{2x2}1, coefficient for {2x2} is 1. So I guessed its \((-1)^{r+c}\).

I thought of it for a while and don't understand why it works. Now I think its just doing two in-ex separately on two dimensions, resulting a factor of \((-1)^{r+1}(-1)^{c+1}\), which is in the desired form.

And I did some math and I solved it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#ifdef DEBUG
#include"bits/dbg.h"
#else
#define dbg(...)
#endif

#include"bits/stdc++.h"
#define int long long
#define P pair<int,int>
#define x first
#define y second
using namespace std;

int n, m, v;
const int maxn = 1e6+5;
const int MOD = 998244353;
int fac[maxn];

int qpow (int a, int b) {
    int ans = 1;
    if (b == 0) return 1;
    while (b) {
        if (b&1) ans = a*ans%MOD;
        a = a*a%MOD;
        b = b>>1;
    }
    return ans%MOD;
}

int inv (int x) {
    return qpow(x, MOD-2);
}

void solve () {
    cin >> n >> m >> v;
    int ans = 0;
    for (int r=1;r<=n;r++) {
        for (int A=1;A<=v;A++) {
            int c0 = (qpow(-1, r)+MOD)%MOD;
            int c1 = (fac[n]*inv(fac[r])%MOD)*inv(fac[n-r])%MOD;
            int c2 = qpow(inv(v)*A%MOD, r*m);
            int c3 = qpow((v-A+1)*inv(v)%MOD, n-r)*qpow(inv(A), r)%MOD;
            int c4 = (qpow(1-c3+MOD, m)-1+MOD)%MOD;
            int prod = 1;
            prod *= c0; prod %= MOD;
            prod *= c1; prod %= MOD;
            prod *= c2; prod %= MOD;
            prod *= c4; prod %= MOD;
            ans += prod; ans %= MOD;
        }
    }
    ans *= qpow(v, n*m); ans %= MOD;
    cout << ans << endl;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    fac[0] = 1;
    for (int i=1;i<maxn;i++) fac[i] = fac[i-1]*i%MOD;
    int t; cin >> t;
    while (t--) solve();
}
Proudly published with Hexo
Theme Journal. by Makito
© 2025 KarL05/Aiyiyi's Blog