Блог пользователя niyaznigmatul

Автор niyaznigmatul, 2 месяца назад, По-русски,

779A - Перераспределение учеников

Автор задачи: MikeMirzayanov

Для решения данной задачи воспользуемся массивом cnt[]. Проитерируемся по первому массиву с успеваемостями, и если очередная успеваемость равна x, увеличим cnt[x] на единицу. Аналогичным образом, проитерируемся по второму массиву, и если очередная успеваемость равна y, уменьшим cnt[y] на единицу.

Если после этого хотя бы один из элементов массива cnt нечетный, ответом будет  - 1 (это означает, что учеников с такой успеваемостью нечетное количество и их никак не удастся разделить пополам). Если же все элементы массива четны, то ответом будет сумма абсолютных величин массива cnt, делённых пополам, причем итоговую сумму тоже нужно разделить пополам, так как каждый обмен при таком нахождении ответа будет посчитан дважды.

779B - Странное округление

Автор задачи: MikeMirzayanov

Для решения данной задачи нам нужно добиться того, чтобы в числе n в конце было k нулей, а перед ними хотя бы одна ненулевая цифра. Будем рассматривать число n как строку и пройдем по ней, начиная с конца (то есть с самого младшего разряда). Пусть cnt равно количеству цифр, которые мы уже рассмотрели. Если очередной символ строки не равен нулю, увеличим ответ на единицу. Если cnt стало равно k и мы рассмотрели не все цифры в строке n — выводим ответ.

В противном случае, нужно удалить из строки все символы, кроме одного, который равен нулю (если таковых несколько, то нужно оставить ровно один из них). Таковой символ обязательно найдется, так как гарантируется, что ответ существует.

779C - Нечестные продавцы

Авторы задачи: MikeMirzayanov и fcspartakm

Для решения данной задачи нужно отсортировать все товары по возрастанию величин ai - bi. Затем нужно проитерироваться по отсортированному массиву. Для очередного товара x, если мы еще не купили k товаров сейчас или после скидок товар x будет стоит не больше, чем сейчас, нужно купить его по цене ax, в противном случае, нужно купить товар x по цене bx.

778A - Игра на строке

Автор задачи: firezi

В задаче нужно понять, в какой последний момент времени строка t будет такой, что из нее можно получить p вычеркиванием букв. Если в данный момент из строки t можно получить строку p вычеркиванием букв, то и в любой момент до этого это также можно было сделать. Поэтому решение — двоичный поиск по числу ходов, которые сделала Настя. Нужно для фиксированного момента времени m проверять, может ли p быть получена из t. Надо сделать m вычеркиваний Насти и проверить, что p подпоследовательность этой строки.

778B - Побитовая формула

Автор задачи: burakov28

Заметим, что задача по битам независима: изменение только значение i-го бита влияет только i-е биты других переменных. А сумма значений переменных больше, чем больше переменных имеют единицу на i-й позиции.

Будем решать задачу для i-го бита, то есть узнаем чему должен быть равен i-й бит загаданного числа. Для этого переберем оба значения и просимулируем программу, заданную во входном файле. Выберем то из двух значений, которое дает больше переменных, на которых стоит единица на i-й позиции. При равенстве выберем минимальное значение, то есть 0.

778C - Петрович --- полиглот

Авторы задачи: niyaznigmatul и YakutovDmitriy

При удалении буквы с индексом p бор меняется так, что все ребра из вершины на глубине p склеиваются в одно, как это видно на картинке из пояснения к примеру. После того, как ребра склеиваются, из нескольких поддеревьев получается их объединение.

Заметим известный интересный факт: если для всех вершин дерева v, пробежаться по всем поддеревьям детей v, кроме самого большого, то это будет работать за суммарно.

Пусть sx — размер поддерева с корнем в вершине x. Рассмотрим ребенка v с самым большим поддеревом — hv, то есть su ≤ shv для всех u — детей v. Если u — ребенок v, и поддерево с корнем в u не самое большое среди детей v, то .

  1. Пусть . Тогда и следовательно .

  2. А если же , то мы знаем, что su + shv < sv, и из этого следует, что .

То есть, если мы рассмотрим вершину w и посмотрим, когда мы по ней пробегались. Пойдем вверх по дереву из вершины w, каждый раз когда мы ее перебирали, размер текущего поддерева хотя бы удваивался. Из этого следует, что каждую вершину мы перебирали не более раз. Это доказывает оценку на все вершины суммарно.

Решение:
1, Перебрать число p
2. Перебрать все вершины v на глубине p
3. Объединить все поддеревья пробежавшись по всем поддеревьям кроме самого большого.

Как объединить поддеревья? Метод первый. Найдем самое большое поддерево, оно уже построено. Попробуем к нему добавить какое-нибудь другое поддерево. Для этого обойдем маленькое поддерево, параллельно проходясь по большому и добавляя вершины, которых в большом нет. Тем самым мы объединим все поддеревья с корнями в детях вершины v и узнаем размер объединения. Далее, надо вернуть все на место. Для этого во время объединения запомним все ячейки памяти, которые изменились, и их старые значения. После объединения, можно в обратном порядке восстановить старые значения.

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

778D - Перекладывание паркета

Автор задачи: pashka

Пусть ширина прямоугольника четная (если нет — повернем). Приведем обе конфигурации к такому виду, что все плитки лежат горизонтально. После этого, поскольку все ходы обратимы, нужно просто развернуть последовательность ходов для второй конфигурации.

Как получить конфигурацию в которой все плитки лежат горизонтально. Пойдем сверху вниз, слева направо, и будем выставлять все плитки в правильное положение. Пусть плитка стоит неправильно. Тогда попробуем повернуть ее в правильное положение. Если это не получается, потому что соседняя плитка ориентирована по-другому, перейдем рекурсивно к ней. Таким образом, получится "лесенка", которая не может идти дальше, чем на n плиток вниз. В конце этой лесенки будет две плитки, ориентированные одинаково. Производя операции снизу вверх, выставим верхнюю плитку в горизонтальное положение.

778E - Продажа чисел

Авторы задачи: niyaznigmatul и VArtem

Поскольку ответ на задачу считается независимо по каждому разряду во всех числах, будем использовать динамическое программирование. Обозначим dpk, C за максимальную возможную стоимость цифр, где k — количество рассмотренных младших разрядов, а C — множество чисел, в которых произошел перенос. Этой информации достаточно, чтобы выбрать, какую цифру поставить в текущем разряде A, и пересчитать переносы в следующий разряд и значение ДП.

Ключевой идеей является то, что возможных множеств чисел не 2n, а не более n + 1. Пусть мы рассмотрели k младших разрядов A и Bi. Рассмотрим все суффиксы чисел Bi длины k, отсортируем их по убыванию лексикографически. Из-за того, что ко всем этим суффиксам в результате добавится одно и то же число, свойство <<иметь перенос>> монотонно: если в числе Bx произойдет перенос, то перенос произойдет и во всех больших числах. Отсюда множество всех чисел, в которых будет перенос в текущем разряде, образует префикс длины m (0 ≤ m ≤ n) этого отсортированного списка. Таким образом, количество состояний ДП сократилось до O(n·|A|). Отсортировать все суффиксы чисел Bi можно с помощью цифровой сортировки за O(n·max |Bi|), приписывая каждый раз слева очередную цифру и пересчитывая порядок.

Осталось реализовать вычисление переходов в ДП за O(1). Для этого нужно поддерживать суммарную стоимость всех цифр в этом разряде, а также количество чисел с переносом в следующий разряд. При добавлении очередного числа с переносом эти величины несложно пересчитываются. После того, как все цифры в A обработаны, нужно обработать оставшиеся цифры в Bi (если такие есть) и взять наилучший ответ. Время работы: .

Разбор задач Codeforces Round #402 (Div. 1)
Разбор задач Codeforces Round #402 (Div. 2)
 
 
 
 
  • Проголосовать: нравится  
  • +94
  • Проголосовать: не нравится  

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

somebody plzz tell how to do string game using binary search.i read tutorial but i didn't get it..

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

    Let's consider the first test case, where you have this order of deleting characters:

    original word: ababcba
    target word: abb
    order: 5 3 4 1 7 6 2.
    

    Let's write down if we could obtain the target word after deleting characters order[0], order[1], ... order[i] of the original word (Note that we always delete characters in this order):

    [     5,   3,   4,  1,  7,  6,  2 ]
    [   YES, YES, YES, NO, NO, NO, NO ]
    

    This sequence is monotonous and thus, we could do a binary search to find the maximum index, which brings "YES". :)

    Hope that helps!

  • »
    »
    2 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    This problem has binary search property: Let i a arbitrary position of a[]. There are 2 cases: If you remove all the character of index a[1..i] and p is a subsequence of t. Then there will exist a position j in t such that 1<=i<=j<=|t| and if we remove all character from [1..j] then p is still a subsequence of t. Otherwise, then there will exist a position j in t such that 1<=j<=i<=|t| and if we remove all character from [1..j] then p is still a subsequence of t and there will be no position >=i that p is a subsequence of t. The first idea you maybe thinking of is to use complete search and search for the latest position that p is subsequence of t. unfortunately this approach take O(n^2) complexity (note that to check subsequence it take O(n)). So instead we can use binary search and search for the latest position and check if it's a subsequence or not.If it is then we move futher to the right, else we move back to the left. For more detail and better understanding see my submission 25052010.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Help me plzzz,What's wrong with my code ? (time limit on test 10) String game 25102212

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    It's a bruteforce, not a binary search.

    • »
      »
      »
      2 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Complete search is not fast enough for this problem because it's O(n^2) and n<=200000, try to use binary search to solve this problem.

»
2 месяца назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Where's the editorial for Div. 1 C and Div. 1 D?

»
2 месяца назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

The way I implemented C was pretty much brute force, but if you calculate the complexity it's N * 26 Log(N).

For each node U, you count how many duplicate nodes you'll have in its subtree if you remove it and its outgoing edges. We add this to the number of removals for level(U) + 1.

So you'll have a dfs(vector v), where all vertices in v are equivalent with respect to U (same prefix in the sub-trie). Since all are equivalent you add v.size()-1 to the number of duplicates. Now for every letter c, you make the vector of nodes that are children of a node in v through an edge labelled with letter c. Now do (at most) 26 dfs calls, one for each new vector. If the current size of the node vector is 1 or 0, you stop since there won't be any extra duplicates. The initial call is dfs(children of U).

Submission

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your solution is also , because if the size of v is 26, then n is distributed in this 26 subtrees, so every time you call dfs3 with v.size() == k, you use k nodes. You use only nodes, which are duplicate, that's why it's the same as if you only iterated over the small subtree.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you elaborate on the the statement: "The complexity is N*26log(N)". That is the most vague part in your solution

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

778C: I dont know why you wrote about biggest child of vertex. I implemented your solution and then removed "lets merge all subtrees to the biggest subtree" rule — it became even faster (935ms 146Mb vs 732ms 124Mb)

So plain solution with rollbacks works.

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    No, your solution makes link to whole subtree, instead of copying it. That's why your merge function works in min(s1, s2) time, where s1 and s2 are the sizes of the subtrees, which is equivalent to iterating over "all vertices in all subtrees except the largest one".

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится -41 Проголосовать: не нравится

      пояснил по понятиям!!!

    • »
      »
      »
      7 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you please explain why they are equivalent? It really puzzled me.

      • »
        »
        »
        »
        7 недель назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Because dfs visits vertex for the first time if it's in both subtrees, that are being merged. Every next time the vertex is visited, it appears again in a new subtree. It means vertex is visited k - 1 times, if it appeared in k subtrees. So, consider biggest subtree and for every vertex this  - 1 from k - 1 means "we don't visit biggest subtree".

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is wrong with my appraoch for "778C — Peterson Polyglot"? normal dfs when i enter vertex i try to kill its children and count the children of the children which occur more than once + number of its children and update kill[depth] after that iterate over kill get the largest one x to be the solution (n-x)... can any one help me http://codeforces.com/contest/778/submission/25119082

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

779B непонятно: входные данные 10203049 2 выходные данные 3 Там же 4 и 9 можно удалить, и получится, что число нацело делится.

  • »
    »
    7 недель назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Должно делиться на 10 во второй, то-есть на 100

    • »
      »
      »
      7 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Так 10203000 делится на 100 нацело.

      • »
        »
        »
        »
        7 недель назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        Удалить это удалить, а не заменить на 00. Если бы удаление делалось заменой на нули, то не было бы возможности получить один 0, в примерах.

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain the time complexity of the binary search solution to the String Game problem?

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

779C — Dishonest Sellers why i need to sort with respect to a[i]-b[i] ? what is the proof ?