Match summary

The 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 Problems

WordsPuzzle

Used as: Division One - Level One:

Value 250

Submission Rate 42 / 62 (67.74%)

Success Rate 26 / 42 (61.90%)

High Score tourist for 236.26 points (6 mins 55 secs)

Average Score 160.87 (for 26 correct submissions)

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 built-in function. The constraints are very low, so the most naive algorithm will pass in time.

Below is shown a pseudo-code for finding the number of different words from secretWords that occur as substrings within some given string str:

int countSWords(String str)
  ret = 0
  for each word w from secretWords
    if w is substring of str
      ret = ret + 1
  return ret
end countSWords

According to the part of problem statement "...to replace at most two letters...", it is clear that we should check for the solution when:

there are no replacements
one letter is replaced
two letters are replaced

Knowing this and having the method countSWords, we can easily write the rest of the solution:

ret = countSWord(mainWord) // no replacements
// one replacement
for each letter ltr of mainWord
  for each word w1 from optionalWords
    string newStr = replace ltr of mainWord with w1
    ret = max(ret, countSWords(newStr)
    
// two replacements
for each letter ltr1 of mainWord
  for each letter ltr2 of mainWord different from ltr1
    for each word w1 from optionalWords
      for each word w2 from optionalWords different from w1 // each word can be used at most once
          string newStr = replace ltr1 and ltr2 of mainWord with w1 and w2, respectively
        ret = max(ret, countSWords(newStr)
return ret

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:

ltr1 is replaced with word1 and ltr2 is replaced with word2
ltr1 is replaced with word2 and ltr2 is replaced with word1

But it's not correct, because we have to check both these replacements, we can't skip any of them.

TurnOnTheLights

Used as: Division One - Level Two:

Value 500

Submission Rate 32 / 62 (51.61%)

Success Rate 22 / 32 (68.75%)

High Score tourist for 475.11 points (6 mins 34 secs)

Average Score 353.73 (for 22 correct submissions)

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 row and col in four possible directions - that gives four possible paths.

When we choose a path, we should make at most K steps along it. Note that this "at most" is placed only to tell that we don't need to worry if some i-th step (i ≤ K) is out of the floor. It is always better to make as much steps as possiblebecause each step can only turn on a light, so making more steps can only increase the result. After we conclude these several facts, the only part that should be done is to turn on the light of each good cell at which Milena steps, to turn on the lights of its neighboring good cells and add each light bulb that just became turned on to the result.

For nice and clean solution you can take a look at ikatanic's solution.

Homework

Initially, 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.

ColoringRectangles

Used as: Division One - Level Three:

Value 1100

Submission Rate 7 / 62 (11.29%)

Success Rate 5 / 7 (71.43%)

High Score tourist for 900.78 points (14 mins 1 secs)

Average Score 716.26 (for 5 correct submissions)

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 y-coordinate 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 two-dimensional. 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 lower-left corner in (x_i, y_j) and upper-right 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):

Note that two rectangle chunks do not overlap, except they can share a side. It is easy to prove because for two rectangle chunks with coordinates (x_i, y_j)-(x_(i+1), y_(j+1) and (x_k, y_m)-(x_(k+1), y_(m+1)), either x_(i+1)≤x_k or x_(k+1)≤x_i, so they can share only a segment.

Also, note that all rectangles are covered by these chunks. allx contains maximal and minimal x-coordinate of all rectangles. In the same way, ally contains maximal and minimal y-coordinate of all rectangles. So, i-th y-stripe is divided by all x-stripes making chunks that cover area from x_min to x_max in the i-th y-stripe. Summing up all y-stripes, 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 x-segment or y-segment 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.

Homework

Can you find the maximal number of polygons that can be constructed using the very first approach?

By boba5551
TopCoder Member