**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>↵
↵
↵
[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>↵
↵
