471.md (19926B)
1 Source: https://codeforces.com/blog/entry/13986 2 3 ## [471A - MUH and Sticks](/contest/471/problem/A "Codeforces Round 269 (Div. 2)") 4 5 Given six sticks and their lengths we need to decide whether we can make an elephant or a bear using those sticks. The only common requirement for both animals is that four leg-sticks should have same length. This means that the answer "Alien" should be given **only** if we can't find four sticks for the legs. Otherwise we will be able to make some animal. The type of the animal will depend on the relation of the remaining sticks' lengths. If they are equal then it will an elephant, if they are different we will have a bear. 6 7 So this algorithm should solve the problem: 8 9 1. Find the number which appears at least four times in the input. 10 2. If no such number exist then the answer is "Alien". 11 3. Otherwise remove four entries of that number from the input. 12 4. After removing that number you will have two numbers left, compare them and decide whether it's an elephant or a bear. 13 14 One shortcut for this problem might be to sort the input array, then if it's a bear or an elephant then 3rd and 4th elements in the sorted should be animal's legs. So you can assume that one of these numbers is the length of the leg and count how many times you see this number in the input. 15 16 Author's solution: [7977022](/contest/471/submission/7977022 "Submission 7977022 by marat.snowbear") 17 18 Since the numbers in the input are very small you can implement 'brute force' solution as well. By brute force solution in this case I mean that you can actually check all possible values for leg-length, head-length and body-length. If in total they give the same set as the input then you found a matching, all you need is to check whether it's a bear or an elephant. And it's an alien if you checked all possible combinations and found nothing matching to the input. Though in this case the brute force solution is not easier than another one. 19 20 Checking all possible lengths solution: [7975645](/contest/471/submission/7975645 "Submission 7975645 by marat.snowbear") 21 22 It seems that there were two common mistakes people were making in this problem: 23 24 1. Not taking into account that legs can be of the same length as body or head. So you can't just count the number of distinct numbers in the input to decide which type of animal is that. We assumed that people might make such a mistake, there was a relevant warning in the statement. 25 2. Trying to sort the input and then check whether some elements in this array are equal to other elements and based on this comparison decide which type of animal is that. People were simply making mistakes when deciding which elements to compare. The correct way to implement this is: 26 27 ``` 28 // 0-indexing below, array is assumed to be sorted 29 30 if (l[0] == l[3]) cout << (l[4] == l[5] ? "Elephant" : "Bear"); 31 else if (l[1] == l[4]) cout << "Bear"; 32 else if (l[2] == l[5]) cout << (l[0] == l[1] ? "Elephant" : "Bear"); 33 else cout << "Alien"; 34 ``` 35 36 Solution: [7977214](/contest/471/submission/7977214 "Submission 7977214 by marat.snowbear") 37 38 This solution seems to be shorter but there are many failed solutions like this because people were not paying enough attention to the details. So I would prefer implementing more straightforward approach. 39 40 Hope you liked the pictures! 41 42 --- 43 44 ## [471B - MUH and Important Things](/contest/471/problem/B "Codeforces Round 269 (Div. 2)") 45 46 You need to check whether exist three pairwise different permutations of the indices of the input which result in array being sorted. Generally you can count the number of total permutation which give non-decreasing array. This number might be very large and it might easily overflow even long integer type. And what is more important is that you don't actually need to count the exact number of such permutations. 47 48 Let's tackle this problem from another angle. Assume you already sorted the input array and you have the corresponding permutation of indices. This already gives you one array for the result, you only need to find two more. Let's look for any pair of equal numbers in the input array, if we swap them then we will get another valid permutation. And if we find one more pair of equal numbers then swapping them you can get third permutation and that will be the answer. You need to keep in mind here that one of the indices when swapping the second time might be the same as one of the numbers in the first swap, that's ok as soon as second index is different. So all you need to do is to find two pairs of indices which point to the equal elements. 49 50 The entire algorithm is as follows: 51 52 1. Transform the input array into array of pairs (tuples), first element of the pair will be the number given in the input array, the second element will be the index of that number. 53 2. Sort that array of pairs by the first element of the pairs. Then the second elements will give you one correct permutation. 54 3. Scan this array in order to find possible swaps. You just iterate over this array and check if the first element in the current pair equals to the first element of the previous pair. If it equals you remember the indices of these two pairs. You stop scanning the array as soon as you have two swaps. 55 4. Then you check how many swaps you have, if you have less than two swaps then there are no three distinct permutations. 56 5. Otherwise you have two swaps which means that you have an answer. So you print the current permutation, then you execute the first swap (you just swap those two elements you remembered in the first swap), then you print the permutation array received after executing that swap. And you execute the second swap and print the permutation array third time. 57 58 Author's solution: [7977528](/contest/471/submission/7977528 "Submission 7977528 by marat.snowbear") 59 60 --- 61 62 ## [471C - MUH and House of Cards](/contest/471/problem/C "Codeforces Round 269 (Div. 2)") 63 64 Card house. This problem required some maths, but just a little bit. So in order to start here let's first observe that the number of cards you need to use for a complete floor with *R* rooms equals to: 65 66 *C* = *C**rooms* + *C**ceiling* = 2·*R* + (*R* - 1) = 3·*R* - 1 67 68 Then if you have *F* floors with *R**i* rooms on the *i*-th floor then the total number of cards would be: 69 70  71 72 where *R* is the total number of the rooms in the card house. 73 74 This already gives you an important property — if you divide *N* + *F* on 3 then the remainder of this division should be 0. This means that if you have found some minimum value of floors somehow and you found maximum possible number of floors in the house, then within that interval only every third number will be a part of the solution, the rest of the numbers will give a non-zero remainder in the equation above. 75 76 Now let's think what is the highest house we can build using *N* cards. In order to build the highest possible house obviously you need to put as few cards on each floor as you can. But we have a restriction that every floor should have less rooms than the floor below. This gives us the following strategy to maximize the height of the house: we put 1 room on the top floor, then 2 rooms on the floor below, then 3 rooms on the next floor, etc. In total then the number of cards we will need equals to: 77 78  79 80 This is minimum number of cards we need in order to build a house with *F* floors. This gives us a way to calculate the maximum height of the house we can build using *N* cards, we just need to find maximum *F* which gives *N**min* < = *N*. Mathematicians would probably solve the quadratic inequation, programmers have two options: 81 82 1. Check all possible *F* until you hit that upper bound. Since *N**min* grows quadratically with *F* then you will need to check only up to  numbers. This gives  time complexity and fits nicely in the given time limit. 83 2. The second approach would be a binary search. Using binary search to find maximum number of the floors would give you *O*(*logN*) time complexity. This was the intended originally solution but it was decided to lower the constraints in order to allow sqrt solutions as well. 84 85 Now that you know the maximum number of the floors in the house you might need to correct it a bit because of that remainder thing we discussed above, this might make your maximum height one or two floors lower. Looking again at the remainder discussion on top we can see that starting from here only every third number will be valid for an answer. Now you can either count them brutally (back to  solution) or you can simply calculate them using this formulae: 86 87 *ans* = (*F**max* + 3 - 1) / 3 (integer division) 88 89 That seems to be it, just don't forget to use longs all the time in this problem. 90 91 Author's *O*(*logN*) solution: [7977863](/contest/471/submission/7977863 "Submission 7977863 by marat.snowbear") 92 93 Authors  solution: [7977888](/contest/471/submission/7977888 "Submission 7977888 by marat.snowbear") 94 95 --- 96 97 ## [471D - MUH and Cube Walls](/contest/471/problem/D "Codeforces Round 269 (Div. 2)") 98 99 In this problem we are given two arrays of integers and we need to find how many times we can see second array as a subarray in the first array if we can add some arbitrary constant value to every element of the second array. Let's call these arrays *a* and *b*. As many people noticed or knew in advance this problem can be solved easily if we introduce difference arrays like that: 100 101 *aDiff**i* = *a**i* - *a**i* + 1 (for every *i* = = 0..*n* - 1) 102 103 If we do that with both input arrays we will receive two arrays both of which have one element less than original arrays. Then with these arrays the problem simply becomes the word search problem (though with possibly huge alphabet). This can be solved using your favourite string data structure or algorithm. Originally it was intended to look for linear solution but then we made time limit higher in case if somebody will decide to send *O*(*NlogN*) solution. I haven't seen such solutions (that is understandable) but some people tried to squeeze in a quadratic solution. 104 105 Linear solution can be made using Z-function or KMP algorithm. In order to add a logarithmic factor you can exercise with suffix array for example. I had suffix array solution as well, but it's a lot messier than linear solution. 106 107 There is one corner case you need to consider — when Horace's wall contains only one tower, then it matches bears' wall in every tower so the answer is *n*. Though for some algorithms it might not even be a corner case if you assume that empty string matches everywhere. Another error which several people did was to use actual string data structures to solve this problem, so they converted the differences to chars. This doesn't work since char can't hold the entire range an integer type can hold. 108 109 I didn't think that switching to difference arrays will be that obvious or well-known, so I didn't expect that this problem will be solved by that many people. 110 111 Author's Z-function *O*(*n* + *w*) solution: [7978022](/contest/471/submission/7978022 "Submission 7978022 by marat.snowbear") 112 113 Author's suffix array *O*((*n* + *w*)·*log*(*n* + *w*)) solution: [7978033](/contest/471/submission/7978033 "Submission 7978033 by marat.snowbear") 114 115 --- 116 117 ## [471E - MUH and Lots and Lots of Segments](/contest/471/problem/E "Codeforces Round 269 (Div. 2)") 118 119 Given a set of horizontal/vertical lines you need to erase some parts of the lines or some lines completely in order to receive single connected drawing with no cycles. 120 121 First of all let's go through naive *N*2 solution which won't even remove cycles. In order to solve this problem you will need a DSU data structure, you put all your lines there and then for every pair of horizontal and vertical line you check if they intersect and if they do you join them in DSU. Also your DSU should hold the sum of the lengths of the joined lines. Initially it should be equal to the line lengths. Since there might be up to *N*2 / 4 intersections between lines we receive a quadratic solution. 122 123 Now let's get rid of cycles. Having the previous solution we can do it pretty easily, all we need is to change the way we were connecting the sets in DSU if some lines intersect. Previously we were simply asking DSU to join them even if they already belong to the same set. Now what we will do is when finding some pair of lines which intersects and is already joined in DSU instead of asking DSU to join them again we will ask DSU to decrement their length sum. In terms of the problem it is equivalent to erasing a unit piece of segment in the place where these two lines intersect and this will break the cycle. With this change we already have a correct solution which is too slow to pass the time limits. 124 125 Now we need to make our solution work faster. We still might have up to *N*2 / 4 intersections so obviously if we want to have a faster solution we can't afford to process intersections one by one, we need to process them in batches. All our lines are horizontal and vertical only, so let's do a sweep line, this should make our life easier. 126 127 Let's assume that we're sweeping the lines from the left to the right. Obviously then the code where the intersections will be handled is the code where we process the vertical line. Let's look at this case closer. We can assume that we're going to add some vertical line on with coordinates (*x*, *y*1, *x*, *y*2), we can also assume that there are some horizontal lines which go through the given *x* coordinate, we track this set of lines while sweeping left to right. So we're going to add a vertical line and let's say that it has *n* intersections with horizontal line. Previously we were handling each intersection separately, but you can see that if some horizontal lines already belong to the same set in DSU and they go next to each other then we don't need to handle them one by one anymore. They already belong to the set in DSU so there is no need to join them, we might only need to count the number of them between *y*1 and *y*2 coordinates, but that can be calculated in logarithmic time. So the trick to get rid of quadratic time complexity is to avoid storing horizontal lines one by one and store instead an interval (across y coordinate) of horizontal lines which belong to the same set in DSU. I will call these intervals **chunks**. You will need to manipulate these chunks in logarithmic time and you will need to locate them by y coordinate so you need to store them in a treap or a STL map for example with *y* coordinate serving as a key. 128 129 To be clear let's see what data each of these chunks will hold: 130 131 ``` 132 struct chunk{ 133 int top, bottom; // two coordinates which describe the interval covered by the chunk 134 int id; // id of this chunk in DSU. Several chunks might have the same id here if they belong to the same set in DSU 135 }; 136 ``` 137 138 And we agreed that data structure which holds these chunks can manipulate them in logarithmic time. 139 140 Let's now get into details to see how exactly it works. While sweeping we will have one of three possible events (listed in the order we need to handle them): new horizontal line starting, vertical line added, horizontal line finishing. First and third operation only update our chunks data structure while the second operation uses it and actually joins the sets. Let's look into each of these operations: 141 142 **horizontal line start**. We need to add one more chunk which will consist of a single point. The only additional operation we might need to do happens when this new line goes through some chunk whose interval already covers this point. In this case we need to split this covering chunk into two parts — top and bottom one. It's a constant number of updates/insertions/removals in our chunk data structure and we agreed that each of these operations can be done in logarithmic time so the time complexity of a single operation of this time is *O*(*logN*). It should be also mentioned here that during processing a single operation of this type we might add at most two new blocks. Since in total we have no more than *N* operations of this type them it means that in total we will have no more than 2·*N* blocks created. This is important for the further analysis. 143 144 **vertical line**. In this operation we need to find all chunks affected by this vertical line and join them. Each join of two chunks takes logarithmic time and we might have up to *n* chunks present there, so we might need up *O*(*NlogN*) time to draw a single vertical line. This doesn't give us a good estimate. But we can see that we have only two ways to get new chunks — they are either added in the step 1 because it's a new line or one chunk is being split into two when we add a line in between. But we have an upper bound on total number of the chunks in our structure as shown above. Ans since we have such an upper bound then we can say that it doesn't matter how many chunks will join a single vertical line because in total all vertical lines will not join more than 2·*N* chunks. So we have an amortized time complexity analysis here, in total all vertical line operations will take *O*(*NlogN*) time. 145 146 There are some other details we need to handle here. For example we need to avoid cycles correctly. This margin is too narrow to contain the proof but the formulae to correct the length sum is like this: 147 148 *d* = *y*2 - *y*1 - (*N**intersections* - 1) + *N**distinctsets* - 1 149 150 where *d* — the number you need to add to the sum of the lengths in DSU 151 152 *N**intersections* — number of horizontal lines intersecting with the given vertical line, I used a separate segment tree to get this value in *O*(*logN*) 153 154 *N**distinctsets* — number of distinct sets in DSU joined by this vertical line, you need to count them while joining 155 156 So this gives you a way to correct the lengths sums. There is one more thing that needs to be mentioned here — it might happen that your vertical line will be contained by some chunk but will not intersect any horizontal lines in it. In this case you simply ignore this vertical line as if it doesn't overlap any chunk at all. 157 158 **horizontal line end**. Finally we came here and it seems to be simple. When some horizontal line ends we might need to update our chunks. There are three cases here: 159 160 a. This line is the only line in the chunks — we simply delete the chunk then. 161 162 b. This line lays on some end of the interval covered by the chunk — we update that end. In order to update it we need to know the next present horizontal line or the previous present horizontal line. I used the same segment tree mentioned above to handle these queries. 163 164 c. This line lays inside some chunk — we don't need to update that chunk at all. 165 166 And that's it! In total it gives *O*(*NlogN*) solution. 167 168 Author's solution: [7978166](/contest/471/submission/7978166 "Submission 7978166 by marat.snowbear") (that chunk data structure is called 'linked_list' in the code because originally I thought it would be a linked list with some way to manipulate it quickly and later I removed all the list functionality). 169 170 --- 171 172 This editorial was written very late in the night, I'm pretty sure there are tons of typos here, I will proof read it tomorrow, but please don't hesitate to report typos and some minor error to be fixed in private messages.