codeforces-scrape

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

908.md (11593B)


      1 Source: https://codeforces.com/blog/entry/56713
      2 
      3 Here's the editorial. Hope you have a happy new year!
      4 
      5 Code can be found here: <https://www.dropbox.com/sh/i9cxj44tvv5pqvn/AACQs7LLNyTZT-Gt_AMf7UQFa?dl=0>
      6 
      7 **New Year and Counting Cards**
      8 
      9 Let's start off a bit more abstractly. We would like to know if the statement "if P then Q" is true, where P and Q are some statements (in this case, P is "card has vowel", and Q is "card has even number"). To do determine this, we need to flip over any cards which could be counter-examples (i.e. could make the statement false).
     10 
     11 Let's look at the truth table for if P then Q (see here: <http://www.math.hawaii.edu/~ramsey/Logic/IfThen.html)>. The statement is only false when Q is false and P is true. Thus, it suffices to flip cards when P is true or Q is false.
     12 
     13 To solve this problem, we need to print the count of vowels and odd digits in the string.
     14 
     15 **stats**
     16 
     17 First solve: [ksun48](/profile/ksun48 "International Grandmaster ksun48") at 00:01:01
     18 
     19 Breakdown of results for submissions that passed pretests
     20 
     21 ```
     22 OK 6427 (98.74%)
     23 CHALLENGED 60 (0.92%)
     24 WRONG_ANSWER 22 (0.34%)
     25 TOTAL 6509
     26 ```
     27 
     28 **New Year and Buggy Bot**
     29 
     30 This problem is intended as an implementation problem. The bounds are small enough that a brute force works. We can iterate through all mapping of numbers to directions (i.e. using next permutation in C++ or doing some recursive DFS if there is no built in next permutation in your language), and simulate the robot's movements. We have to be careful that if the robot ever gets in an invalid state, we break out early and say the mapping is invalid.
     31 
     32 **stats**
     33 
     34 First solve: [jonathanirvings](/profile/jonathanirvings "Grandmaster jonathanirvings"), [dotorya](/profile/dotorya "Legendary Grandmaster dotorya") at 00:05:16
     35 
     36 Breakdown of results for submissions that passed pretests
     37 
     38 ```
     39 OK 4192 (83.72%)
     40 WRONG_ANSWER 652 (13.02%)
     41 CHALLENGED 126 (2.52%)
     42 RUNTIME_ERROR 33 (0.66%)
     43 TIME_LIMIT_EXCEEDED 4 (0.08%)
     44 TOTAL 5007
     45 ```
     46 
     47 **New Year and Curling**
     48 
     49 This is another simulation problem with some geometry. As we push a disk, we can iterate through all previous disks and see if their *x*-coordinates are  ≤ 2*r*. If so, then that means these two circles can possibly touch.
     50 
     51 If they do, we can compute the difference of heights between these two circles using pythagorean theorem. In particular, we want to know the change in *y* coordinate between the two touching circles. We know the hypotenuse (it is 2*r* since the circles are touching), and the change in *x*-coordinate is given, so the change in *y* coordinate is equal to ![](https://espresso.codeforces.com/57fad12c8db4c3cdacbeea280b56c4bbabf54678.png), where *dx* is the change in *x*-coordinate.
     52 
     53 We can then take the maximum over all of these cases to get our final *y*-coordinate, since this is where this disk will first stop. Overall, this takes *O*(*n*2) time.
     54 
     55 **stats**
     56 
     57 First solve: [ehnryx](/profile/ehnryx "Candidate Master ehnryx") at 00:04:05
     58 
     59 Breakdown of results for submissions that passed pretests
     60 
     61 ```
     62 OK 2694 (63.81%)
     63 WRONG_ANSWER 1064 (25.20%)
     64 CHALLENGED 448 (10.61%)
     65 RUNTIME_ERROR 11 (0.26%)
     66 TIME_LIMIT_EXCEEDED 4 (0.09%)
     67 MEMORY_LIMIT_EXCEEDED 1 (0.02%)
     68 TOTAL 4222
     69 ```
     70 
     71 **New Year and Arbitrary Arrangement**
     72 
     73 The main trickiness of this problem is that the sequence could potentially get arbitrary long, but we want an exact answer. In particular, it helps to think about how to reduce this problem to figuring out what state we need to maintain from a prefix of the sequence we've built in order to simulate our algorithm correctly. This suggests a dynamic programming approach.
     74 
     75 For our dp state, we need to keep track of something in our prefix. First, the most obvious candidate is we need to keep track of the number of times 'ab' occurs in the prefix (this is so we know when to stop). However, using only this is not enough, as we can't distinguish between the sequences 'ab' and 'abaaaa'. So, this suggests we also need to keep track of the number of 'a's.
     76 
     77 Let *dp*[*i*][*j*] be the expected answer given that there are *i* subsequences of the form 'a' in the prefix and *j* subsequences of the form 'ab' in the prefix.
     78 
     79 Then, we have something like *dp*[*i*][*j*] = (*p**a* * *dp*[*i* + 1][*j*] + *p**b* * *dp*[*i*][*i* + *j*]) / (*p**a* + *p**b*). The first term in this sum comes from adding another 'a' to our sequence, and the second comes from adding a 'b' to our sequence. We also have *dp*[*i*][*j*] = *j* if *j* ≥ *k* as a base case. The answer should be *dp*[0][0].
     80 
     81 However, if we run this as is, we'll notice there are still some issues. One is that *i* can get arbitrarily large here, as we can keep adding 'a's indefinitely. Instead, we can modify our base case to when *i* + *j* ≥ *k*. In this case, the next time we get a 'b', we will stop, so we can find a closed form for this scenario. The second is that any 'b's that we get before any occurrences of 'a' can essentially be ignored. To fix this, we can adjust our answer to be *dp*[1][0].
     82 
     83 **stats**
     84 
     85 First solve: [dotorya](/profile/dotorya "Legendary Grandmaster dotorya") at 00:16:46
     86 
     87 Breakdown of results for submissions that passed pretests
     88 
     89 ```
     90 OK 449 (99.78%)
     91 WRONG_ANSWER 1 (0.22%)
     92 TOTAL 450
     93 ```
     94 
     95 **New Year and Entity Enumeration**
     96 
     97 Let's ignore *T* for now, and try to characterize good sets *S*.
     98 
     99 For every bit position *i*, consider the bitwise AND of all elements of *S* which have the *i*-th bit on (note, there is at least one element in *S* which has the *i*-th bit on, since we can always ![](https://espresso.codeforces.com/710f28a2927ce8a5a35e7f62fe8d16bc2c056701.png) by *m*). We can see that this is equivalent to the smallest element of *S* that contains the *i*-th bit. Denote the resulting number as *f*(*i*).
    100 
    101 We can notice that this forms a partition of the bit positions, based on the final element that we get. In particular, there can't be a scenario where there is two positions *x*, *y* with ![](https://espresso.codeforces.com/59e90e6cdfed6f36209e8e9fca0f686b2f278330.png) such that ![](https://espresso.codeforces.com/40f1304cd24586697113a18ab9333014b5864a06.png). To show this, let ![](https://espresso.codeforces.com/949010f9bb7225b59b8c3f579227a21a6bf521ae.png), and without loss of generality, let's assume ![](https://espresso.codeforces.com/99ea9a7553282046d6819e24654114ff1122c35a.png) (it can't be simultaneously equal to *f*(*x*), *f*(*y*) since ![](https://espresso.codeforces.com/59e90e6cdfed6f36209e8e9fca0f686b2f278330.png)). If the *x*-th bit in *b* is on, we get a contradiction, since *b* is a smaller element than *f*(*x*) that contains the *x*-th bit. If the *x*-th bit in *b* is off, then, ![](https://espresso.codeforces.com/75d2412a633546b11fc2a81fc9dd2b1df58e69a1.png) is a smaller element of *S* that contains the *x*-th bit.
    102 
    103 So, we can guess at this point that good sets *S* correspond to partitions of {1, 2, ..., *m*} one to one.
    104 
    105 Given a partition, we can construct a valid good set as follows. We can observe that a good set *S* must be closed under bitwise OR also. To prove this, for any two elements ![](https://espresso.codeforces.com/2fedfcf521d51216800061f2361f0f6777c812d6.png), ![](https://espresso.codeforces.com/77cb31cd569023d5a395ded905faf798466eb6ee.png). Since the latter is some composition of XORs and ANDs, it it also in *S*. So, given a partition, we can take all unions of some subset of the partitions to get *S*.
    106 
    107 For an actual solution, partitions can be computed with bell numbers, which is an *O*(*m*2) dp (see this: <http://mathworld.wolfram.com/BellNumber.html> ).
    108 
    109 Now, back to *T*, we can see that this decides some partitions beforehand. In particular, for each bit position, we can make a *n*-bit mask denoting what its value is in each of the *n* given values. The partitions are based on what these masks are. We can find what the sizes of these splits are, then multiply the ways to partition each individual split together to get the answer.
    110 
    111 **stats**
    112 
    113 First solve: [Petr](/profile/Petr "Legendary Grandmaster Petr") at 00:26:54
    114 
    115 Breakdown of results for submissions that passed pretests
    116 
    117 ```
    118 OK 166 (100.00%)
    119 TOTAL 166
    120 ```
    121 
    122 **New Year and Rainbow Roads**
    123 
    124 Let's make a few simplifying observations
    125 
    126 * It is not optimal to connect a red and blue point directly: Neither Roy or Biv will see this edge.
    127 * If we have a sequence like red green red (or similarly blue green blue), it is not optimal to connect the outer two red nodes. We can replace the outer edge with two edges that have the same weight. This replacement will form some cycle in the red-green points, so we can remove one of these edges for a cheaper cost.
    128 
    129 With these two observations, we can construct a solution as follows. First, split the points by the green points. Each section is now independent. There are then two cases, the outer green points are not directly connected, in which case, we must connect all the red/blue points in the line (for 2 * length of segment weight), or the outer green points are directly connected, in which case, we can omit the heaviest red and blue segment (for 3 * length of segment — heaviest red — heaviest blue). Thus, this problem can be solved in linear time.
    130 
    131 Be careful about the case with no green points.
    132 
    133 **stats**
    134 
    135 First solve: [Petr](/profile/Petr "Legendary Grandmaster Petr") at 00:38:32
    136 
    137 Breakdown of results for submissions that passed pretests
    138 
    139 ```
    140 OK 246 (90.44%)
    141 WRONG_ANSWER 24 (8.82%)
    142 RUNTIME_ERROR 2 (0.74%)
    143 TOTAL 272
    144 ```
    145 
    146 **New Year and Original Order**
    147 
    148 This is a digit dp problem. Let's try to solve the subproblem "How many ways can the i-th digit be at least j?". Let's fix j, and solve this with dp. We have a dp state dp[a][b][c] = number of ways given we've considered the first *a* digits of *X*, we need *b* more occurrences of digits at least *j*, and *c* is a boolean saying whether or not we are strictly less than *X* or not yet.
    149 
    150 For a fixed digit, we can compute this dp table in *O*(*n*2) time, and then compute the answers to our subproblem for each *i* (i.e. by varying *b* in our table).
    151 
    152 **stats**
    153 
    154 First solve: [dotorya](/profile/dotorya "Legendary Grandmaster dotorya") at 00:49:58
    155 
    156 Breakdown of results for submissions that passed pretests
    157 
    158 ```
    159 OK 46 (100.00%)
    160 TOTAL 46
    161 ```
    162 
    163 **New Year and Boolean Bridges**
    164 
    165 First, let's find connected components using only AND edges. If there are any XOR edges between two nodes in the same component, the answer is -1.
    166 
    167 Now, we can place all components in a line. However, it may be optimal to merge some components together. It only makes sense to merge components of size 2 or more, of which there are at most *k* = *n* / 2 of them.
    168 
    169 We can make a new graph with these *k* components. Two components have an edge if all of the edges between them are OR edges, otherwise, there is no edge.
    170 
    171 We want to know what is the minimum number of cliques needed to cover all the nodes in this graph. To solve this, we can precompute which subsets of nodes forms a clique and put this into some array. Then, we can use the fast walsh hadamard transform to multiply this array onto itself until the element 2*k* - 1 is nonzero. Naively, this is *O*(2*k* * *k*2), but we can save a factor of *k* by noticing we only need to compute the last element, and we don't need to re-transform our input array at each iteration.
    172 
    173 **stats**
    174 
    175 First solve: [dotorya](/profile/dotorya "Legendary Grandmaster dotorya") at 01:49:01
    176 
    177 Breakdown of results for submissions that passed pretests
    178 
    179 ```
    180 OK 10 (100.00%)
    181 TOTAL 10
    182 ```