codeforces-scrape

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

1209.md (9471B)


      1 Source: https://codeforces.com/blog/entry/69791
      2 
      3 # [1209A — Paint the Numbers](https://codeforces.com/contest/1209/problem/A)
      4 
      5 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 Consider the smallest element $x$ in the array. We need to paint it in some color, right?
      8 
      9 Observe, that we can paint all elements divisible by $x$ in that color as well.
     10 
     11 So we can perform the following while the array is not empty:
     12 
     13 * find the minimum element $x$,
     14 * assign new color and remove all elements divisible by $x$
     15 
     16 Complexity: $\mathcal{O}(n^2)$.
     17 
     18 # [1209B — Koala and Lights](https://codeforces.com/contest/1209/problem/B)
     19 
     20 Author: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
     21 
     22 Because each individual light flashes periodically, all the lights together are periodic as well.
     23 
     24 Therefore, we can simulate the lights up to the period to get the answer.
     25 
     26 The actual period can be calculated as follows:
     27 
     28 **Spoiler**
     29 
     30 * If a light toggles every $t$ seconds, its period is $2t$.
     31 * The overall period is the least common multiple of the individual periods $2,4,6,8,10$, which is $120$.
     32 * There is also a "pre-period" of $5$ since lights can start toggling at time 5 in the worst case, so the time we need to simulate is bounded by $125$
     33 
     34 However, computing the actual period is not necessary and a very large number will work (like $1000$).
     35 
     36 Challenge: Can we bound the time even more?
     37 
     38 # [1209C — Paint the Digits](https://codeforces.com/contest/1209/problem/C)
     39 
     40 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     41 
     42 The sequence must split into two non-decreasing where the end of the first $\le$ start of the second.
     43 
     44 Let's bruteforce the value $x$, so that all elements $ \lt x$ go to the color $1$, all elements $ \gt x$ go to the color $2$, and for $=x$ we are not sure.
     45 
     46 Actually, we can say that all elements equal to $x$, which go before the first element $ \gt x$ сan safely go to the color $2$, while the rest can only go to the color $1$.
     47 
     48 So we colored our sequence and we now only need to check whether this coloring is fine.
     49 
     50 Complexity is $10 \cdot n$.
     51 
     52 # [1209D — Cow and Snacks](https://codeforces.com/contest/1209/problem/D)
     53 
     54 Author: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
     55 
     56 Since every animal has exactly two favorite snacks, this hints that we should model the problem as a graph. The nodes are the snacks, and the edges are animals with preferences connecting snack nodes.
     57 
     58 Let's consider a connected component of the graph with size greater than $1$. The first animal (edge) in that component to eat must take two snacks (nodes), all other snack nodes will be eaten by exactly one animal edge. It is always possible to find an order so that no other animals takes two snacks (for example, BFS order). Thus, a connected component with $c$ vertices can satisfy at most $c-1$ animals.
     59 
     60 Let $N$ be the number of snacks, $M$ be the number of animals, and $C$ be the number of connected components (including those of size 1). The number of satisfied animals is $N-C$, so the number of of unhappy animals is $M-(N-C)$.
     61 
     62 Complexity: $\mathcal{O}(n+m)$
     63 
     64 # [1209E1 — Rotate Columns (easy version)](https://codeforces.com/contest/1209/problem/E1)
     65 
     66 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and [cdkrot](/profile/cdkrot "International Grandmaster cdkrot")
     67 
     68 There many approaches possible, let's describe one of them.
     69 
     70 Let's change the problem to the following:
     71 
     72 * Rotate columns any way you want.
     73 * Select in each row one value, maximizing the sum.
     74 
     75 This can be done with a dp, states are (prefix of columns, mask of taken columns). Basically at each step we are rotating the current column and fixing values for some of the rows.
     76 
     77 The most simple way to write this makes $3^n \cdot m \cdot n^2$ (for every submask->mask transition iterate over all possible shifts and elements to consider in cost function).
     78 
     79 But if we precalculate the cost function in advance, we will have $\mathcal{O}((3^n + 2^n n^2) \cdot m)$.
     80 
     81 # [1209E2 — Rotate Columns (hard version)](https://codeforces.com/contest/1209/problem/E2)
     82 
     83 The previous solution is slightly too slow to pass the large constraints.
     84 
     85 Let's sort columns by the maximum element in them. Observe, that it is surely unoptimal to use columns which go after first $n$ columns in sorted order (we could've replaced them with some unused column).
     86 
     87 So we can solve the hard version with previous solution in which we consider only best $n$ columns.
     88 
     89 Complexity $\mathcal{O}((3^n + 2^n \cdot n^2) \cdot n + T(sort))$
     90 
     91 # [1209F — Koala and Notebook](https://codeforces.com/contest/1209/problem/F)
     92 
     93 Author: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining")
     94 
     95 First split all edges into directed edges with single digit labels, creating $\mathcal{O}(m\log{m})$ dummy vertices if necessary.
     96 
     97 Since the first edge will not be zero (no leading zeros), longer paths are always greater. With a BFS, this reduces the problem to finding lexicographical minimal paths in a DAG.
     98 
     99 To avoid needing to compare long sequences, we will instead visit all the vertices in order by their lexicographical minimal path. This can be done efficiently by something like BFS/DFS.
    100 
    101 The main idea is to visit sets of vertices at a time. If we have a set of vertices whose minimal paths are $P$, we can find the set of vertices whose minimal paths are $P0$ by following all outgoing $0$ edges. Then, we find the set of vertices whose minimal paths are $P1$ by following all outgoing $1$ edges, and so on for all digits. Since we ignore vertices once they are visited, this is $\mathcal{O}(m\log{m})$
    102 
    103 # [1209G1 — Into Blocks (easy version)](https://codeforces.com/contest/1209/problem/G1)
    104 
    105 Author: [Errichto](/profile/Errichto "International Grandmaster Errichto")
    106 
    107 Let's solve easier version first (we will reuse core ideas in hard version as well).
    108 
    109 Clearly, if some two integers are ``hooked'' like in $1 \ldots 2 \ldots 1 \ldots 2$, then they will end up being turned into the same integer.
    110 
    111 So when we see integer $x$ with first occurrence at $a$ and last at $b$, let's mark segment $[a; b]$ as blocked. E.g. for array $[3, 3, 1, 2, 1, 2]$ we have not blocked only the bar between $3$ and $1$, that is we have $|3, 3 | 1, 2, 1, 2|$.
    112 
    113 Now for every such segment we have to change all elements into a common element. So the answer for a segment is segment length minus the number of occurrences of the most frequent element.
    114 
    115 One easy implementation is as follows: blocking is "+= 1 on segment" (can be done easily in $\mathcal{O}{(n + operations)}$ in offline, then for an element $x$, put the number of it's occurrences in the position of first occurrences.
    116 
    117 Now we only need to compute max on disjoint segments, so it can be done in a naive way.
    118 
    119 Complexity: $\mathcal{O}(n)$.
    120 
    121 # [1209G2 — Into Blocks (hard version)](https://codeforces.com/contest/1209/problem/G2)
    122 
    123 To adjust the solution for many queries we need to create some sophisticated data structure.
    124 
    125 E.g. we all know that mentioned above "+= 1 on a segment" is easily done with a segtree. If we maintain for every value $a_i$ the corresponding set of occurrences, it's easy to update mentioned above ``number of occurrences in the first position''.
    126 
    127 So what we need to do now? We need to dynamically recalculate the sum of minimums (and the set segments to calculate minimum can change quite much due to updates).
    128 
    129 You probably also now that we can design a segtree which supports range increments and query (minimum, number of minimums) on the segment. In a similar way we can build a structure which returns (minimum, number of minimums, the sum of largest stored counts between minimums). Just maintain a few values in each node and do lazy propagation.
    130 
    131 Complexity $\mathcal{O}(q \log n)$.
    132 
    133 # [1209H — Moving Walkways](https://codeforces.com/contest/1209/problem/H)
    134 
    135 Author: [Errichto](/profile/Errichto "International Grandmaster Errichto")
    136 
    137 Some minor tips:
    138 
    139 * Everything is a walkway. When there is no walkway, it is a walkway of speed $0$.
    140 * You can increase all speeds by $1$ and assume that you own speed is in $[-1; +1]$
    141 * Energy is an entity which is $\delta$ speed $\times$ time, which is distance.
    142 
    143 Also if you spend $x$ energy per segment of len $l$ and speed $v$, it is not important how exactly you will distribute it over the walking process. In any way, you will walk by feet $l - x$ meters in time $(l - x) / v$.
    144 
    145 So it turns out it's better to distribute more energy to low-speeded walkways (because the denominator is smaller).
    146 
    147 Assume that you (by default) save up all energy on any non-feet path (for feet path it's always optimal to walk with speed $\ge 1$ ($\ge 0$ after speeds hack), so now save up's).
    148 
    149 Build an energy graphic where the Ox axis will correspond to the **point** you are in (not time). It will be a piecewise linear function, so it is enough to store it's value only in points corresponding to points between walkways. Iterate over walkways in the order of speed and try to steal as much energy as possible to the current walkway.
    150 
    151 What are the limits of stealing energy?
    152 
    153 * there is a restriction based on $l$ and $v$ (if you take too much energy, you wouldn't be able to fully walk it up)
    154 * the graphic must still be able above $0$ at all points.
    155 
    156 The latter condition is just a suffix minima on a segment tree.
    157 
    158 Complexity: $\mathcal{O}(n \log n)$.