Tuesday, October 28, 2008 Match summaryThe match atracted 66 competitors. Coders were faced with standard Easy problem, a little bit easier Medium and a little bit harder Hard problem. Success rate for Easy problem was low  only 56.52%. Only 5 coders managed to solve Hard problem correctly. First submission was made by bbi5291 who submitted Easy problem for 234.32 points. tourist was the first who submitted all the problems and won the match. tourist showed great performance scoring the fastest time on each problem  congrats! Challenge and System test phase didn't make any changes in the first five places that were occupied by tourist, SourSpinach, gnocuil, ikicic and devilkind, respectively. The ProblemsWordsPuzzleUsed as: Division One  Level One:
This problem is really straightforward. Basically, the most important thing is to carefully read the problem statement and implement string replacing, because for finding substrings one can use builtin function. The constraints are very low, so the most naive algorithm will pass in time.
Below is shown a pseudocode for finding the number of different words from
According to the part of problem statement "...to replace at most two letters...", it is clear that we should check for the solution when:
countSWords , we can easily write the rest of the solution:
For fast and clean solution you can take a look at sajninredoc's
solution.
You can also take a look at UranusX's
interesting solution.
Note that for two fixed mainWord letters ltr1 and ltr2 ,
if we consider (ltr1 , ltr2 ) the same as (ltr2 , ltr1 )
(practically, to check only one combination of two letters) then we can't consider
(word1 , word2 ) the same as (word2 , word1 ), and vice versa.
In case we did so, only one of these two replacements would be checked:
Used as: Division One  Level Two:
This problem was a bit easier then usual TCHS Medium. The reason behind that was a bit harder Hard problem.
Milena made a decision to do nothing complex, she chose very basic stepping. So after all, our task was
to go from given
When we choose a path, we should make at most For nice and clean solution you can take a look at ikatanic's solution. HomeworkInitially, a bit harder version was proposed. The version asked to return the number of turned on lights if light bulbs are turned on recursively  "If a light bulb below some cell becomes turned on, lights below all neighboring cells also become turned on (and their neighbors will be turned on as well, and so on)". So making only one step in Example 5 is enough to turn on all the lights. You can try to solve this version of the problem if the maximal size of the floor is 1000x1000. ColoringRectanglesUsed as: Division One  Level Three:
I see several approaches for this problem. In each of them we should calculate the visible area of each rectangle in order to choose rectangles that should be colored. After these areas are calculated, we should just color rectangles in descending order of their visible areas. If several rectangles have the same visible areas, the rectangle with the smallest index must be colored first (in order to achieve lexicographical minimality of result). Probably, the most intuitive calculation of visible area for rectangle rect with index idx, is to start with polygon rect and discard the part of polygon that overlaps with rectangle with index idx+1. Then new polygon should be checked againts rectangle with index idx+2, and so on. At some moment, after discarding overlapping part, from one polygon we can get two. This method can become very complex and that kind of solution is too hard for 1100. Another way to solve it is to use some kind of "flood fill" algorithm  i.e. fix ycoordinate and make partition x_1, x_2, ..., x_m of the segment [10000, 10000] in such way that x_(j+1)x_j is maximal and each x, x_j < x < x_(j+1), belongs to only one rectangle. This kind of solution can be very interesting and we can discuss it at the forum. As you see, the idea is to break longer segment into chunks that can easily be used to calculate the visible area of a rectangle. Now, the question is how to assign a chunk to the corresponding rectangle. One way is to go by chunks and maintain for each chunk the highest index of rectangle that contains it. Another way is to pass over all rectangles, starting from one with the highest index, and assign to each rectangle all unassigned chunks that belong to it. Maybe at the moment the second way seems a bit unlogical, because it is slower than the first one and the first works very nice, but we will see that similar idea as in the second approach will be used in the final solution. We can also find that there is an approach that is very easy for coding. We can try to represent the Cartesian plane as the matrix of 20000x20000 unit squares. If we have such matrix, then for each rectangle we can mark its unit squares  if one unit square should be marked to belong to more than one rectangle, then we mark as belonging to the one with highest index. The problem with this approach is that we don't have enough memory for such matrix and it is too slow. However, it could be a very useful idea if the constraints were smaller. Ok, let's summarize: the first approach is probably too complex; the third approach takes too much resources; the first way of the second approach is very good, but we should do that for each y, y_min ≤ y ≤ y_max, and what if we raised constraints and set y_max  y_min = 10^9? Combining both ways gives us solution that doesn't not depend on how big x and y are, it depends only on the number of rectangles. It would be great if we can divide the plane into some chunks that are twodimensional. In our case, the best and the most intuitive is if those chunks are rectangles. I will describe the solution and then explain it. Take x coordinates of all rectangles' vertical sides, let it be allx. In the same way, take y coordinates of all rectangles' horizontal sides, let it be ally. Sort allx, sort ally. After sorting, allx will contain coordinates x_1, x_2, ..., x_m, such that x_i ≤ x_(i+1). The same holds for ally. Then for each rectangle rectChunk with lowerleft corner in (x_i, y_j) and upperright corner in (x_(i+1), y_(j+1)), for all i, 1 ≤ i < m, and for all j, 1 ≤ j < m, check whether rectChunk belongs to some of the given rectangles and if it belongs, mark it as a part of rectangle with the highest index.Basically, the idea is to divide the plane into stripes by x coordinates and into stripes by y coordinates and then to combine these stripes in order to get rectangle chunks. To get it more clear, please take a look at the image below (it contains the rectangle chunks that are made from Example 0):
Also, note that all rectangles are covered by these chunks. allx contains maximal and minimal xcoordinate of all rectangles. In the same way, ally contains maximal and minimal ycoordinate of all rectangles. So, ith ystripe is divided by all xstripes making chunks that cover area from x_min to x_max in the ith ystripe. Summing up all ystripes, we get that all rectangles are covered. And the last thing we should show is that some rectangle chunk rectChunk belongs to only one rectangle (except its area is 0, but that kind of chunk is not important in this case). If we suppose it is not true, that means there is some xsegment or ysegment that intersects rectChunk, but it is impossible because all x and y coordinates of all rectangles are included and chunks are made from those consecutive coordinates. Having solution described and several short facts explained, it should be easy to code the solution and, the most important, to see why it is correct. For nice and clean solution you can take a look at devilkind's solution. I have found gnocuil's solution as a very interesting one. Basically, he is using the same idea with chunks, but he is doing that recursivelly, sometimes checking less number of chunks that just described solution does. HomeworkCan you find the maximal number of polygons that can be constructed using the very first approach? 
