CodeCraft-21 and Codeforces Round #711 (Div. 2) Editorial

Revision en1, by ninja_28, 2021-03-29 19:49:16

Problem A: GCD Sum

Author and Problemsetting: ninja_28
Editorialist: sigma_g

Hint
Hint 2
Hint 3
Solution
Corner cases
C++ solution

<div>5e5ad99cb69bd5a839e7de122f59bb49</div>

Problem B: Box Fitting

Author and Editorialist: sigma_g
Problemsetting: ninja_28

Hint
Hint 2
Solution summary
Solution implementation
Another implementation
Proof of correctness - brief
Proof of correctness - elaborate
Does this solution work when block widths are not a power of two?
C++ solution
Python solution
C++ solution - multiset
Problem C: Planar Reflections
==================

Author, Problemsetter and Editorialist: [user:sigma_g]

<div>f5e0f3e29b507a13ab347e5872f4a15c</div>

<div>d3b56d8d6cfbbbf430badad4fb6f7432</div>

<div>2223acefbe47c2045fd62c4eab3fc20c</div>

<div>c0e480b6a8cabab5a568de366018e592</div>

<div>185601b585c2277719599830636911f1</div>

<div>415ecf8c07909e0d5a3f421f46f47a2d</div>

<div>b7ae2add88fed52ad7c2ec752856e2a7</div>

Problem D: Bananas in a Microwave

Author: shash42 Problemsetting and Editorialist: sigma_g

Brute force solution
Optimizing the brute force: hint
Optimizing the brute force: hint 2
Optimizing the brute force: details
Optimized solution implementation
Common mistakes

C++ solution

include

include

using namespace std; using LL = long long;

const int DIV = 1e5;

inline LL ceil(LL x, LL y) { return (x + y — 1) / y; }

int main() { int T, M; cin >> T >> M;

vector<bool> is_seen(M + 1, false);
is_seen[0] = true;
vector<int> answer(M + 1, -1);
answer[0] = 0;

for (int timestep = 1; timestep <= T; timestep++) {
    auto new_is_seen = is_seen;

    int t, y;
    LL x;
    cin >> t >> x >> y;

    auto operation = [&](long long &curr) {
        if (t == 1) {
            curr = curr + ceil(x, DIV);
        } else {
            curr = ceil(curr * x, DIV);
        }
    };

    for (int k = 0; k <= M; k++) {
        if (is_seen[k]) {
            long long curr = k;
            operation(curr);

            for (int a = 1; a <= y;) {
                if (curr > M) break;
                if (is_seen[curr]) break;

                new_is_seen[curr] = true;
                answer[curr] = timestep;

                a++;
                operation(curr);
            }
        }
    }

    is_seen = new_is_seen;
}

for (int i = 1; i <= M; i++)
    cout << answer[i] << " ";

cout << endl;

}

</spolier>

<spoiler summary="Python solution">
</spolier>

Problem E: Two Houses

Author: dixitgarg Problemsetting and Editorialist: dixitgarg

In this problem we have to output two nodes $$$a$$$ and $$$b$$$ such that there is a path from $$$a$$$ to $$$b$$$ and $$$b$$$ to $$$a$$$ and the absolute value of the difference of the indegree $$$(|k_a - k_b|)$$$ should be maximum. First of all let us think of bireachability only i.e how to find two nodes $$$a$$$ and $$$b$$$ such that they are both reachable from each other? How can we verify this from the judge? Because if we ask $$$"? \ a \ b"$$$ i.e whether there is a path from $$$a$$$ to $$$b$$$ or not, then if the judge answers "Yes", we can't ask further queries. So we have to ask queries for those pairs $$$(a,b)$$$ for which we are sure that there is a path from $$$b$$$ to $$$a$$$. So how to ensure whether there is a path from $$$b$$$ to $$$a$$$ or not?

The answer lies in the fact that the given graph is not an ordinary graph, it is a special one. For every pair of vertices in this graph, there is a directed edge. So this type of graph has some interesting properties which we are going to see now.

Image how the compressed SCC of the graph will look like. For every pair of nodes of compressed SCC, there will be an edge, so it will have exactly one source, one sink and there would be only one possible topological sorting of this compressed SCC.

Proof of unique topological sorting

Since there is an edge between every pair of nodes, for every pair of nodes in the compresses SCC also, there would be an edge. And we know that if there is an edge between node $$$a$$$ to node $$$b$$$, then node $$$a$$$ comes before node $$$b$$$ in the topological sort. So for every pair of nodes of compressed SCC, we know which node would come first in the topological sorting, so it would result in a unique topological sorting.

Now we'll see one interesting and important property of this graph.

Property : Consider two consecutive strongly connneted components in the topological sorting, then all nodes present in the left component will have indegree strictly less than all nodes present in the right component. Here left denotes lower enumeration in the topological sorting.

Proof

Using the above property we can argue that if indegree of node $$$a$$$ is greater than the indegree of node $$$b$$$, then node $$$a$$$ is reachable from node $$$b$$$. Because either node $$$a$$$ lies in the same SCC or to the SCC of higher enumeration in topological sorting. In both cases $$$a$$$ is reachable from $$$b$$$.

So we can store all pairs of nodes $$$(a,b), 1 \leq a \leq n, 1 \leq b \leq n, a < b$$$ in an array and sort it according to decreasing order of absolute value of difference of indegrees i.e $$$|k_a - k_b|$$$. And if we pick a pair, let it be ($$$a$$$,$$$b$$$) and $$$indegree[b] > indegree[a]$$$, then we are sure that $$$b$$$ is reachable from $$$a$$$ so we need to check whether $$$a$$$ is reachable from $$$b$$$ or not, so we ask $$$"? \ b \ a"$$$ and if the judge responds by "Yes", then it means both $$$a$$$ and $$$b$$$ are reachable from each other. Since we were iterating in the dereasing order of $$$|k_a - k_b|$$$, we get the optimal answer.If judge never outputs "Yes" in the whole process, then there is no pair of nodes which are reachable from each other. So we will output $$$"? \ 0 \ 0"$$$

Overall Complexity : $$$O(n^2 \log_2 n)$$$

C++ solution

include <bits/stdc++.h>

using namespace std;

int main() { int n; cin >> n;

vector<int> indegree(n);

for (int i = 0; i < n; i++) {
    cin >> indegree[i];
}

vector<pair<int, pair<int, int>>> vec;

for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
        if (indegree[i] > indegree[j])
            vec.push_back({indegree[i] - indegree[j], {i, j}});
        else
            vec.push_back({indegree[j] - indegree[i], {j, i}});
    }
}

sort(vec.rbegin(), vec.rend());

for (auto it : vec) {
    if (it.first < 0)
        break;

    int a = it.second.first, b = it.second.second;
    cout << "? " << a + 1 << " " << b + 1 << endl;
    cout.flush();
    string str;
    cin >> str;
    if (str == "Yes") {
        cout << "! " << a + 1 << " " << b + 1 << endl;
        cout.flush();
        return 0;
    }
}

cout << "! 0 0" << endl;
cout.flush();

return 0;

}

</spolier>

<spoiler summary="Python solution">

import sys input = lambda: sys.stdin.readline().rstrip()

n = int(input())

indegs = list(map(int, input().split()))

pairs = [] for i in range(n): for j in range(i + 1, n): if indegs[i] > indegs[j]: pairs.append((indegs[i] — indegs[j], (i, j))) else: pairs.append((indegs[j] — indegs[i], (j, i)))

pairs = sorted(pairs, reverse=True) l = len(pairs)

for _, nodes in pairs: ni, nj = nodes

sys.stdout.write(f"? {ni + 1} {nj + 1}\n")
sys.stdout.flush()

s = input()
if s == "Yes":
    sys.stdout.write(f"! {ni + 1} {nj + 1}\n")
    exit(0)

sys.stdout.write("! 0 0\n")

</spolier>

Problem F: Christmas Game

Author: nikhil_c Problemsetting and editorialist: sigma_g

How do we solve a standard Nim game on arrays?
How to solve tree nim game for one rooting if K = 1: classifying odd/even steps

Let us say it's Alice's turn. If Alice moves some coins from an even step to an odd step, then Bob can move exactly those same coins from that odd step back to an even step. After this transition, once again it's Alice's move. In fact, we realize that Bob can "revert" every even->odd move by Alice.

Therefore, if Alice wants to win, she has to play at least one odd->even move. Moves that go from even->odd do not affect the game state at all, as the other player can always play another move that reverts them. Therefore, we can say that any coins present on even steps will not change the game state.

How to solve tree nim game for one rooting if K = 1: how bad are even steps

Hence, we can conclude that moving a coin from odd step to an even step is as good as taking a coin from the odd step and throwing it away.

Reducing tree nim game to linear array: the stair case nim

Extending to general K

How to calculate these xors? At each node $$$x$$$, we store a vector of size $$$D(n) = 2\cdot K$$$ where $$$D(n)_i$$$ is the xorsum of all nodes having their depth = $$$i$$$ — relative to node $$$x$$$ — in the subtree of node $$$n$$$.

Calculating the answer for all roots

C++ solution

include

include

using namespace std;

const int N = 1e5 + 1; const int K = 20 + 1;

using VI = vector; using VVI = vector<vector>;

VVI dp(N, VI(2 * K)); VI a(N); vector win(N); int n, k, k2;

void dfs(VVI &adj, int node, int prev) { dp[node][0] = a[node];

for (auto neigh : adj[node]) {
    if (neigh == prev) continue;
    dfs(adj, neigh, node);

    for (int rem = 1; rem < k2; rem++)
        dp[node][rem] ^= dp[neigh][rem - 1];

    dp[node][0] ^= dp[neigh][k2 - 1];
}

}

void dfs2(const VVI &adj, const int node, const int prev, const vector &my_xors) { vector final_xors(k2); for (int i = 0; i < k2; i++) final_xors[i] = my_xors[i] ^ dp[node][i];

unsigned int odd_layer_xor = 0;
for (int i = k; i < k2; i++)
    odd_layer_xor ^= final_xors[i];
win[node] = odd_layer_xor > 0;

for (auto neigh : adj[node]) {
    if (neigh == prev) continue;

    auto xor_send = final_xors;

    // remove all contribution of this subtree
    for (int i = 1; i < k2; i++)
        xor_send[i] ^= dp[neigh][i - 1];

    xor_send[0] ^= dp[neigh][k2 - 1];

    // whatever was depth k for me is depth k+1 for my child node
    int last = xor_send.back();
    for (int i = k2 - 1; i > 0; i--)
        xor_send[i] = xor_send[i - 1];

    xor_send[0] = last;

    dfs2(adj, neigh, node, xor_send);
}

}

int main() { cin >> n >> k; k2 = 2 * k;

VVI adj(n + 1);

for (int i = 0; i < n - 1; i++) {
    int x, y; cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
}

for (int i = 1; i <= n; i++) cin >> a[i];

dfs(adj, 1, 0);
dfs2(adj, 1, 0, vector<unsigned int>(k2));

for (int i = 1; i <= n; i++) cout << (win[i] ? 1 : 0) << " ";

return 0;

}

</spoiler>

<spoiler summary="PyPy3 solution">

n, k = list(map(int, input().split())) k2 = 2 * k

dp = [[0 for _ in range(k2)] for _ in range(n + 1)] adj = [[] for _ in range(n + 1)]

for _ in range(n — 1): _x, _y = list(map(int, input().split())) adj[_x].append(_y) adj[_y].append(_x)

a = [0] + list(map(int, input().split()))

win = [0 for _ in range(n + 1)]

parent = [0 for _ in range(n + 1)]

def dfs(node): global parent global dp

stack = [node]

pass_num = [0 for _ in range(n + 1)]

while stack:
    node = stack[-1]

    pass_num[node] += 1

    if pass_num[node] == 1:
        for neigh in adj[node]:
            if neigh == parent[node]:
                continue

            parent[neigh] = node
            stack.append(neigh)

        continue

    dp[node][0] = a[node]
    stack.pop()

    for neigh in adj[node]:
        if neigh == parent[node]:
            continue

        for rem in range(1, k2):
            dp[node][rem] ^= dp[neigh][rem - 1]

        dp[node][0] ^= dp[neigh][k2 - 1]

def dfs2(node): global win

stack = [[node, [0 for __ in range(k2)]]]

global dp

while stack:
    node, prev_xors = stack[-1]
    stack.pop()

    final_xors = [x ^ y for x, y in zip(prev_xors, dp[node])]

    for neigh in adj[node]:
        if neigh == parent[node]:
            continue

        send_xors = [x for x in final_xors]
        for i in range(1, k2):
            send_xors[i] ^= dp[neigh][i - 1]
        send_xors[0] ^= dp[neigh][k2 - 1]

        send_xors = [send_xors[-1]] + send_xors[:-1]
        stack.append([neigh, send_xors])

    odd_xor = 0
    for i in range(k, k2):
        odd_xor ^= final_xors[i]

    win[node] = 1 if odd_xor > 0 else 0

dfs(1) dfs2(1) print(" ".join(list(map(str, win[1:]))))

</spoiler>

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en16 English ninja_28 2021-04-11 21:29:29 1688 Reverted to en14
en15 English ninja_28 2021-03-31 08:03:57 1688
en14 English ninja_28 2021-03-30 19:10:58 1 Tiny change: 'n (x + y -1) / y;\n}' -> 'n (x + y - 1) / y;\n}'
en13 English ninja_28 2021-03-30 19:10:08 1 Tiny change: 'n (x + y - 1) / y;\n}' -> 'n (x + y -1) / y;\n}' (published)
en12 English ninja_28 2021-03-30 19:09:14 0 Tiny change: 'rn (x + y - 1) / y;\' -> 'rn (x + y \- 1) / y;\' (saved to drafts)
en11 English ninja_28 2021-03-30 19:07:09 0 Tiny change: ' LL y) {\n return (x ' -> ' LL y) {\nreturn (x '
en10 English ninja_28 2021-03-30 19:04:13 0 Tiny change: 'urn (x + y - 1) / y;\n}' -> 'urn (x + y1) / y;\n}'
en9 English ninja_28 2021-03-30 08:46:56 638
en8 English ninja_28 2021-03-29 20:59:49 40
en7 English ninja_28 2021-03-29 20:46:59 33
en6 English ninja_28 2021-03-29 20:43:20 1797
en5 English ninja_28 2021-03-29 20:32:45 3087
en4 English ninja_28 2021-03-29 20:12:27 152 Tiny change: 'A: GCD Sum\n========' -> 'A: GCD Sum [problem:1498A]\n========'
en3 English ninja_28 2021-03-29 20:09:19 8594
en2 English ninja_28 2021-03-29 19:57:29 8154 Tiny change: 'rn (x + y &mdash; 1) / y;\n' -> 'rn (x + y - 1) / y;\n' (published)
en1 English ninja_28 2021-03-29 19:49:16 32671 Initial revision (saved to drafts)