NALP's blog

By NALP, 11 years ago, translation, In English

Task A. Double Cola

Let's designate characters on the first letter of the name. The queue looks like: SH-L-P-R-G, through 5 cans: SH-SH-L-L-P-P-R-R-G-G, through 10 cans: SH-SH-SH-SH-L-L-L-L-P-P-P-P-R-R-R-R-G-G-G-G.

The regularity is clear, and the solution is very simple: we will be iterated on p - we will find such minimum p that 5· 2p > n (thus if this number is less or equally we will subtract it from n) then we know that at first 2p Sheldon's stand, then 2p Leonard's and so on. And now we can easily answer who took a can number n (namely there was a person with number n / 2p in sequence SH-L-P-R-G (in 0-indexation).

Task B. Sets

For the solution the following important fact is required to us: we will admit elements v and u are in one set then in any of n· (n - 1) / 2 of sequences from the input data where meets v  u necessarily meets. And also if v and u are in different sets there is such sequence in which is v, but isn't present u. Then it is possible to enter the equivalence relation for all elements of all sets - two elements are equivalent, if there is no sequence where one element meets, and another isn't present. Classes of equivalence also are required sets.

It was possible to consider the answer as following algorithm: we will write out for each number the list of numbers of sequences where there is this number, and will unite two numbers if these lists are equal. This algorithm can be realized for O(n2 * log(n)) however the solution for O(n3) passes all tests with time large supply too.

The special case is a test with n = 2. This test was used for a considerable quantity of hacks.

Task C. General Mobilization

At first we will estimate from above the maximum time to which all divisions will reach capital - obviously it is required no more n days for this purpose. Therefore restrictions quite allowed model movements of divisions. The key moment of the solution - we will always consider divisions in priority order. Then in every day we will consider the list of those divisions who hasn't reached yet capital, and we will put in priority order on the necessary train. If the train is already filled, the division remains in a current city, differently we will change its position, and in day when the division will reach capital we will write down the answer. Total: in total days which it is necessary model, no more n, and every day we move no more n divisions. So our solution has asymptotic form no more O(n2)

The solutions using various structures of the data (sets, turns with priorities etc.) work for O(n2· log(n)) and it didn't always keep within in TL.

Task D. Two out of Three

The problem dares the dynamic programming. We will consider a state (i, j) meaning that in the current turn there is a person number i and also all people from j to n inclusive. Any turn achievable of the initial can be presented by corresponding condition. The quantity of conditions is O(n2), the quantity of transitions is only 3, that is O(1). So the total asymptotic form is O(n2).

Task E. Corridor

This problem has some solutions based on the various methods of the search of the area of the association of the figures on a plane. One of such methods is the method of vertical decomposition (more in detail you can esteem in various articles) and also it was possible to notice that among figures there are no three having non-zero crossing and consequently was to learn to find a total area of two figures enough. For this purpose also it was possible to use the various methods, for example, the author's solution is based on algorithm of cutting off of a convex polygon by a semiplane. Authors supposed the solution for O(n2).
  • Vote: I like it
  • +16
  • Vote: I do not like it

7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

This English is really cryptic. I believe there might be a typo in the authors editorial for Task A. Through 10 cans, you arrive at the queue P-R-R-G-G-SH-SH-SH-SH-L-L-L-L-P-P. However, on 20 cans you arrive at the queue SH-SH-SH-SH-L-L-L-L-P-P-P-P-R-R-R-R-G-G-G-G.

So, I can kind of see the pattern the author talks about like so: 0: 5 = 5*2^0, 5: 10 = 5*2^1, 15: 20 = 5*2^2, ...,

I'm not crystal clear with the final mathematical expression that we are to base our code on, though. Could anyone help?

  • »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think the author means something like this:

    let's call distribution to a new queue, that is a queue that is formed when all people in a previous queue has taken their can.

    a special case is the first queue, it is: SH-L-P-R-G

    so when the first queue is finished we created a new queue (distribution), the second queue is: SH-SH-L-L-P-P-R-R-G-G

    when we finish with it the next distribution will be SH-SH-SH-SH-L-L-L-L-P-P-P-P-R-R-R-R-G-G-G-G.

    and so on.

    so we have to reach the nth distribution such as (5.2p) > n where p is the nth distribution, once in the nth distribution we can get easily the name of the person who take the can.

7 years ago, # |
  Vote: I like it 0 Vote: I do not like it


6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i dont get what the author is trying to say in problem A.can somebody please explain?