Codeforces Round #841 (Div. 2) and Divide By Zero 2022 Editorial
Difference between en11 and en12, changed 39 character(s)
**UPD**: Code links are working now↵
↵
[problem:1731A]↵
 ↵
Idea: [user:s_jaskaran_s,2022-12-27]↵
 ↵
↵
<spoiler summary="Hint">↵
What is the maximum value of $a + b$ when $a \cdot b = x$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1731A]↵
</spoiler>↵
↵
 ↵
↵
<spoiler summary="Code">↵
[submission:186975476]↵
</spoiler>↵
↵
 ↵
[problem:1731B]↵
 ↵
Idea: [user:s_jaskaran_s,2022-12-27]↵
 ↵
↵
<spoiler summary="Hint">↵
Check which direction is optimal for the next 2 steps and why? ↵
↵
- 2 times Right? ↵
↵
- 2 times Down?↵
↵
-  1 time Right and 1 time Down? ↵
↵
- 1 time Down 1 time Right?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1731B]↵
</spoiler>↵
↵
 ↵
↵
<spoiler summary="Code">↵
[submission:186975620]↵
</spoiler>↵
↵
 ↵
[problem:1731C]↵
 ↵
Idea: [user:ka_tri,2022-12-27]↵
↵
<spoiler summary="Hint 1">↵
What are the numbers with the odd number of divisors?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How many numbers with the odd number of divisors can be there in the range $2 \cdot 10^5$?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try using prefix $\operatorname{XOR}$, iterating through all such numbers.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1731C]↵
</spoiler>↵
↵
 ↵
↵
<spoiler summary="Code(C++)">↵
[submission:186975655]↵
</spoiler>↵
↵
<spoiler summary="Code(Python)">↵
[submission:186975680]↵
</spoiler>↵
↵
 ↵
[problem:1731D]↵
 ↵
Idea: [user:s_jaskaran_s,2022-12-27]↵
 ↵
↵
<spoiler summary="Hint 1">↵
For a particular size, how to check if there's a cube greater than that?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try Binary search on side length.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Let $x$ be the side length. How to check if a square has all its elements $\geq x$ in $O(1)$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1731D]↵
</spoiler>↵
↵
 ↵
↵
<spoiler summary="Code(Prefix Sum)">↵
[submission:186975714]↵
</spoiler>↵
↵
<spoiler summary="Code(Sparse Table)">↵
[submission:186975738]↵
</spoiler>↵
↵
 ↵
[problem:1731E]↵
 ↵
Idea: [user:s_jaskaran_s,2022-12-27]↵
 ↵
↵
<spoiler summary="Hint 1">↵
Can you find the number of edges for each possible $GCD$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Did you try Greedy?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1731E]↵
</spoiler>↵
↵
 ↵
↵
<spoiler summary="Code">↵
[submission:186975762]↵
</spoiler>↵
↵
 ↵
[problem:1731F]↵
 ↵
Idea: [user:nishkarsh,2022-12-27] and [user:s_jaskaran_s,2022-12-27]↵
 ↵
↵
↵
<spoiler summary="Solution">↵
[tutorial:1731F]↵
</spoiler>↵
↵
 ↵
↵
<spoiler summary="Code">↵
[submission:186975785]↵
</spoiler>↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English adedalic 2022-12-28 00:28:46 39 Tiny change: '[problem:1' -> '**UPD**: Code links are working now\n\n[problem:1'
en11 English adedalic 2022-12-28 00:26:57 46
en10 English adedalic 2022-12-28 00:20:18 8 Tiny change: 'ssion:186955913]\n</spoil' -> 'ssion:186975476]\n</spoil'
en9 English s_jaskaran_s 2022-12-27 20:44:16 33 Tiny change: '="Code">\nTo be updated\n</spoile' -> '="Code">\n[submission:186957540]\n</spoile'
en8 English s_jaskaran_s 2022-12-27 20:38:58 0 (published)
en7 English s_jaskaran_s 2022-12-27 20:35:24 265 (saved to drafts)
en6 English s_jaskaran_s 2022-12-27 19:59:42 0 (published)
en5 English s_jaskaran_s 2022-12-27 19:51:06 238
en4 English s_jaskaran_s 2022-12-27 18:29:02 91
en3 English s_jaskaran_s 2022-12-27 17:21:02 1
en2 English s_jaskaran_s 2022-12-27 17:18:01 12509 Tiny change: ' elements \geq $x$ in $O(1' -> ' elements $\geq x$ in $O(1'
en1 English s_jaskaran_s 2022-12-27 16:48:00 11602 Initial revision (saved to drafts)