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

Revision en3, by ninja_28, 2021-03-29 20:09:19

# Problem A: GCD Sum

Author and Problemsetting: ninja_28
Editorialist: sigma_g

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

# 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: sigma_g

Hint 1
Solution idea
Solution details
Implementation details
Note
C++ solution

# 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
Python solution

# Problem E: Two Houses

Author, 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

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
Python solution

# 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
How to solve tree nim game for one rooting if K = 1: how bad are even steps
Reducing tree nim game to linear array: the stair case nim
Extending to general K
Calculating the answer for all roots
C++ solution
Python solution

#### History

Revisions

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