Infoleague Winter 2022 Round 1 Div. 2 Editorial

Правка en4, от Gheal, 2022-01-08 16:52:11

103503A — Make Sum Great Again

Author: Gheal

Hint 1
Hint 2
Hint 3
Hint 4
Solution

103503B — Binary Search Search

Author: Gheal

Hint 1
Hint 2

Solution> Solution:</p><p>To better understand the solution, let's consider $$$n=12$$$. The final array is the BFS traversal starting from the root of the following binary tree:</p><p>\begin{center}\includegraphics[scale=0.7]{arbore_binar_fml_2.png}\end{center}</p><p>This binary tree was generated by starting with the root $$$m=\lfloor \frac{n+1}{2} \rfloor=6$$$. Each node $$$m=\lfloor \frac{l+r}{2}\rfloor$$$ has up to two children: $$$m_1=\lfloor \frac{l+(m-1)}{2} \rfloor$$$ and $$$m_2=\lfloor \frac{r+(m+1)}{2} \rfloor$$$. </p><p>If our given integer $$$k$$$ is in a complete layer, then we can employ a binary search-type algorithm to find the position of $$$k$$$:</p><p>\begin{lstlisting} l = 1, r = n, position = 1, visited_nodes = 1 while(visited_nodes<=n){ m = (l + r) / 2</p> <pre>if(k==m){ print position return } if(k<m) position = position * 2 else position = position * 2 + 1 visited_nodes = visited_nodes * 2 + 1</pre><p>} \end{lstlisting}</p><p>This algorithm has the added benefit of not printing anything if $$$k$$$ is not in a complete layer. In this case, the position of $$$k$$$ in the last layer can be determined from $$$position$$$, although this isn't as straightforward. If the binary tree were complete, then the position of $$$k$$$ in the last layer would be $$$position-\frac{\text{visited_nodes}-1}{2}$$$, since there are $$$\frac{\text{visited_nodes}-1}{2}$$$ nodes on the other layers, all of which will be printed before $$$k$$$.</p><p>By looking at the missing nodes from the binary tree for $$$n=12$$$, one may make the crucial observation that the general case position for $$$k$$$ in the last layer is equal to $$$k-(position-\frac{\text{visited_nodes}-1}{2})$$$. </p><p>In conclusion, the final position for $$$k$$$ will be $$$k-(position-\frac{\text{visited_nodes}-1}{2})+\frac{\text{visited_nodes}-1}{2}=k+\text{visited_nodes}-position-1$$$.</p><p>Time complexity per testcase: $$$O(log n)$$$ </spoiler></p>

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en20 Английский Gheal 2022-01-08 21:32:38 152
en19 Английский Gheal 2022-01-08 21:02:08 0 (published)
en18 Английский Gheal 2022-01-08 20:53:28 372
en17 Английский Gheal 2022-01-08 17:36:05 134
en16 Английский Gheal 2022-01-08 17:26:10 4809
en15 Английский Gheal 2022-01-08 17:24:06 1808
en14 Английский Gheal 2022-01-08 17:22:43 708
en13 Английский Gheal 2022-01-08 17:20:14 820 Tiny change: 'eq 0$;\n- \neq k$.\' -> 'eq 0$;\n- $a_i \neq k$.\'
en12 Английский Gheal 2022-01-08 17:02:26 5 Tiny change: 'eq 0$;\n- \neq k$.\' -> 'eq 0$;\n- $a_i \neq k$.\'
en11 Английский Gheal 2022-01-08 17:02:02 56
en10 Английский Gheal 2022-01-08 17:01:18 5
en9 Английский Gheal 2022-01-08 17:00:59 1438 Tiny change: '="Solution>\n\nTo be' -> '="Solution">\n\nTo be'
en8 Английский Gheal 2022-01-08 16:57:22 6 Tiny change: '="Solution>\n\nTo be' -> '="Solution">\n\nTo be'
en7 Английский Gheal 2022-01-08 16:56:32 2 Tiny change: '="Solution>\n\nTo be' -> '="Solution">\n\nTo be'
en6 Английский Gheal 2022-01-08 16:56:14 51
en5 Английский Gheal 2022-01-08 16:55:40 122
en4 Английский Gheal 2022-01-08 16:52:11 2248 Tiny change: 'tion">\n\n\textbf{Lemma:} The numbe' -> 'tion">\n\n**Lemma:** The numbe'
en3 Английский Gheal 2022-01-08 16:47:07 13 Tiny change: 'tion">\n\n\textbf{Lemma:} The numbe' -> 'tion">\n\n**Lemma:** The numbe'
en2 Английский Gheal 2022-01-08 16:46:52 797
en1 Английский Gheal 2022-01-08 16:46:10 1652 Initial revision (saved to drafts)