vepifanov's blog

Codeforces Beta Round #37 (Tutorial)
By vepifanov, 13 years ago, translation, In English

A. Towers
The total number of towers is equal to number of different numbers in this set. To get the maximum height of the tower, it was possible to calculate for each length the number of bars with this length, and from these numbers is to choose the maximum.

B. Computer Game
Constraints in the problem allows us to solve it this way: we keep the current number of health from the boss, and current summary damage from used scrolls per second. At the next step, we choose which scrolls we can use in the current second. Of all these, we find the scroll, which causes the most damage, and apply it. If at some point we could not use any of the scrolls, and the current damage in one second does not exceed regeneration, we deduce that there are no answers. Otherwise, continue to iterate the algorithm until the number hit points will be nonnegative.

C. Old Berland Language
One of the easiest to understand solutions of this problem is as follows: sort the words in ascending order of length, while remembering their positions in the source list. We will consistently build our set, starting with the short strings: strings of length one can only be strings "0" and "1". If the number of words of length one in a set are more than two, hence there are no answers. Add the desired number of strings of length one to answer, and remove it from the current list. Then look at the string of length two: each of the remaining strings of length one can be extended in two ways (having added to each of these symbols 0 and 1). Add the desired number of strings of length two in our answer, and then increase the length of the remaining strings by one. Continue this process, until we get all words from the input set. You can see that if at some moment the number of allowable words exceeded the number of remaining, the extra words can be ignored and solution takes O (N * the maximum length of input set) time.

D. Lesson Timetable

This problem is solved by dynamic programming:

state of dynamics will be a pair of numbers - the number of current room and number of groups which have first lesson in the room with a number not exceeding the current and for which the second room is not defined yet. For each state check all possible number of groups for which the second lesson will be held in the current classroom. When you add an answer from the new state, it must be multiplied by the corresponding binomial coefficients (the number of ways to select groups which have the first lesson in next room - Xi + 1, and the number of ways to select groups which have the second lesson in the current classroom).

 

E. Trial for Chief

First, we construct the following graph: each cell we associate a vertex of the same color as the cell itself. Between neighboring cells hold an edge of weight 0, if the cells share the same color and weight of 1, if different. Now, for each cell count the shortest distance from it to the most distant black cell (denoted by D). It is easy to see that we can construct a sequence of D + 1 repainting leads to the desired coloring:

  • The first step of color all the cells at a distance less than or equal to D in black color
  • At the second step color all the cells at a distance less than or equal to D - 1 in white
  • Etc.

Of all the cells, choose the one for which this distance is minimal, and this distance increased by one will be the answer to the problem.
  • Vote: I like it
  • +32
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In the tutorial of Problem E, the way to paint the cells is brilliant. Meanwhile finding the cell to minimize D is just to optimize the solution in this way.
But how to prove that this method you paint the cells is the best? Thank you very much.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    The proof is in short looks like this:

    First, compress all vertices between which distance is equal to zero in one component (get graph of connected components).
    Note that if we repaint some cell, it can be repainted and all its component, as a result coloring will not change.

    1) we can prove that any coloring can be reduced to a form such that each subsequent repainting is a subset of the previous one.
    2) the last repainting will consist of exactly one vertex (possibly the whole monochromatic connected region of the original board).

    Therefore, one of the best answers will be of the form described in the review. If as the initial vertex, we take a cell, lying in the last repainting of the optimal sequence, the algorithm finds the solution not worse than optimal.
    Прослушать
    На латинице

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I tried to simulate exactly the algorithm described for Problem C, but it obviously times out since it requires a huge memory space. Can anybody tell me how do i optimize it? I've posted my solution here -
http://ideone.com/il8Do
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Хотелось бы чтобы отписались люди, сдавшие эту задачу и имеющие альтернативные решения.
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Well, my solution doesn't need any memory at all. Process the lengths of the words in increasing order and try to find lexicographically smallest word at each step. Suppose s is the last word written out, and its length is k. Then all strings that have length k and are lexicographically not larger than s, are 'bad' (each of them has a prefix that is already written out). So, to find out the k-prefix of the next word we need to increase s by 1 (as a binary number). Obviously, if s consists of 1's it's impossible, since we will get a word of length k+1. Now we need to find lexicographically smallest encoding of the next word. To do that, just add zeros to the increased value of s.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    This is solution of problem C from tutorial:
    http://ideone.com/lHtSZ
    → Reply