1826.md (2718B)
1 Source: https://codeforces.com/blog/entry/115892 2 3 The problems were named after songs of my favorite musical group, Hippie Sabotage. Give them a try! 4 5 [1826A - Trust Nobody](/contest/1826/problem/A "Codeforces Round 870 (Div. 2)") 6 7 **Hint1** 8 9 Check each number of liars independently. 10 11 **Hint2** 12 13 How to check, whether there are exactly $x$ liars? 14 15 **Solution** 16 17 Tutorial is loading... 18 19 С++ Implementation: [204718333](/contest/1826/submission/204718333 "Submission 204718333 by Akulyat") 20 21 [1826B - Lunatic Never Content](/contest/1826/problem/B "Codeforces Round 870 (Div. 2)") 22 23 **Hint1** 24 25 How to solve for $n = 2$? 26 27 **Hint2** 28 29 How to solve for $n = 4$? 30 31 **Solution** 32 33 Tutorial is loading... 34 35 С++ Implementation: [204718497](/contest/1826/submission/204718497 "Submission 204718497 by Akulyat") 36 37 [1826C - Dreaming of Freedom](/contest/1826/problem/C "Codeforces Round 870 (Div. 2)") 38 39 **Hint1** 40 41 What is the number of options that is present in the infinite amount of rounds? 42 43 **Hint2** 44 45 Choose the smallest such number of options. 46 47 **Hint3** 48 49 How does this number and $m$ relate to the answer? 50 51 **Solution** 52 53 Tutorial is loading... 54 55 С++ Implementation: [204718535](/contest/1826/submission/204718535 "Submission 204718535 by Akulyat") 56 57 [1826D - Running Miles](/contest/1826/problem/D "Codeforces Round 870 (Div. 2)") 58 59 **Hint1** 60 61 What can we say about the position of the maximum elements relative to $[l, r]$? 62 63 **Hint2** 64 65 You can use DP, or otherwise: 66 Iterate over the middle maximum element and choose $[l, r]$ greedily. 67 68 **Solution** 69 70 Tutorial is loading... 71 72 С++ Implementation: [204718553](/contest/1826/submission/204718553 "Submission 204718553 by Akulyat") 73 74 [1826E - Walk the Runway](/contest/1826/problem/E "Codeforces Round 870 (Div. 2)") 75 76 **Hint1** 77 78 What is the relation between two models that go one after another in a show? 79 80 **Hint2** 81 82 If you calculate the relation "model $i$ can go before model $j$" somehow, how to calculate the answer? 83 84 **Answer** 85 86 Use DP on the graph. 87 88 **Hint3** 89 90 How to calculate this relation fast enough? 91 92 **Answer** 93 94 Bitsets 95 96 **Solution** 97 98 Tutorial is loading... 99 100 С++ Implementation: [204718603](/contest/1826/submission/204718603 "Submission 204718603 by Akulyat") 101 102 [1826F - Fading into Fog](/contest/1826/problem/F "Codeforces Round 870 (Div. 2)") 103 104 **Hint1** 105 106 What happens in the general case after 2 queries? 107 108 **Answer** 109 110 There are $O(n^2)$ candidates for an answer. 111 112 **Hint2** 113 114 Can we solve the question in 3 queries? 115 116 **Answer** 117 118 Yes! 119 120 **Hint3** 121 122 How to choose the third query, so that we don't intersect any bad candidates? 123 124 **Solution** 125 126 Tutorial is loading... 127 128 С++ Implementation: [204718641](/contest/1826/submission/204718641 "Submission 204718641 by Akulyat")