dmkozyrev's blog

By dmkozyrev, history, 7 days ago, In Russian,

Здравствуйте! Пытаюсь сдать задачу "882. Губернатор" с сайта acmp.ru. Недавно я создавал аналогичный пост для другой задачи, под которым подсказали, что в задачах такого рода должен работать жадный алгоритм и нужно лишь определить предикат для сортировки.

В этой же задаче я понял, что ответ не зависит от K и необходимо минимизировать сумму:

an·an - 1·...·a2·b1 + an·an - 1·...·a3·b2 + an·an - 1·...·a4·b3 + ... + an·bn - 1 + bn

Здесь индексами обозначена последовательность взятия.

Я генерировал маленькие случайные тесты, для которых можно перебрать все n! перестановок и пробовал подобрать предикат, но все безрезультатно. Максимально близко к случайным тестам размера 10 подошел предикат , где — произведение всех ai. На этом идеи кончились и нужна помощь. Может из-за маленького n решение предполагает динамику за O(n2) времени с памятью O(n), но с ней тоже не вяжется.

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

By dmkozyrev, history, 2 weeks ago, translation, In English,

UPD: while I was translating this post from Russian to English, dacin21 wrote his post, more advanced, link. I hope that my post will help beginners, but in my post more rough estimates.

And in Russia we call rolling hashes as a polynomial hashes.

Hello, codeforces! This blogpost is written for all those who want to understand and use polynomial hashes and learn how to apply them in solving various problems. I will briefly write the theoretical material, consider the features of the implementation and consider some problems, among them:

  1. Searching all occurrences of one string of length n in another string length m in O(n + m) time

  2. Searching for the largest common substring of two strings of lengths n and m (n ≥ m) in O((n + m·log(n))·log(m)) and O(n·log(m)) time

  3. Finding the lexicographically minimal cyclic shift of a string of length n in O(n·log(n)) time

  4. Sorting of all cyclic shifts of a string of length n in lexicographic order in O(n·log(n)2) time

  5. Finding the number of sub-palindromes of a string of length n in O(n·log(n)) time

  6. The number of substrings of string of length n that are cyclic shifts of the another string length m in O((n + mlog(n)) time

  7. The number of suffixes of a string of length n, the infinite extension of which coincides with the infinite extension of the given string for O(n·log(n)) (extension is a duplicate string an infinite number of times).

  8. Largest common prefix of two strings length n with swapping two chars in one of them O(n·log(n))

Note 1. It is possible that some problems can be solved more quickly by other methods, for example, sorting the cyclic shifts — this is exactly what happens when constructing a suffix array, to search for all occurrences of one string in another will allow the Knut-Morris-Pratt algorithm, the Manaker algorithm works well with the sub-palindromes, and for own suffixes there is a prefix function.

Note 2. In the problems above, an estimate is made when a hash search is performed by sorting and binary searching. If you have your own hash table with open mixing or overflow chains, then you — lucky, boldly replace the hash search for a search in your hash table, but do not try to use std::unordered_set, as in practice the search in std::unordered_set loses sorting and binary search in connection with the fact that this piece obeys the C++ standard and has to guarantee a lot to the user, which is useful for industrial coding and, often, is useless in the competitive programming, so sorting and binary search for simple structures gain absolute primacy in C++ in speed of work , if not used additional own structures.

Note 3. In cases where comparison of elements is slow (for example, comparison by hash in O(log(n)) time), in the worst case std::random_shuffle + std::sort always loses std::stable_sort, because std::stable_sort guarantees the minimum number of comparisons among all sorts (based on comparisons) for the worst case.

The solution of the listed tasks will be given below, the source codes also.

As advantages of polynomial hashing I can notice that you often do not need to think, you can immediately take and write a naive algorithm to solve the problem and speed it up with polynomial hashing. Personally, firstly, I think about solution with a polynomial hash, perhaps that's why I'm blue.

Among the disadvantages of polynomial hashing: a) Too many operations getting remainder from the integer division, sometimes on the border with TLE for large problems, and b) on the codeforces in C++ programs are often small guarantees against hacking due to MinGW: std::random_device generates the same number every time, std::chrono::high_resolution_clock ticks in microseconds instead of nanoseconds. (The Cygwin compiler for windows wins against MinGW).

`UPD`: Solved а)
`UPD`: Solved b)

What is polynomial hashing?

Hash-function must assign to the object a certain value (hash) and possess the following properties:

  1. If two objects are equal, then their hashes are equal.

  2. If two hashes are equal, then the objects are equal with a high probability.

A collision is the very unpleasant situation of equality of two hashes for not equal objects. Ideally, when you choose a hash function, you need to ensure that probability of collision lowest of possibles. In practice — just a probability to successfully pass a set of tests to the task.

There are two approaches in choosing a function of a polynomial hash that depend on directions: from left to right and from right to left. To begin with, consider the option from left to right, and below, after describing the problems that arise in connection with the choice of the first option, consider the second.

Consider the sequence {a0, a1, ..., an - 1}. Under the polynomial hash from left to right for this sequence, we have in mind the result of calculating the following expression:

Here p and m — point (or base) and a hash module, respectively.

The conditions that we will impose: , .

Note. If you think about interpreting the expression, then we match the sequences {a0, a1, ..., an - 1} number of length n in the number in system with base p and take the remainder from its division by the number m, or the value of the polynomial (n - 1)-th power with coefficients ai at the point p modulo m. We'll talk about the choice of p and m later.

Note. If the value of (not by modulo), is placed in an integer data type (for example, a 64-bit type), then each sequence can be associated with this number. Then the comparison by greater / less / equal can be performed in O(1) time.

Comparison by equal in O(1) time

Now let's answer the question, how to compare arbitrary segments of sequence for O(1)? We show that to compare the segments of given sequence {a0, a1, ..., an - 1}, it is sufficient to compute the polynomial hash on each prefix of the original sequence.

Define a polynomial hash on the prefix as:

Briefly denote as and keep in mind that the final value is taken modulo m. Then:

General form:

The polynomial hash on each prefix can be calculated in O(n) time, using recurrence relations:

Let's say we need to compare two substrings that begin with i and j and have the length len, for equality:

Consider the differences and . It's not difficult to see that:

We multiply the first equation by pj, and the second by pi. We get:

We see that on the right-hand side of the expressions in brackets polynomial hashes were obtained from the segments of sequence:

Thus, in order to determine whether the required segments of sequence have coincided, we need to check the following equality:

One such comparison can be performed in O(1) time, assuming the degree of p modulo precalculated. With the module m, we have:

Problem: Comparing one segment of sequence depends on the parameters of the other segment of sequence (from j).

The first solution of this problem (given by veschii_nevstrui) is based on multiplying the first equation by p - i, and the second by p - j. Then we get:

We can see that in the right-hand parts of equations we get a polynomial hash from the needed segments of sequence. Then, the equality is checked as:

To implement this, we need to find the inverse element for p modulo m. From the condition gcd(p, m) = 1, the inverse element always exists. To do this, we need calculate or just know the value of the Euler function for the selected module φ (m) and get power φ(m) - 1 for p. If we precalculate the powers of the inverse element for the selected module, then the comparison can be performed in O(1) time.

The second solution we can use if we know the maximum lengths of compared segments of sequences. Let's denote the maximum length of compared lines as . We multiply 1-th equation by power mxPow - i - len + 1 of p, and 2-nd equation by mxPow - j - len + 1 power of p. We get:

We can note that on the right-hand sides of equals a polynomial hash of segments of sequence. Then, the equality is checked as follows:

This approach allows you to compare one substring of length len with all substrings of length len by equality, including substrings of another string, since the expression for the substring of the length len starting at the position i, depends only on the parameters of the current substring i, len and constant mxPow, and not from the parameters of another substring.

Now consider another approach for choosing polynomial hash function. Define a polynomial hash on the prefix as:

Briefly denote as and keep in mind that the final value is taken modulo m. Then:

The polynomial hash on each prefix can be calculated in O(n) time, using recurrence relations:

Let's say we need to compare two substrings that begin with i and j and have the length len, for equality:

Consider the differences and . It's not difficult to see that:

We see that on the right-hand side of the expressions in brackets polynomial hashes were obtained from the segments of sequence:

Thus, in order to determine whether the required segments of sequence have coincided, we need to check the following equality:

One such comparison can be performed in O(1) time, assuming the degree of p modulo m precalculated.

Comparison by greater / less in O(log(n)) time

Consider two substrings of (possibly) different strings of lengths len1 and len2, (len1 ≤ len2), starting in the positions i and j respectively. Note that the ratio greater / less is determined by the first non-equal symbol in these substrings, and before this position strings are equal. Thus, we need to find the position of the first non-equal symbol by the binary search method, and then compare the found symbols. By comparing substrings to equality in O(1) time, we can solve the problem of comparing substrings by greater / less in O(log(len1)) time:

Pseudocode

Minimizing the probability of collision

Using approximations in birthday problem, we get (perhaps a rough) estimate of the probability of collision. Suppose we compute a polynomial hash modulo m and, during the program, we need to compare n strings. Then the probability that the collision will occur:

Hence it is obvious that m needs to be taken much more than n2. Then, approximating the exponential as Taylor series, we get the probability of collision on one test:

If we look at the problem of searching of occurrences of all cyclic shifts of one row in another string of lengths to 105, then we can get 1015 comparisons of strings.

If we take a prime modulo of the order 109, then we will not go through any of the maximum tests.

If we take a module of the order 1018, then the probability of collision on one test is  ≈ 0.001. If the maximum tests are 100, the probability of collision in one of the tests is  ≈ 0.1, that is 10%.

If we take the module of the order 1027, then on the 100 maximum tests the probability of collision is  ≈ 10 - 10.

Conclusion: the higher the value of module, the more likely that we must pass the test. This probability not includes estimate probability of hack your solution.

Double polynomial hash

Of course, in real programs we can not take modules of the order 1027. How to be? To the aid comes the Chinese theorem on the remainders. If we take two mutually simple modules m1 and m2, then the ring of residues modulo m = m1·m2 is equivalent to the product of rings modulo m1 and m2, i.e. there is biection between them, based on the idempotents of the residue ring modulo m. In other words, if you calculate modulo m1 and modulo m2, and then compare two segments of sequence with and simultaneously, then this is equivalent to comparing a polynomial hash modulo m. Similarly, we can take three mutually prime modules m1, m2, m3.

Features of the implementation

So, we came to the implementation of the above. Goal — the minimum of the number of the remainder calculation from the integer division, i.e. get two multiplications in a 64-bit type and one take the remainder from division in 64-bit type for one calculation of a double polynomial hash, get a hash modulo about 10^27 and protect the code from hacking on сodeforces

Selection of modules. It is advantageous to use a double polynomial hash on the modules m1 = 1000000123 and m2 = 2^64. If you do not like this choice of m1, you can select 1000000321 or 2^31-1, the main thing is to choose such a prime number so that the difference of the two residues lies within the signed 32-bit type (int). A prime number is more convenient, since the conditions gcd(m1, m2) = 1 andgcd(m1, p) = 1 are automatically provided. The choice of m2 = 2^64 is not accidental. The C++ standard ensures that all calculations in the unsigned long long are executed modulo 2^64 automatically. Separately, the module 2^64 can not be taken, because there is an anti-hash test, which does not depend on the choice of the hash pointp. The module m1 should be specified as constant to speed up the taking the remainder (the compiler (not MinGW) optimizes, replacing by multiplication and bitwise shifting).

Sequence encoding. If given a sequence of characters, consisting, for example, of small Latin letters, then you not need to encode anything, because each character already corresponds to its code. If a sequence of integers is given that is reasonable for a representation in memory of length, then it is possible to collect all the occurring numbers into one array, sort, delete the repeats and assign to each number in the sequence its index in sorted set. Code zero is forbidden: all sequences of the form 0,0,0, .., 0 of different length will have the same polynomial hash.

Choosing of the base. As the base p it suffices to take any odd number satisfying the condition max(a[i]) < p < m1. (odd, because then gcd(p, 2 ^ 64) = 1). If you can be hacked, then it is necessary to generate p randomly with every new program start, and generation with std::srand(std::time(0)) and std::rand() is a bad idea, because std::time(0) ticks very slowly, and std::rand() does not provide enough uniformity. If the compiler is not MINGW (unfortunately, MinGW is installed on the codeforces), then you can use std::random_device, std::mt19937, std::uniform_int_distribution<int> (in cygwin on windows and gnu gcc on linux this set provides almost absolute randomness). If you were unlucky and you use only MinGW, then there is nothing left to do but replace std::random_device with std::chrono::high_resolution_clock and hope for the best (or is there a way to get some counter from the processor?). On MinGW, this timer ticks in microseconds, on cygwin and gnu gcc in nanoseconds.

Warranties against hacking. Odd numbers up to a module of the order of 10^9 are also of the order of 10^9. The cracker will need to generate an anti-hash test for each odd number so that there is a collision in the space to 10^27, compile all the tests into one big test and hack you! This is if you do not use MinGW on Windows. On MinGW, the timer is ticking, as already mentioned, in microseconds. Knowing when solution was started on the server with an accuracy of seconds, it is possible for each of the 10^6 microseconds to calculate what random p was generated, and then the number of variants in the 1000 times less. If 10^9 is some cosmic number, then 10^6 already seems not so safe. If you use std::time (0) only 10^3 number of variants (milliseconds) — can be hacked! In the comments I saw that grandmasters know how to break a polynomial hash modulo ot order of 10^36.

Ease of use. It is convenient to write a universal object for a polynomial hash and copy it to the task where it might be needed. It is better to write independently for your needs and goals in the style in which you write to understand the source code if necessary. All problems in this post are solved by copying the one class object. It is possible that there are specific tasks in which this does not work.

UPD: To speed up programs, you can quickly calculate the remainder of the divisions by modules 231 - 1 and 261 - 1. The main difficulty is multiplication. To understand the principle, look at this post by dacin21 in Larger modulo and his comment.

Mult mod `2^61-1`
Problem 1. Searching all occurrences of one string of length n in another string length m in O(n + m) time
Problem 1 statement in English

Link on problen on acmp.ru.

Solution and code
Problem 2. Searching for the largest common substring of two strings of lengths n and m (n ≥ m) in O((n + m·log(n))·log(m)) and O(n·log(m)) time

Link on problem on acm.timus.ru with length 10^5.

Link on problem on spoj.com with length 10^6.

Solution and code
Problem 3. Finding the lexicographically minimal cyclic shift of a string of length n in O(n·log(n)) time
Problem 3 statement in English

Link on problem 3

Solution and code
Problem 4. Sorting of all cyclic shifts of a string of length n in lexicographic order in O(n·log(n)2) time
Problem 4 statement in English

Link on problem 4

Note
Solution and code
Problem 5. Finding the number of sub-palindromes of a string of length n in O(n·log(n)) time
Problem 5 statement in English

Link on problem 5 with length 10^5

Link on problem 5 with length 10^6

Solution and code
Problem 6. The number of substrings of string of length n that are cyclic shifts of the another string length m in O((n + mlog(n)) time
Problem 6 statement in English

Link on problem 6

Solution and code
Problem 7. The number of suffixes of a string of length n, the infinite extension of which coincides with the infinite extension of the given string for O(n·log(n)) (extension is a duplicate string an infinite number of times).
Problem 7 statement in English

Link on problem 7

Solution and code
Problem 8. Largest common prefix of two strings length n with swapping two chars in one of them in O(n·log(n)) time

Link on problem

You can check the editorial written by a_kk and smokescreen on this site for getting solution without hashes in O(n) time.

Solution and code

That's all. I hope this post will help you to apply hashing and solve more difficult problems. I will be glad to any comments, corrections and suggestions from you. Share other problem and, possibly, your solutions, solutions without hashes. Thank you for reading this tutorial! There are many useful comments in russian under this blogpost, if you want, you can check them with google translate.

Links:

Rolling Hash (Rabin-Karp Algorithm)

Read more »

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

By dmkozyrev, history, 3 weeks ago, translation, In English,

On the Internet since 2004 there is a game "Bug". This is in russian, but you can use the google translator for translate all page, or ask me if there is something that is not clear after translation.

Goal of game — build a correct labyrinth 19 x 29 for bug. Result — number of bug's movements from start point to finish point. The results on the site are sorted by the amount of movement of the bug for the passage of the labyrinth. Algorithm of bug's movement:

Bug always starts movement from the upper left corner, and the exit is always in the lower right corner. The bug is not moving optimally, but in the following way: he goes to where he was not yet, or was there less often. Passing every cell of the labyrinth, the beetle remembers: how many times he was in this cell and when thinking about the direction of his movement at some particular moment he looks: how many times he was in the cell from down side, how many from the right side, how many on the left and how much from up side and moves to where he was fewer times. If there are several such directions and one of them equal with the current direction of the movement, bug does not change direction, otherwise bug moves according to the following priorities: down, right, up, left. Example: if the minimum number of visits immediately to the right and left (but bug is moving up or down), the bug goes to the right, because the "right" priority is higher.

My implementation on C++.

Example of labyrinth with score 734.938
Correct implementation on js from authors
Check your implementation

The site has a table of records for all the labyrinths, in which the user is specified and the result of the bug's passing through its most difficult for bug labyrinth. I'm there, 5 th place with 10 million moves. By the way, the winner received 250 million moves quite recently.

For 14 years of work, no good upper bounds were obtained for the maximum possible number of steps of the bug, and no algorithm for constructing the worst test was obtained.

Those interested are invited to play the game "Bug", to generate labyrinths and research this algorithm. Perhaps, it will be possible to shift the leaders from their pedestal. Maybe you can create english version of this game.

UPD: For speed up bug on the site for test your labyrinth you can open google chrome console on F12 and set speed = 1/512. To register a record, you do not have to wait. Just click on 'save' button and your result will be sent on server.

Read more »

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

By dmkozyrev, history, 3 weeks ago, In Russian,

Здравствуйте! Есть q запросов вида xi к массиву a из n элементов — целых 32-битных беззнаковых чисел. Каждый запрос — побитовый xor всех элементов массива с элементом xi. После каждого запроса нужно выводить максимум на всем массиве. Ограничения на n и q порядка 2·105.

Я помню задачу с нахождением суммы на отрезке и применением xor на отрезке — там она решалась построением 32 деревьев отрезков под каждый разряд, а сумма формировалась как сумма элементов по модулю 2 умноженная на соответствующую степень двойки, которой соответствует дерево отрезков.

В этой же задаче отрезок не произвольный, а фиксированный — весь массив. Как решать эту задачу?

Приведу изначальную формулировку, может она легче: есть два массива a и b длины n, нужно найти максимальное значение среди всех попарных xor элементов пар (a[i], b[j]) элементов массивов.

Ну и еще более изначальную: есть корневое дерево с n вершинами и n-1 ребрами. На ребрах записаны некоторые целые числа, а на каждом ребре одно число. Нужно выбрать две различные вершины дерева u и v такие, что выписав все числа на пути от вершины u до корня и от вершины v до корня, а затем выполнить операцию xor для всех выписанных элементов, итоговое значение было бы максимальным среди всех пар (u,v). В ответ выдать это значение. Задача

UPD: Сдал задачу при помощи сортировки + неявного бора + бинарного поиска за O(n * log(n) * WORD_WIDTH). Код к задаче, исходная формулировка оказалась легче — не пришлось изменять элементы массива.

Read more »

 
 
 
 

By dmkozyrev, history, 3 weeks ago, In Russian,

Зачастую мне удается подобрать контр-тесты к своим полным решениям уже после их сдачи. Я не помню всех задач, но я точно валил свое accepted-решение задачи с сортировкой по полярному углу в long double с применением atan2 в одном из первых образовательных раундов (или даже в самом первом). Есть ли на codeforces механизм добавления тестов к задачам в уже завершенных контестах и перетестирование решений? Если нет, то мне кажется, что сохранение возможности взламывать решения в любой момент времени с момента завершения контеста и добавление тестов из успешных взломов было бы неплохим усовершенствованием, ведь многие люди дорешивают старые задачи. Если каждый раз перетестировать решения затратно, то можно, например, накапливать изменения и делать это раз в сутки, пока все спят или ищут на какую кнопку стать легендарным гроссмейстером, и уведомлять пользователей о падении их старых решений.

Пример

UPD: Приношу свои извинения, задача C. Ближайшие вектора из образовательного раунда 1 была упомянута ошибочно, так как в ней ограничения на координаты 10^4 по модулю. Я перепутал ее с задачей 4774. Выпуклая оболочка с сайта e-olymp, где проходит неверное решение, не смотря на наличие 34 тестов к задаче. В ней ограничения на координаты до 10^9 по модулю, а, как известно, atan2(1, -10^9) и atan2(1, -10^9+1) отличаются в 18-м знаке после запятой. Используемый тип long long конвертируется в double и ошибка неизбежна. Нужно либо писать решение в целых числах, либо явно конвертировать в long double.

Read more »

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

By dmkozyrev, history, 3 weeks ago, In Russian,

Все заминусовано в комментах, это какой-то флешмоб неадекватов? Если нет, то почему? Ну а если да, то зачем?

Read more »

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

By dmkozyrev, history, 3 weeks ago, In Russian,

UPD: сдалось, доказательство dalex

Не могу решить задачу 788. Интересная игра с числами с сайта acmp.ru. Жадное решение (отсортировать пары по (a, b) и по (b, a) в двух массивах, идти по ним двумя указателями и набирать для каждого игрока из начала массивов еще никем не взятые пары) — не проходит, на этом идеи закончились. Подкиньте, пожалуйста, идеи, или направьте рассуждения в правильном направлении, может на codeforces есть аналогичная задача с разбором, заранее спасибо.

Read more »

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

By dmkozyrev, history, 4 weeks ago, In Russian,

Последнее обновление: решение за O(n) динамическим программированием

Здравствуйте! Задача 736. Удаление с acmp.ru. Суть задачи: на каждой итерации из массива длины n до 5·106 удаляются элементы с индексами k, 2k, 3k и т.д. Затем все неудаленные элементы сдвигаются и операция повторяется до тех пор, пока длина массива не станет меньше k. Нужно для каждого элемента во вводе сообщить, каким по счету он уйдет.

UPD: Решено за O(q * sqrt(n)). Решение Wild_Hamster

Решение

UPD2: Так как задача находится в теме "структуры данных", то авторское решение использует некую хитрую структуру данных, которая укладывается и в предел по времени, и в предел по памяти. На это же и намекают лучшие попытки к задаче: там есть решения с 39 МБ и 59 МБ по памяти.

Попробовал сдать код деревом отрезков за O(n log(n)). На acmp.ru — Memory Limit Exceeded (на ideone.com 0.780 с, 84 MB)

UPD3: Написал код деревом Фенвика за O(n log(n)). На acmp.ru — Time Limit Exceeded на 19-м тесте. (на ideone.com 0.480 с, 40 MB).

UPD4: Решение динамическим программированием за O(n): можно решать задачу на префиксе количества итераций, совершенных алгоритмом. Для того, чтобы дать ответ, нам для каждого элемента нужно определить, на какой итерации алгоритма он будет удален, и какому элементу на предыдущей итерации он эквивалентен и использовать уже посчитанный ответ для этого элемента.

Исходный код

Read more »

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

By dmkozyrev, history, 4 weeks ago, In Russian,

Здравствуйте! На acmp.ru есть задача о разрезании квадратного торта со свечками: необходимо определить, можно ли разрезать торт одним прямолинейным разрезом на две части равной площади так, чтобы все свечки оказались в одной половине. Задача с четвертьфинала Чемпионата мира Восточно-сибирского региона 2009 года.

Мое решение следующее:

  1. Прямой разрез обязательно должен проходить через центр квадрата, поэтому масштабируем координаты точек в два раза, смещаем на сторону квадрата. После этой операции центр квадрата находится в центре координат. Если какая-то точка лежит в центре квадрата — ответ NO. Если всего одна точка — ответ YES.

  2. Сортируем точки по полярному углу. Используя предикат x > 0 || (x == 0 && y > 0) разбиваем множество всех точек на две части, каждую из которых сортируем в целых числах, затем склеиваем две части и дублируем первую точку в конец.

  3. Смотрим на знак векторного произведения соседних векторов. Если он отрицателен, то угол между векторами строго больше 180 градусов, следовательно можно провести разрез по прямой линии — ответ YES. Если ничего не подошло, ответ — NO.

Код выдает неправильный ответ на 9-м тесте.

UPD. Проблема решена. Контр-тест, который валит решение выше:

100
2
51 50
52 50

В данном случае после преобразования получаются векторы (2, 0) и (4, 0), которые имеют один и тот же полярный угол, их векторное произведение равно нулю, значит решение выдаст неверный ответ NO, а должно YES.

Исправить это просто: после сортировки нужно удалить повторяющиеся углы. Сделать это можно при помощи std::vector::erase и std::unique. Исправленное решение в целых числах, которое прошло все тесты.

Read more »

 
 
 
 

By dmkozyrev, history, 5 weeks ago, In Russian,

Здравствуйте!

Дали задание написать сбалансированное дерево поиска с операциями: пробежаться по всем элементам за O(n) в порядке неубывания, вставить новый элемент за O(log(n)), найти определенный элемент за O(log(n)). Известно, что на любой момент работы программы в дереве  ≤ n элементов. Дерево должно работать поверх массива размера O(n).

Перед тем, как начать думать о написании своей реализации, полез в интернет, а там ничего нет о реализации сбалансированных деревьях на массивах, в связи с этим встал вопрос: может это и не возможно сделать вовсе?

Read more »

 
 
 
 

By dmkozyrev, history, 5 weeks ago, In Russian,

Здравствуйте! На acmp.ru есть интересная задача — самая сложная задача с полуфинала ВКОШП 2016/2017 Красноярского края. Ниже приведу краткое условие.

Есть циклический массив длины n (1 ≤ n ≤ 105) из целых неотрицательных чисел (все его элементы расположены по кругу), сумма элементов которого не превосходит 109. Требуется для каждого k от 1 до n определить, можно ли разбить отрезок [1..n] массива на k непересекающихся отрезков, сумма элементов в которых равна и каждый элемент покрыт хотя бы одним отрезком. Так как массив циклический, то за элементом с индексом n следует элемент с индексом 1, таким образом, последний отрезок может переходить через границу массива.

Раньше этот пост содержал просьбу помочь, так как не проходило мое решение. После обсуждения и изучения контр-тестов, предоставленных YANORMALNOSUPERGOOD, выяснилось, что это решение и не должно проходить, так как оно основывается на жадности, после чего было придумано следующее решение: для каждого делителя si суммы всех элементов S для каждого отрезка [l,  r], содержащего начальный элемент массива, при помощи бинарного поиска и префикс-сумм предпринимается попытка построить еще ki =  отрезков (ki ≤ n), сумма на которых в точности равна si. Если я ничего не перепутал, то это решение занимает O(count(kin + sum(kilog(n)) ≈ O(n4 / 3·log(nlog(log(n))) по времени. На сервере оно работает за 1.5 секунды.

Вопрос: можно ли решить оптимальнее, легче (возможно, за один проход по массиву), и нет ли контр-тестов, которые должны вызывать TLE у решения выше?

UPD: AeonHQ и YANORMALNOSUPERGOOD показали, что оптимальнее решить можно, а именно, за время O(n·numberOfDivisors(S). Причем, в оценке участвуют только делители, которые не превосходят n. Ключевой момент — избавиться от бинарного поиска, который выполнялся sumOfDivisors(S) раз. Для этого можно перейти к динамическому программированию и для одного делителя предподсчитать определенную величину, которая позволит за O(1) отвечать на запрос о максимальном количестве искомых отрезков. Решения с указанной асимптотикой приведены в комментариях здесь и здесь.

Возможно, асимптотику можно еще улучшить, воспользовавшись тем фактом, что если мы выяснили, что для какого-то делителя суммы ответ 0, то и для всех делителей, кратных ему, ответ 0, а если для какого-то делителя ответ 1, то и для всех делителей, на которые он делится, ответ 1.

Read more »

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

By dmkozyrev, history, 6 weeks ago, In English,

Hello, codeforces! How we can solve this problem:

We are given an array a[1...n] (n ≤ 200000, 1 ≤ a[i] ≤ 1000000) of integers and given q queries (q ≤ 200000): li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 1000000). For each query we need to answer how many indexes j: li ≤ j ≤ ri and gcd(a[j], x) = 1.

Here's what I got:

1) before 1.000.000 only 78.498 primes

2) each number from input have no more than 7 prime divisors, because 2 × 3 × 5 × 7 × 11 × 13 × 17 = 510.510

3) count(li, ri, xi) = count(1, ri, xi) - count(1, li - 1, xi), li > 1

Time Limit is 1.5 s, Memory Limit is 64 MB.

Example:

6
1 2 3 4 5 6
4
1 6 1 --> 6
1 6 2 --> 3
2 4 6 --> 0
3 6 10 --> 1

UPD: solved by AeonHQ. Memory: 21 MB, Time: 1.2 s on worst case.

Read more »

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

By dmkozyrev, history, 2 months ago, In Russian,

Например, ко второму образовательному раунду? Это так задумано или забыли открыть после серии обновлений платформы? Если задумано, то почему? Среди официальных раундов встречаю такое впервые, раньше встречал эту ситуацию с раундами в разделе "тренировки", например, с задачами с квалификационного этапа ACM-ICPC моего региона

Read more »

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

By dmkozyrev, history, 2 months ago, In Russian,

Привет, codeforces! В рамках проекта по подготовке к олимпиадам по программированию в качестве задания была выдана эта задача на двумерное динамическое программирование.

Кратко суть задачи: дана матрица размера n2, где n ≤ 200 , в которой есть нулевые и ненулевые элементы. Расстояние на матрице между ячейками (x1, y1) и (x2, y2) определяется как dist = |x1 - x2| + |y1 - y2|. Каждый нулевой элемент нужно заменить ближайшим к нему ненулевым элементом, а если подходящих элементов несколько, то оставить без изменений.

Я написал решение на C++, которое получило вердикт Accepted, и решил ради эксперимента перенести его на python3, чтобы попрактиковаться с новым языком программирования. Вот что из этого вышло. Действий получается порядка O(n2), но с большой константой. При n = 200 должно пройти, но не проходит — вердикт TLE. Можно ли как-нибудь ускорить решение на python3, заменив ввод-вывод более быстрым (уже вроде как заменил, но может можно еще быстрее), или применив какие-нибудь другие хитрости, так, чтобы оно получило вердикт Accepted?

Кратко суть решения:

  1. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x *  и y ≥ y * .
  2. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x *  и y ≥ y * .
  3. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x *  и y ≤ y * .
  4. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x *  и y ≤ y * .
  5. Объединение ответов

Для каждого прохода 1-4 используем метод ДП, комбинируя ответы для соседних элементов, например, в 1 пункте: answer[x][y] = combine(answer[x - 1][y], answer[x][y - 1]) + 1

Read more »

 
 
 
 

By dmkozyrev, history, 2 months ago, translation, In English,

Hello, codeforces! I do not know how to solve this DP problem, so I really want to know how. I will explain the condition of this problem briefly. Link on original pdf with examples.

On our way we will meet several groups of bandits (from 1 to 20). Each group has two parameters:

  1. size[i] — number of bandits (from 1 to 1000)
  2. cost[i] — cost we have to pay them if we do not want to have problems (from 1 to 1000)

We can:

  1. Pay them cost[i] to pass them

  2. Pay them 2 * cost[i] to hire them

  3. Fight them. In this case we will lose size[i] hired soldiers. The first to die are those who had been hired earlier. The hired mercenaries leave our squad after participating in three battles.

You need to go all the way, having spent the least amount of money. Answer — this amount. At the initial time in our squad there are no soldiers.

The input file contains from 1 to 50 tests. On each input file, time limit — 3 sec, memory limit — 256 MB. Therefore, for one test — 0.06 sec. Tests can be different, numbers cost[i] and size[i] can be different.

I tried to apply two-dimensional dynamic programming:

  1. k — Number of passed groups.

  2. sum — The amount of money spent

The cell dp[k][sum] contains the best triple of the mercenaries (n1, n2, n3), who can fight in one battle, two and three battles. But I can not understand how to choose the best triple among all the transitions.

If we use sum of components, triple (1000, 0, 0) will be better, then (0, 0, 999), but after battle with size[i] = 1 we get (0, 0, 0) from first and (0, 998, 0) from second triple and second will be better.

If we use lexicographic order, triple (0, 0, 1) will be better, then (1000, 0, 0), but first triple can not win in battle with size[i] = 1000 bandits.

I ask you to help finish this problem to the end and, if possible, provide links to similar problems.

Read more »

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