codeforces-scrape

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

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")