Solution Codeforces Round 150

Link: http://codeforces.com/blog/entry/5895

Adiv2. Consider an array A of integers in range from 1 to nk. Let's remove from A all numbers a_i and all other numbers store into an array B. The array B will have (n - 1)k elements. Now for i-th kid you should output numbers a_i, B[(n - 1) * (i - 1) + 1], B[(n - 1) * (i - 1) + 2], ... B[(n - 1) * (i - 1) + n - 1] (Bis 1-based).

Author is [user:Gerald] .

Bvid2. Solution 1. You should write some bruteforce solution over all numbers with no more than 9 digits (number 10⁹ should be considered separately). Bruteforce algo seems like this:

dfs( int num ) // run it as dfs(0)
  if (num > 0 && num <= n) ans++
  if (num >= 10^8) return
  for a = 0..9 do
    if num*10+a>0 then
      if number num*10+a has no more than 2 different digits then
        dfs( num*10+a )

ans will store the answer. After that you wrote bruteforce, you can run it and see that it works fast (that is same time for any testcase).

Solution 2. Let's build all undoubdetly lucku numbers using bitmasks. You can iterate over length of number L, pair of digits x and y, and bitmask m of length L. If the i-th bit of m is 1, the i-th digit of number should be x; otherwise it should be y. So about 10³ × 2¹⁰ numbers will be generated (it is very rough estimate, count of numbers will be more than 10 times less).

In this solution you should accurately process the case of leading zeroes and the case when all digits of number are same.

Author is [user:Gerald]

Adiv1, Cdiv2 Let's see how function f changes for all suffixes of sequence a. Values of f will increase when you will increase length of suffix. For every increase all 1-bits will stay 1-bits, but some 0-bits will be changed by 1-bits. So, you can see that no more than k increasing will be, where k number of bits (in this problem k = 20). Among all suffixes will be no more that k + 1 values of function f.

Now you can run over sequence a trom left to right and support an array m (or a set) of values of f for all subsegments that end in the current position. Size of m always no more than k + 1. When you go from position i - 1 into position i, you should replace m = {m₁, m₂, ..., m_t} by m' = {a_i, m₁|a_i, m₂|a_i, ...m_t|a_i}. After that you should remove from m repeated values (if you use set, set will do this dirty work itself). Then you should mark all numbers from m in some global array (or put them into some global set). At the end you should calculate answer from the global array (or set).

Authors are [user:Gerald] , [user:Ripatti]

Bdiv1, Ddiv2 You should check for every edge: this one can be body of hydra or not. Let's fix some edge (u, v) (order of vertices is important, i.e. you should also check edge (v, u)). Now you should chose some set of h vertices connected with u and some set of t vertices connected with v. These sets should not contain vertices u and v. Also, these two sets should have no common vertices.

If  and , there is no any hydra here.

Orherwise, if  or , there is some hydra in any case. Even if all vertices connected with u and with v are common, number of them so big, that you always can split them into groups of size  ≥ h and size  ≥ t.

The last case is  and . Here you can find all common vertices in O(h + t), using array of flags. When you find the common subset, you can easy check existence of hydra.

UPD How to find common vertices in O(h + t) using array of flgs? You should initailize that array in the beginning of program. For every check you should do following actions. Firstly in  you should mark in the array all neighbours of u. After that you should iterate over all adjacent to v vertices and check value of flag in the array for every of them (in ). Vertices that have "thue" in the array will be common. Finally you should clear the array in : you should iterate over all adjacent to u vertices again and mark these vertices in the array as "false". Because  and , the total complexity will be O(h + t).

All edges can be checked in time O(m(h + t)). So you either find reqired edge or find that there is no required edge. Also in time O(m) you can build hydra with fixed body-edge.

This problem also has solution in  independent from values of h and t, but this solution is more complex.

Author is [user:Ripatti]

Cdiv1, Ediv2 Firstly tou should emulate all process in "idle mode". Let farmer was in points (x₀ + 1 / 2, y₀ + 1 / 2), (x₁ + 1 / 2, y₁ + 1 / 2), ... , (x_n + 1 / 2, y_n + 1 / 2). Coordinates x₀, x₀ + 1, x₁, x₁ + 1, ... x_n,x_n + 1 on axis x are interesting for us. Coordinates y₀, y₀ + 1, y₁, y₁ + 1, ... y_n, y_n + 1 on axis y are interesting too. You should store all of them into two arrays. Also you should add to these coordinates bounds of the field.

Then you should build "compressed" field: every cell of this field means rectangle of the starting field that placed between neighbour interesting coordinates. Size of the compressed field is O(n) × O(n). Let's initally all cells painted into the white color. Now you should emulate all process again and paint all visited cells in the compressed field by the black color. During every move you will paint O(n) cells, so all process will be done in O(n²).

Now you should emulate bugs' actions. You should run DFS (ot BFS) from some border cell of the compressed field and paint all reached cells be red color.

At the end you should iterate over all compressed field and find sum of areas of rectengles corresponding to black and white cells. So, you will receive the answer.

This solution works in O(n²).

Author is [user:Ripatti]

Ddiv1 You need for every column find the lowermost cube that you can see. You will see all cubes above this cube.

Consider the city from above. You will see drid of size n × n. Now you should draw the line through every node of the grid parallel to vector v. We need know only that happens in every strip between two neighbour lines. Every column cover segment of O(n) adjacent strips.

Now you should create an array a; every element of a corresponding to one strip. This array will store maximal height of considered columns.

Then you should sort all columns in order if increasing distance from observer. In that order you should do following queries of 2 types:

1. Minimum on segment. This query is needed when you want find the lowermost visible cube.
2. Replace a_i → max(a_i, h) on segment. You need this query for "drawing" column in the array.

That is all solution. You just need choose some data structure that can fast do queries. You can select from: block decomposition (length of every block should be ; because length of every query aboutO(n), total complexity of solution will be O(n^5 / 2)), segment tree (), stupid array (it'sO(n³), cache optimized implementaton fits in the time limit).

Author is [user:Ripatti]

Ediv1 We will build the matrix constructively. At any step we will have array of groups of columns. Order of groups is defined but order of columns inside every group is unknown.

During building we will change order of rows because it is doesn't affect the answer (we can build answer using order of columns only).

Consider the way of building of the matrix. Firstly you should find the row that has maximal number of ones. You should swap this row with the first row. Aftar that two groups of columns should be created. Into the first group you should put columns that have "1" in the firts row; all other columns should be stored into the second group. The second group is "special" --- see about it below.

Now you should more times search the row that has "1" in at least two groups. For every of that rows you can determine positions of all ones no more than only way. If you determined no ways, you should output NO and finish execution. After that you determined positions of ones, you should split some groups of columns into two subgroups.

About "special" group. You should take into account case when you should drop some columns from this group and insert them before all groups. You will never face with situation when it is not clear which columns should be dropped and which should not, because in the beginning you chose the row with maximal number of ones.

After repeating process than described above sevaral times, "good" rows may end. I.e. for every row all ones will be placed in no more than one group. Now you should recursively do solution described above inside every of groups of columns.

The solution works in O(n³). It can be upgraded to , but it was not required.

UPD Also here some O(n²) solution exists based on PQ-trees, as said [user:mugurelionut]. More information here.