Educational Codeforces Round 180 |

index

Problem A

Observation

If $x \le a \le y$ or $y \le a \le x$ , then Bob might lose, because the prize could show up on the “opposite side” of Alice. In other words, if both $x$ and $y$ are on the same side of $a$ , then Bob can always win by choosing the side that contains the prize.

That’s the only observation needed. The time complexity is $O(1)$ .

1
void shiina_mashiro() {
2
    int a, b, c; cin >> a >> b >> c;
3
    if(a < b && a < c) {
4
        cout << "Yes" << nl;
5
        return;
6
    }
7
    if(a > b && a > c) {
8
        cout << "Yes" << nl;
9
        return;
10
    }
11
    cout << "No" << nl;
12
}

Problem B

I thought I solved it immediately, so I coded it up in 2 minutes and instantly got WA. This is probably reducible to less cases, but I didn’t think too much.

Observation

If there already exists an $i$ such that $|a_i - a_{i+1}| \leq 1$ , then clearly the answer is 0.
If there is no such $i$ , then we have to make sure the array is not strictly increasing or decreasing. There’s many ways to check this, but I just checked if there exists an $i$ such that $a_i$ is between $a_{i+1}$ and $a_{i+2}$ , or vice versa.
As long as it’s not strictly increasing or decreasing, the answer is 1, because for example $3,2,4$ , we can convert to $3,3$ , i.e. convert to whichever number is sandwiched between the other two.

Time complexity is $O(n)$ .

1
void shiina_mashiro() {
2
    int n; cin >> n;
3
    vector<int> vi(n);
4
    for(int i = 0; i < n; i++) cin >> vi[i];
5

6
    int ok = 0;
7
    for(int i = 0; i < n-1; i++) {
8
        if(abs(vi[i+1]-vi[i]) <= 1) ok = 1;
9
    }
10
    if(ok) {
11
        cout << 0 << nl;
12
        return;
13
    }
14
    int ok2 = 0;
15
    for(int i = 0; i < n-2; i++) {
16
        if(min(vi[i], vi[i+1]) <= vi[i+2] && max(vi[i], vi[i+1]) >= vi[i+2]) ok2 = 1;
17
        if(min(vi[i+1], vi[i+2]) <= vi[i] && max(vi[i+1], vi[i+2]) >= vi[i]) ok2 = 1;
18
    }
19
    if(!ok2) {
20
        cout << -1 << nl;
21
        return;
22
    }
23
    cout << 1 << nl;
24
}

Problem C

Observation

Let’s say Alice pick 3 numbers where $x \leq y \leq z$ . So Bob can try to sabotage and pick $z$ , so we must ensure $x + y > z$ . Otherwise, if $z$ isn’t the largest number in the array, Bob can always pick $\max(A)$ , so also have to ensure $x + y + z > \max(A)$ .

We need to try finding this below $O(n^3)$ , so fix the smallest number $x$ . Then $y$ and $z$ can be found using two pointers.

Time complexity is $O(n^2)$ .

1
void shiina_mashiro() {
2
    int n; cin >> n;
3
    int mx = 0;
4
    vector<int> vi(n);
5
    for(auto&a: vi){
6
        cin >> a;
7
    }
8

9
    int ans = 0;
10
    for(int i = 0; i < n; i++) for(int j = i+1, L = n-1, R = j+1; j < n; j++) {
11
        ckmax(L, j+1);
12
        while(L-1 > j && vi[i] + vi[j] + vi[L-1] > vi[n-1]) {
13
            L--;
14
        }
15
        ckmax(R, j+1);
16
        while(R < n && vi[i] + vi[j] > vi[R]) {
17
            R++;
18
        }
19
        ans += max(0LL, R-L);
20
    }
21
    cout << ans << nl;
22
}

Problem D

I got WA 9 times… on this problem and another 4 times after failing to solve in contest. I think this is a classic “not thinking clearly enough”. It was pretty obvious that if we alternate the direction of the edges, we will get $n-1$ paths.

Originally I thought we need to find a degree 1 vertex and simply flip aim that edge. Idk why but I assumed the tree is rooted, and kept incorrectly counting the number of paths, but you can pretty easily verify that this is a wrong idea.

Then I realized for a degree 2 vertex, you could aim them in the same direction and it would add exactly 1 path, i.e. $u \rightarrow v \rightarrow w$ , but somehow I was stuck in the first idea, so I thought either $u$ or $w$ needed to be degree 1. I couldn’t implement either, so I kept trying some weird ways of rooting the tree.

Observation

Find any degree 2 vertex, and root the tree there. For it’s left and right subtree, alternate the direction of the edges, and make sure their ith layer is flipped compared to the other subtree.

Time complexity is $O(n)$ .

1
void shiina_mashiro() {
2
    int n; cin >> n;
3
    vector<vector<int>> adj(n);
4
    for(int i = 0; i < n-1; i++) {
5
        int u, v; cin >> u >> v;
6
        --u; --v;
7
        adj[u].pb(v);
8
        adj[v].pb(u);
9
    }
10
    if(n==2) {
11
        cout << "No" << nl;
12
        return;
13
    }
14
    int root = -1;
15
    for(int i = 0; i < n; i++) {
16
        if(sz(adj[i]) == 2) {
17
            root = i;
18
            break;
19
        }
20
    }
21
    if(root == -1) {
22
        cout << "No" << nl;
23
        return;
24
    }
25
    vector<pii> ans;
26
    auto dfs = [&](auto &&s, int u, int p, int f) -> void {
27
        if(f&1) ans.pb({u, p});
28
        else ans.pb({p, u});
29
        for(auto&e: adj[u]) if(e != p) {
30
            s(s, e, u, f^1);
31
        }
32
    };
33
    dfs(dfs, adj[root][0], root, 0);
34
    dfs(dfs, adj[root][1], root, 1);
35
    cout << "Yes" << nl;
36
    for(auto &[a, b] : ans) {
37
        cout << a+1 << " " << b+1 << nl;
38
    }
39
}