Solution for Codeforces Round 157

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

[problem:259A]

Obviously, the only correct rows are rows WBWBWBWB and BWBWBWBW. Only thing you need to do is to check whether each string is one of these. If yes then print YES, else print NO.

[problem:259B]

Since each number is less than or equal to 10⁵, you can loop all possible a_1, 1 values, the rest of cells can be calculated from this.

[problem:258A]

It's pretty easy to notice that you need to delete the first (from the left) 0-digit. The only catchy case is 111...111 — here you need to delete any of 1-digits.

[problem:258B]

First of all, lets think about the problem of finding array c_i — the number of integers from 1 to m such, that the number of lucky digits is equal to i. It's pretty standart dynamic programminc problem, which can be solved with state [position][less][count].

It can be solved directly using DP, but to simplify a bit you can use brute froce (recursion) to brute all possible assignments of numbers of lucky digits in for all paries (up to 9 digits). Now you can divide all parties in several indepentent groups, each of which should contain the same number of lucky digits. Consider that the party of Litte Elephant is with number 1. Than assignment for the first position should have more digits than the sum of the rest (because of the statement). Since all groups are indepented (because there is no number that can have different number of lucky digits, obviously) you can find the number of resulting assignments for each group and find the final result by multiplying these all numbers and taking modulo 10⁹ + 7.

Consider that you have group of size t, each number of which should contain l lucky digits. That it's pretty easy to understand that the number of assignment is equal to (c_l)  (c_l - 1)  (c_l - 2)  ...  (c_l - t + 1).

[problem:258C]

The complexity of the possible solution is O(n  sqrt(n)  log(n)). You can see that statementlcm(b₁, b₂, ..., b_n) = max(b₁, b₂, ..., b_n) is equal to statement "All the numbers b₁, b₂, ..., b_n must divide max(b₁, b₂, ..., b_n)". You can iterate that max(b₁, b₂, ..., b_n), let it be equal to m. Find all divisors of m and sort them - p₁, p₂, ..., p_k. For each i between 1 and k you can find (using simple DP) the number of numbers a_j that p_i ≤ a_j < p_i + 1 (if i = k than p_i + 1 = max(a₁, a₂, ..., a_n) + 1), denote it asq_i. Then the reuslt is equal to 1^q₁  2^q₂  3^q₃  ...  p^q_p, because for each of the q₁ numbers there is 1 way to assign, for each of q₂ numbers there is 2 ways of assignments, and so on. But you should notice that if doing this problem in such way, you need to garantee that there is some i such b_i = m. Hance you need from the last multiplier (p^q_p) subtract (p - 1)^q_p - all the ways that there is no number equal to m.

Solution of Codeforces Round 156

Link: http://codeforces.ru/blog/entry/6161

255A - Greg's Workout

It is not hard problem. We must calculate sums of numbers for each group and print group with maximum count.

255B - Code Parsing

Not hard to see that after few operations of first type string will become: x..xy..y. After fer operations of second type, there will be only letters of one type, count of this letters will be: |count(x) — count(y)|

256A - Almost Arithmetical Progression

Заметим, что ответ это длина последовательности: a, b, a, b, ... где a и b — некоторые целые числа. Зафиксируем одно число (допустим a), будем перебирать число b, и считать какой мы получим ответ, если это будет последнее число в последовательности. Заметим, что для фиксированных a, b — ответ считается жадно. Так же будем действовать и тут. Будем искать последнее вхождение числа b до зафиксированного, что между ними есть число a, и будем брать ответ как длина до найденного числа +2 (икасть будем с помощью метода двух указателей). Так же нужно рассмотреть случай, когда это будет 1е или 2е вхождение в последовательность.
Так же существует решение с помощью динамического программирования.
Асимптотика обоих решений O(n^2).
Буду очень рад, если кто то напишет решение с лучшей асимптотикой.

256B - Mr. Bender and Square

Solution — binary search for answer. Next we have to calculate the area of a truncated square set at 45 degrees. This can be done as follows: Calculate its total area. Subtract area that cuts off the top line. Similarly, for the lower, left and right line. Add parts that are cutted by corners. You can write a function that finds the length of the truncation desired area, for that would not write a lot of code.

256C - Furlo and Rublo and Game

Note that after the first move any pile turns into a pile no larger than 1000000. We assume Grundy function for numbers less than 1 million. Grundy function is very small, you can start on the partial sums for each type of function that would quickly tell what function is in the interval, and which are not present. Knowing the answer is not difficult to find small response for all piles.

256D - Liars and Serge

If person say number x, and at all x was said by x persons, then we cannot tell anything about fixed person.

Now we understand which sequence are good for us. We will calculate their count wuth dynamic programming dp[n][m][k], n — which persons answers we set to the sequence right now, m — how mant persons gived theis answers, k — how many persons from them are liers.
Transfer:
dp[n][m][k]*cnk[N-m][n] -> dp[n+1][m+n][k]
dp[n][m][k]*cnk[N-m][p] -> dp[n+1][m+p][k+p] p = 1 .. N, p != n.
We assume, that N — total number of the persons. This solution get TLE, becouse complexity if O(N^4). We need to use precalc. It will not be so big, as N is power of 2.

256E - Lucky Arrays

Solution is — interval tree. We will save dynamic programming f[i,j] in each vertex, this dp means: in how many ways we can change all 0 to some numbers on interval, such that it will be valid and first element will be i and last will be j.

With normal implementation its easy to pass system tests.

Solution of Codeforces Round 155

Link: http://www.codeforces.com/blog/entry/6085

254A - Cards with Numbers

For each x from 1 to 5000 store a list L(x) of such indexes i that a_i = x. Then just check that all lists have even size and output the elements of each list in pairs.

254B - Jury Size

One of the possible solutions is: for each Olympiad find the period of the preparation. This can be done by iterating the days back from the day of the Olympiad. For each day d of the preparation add p_i to the number of distinct jury members that have to work on problems on day d. Then the answer is maximum calculated sum over all days. Be careful with the year 2012.

254C - Anagram

Lets denote the number of character x in s by C_s(x). Similarly C_t(x) is defined. Then the minimum number of changes required to get anagram of t from s is equal to . Now we need to obtain lexicographically minimum solution. Lets iterate through the positions in s from the left to the right. For a fixed position, look through all characters from 'a' to 'z' and for each character decide whether the optimal answer can contain this character in that position. If it can, put this character in that position and continue with the next position. To check if the given character is suitable quickly, we maintain the values C_s(x) and C_t(x) while iterating through positions.

254D - Rats

Choose arbitrary rat (for say, the leftmost of the upmost). It's cell should be cleared. Make a BFS that never goes further than d from this cell (we will call such a BFS by d-BFS). It will visit approximately 2d²cells in the worst case. So, we have to blow the first grenade in one of the visited cells. Lets check every visited cell as a candidate. Make a d-BFS from the candidate cell. Some cells with the rats will not be visited. That means that they should be cleared by the second grenade. Choose arbitrary cell with a rat that was not cleared by the first grenade. Make a d-BFS from it. All cells visited by this BFS are candidates to blow the second grenade. Lets check every such cell. Checking a cell again means making a d-BFS from it. If this BFS visits all cells that were not cleared by the first grenade, that we have found a solution. As every d-BFS visits at most 2d², the overall number of steps is approximately 8d⁶.

254E - Dormitory

The problem can be solved by dynamic programming: denote as D(n, r) the maximum rating that we can achieve in the first n days with the condition that we have r kilos of food remaining from the day n - 1. It is obvious that if we decide to feed k friends on some day, the better way is to feed k friends with the lowest f_j (of course we consider only friends that live with Vasya on that day). So we need to sort all available students in the order of increasing f_j and try to feed 0, 1, 2, ldots first students in this order. We have 400² states and 400 transitions from each state.

Solution codeforces Round 154

Link: http://www.codeforces.com/blog/entry/6073

253A - Boys and Girls

Lets assume that we have more boys than girls (the other case is solved similarly). Then we can construct one of the optimal solutions in the following way: we add pairs consisting of a boy and a girl (BG, in that order) to the end of the line until we don't have girls any more. Then add remaining boys to the end of the line. For instance, with 7 boys and 4 girls we will come to the solution BGBGBGBGBBB.

253B - Physics Practical

For each x from 1 to 5000 calculate count(x) — the number of measurements equal to x. The iterate over all possible minimal values m (from 1 to 5000). For a fixed m we can easily figure out which numbers we have to erase: we should erase every number k that k < m or k > 2·m. To find out the number of such values in the given sequence, we should sum up values count(k) for all such k.

253C - Text Editor

One of the solutions to the problem is breadth-first-search (BFS). Vertices of the graph correspond to all possible pairs (r, c), denoting the row and the position of the cursor. Each vertex has at most four arcs leaving it (these arcs correspond to pressing the buttons). So we need to find the shortest path from one vertex to the other. There are at most 10⁷ vertices and at most 4·10⁷ arcs. This problem can also be solved with some greedy observations.

253D - Table with Letters - 2

Lets iterate over all pairs of rows i, j (i < j), that bounds the sub-table from the top and from the bottom. Then for each character ch make a list of such column numbers k that T[i, k] = T[j, k] = ch. Consider such list for some fixed character ch. All we need to count is the number of pairs l, r (l < r) in this list such that the sub-table with corners at (i, l) and (j, r) contains not more than k characters "a". This can be done using two standard techniques: two-pointer method and calculating partial sums.

253E - Printer

First lets learn how to simulate the process with all priorities known. We will keep the priority queue of tasks. The task enters the queue when the printer receives this task, and leaves the queue when the printer finishes it. Then every change in the queue happens when one of the two possible events occurs: the printer receives some task or finishes printing some task. Between the consecutive events printer just prints pages from the tasks with the highest priority. So, if we maintain a set of events, the simulation can be done in O(NlogN).

To solve the problem, make an obvious observation: the higher priority the task has, the sooner the printer finishes it. Then the required missing priority can be found using binary search. Also we can search the missing priority among O(N) values. The overall complexity is O(Nlog²(N)).

This problem also has O(NlogN) solution, which will be described later.

Solution of Codeforces Round 151 Div 2

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

Codeforces Round #151 (Div. 2) Tutorial

By HolkinPV, 4 days ago, translation, , 

246A - Buggy Sorting

In this problem you should hack the sorting algorithm, of course it was incorrect. It was correct only for arrays with n <  = 2. In other cases you could print n, n–1, ..., 1 as a counter-example. To make the sorting right, the second cycle should be from 1 but not from i.

246B - Increase and Decrease

Note, that you can always get the answer n–1. To get this result you should make first n–1 equal using the last element as the second element in pair of given operation. But after it, the whole array could become equal. It could happen if the sum of array’s elements is divisible by n. So the answer is n–1 orn.

246C - Beauty Pageant

This problem was rather mathematical. The correct solution is: firstly take every element once, then take the maximum and any other, then two maximums and any other, then three maximums and any other and so on. In this case, you get as many sets as you need in this problem. It is easy to check, that all sums will be different.

246D - Colorful Graph

This problem could be solved in this way: create new graph where vertices are the colors of the given graph. The edge between vertices u and v belongs this new graph if there are two vertices a and b in the given graph such that c[a] = u and c[b] = v. So, the answer is such color k with minimum number, that the degree of the vertex k in the new graph is maximum (without multiple edges). Such solution could be written using O(M·log(N)) time.

246E - Blood Cousins Return

This problem had little in common with problem 208E - Blood Cousins. In comments to this problem there was given a solution using structure deque (array in which you can add or delete elements from both endings). Let’s describe solution using this structure.

Firstly all different names change with different integers and for every vertex v save all queries with this vertex. Then for every vertex, which is root of some tree make dfs, the parameters of dfs are vertex vand deque <set > z. This deque for every depth i of the subtree of v save set — all different names (integers) on depth i.

This deque could be calculated simply. Consider all sons of v and calculate such deque for them. Obviously, the size of our deque z will be maximum of sizes of descendants’ deques. Then consider every descendants’ deques and merge appropriate sets of integers. Of course, we will merge smaller set to a larger set. After that you should insert to the beginning of deque z the set of size 1 — color of vertex v.

After this, you can at once answer all queries of vertex v. Answer is 0 if v has no descendants on the depth k or the size of z[k]. It is known that such method has good asymptotic, the author’s solution works about one second.

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.