1731.md (3085B)
1 Source: https://codeforces.com/blog/entry/110630 2 3 **UPD**: Code links are working now 4 5 [1731A - Joey Takes Money](/contest/1731/problem/A "Codeforces Round 841 (Div. 2) and Divide by Zero 2022") 6 7 Idea: [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s") 8 9 **Hint** 10 11 What is the maximum value of $a + b$ when $a \cdot b = x$? 12 13 **Solution** 14 15 Tutorial is loading... 16 17 **Code** 18 19 [186975476](/contest/1731/submission/186975476 "Submission 186975476 by adedalic") 20 21 [1731B - Kill Demodogs](/contest/1731/problem/B "Codeforces Round 841 (Div. 2) and Divide by Zero 2022") 22 23 Idea: [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s") 24 25 **Hint** 26 27 Check which direction is optimal for the next 2 steps and why? 28 29 * 2 times Right? 30 * 2 times Down? 31 * 1 time Right and 1 time Down? 32 * 1 time Down 1 time Right? 33 34 **Solution** 35 36 Tutorial is loading... 37 38 **Code** 39 40 [186975620](/contest/1731/submission/186975620 "Submission 186975620 by adedalic") 41 42 [1731C - Even Subarrays](/contest/1731/problem/C "Codeforces Round 841 (Div. 2) and Divide by Zero 2022") 43 44 Idea: [ka_tri](/profile/ka_tri "Candidate Master ka_tri") 45 46 **Hint 1** 47 48 What are the numbers with the odd number of divisors? 49 50 **Hint 2** 51 52 How many numbers with the odd number of divisors can be there in the range $2 \cdot 10^5$? 53 54 **Hint 3** 55 56 Try using prefix $\operatorname{XOR}$, iterating through all such numbers. 57 58 **Solution** 59 60 Tutorial is loading... 61 62 **Code(C++)** 63 64 [186975655](/contest/1731/submission/186975655 "Submission 186975655 by adedalic") 65 66 **Code(Python)** 67 68 [186975680](/contest/1731/submission/186975680 "Submission 186975680 by adedalic") 69 70 [1731D - Valiant's New Map](/contest/1731/problem/D "Codeforces Round 841 (Div. 2) and Divide by Zero 2022") 71 72 Idea: [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s") 73 74 **Hint 1** 75 76 For a particular size, how to check if there's a cube greater than that? 77 78 **Hint 2** 79 80 Try Binary search on side length. 81 82 **Hint 3** 83 84 Let $x$ be the side length. How to check if a square has all its elements $\geq x$ in $O(1)$? 85 86 **Solution** 87 88 Tutorial is loading... 89 90 **Code(Prefix Sum)** 91 92 [186975714](/contest/1731/submission/186975714 "Submission 186975714 by adedalic") 93 94 **Code(Sparse Table)** 95 96 [186975738](/contest/1731/submission/186975738 "Submission 186975738 by adedalic") 97 98 [1731E - Graph Cost](/contest/1731/problem/E "Codeforces Round 841 (Div. 2) and Divide by Zero 2022") 99 100 Idea: [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s") 101 102 **Hint 1** 103 104 Can you find the number of edges for each possible $GCD$? 105 106 **Hint 2** 107 108 Did you try Greedy? 109 110 **Solution** 111 112 Tutorial is loading... 113 114 **Code** 115 116 [186975762](/contest/1731/submission/186975762 "Submission 186975762 by adedalic") 117 118 [1731F - Function Sum](/contest/1731/problem/F "Codeforces Round 841 (Div. 2) and Divide by Zero 2022") 119 120 Idea: [nishkarsh](/profile/nishkarsh "Master nishkarsh") and [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s") 121 122 **Solution** 123 124 Tutorial is loading... 125 126 **Code** 127 128 [186975785](/contest/1731/submission/186975785 "Submission 186975785 by adedalic")