codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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