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 , 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  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  such that . To show this, let , and without loss of generality, let's assume  (it can't be simultaneously equal to *f*(*x*), *f*(*y*) since ). 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,  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 , . 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 ```