2014.md (5436B)
1 Source: https://codeforces.com/blog/entry/134210 2 3 [I'm currently live discussing the problems.](https://youtu.be/RTB1bVkLshI) I will add problemwise timestamp after the discussion stream. You can join in if something in this blog is unclear or there are more questions. 4 5 [2014A - Robin Helps](/contest/2014/problem/A "Codeforces Round 974 (Div. 3)") 6 7 **Idea** 8 9 Maintain current amount of gold Robin has. Process all ai. 10 11 * If ai>=k, increase counter by ai 12 * If ai==0 and we have some gold, decrease current gold by 1 and increase answer. 13 14 My submission — [282225317](/contest/2014/submission/282225317 "Submission 282225317 by aryanc403") 15 16 **Video Editorial** 17 18 [2014B - Robin Hood and the Major Oak](/contest/2014/problem/B "Codeforces Round 974 (Div. 3)") 19 20 **Hint 1** 21 22 On last day only leaf grown between n-k+1 and n day will remain. 23 24 **Hint 2** 25 26 pow(i,i) is odd if i is odd, even if i is even. 27 28 **Hint 3** 29 30 We need no of odd numbers between n-k+1 and n 31 32 My submission — [282233711](/contest/2014/submission/282233711 "Submission 282233711 by aryanc403") 33 34 **Video Editorial** 35 36 [2014C - Robin Hood in Town](/contest/2014/problem/C "Codeforces Round 974 (Div. 3)") 37 38 **Hint 1** 39 40 Answer is impossible if n less than 3. 41 42 **Hint 2** 43 44 Lets first find minimum no of people that should be unhappy (say K). 45 46 **Hint 3** 47 48 Lets sort A, now average should be more than 2*Ak 49 50 **Hint 4** 51 52 Lets say pot has X gold. 53 Let S be the total gold. 54 55 $2*Ak \lt (S+X)/N$ 56 $2*N*Ak \lt S+X$ 57 $2*N*Ak-S \lt X$ 58 $2*N*Ak-S+1 \le X$ 59 60 So X should be max(0,2*N*ak-S+1) 61 62 My submission — [282243282](/contest/2014/submission/282243282 "Submission 282243282 by aryanc403") 63 64 **Video Editorial** 65 66 [2014D - Robert Hood and Mrs Hood](/contest/2014/problem/D "Codeforces Round 974 (Div. 3)") 67 68 **Hint 1** 69 70 For each starting day lets find how many jobs it overlaps with. 71 72 **Hint 2** 73 74 [Two Pointers](https://usaco.guide/silver/two-pointers) 75 76 My submission — [282252869](/contest/2014/submission/282252869 "Submission 282252869 by aryanc403") 77 78 **Video Editorial** 79 80 [2014E - Rendez-vous de Marian et Robin](/contest/2014/problem/E "Codeforces Round 974 (Div. 3)") 81 82 **Hint 1** 83 84 > In addition, h of the n vertices each has a single horse available. 85 86 Just forget this condition exists, and assume each place contains unlimited horses. 87 88 **Hint 1** 89 90 Now for each place try to find the minimum time, if we reach there using a horse, and without a horse. 91 92 **Hint 3** 93 94 Try to solve above problem using a modified version of [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) 95 96 **Hint 3** 97 98 At last fix a meeting point, and take maximum of minimum time each person takes to reach there with or without horse. 99 100 My submission — [282288329](/contest/2014/submission/282288329 "Submission 282288329 by aryanc403") 101 102 **Video Editorial** 103 104 [2014F - Sheriff's Defense](/contest/2014/problem/F "Codeforces Round 974 (Div. 3)") 105 106 **Hint 1** 107 108 [DP on trees](https://usaco.guide/gold/dp-trees) 109 110 **Hint 2** 111 112 For each subtree dp1[u] denotes the best possible sum we can get if we consider only subtree of u and u is destroyed. 113 For each subtree dp2[u] denotes the best possible sum we can get if we consider only subtree of u and u is not destroyed. 114 115 My submission — [282298489](/contest/2014/submission/282298489 "Submission 282298489 by aryanc403") 116 117 **Video Editorial** 118 119 [2014G - Milky Days](/contest/2014/problem/G "Codeforces Round 974 (Div. 3)") 120 121 **Hint 1** 122 123 Lets first process each day one by one. 124 125 **Hint 2** 126 127 We should maintain list of all drinkable milks in a map. 128 We should remove all non drinkable milk. 129 We should add all the new milk we have got today. 130 131 **Hint 3** 132 133 Now split into 2 cases — 134 135 * Latest milk quantity is less than m. 136 * Latest milk quantity is atleast m, 137 138 **Hint 4** 139 140 For case 1, when latest milk quantity is less than m, 141 We should bruteforce by taking latest milk and until we have total m, or no milk remains. 142 143 Then increase time by 1. 144 145 **Hint 5** 146 147 For case 2, when latest milk quantity is atleast m, 148 149 Here, lets try to find how long can we drink current milk. 150 151 We can drink it until — 152 153 * Some other milk comes 154 * If current quantity is C, then we can drink it for next C/m days 155 * If this milk came on dj day, we can drink it until dj+k-1 day 156 157 Take minimum of these 3, and assume we have gotten m milk each day. 158 Then remove this quantity from latest milk, and increase time. 159 160 My submission — [282316286](/contest/2014/submission/282316286 "Submission 282316286 by aryanc403") 161 162 **Video Editorial** 163 164 [2014H - Robin Hood Archery](/contest/2014/problem/H "Codeforces Round 974 (Div. 3)") 165 166 **Hint 1** 167 168 Lets say we are playing game on targets B1,B2,B3,...,Bm 169 What is the optimal strategy for players? 170 171 **Hint 2** 172 173 Players should always chose the maximum target. 174 175 **Hint 3** 176 177 Lets sort B in descending order. 178 Then Robin takes B1,B3,B5... and Sheriff will take B2,B4,.... 179 180 **Hint 4** 181 182 Because B1 \ge B2, B3 \ge B4, and so on... 183 At this point, Sheriff can never win. 184 When can we have a draw? 185 186 **Hint 5** 187 188 We will have a draw if and only if no of targets is even, and B1 = B2, B3 = B4, and so on... 189 190 **Hint 6** 191 192 In other words, frequency of every no in B should be even. 193 194 **Hint 7** 195 196 How to check if frequency of every no is even? 197 [Zobrist Hashing](https://codeforces.com/blog/entry/85900) 198 199 My submission — [282302515](/contest/2014/submission/282302515 "Submission 282302515 by aryanc403") 200 201 **Video Editorial** 202 203 **Chat QnA**