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

Правка en3, от 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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)