codeforces-scrape

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

1534.md (4633B)


      1 Source: https://codeforces.com/blog/entry/91760
      2 
      3 [1534A - Colour the Flag](/contest/1534/problem/A)
      4 
      5 Author: [crackersamdjam](/profile/crackersamdjam "Grandmaster crackersamdjam")
      6 
      7 **Hint 1**
      8 
      9 Let's say you know the colour of the first square, what colours can you figure out next?
     10 
     11 **Hint 2**
     12 
     13 Colour it like a chessboard, but there's more than one possible chessboard!
     14 
     15 **Hint 3**
     16 
     17 Brute force the color of the first square!
     18 
     19 **Tutorial**
     20 
     21 Tutorial is loading...
     22 
     23 **Solution**
     24 
     25 [119400830](/contest/1534/submission/119400830 "Submission 119400830 by Dormi")
     26 
     27 [1534B - Histogram Ugliness](/contest/1534/problem/B)
     28 
     29 Author: [Dormi](/profile/Dormi "Grandmaster Dormi")
     30 
     31 **Hint 1**
     32 
     33 Consider the contribution of each pillar to the answer.
     34 
     35 **Hint 2**
     36 
     37 How does doing the operation on a pillar change the contribution to the answer?
     38 
     39 **Hint 3**
     40 
     41 You only want to do an operation on a pillar if the top cell contributes 2 to the answer.
     42 
     43 **Tutorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution**
     48 
     49 [119400874](/contest/1534/submission/119400874 "Submission 119400874 by Dormi")
     50 
     51 [1534C - Little Alawn's Puzzle](/contest/1534/problem/C)
     52 
     53 Author: [Ninjaclasher](/profile/Ninjaclasher "Candidate Master Ninjaclasher")
     54 
     55 **Hint 1**
     56 
     57 Let's say you know whether you flipped the first cell or not, which new columns must be flipped?
     58 
     59 **Hint 2**
     60 
     61 Create a graph of $n$ nodes, draw an edge between two values if they both exist in the same column, what structure does this graph have?
     62 
     63 **Hint 3**
     64 
     65 It is a bunch of disjoint cycles (since each node has an in-degree of $2$).
     66 
     67 **Hint 4**
     68 
     69 Each cycle is independent, and there are $2$ ways to flip each cycle.
     70 
     71 **Tutorial**
     72 
     73 Tutorial is loading...
     74 
     75 **Solution**
     76 
     77 [119400885](/contest/1534/submission/119400885 "Submission 119400885 by Dormi")
     78 
     79 [1534D - Lost Tree](/contest/1534/problem/D)
     80 
     81 Author: [Plasmatic](/profile/Plasmatic "Grandmaster Plasmatic")
     82 
     83 **Hint 1**
     84 
     85 All trees are bipartite.
     86 
     87 **Hint 2**
     88 
     89 Find a $2$-coloring of a tree in one query.
     90 
     91 **Hint 3**
     92 
     93 You can find all nodes adjacent to one node in one query.
     94 
     95 **Hint 4**
     96 
     97 The min(number of black, number of white) nodes is $\leq \left \lfloor{\frac{n}{2}}\right \rfloor$.
     98 
     99 **Tutorial**
    100 
    101 Tutorial is loading...
    102 
    103 **Solution**
    104 
    105 [119400891](/contest/1534/submission/119400891 "Submission 119400891 by Dormi")
    106 
    107 [1534E - Lost Array](/contest/1534/problem/E)
    108 
    109 Author: [Plasmatic](/profile/Plasmatic "Grandmaster Plasmatic")
    110 
    111 **Hint 1**
    112 
    113 Try to solve this problem for $n \leq 15$.
    114 
    115 **Hint 2**
    116 
    117 Try BFSing on the bitmasks.
    118 
    119 **Hint 3**
    120 
    121 Do we really care about what elements are in the bitmask?
    122 
    123 **Hint 4**
    124 
    125 Only the number of nodes in each mask matters.
    126 
    127 **Tutorial**
    128 
    129 Tutorial is loading...
    130 
    131 **Solution**
    132 
    133 [119400897](/contest/1534/submission/119400897 "Submission 119400897 by Dormi")
    134 
    135 [1534F1 - Falling Sand (Easy Version)](/contest/1534/problem/F1)
    136 
    137 Author: [Dormi](/profile/Dormi "Grandmaster Dormi")
    138 
    139 **Hint 1**
    140 
    141 Make a directed graph on the sand.
    142 
    143 **Hint 2**
    144 
    145 The graph should satisfy the following property: if a node $a$ can reach another node $b$ by a sequence of edges, disturbing $a$ will disturb $b$.
    146 
    147 **Hint 3**
    148 
    149 Compress scc's in the graph.
    150 
    151 **Hint 4**
    152 
    153 You must disturb all nodes with in-degree $0$ in the new graph.
    154 
    155 **Tutorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Solution**
    160 
    161 [119400903](/contest/1534/submission/119400903 "Submission 119400903 by Dormi")
    162 
    163 [1534F2 - Falling Sand (Hard Version)](/contest/1534/problem/F2)
    164 
    165 Author: [Dormi](/profile/Dormi "Grandmaster Dormi")
    166 
    167 **Hint 1**
    168 
    169 Continued from $F1$, read that first.
    170 
    171 **Hint 2**
    172 
    173 The $a_i^\texttt{th}$ nodes from the bottom of each column must eventually be disturbed (call them special).
    174 
    175 **Hint 3**
    176 
    177 If a special node can reach another special node, you can delete that node.
    178 
    179 **Hint 4**
    180 
    181 Each node will remove some contiguous subsegment of the remaining special nodes' columns.
    182 
    183 **Hint 5**
    184 
    185 Find a greedy strategy to cover all of the columns.
    186 
    187 **Tutorial**
    188 
    189 Tutorial is loading...
    190 
    191 **Solution**
    192 
    193 [119400908](/contest/1534/submission/119400908 "Submission 119400908 by Dormi")
    194 
    195 [1534G - A New Beginning](/contest/1534/problem/G)
    196 
    197 Author: [Aaeria](/profile/Aaeria "Master Aaeria")
    198 
    199 **Tutorial**
    200 
    201 Tutorial is loading...
    202 
    203 **Solution**
    204 
    205 [119400915](/contest/1534/submission/119400915 "Submission 119400915 by Dormi")
    206 
    207 [Tests generator](https://github.com/zzaria/programming-contest-resources/blob/main/my%20problems/cf1524/g.zip)
    208 
    209 [1534H - Lost Nodes](/contest/1534/problem/H)
    210 
    211 Author: [Ninjaclasher](/profile/Ninjaclasher "Candidate Master Ninjaclasher")
    212 
    213 **Tutorial**
    214 
    215 Tutorial is loading...
    216 
    217 **Solution**
    218 
    219 [119400928](/contest/1534/submission/119400928 "Submission 119400928 by Dormi")