Endagorion's blog

By Endagorion, 4 years ago, In Russian,

Just a few quick notes about problems (not the full-sized editorial as usual).

A — Buildind a Bookshelf

Iterate over all possible lengths of top/floor lt and walls lw (note that they can be equal); reserve two planks of chosen lengths for each. If there are ai planks of length li left, there should at least (be careful not to divide by zero of lw = 1!) departments of width li. The number of inner walls is equal to the number of departments, except for the case when the total width of departments is equal to the width of the bookshelf (we don't need the last inner wall). Check if there are sufficient planks for inner walls, and also if the departments fit into the bookshelf; also, excessive inner walls should placed in the free space. That's an O(n3) solution; finally, notice that the floor should be longer than all the shelves, thus it makes sense to try only the two largest types of planks for the floor. Finally, O(n2).

B — Flatland Division

The most failed problem of the contest. Most accepted solutions are for this problem, I guess, due to a) it was in the beginning of the problemset, and b) this type of problem occurs frequently on many contests. I apologize for the low quality of the problem.

The idea is as follows: the dividing line can be moved so that is nearly passes throw some two cities. Iterate over the pair of these 'border' cities, and find the total population on both sides of the line; choose the best option. To speed up, fix one border city and rotate the line around it. there are O(n) events when a changes side respective to the line; sort them by angle and process iteratively. That makes up for an solution. I tried to make sure no O(n3) solutions pass, but it seems I failed even at that. =(

C — Solitaire Simplified

There is a straightforward O(n4) DP solution which basically stores all the interesting info about the state of the game; it can be probably optimized to O(n3). I will describe another, more thought-requiring solution.

Consider an inverse permutation of the deck; that is, if the i-th number of the deck is pi, numbers qi are determined by qpi = i. The number 1 will be surely thrown out on the first discarded through the cards; the number will be discarded on the first pass if q2 > q1 or q2 > q3 > ... > qn; and so on.

We see that on each pass through the cards maximal increasing prefix and maximal decreasing suffix of q will be discarded; on the next pass the new maximal monotonous prefix and suffix will be discarded and so on. Suppose there will be m passes through the deck, and the final number is k; this means that there are exactly m - 1 increases in q to the right of k, and exactly m - 1 drops (or, in other words, k - (m - 1) increases) to the left of k; thus the total number of increases will be k - 1 regardless of m. The problem reduced to a classic one: count the number of permutations of n number with exactly k - 1 increases. It can be done straightforwardly in O(n3), or even faster using some ingenious formulas.

D — Xor

Coming up.

E — Tree Growing

The information about the tree can be stored simply as a sequence of operations. The sizes of the tree after each operation will also be useful. The "+ k" is thus trivial.

Now to find the distance between two vertices. This can be divided into two tasks: finding depth (distance from the root) d(v) of the vertex v given its number, and determining depth of the LCA of two vertices; the distance is given by d(x) + d(y) - 2d(lca(x, y)).

If v = 1, the depth is clearly 0. Otherwise, the number of the subtree of the root which contains v is ⌊ (v - 1) / s, where s is the size of a single subtree. Similarly, the number of vertex v in the subtree in its original numeration is . We have reduced the problem to the similar one concerning the subtree; treat it recursively. The sequence of sizes provides all the necessary information; thus, the depth can be found in O(h), where h is the height of the tree.

To find LCA of x and y, proceed similarly; the root of the current tree if the LCA if one of x or y is the root, or they are contained in different subtrees. Thus, the depth of LCA can also be found in O(h).

Unfortunately, h can be rather large. However, there can be very few operations (less than 60) with k ≥ 2 as the total number of vertices is at most 1018. We can store the operations with k = 1 in compressed form, as they just attach one edge to the root of tree. Finally, all the operations with little enhancement can be done in O(h'), where h' is the number of operations with k > 1.

F — To Saw Or Not To Saw

If a = c, the answer is simply min(b, d) (the shortest sawtooth length).

Otherwise, suppose a > c. Consider the space between two sawtooths of (c, d)-saws; we may as well consider the (a, b)-saw wrapped up around the space. The ends of the sawtooths of (a, b)-saw form a modular sequence , which is the same set of ends as the periodical sequence with diffence ; thus the (a, b)-saw can be changed to the saw with difference but the same angle of sawtooths. Finally, we arrive at the previous situation with the common difference of ; the saw with the least steep angle of sawtooth will determine the maximal length. Thus, the answer is . Do not forget to use 64-bit integers for multiplication.

 
 
 
 
  • Vote: I like it
  • +77
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Simple solution without any data-dependens optimization: cpp java

n3 * (1 + o(1)) multiplications. cpp — 0.79 sec. java — 1.3 sec.

How possible create test agains it? Execution time depends on the value of n only. (Without any branch-prediction as possible)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The simplest method is to make n bigger, such as 2000. Obviously, solution will pass the test cases while O(n3) solution will get TLE.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Some good assimptotic solutions (sorry, ru-comment) takes with n = 1000 1.6 second. I affraid that increase n to 2000 leads to slow this solution to 1.6 * 4 = 6.4 second. O(n^3) solition will takes 0.79 * 8 = 6.32 second.

      This is anought large time for time limit. How large time limit should be?

      P.S. Ofcouse we can cut slow (with alot atan2 calls, for example) O(n^2 log n) solutions. But this is boring.

      P.P.S. Skylake with AVX-512 is coming, it takes separate O(n^2 log n) from O(n^3) solutions more difficult.

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

      I optimize my solution a bit and have cpp, 220 ms AC. (still O(n^3) operations)

      Even we make n 2000, my solution still running in 1.6-1.8 seconds. I'm not sure that is possible to set limits to cut O(n^3) solutions and keep timelimit < 20 sec.

      P.S. n = 4000 (x16 for O(n^2 log n)) execution time -> 13.5 sec.

      P.P.S If optimize(O3) hack scares you, there is a bit straight variant (extra fast)

      P.P.P.S Waiting impatiently AVX2 and AVX-512.

»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Could you attach your implementations along with the editorial?

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

Could you elaborate on the O(n4) DP solution in C?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I had following O(n^4) DP:

    dp[n][k][number_of_last_element_that_are_not_minimum][number_of_last_element_that_are_not_maximum] = number of ways.

    Then we choose one following: Either first element is minimum, then we use dp[n — 1][k — 1][0][number_of_last_element_that_are_not_maximum] or maximum: dp[n — 1][k][number_of_last_element_that_are_not_minimum][0] or any other(we put it to the end): dp[n][k][number_of_last_element_that_are_not_minimum + 1][number_of_last_element_that_are_not_maximum + 1]

    answer is dp[n][k][0][0]

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Will editorial for D be published?

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

Can someone, please, explain problem F in more detail?