Блог пользователя danilka.pro

Автор danilka.pro, 9 лет назад, По-русски

483A - Опровержение гипотез

Автор задачи gridnevvvit

В задаче предполагалось два решения:

  1. Перебрать всевозможные тройки, и проверить, правда ли, что для этой тройки гипотеза неверна. Асимптотика такого решения O(n3logA)
  2. Разобрать несколько случаев. Например, это можно сделать так:

if (l % 2 != 0) l++; if (l + 2 > r) out.println(-1); else out.println(l + " " + (l + 1) + " " + (l + 2));

Авторское решение: 8394832

483B - Друзья и подарки

Автор задачи gridnevvvit

Авторское решение — бинпоиск по ответу. Во-первых, заметим, что если из набора 1, 2, ..., v можно собрать подарки, то и из набора 1, 2, ..., v, v + 1 можно собрать подарки. Пусть f(v) — функция, возвращающая ответ на вопрос: правда ли, что из набора 1, 2, ..., v можно собрать подарки друзьям. пусть f1 — количество чисел, которые делятся на x, а f2 — количество чисел, которые делятся на y. и число both — количество чисел которые делятся и на x, и на y. Тогда в первую очередь первому другу мы постараемся отдать f2 - both чисел, а второму — f1 - both чисел. После этого нужно проверить, сможем ли мы раздать числа, которые не делятся ни на одно из чисел x и y.
Таким образом, решение за

Авторское решение: 8394846

483C - Разнообразная перестановка / 482A - Разнообразная перестановка

Автор задачи gridnevvvit

Разберем, как работает решение на большом примере, например

1 10 2 9 3 8 4 7 5 6

На нечетных местах мы имеем возрастающую последовательность 1, 2, 3 .., а на четных — убывающую последовательность n, n - 1, n - 2, ... Получим таким образом решение, выведем первые k чисел указанной выше последовательности, а потом сделаем так, чтобы соседние разности были равны единице.

Решение за асимптотику O(n).

Авторское решение: 8394876

483D - Интересный массив / 482B - Интересный массив

Автор задачи gridnevvvit

Будем решать задачу отдельно для каждого бита. Предположим, что пришло новое ограничение: l[i], r[i], q[i]. Если в числе q[i] бит с номером pos единичный, то у всех чисел на отрезке [l[i], r[i]] этот бит тоже будет единичным. Теперь можно воспользоваться стандартной идеей прибавления на отрезке оффлайн. Сделаем два прибавления в массиве s[bit] — в позиции l[i] мы сделаем прибавление 1, а еще одно в позиции r[i] + 1, там мы прибавим -1. Таким образом, если мы насчитаем частичные суммы на массиве s[bit], то, если s[bit][i] > 0, то бит bit в этом числе будет единичным, иначе — нет. После этого можно реализовать дерево отрезков, чтобы проверить выполнимость изначальных запросов.

Авторское решение: 8394894

483E - Игра со строками / 482C - Игра со строками

Автор задачи gridnevvvit

Переберем все пары строк, и подсчитаем маску mask — единичные биты будут находится только в позициях, в которых эти две пары строк имеют одинаковые символы. Таким образом, используя биты, соответствующие любой подмаске маски mask, мы не сможем отличить эту пару строк, поэтому добавим в маску d[mask] биты в позиции i и j. Таким образом, в d[mask] мы храним маску тех строк, которые мы не сможем отличить по заданной маске mask. Используя указанную выше информацию, мы сможем просто насчитать эту динамику.

Теперь, когда у нас имеется эта динамика, нетрудно восстановить ответ. Переберем маску mask. Попробуем задать еще один вопрос, то есть добавить в эту маску еще один бит. После этого мы могли отгадать некоторые строки, а именно те, что останутся в виде единичных битов в маске s = d[mask] ^ d[mask | (1 << pos)] (pos — позиция нового вопроса). Осталось аккуратно подсчитать количество бит в маске s и пересчитать искомое математическое ожидание.

Авторское решение: 8394918

482D - Случайная функция и дерево

Автор задачи RoKi

Посчитаем динамику d[v][p] — ответ на задачу для поддерева вершины v с размером, имеющим четность p.

Научимся считать эту динамику для вершины v. Для начала посчитаем количество различных раскрасок при обходе потомков в порядке возрастания номеров. Умножим эту величину на 2 и получим раскраски при обходе потомков в порядке убывания номеров. Но теперь, возможно, появились раскраски, которые мы учли 2 раза. Давайте рассмотрим некоторое поддерево вершины v и поймем, когда оно учтется 2 раза.

Рассмотрим четности поддеревьев потомков, которых посетила наша функция (0 или 1). Первое, что нужно заметить: если среди этих величин есть различные значения, то такое поддерево при разных обходах будет раскрашено по-разному (это вы можете доказать сами). Теперь все наши посещенные потомки имеют одинаковые по четности размеры поддеревьев. Если размеры поддеревьев четные, то очевидно, что такое дерево учтется 2 раза. А вот если размеры поддеревьев нечетные, то нас интересуют только случаи, когда мы посетили нечетное количество потомков. Таким образом, из нашей динамики нужно вычесть количество способов раскрасить любое количество потомков с четным размером поддерева и нечетное количество потомков с нечетным размером поддерева.

Авторское решение: 8394936

482E - ELCA

Автор задачи danilka.pro

Будем обрабатывать M запросов блоками по штук (таких блоков, очевидно, тоже ). Каждый блок обрабатывается следующим образом:

Сначала поиском в глубину посчитаем для каждой вершины v значение , где u — любой предок v, а sizei — размер поддерева вершины i, включая саму вершину. Эта величина характеризует изменение ответа при 'отрывании' или 'прикреплении' вершины v, а именно, после выполнения одной из этих операций ответ изменится на pathv·sizev (уменьшится или увеличится соответственно).

Тем же образом посчитаем значение chv — количество всевозможных пар вершин, наименьший общий предок которых равен v. Эта величина характеризует изменение ответа при изменении Vv, а именно, при изменении величины Vv на dVv ответ изменится на chv·dVv.

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

На следующем рисунке представлен пример такого 'сжатия'. Красным обозначены вершины в блоке запроса, синим — помеченные вершины, пунктиром — ребра Pv → v сжатого дерева.

Пример сжатого дерева

На таком сжатом дереве нужно посчитать для каждой вершины v еще одну величину Cv — размер поддерева вершины исходного дерева, которая лежит на пути от Pv до v в исходном дереве после Pv (непосредственный сын Pv).

Попробуем обработать запрос на смену родителя вершины v с pv на u в сжатом дереве. Ответ, как уже было сказано выше, сначала уменьшится на pathv·sizev. Теперь для каждой вершины i, лежащей на пути от корня до Pv, изменятся две величины: sizei уменьшится на sizev, а chi уменьшится на величину, равную sizev·(sizei - Ct), (Pt = i), а pathi останется прежним. Для всех остальных вершин j, напротив, изменится лишь величина pathj — она уменьшится на . Теперь мы получили сжатое дерево, в котором все величины посчитаны с учетом того, что поддерево вершины v было удалено. Аналогичным образом происходит пересчет величин с учетом добавления вершины v в качестве сына вершины u (не забываем обновлять также и Cv).

Посмотрим, как будет выглядеть обработка запроса на смену значения Vv вершины v. Ответ, как было описано, изменится на chv·dVv. Также изменятся все pathi для вершин, лежащих в поддереве v (их несложно пересчитать с помощью значений Cto, все остальные значения останутся прежними.

Таким образом, сложность решения составляет , что в случае N = M составляет .

Авторское решение: 8394944

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

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

По div1B — поскольку построенный массив не будет меняться, можно вместо дерева отрезков использовать частичные суммы.

Посчитаем для каждого бита количество чисел на отрезке, которые содержат 1 в этом бите. В AND'е на отрезке этот бит будет единичным, если это количество равно длине отрезка.

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

C можно было решать, перебирая рекурсивно маски и пересчитывая классы эквивалентности за O(n) при добавлении позиции в маску.

По времени получается O(2^length * n) и заходит в TL на грани (спасибо за ограничения), но зато памяти достаточно всего O(n*length*length).

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

Well, will English translations be available at sometime? google translate was blocked in China.:D

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

А разбор по задаче Div1-D будет?

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

Div. 1 B — можно решать, не разбивая по битам. Дерево отрезков с модификацией "побитовое ИЛИ" на подотрезке и запросом "побитовое И" на подотрезке (для проверки).

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

I think that problem 483B could be solved in a mush easier way, which works O(1): 8386617

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

There are lots of very similar ways to solve Game with Strings. Here are two more of them: first, calculate d[mask] as in the editorial.

1) The number of different masks you visit during a game is equal to number of questions you ask. So from linearity of expectation the expected number of questions is the sum of the probability that you will visit mask, for all masks.

That probability is easy to calculate: it's .

See 8396215 for the code.

2) Let dp[mask] be the expected number of questions from state mask. When we try to ask question pos in state mask, the chance that we will not guess correctly right away is equal to the fraction frac = bitCount(d[mask ^ (1<<pos)]) / bitCount(d[mask]).

So dp[mask] is equal to the average of 1 + dp[mask ^ (1<<pos)] * frac, for all pos not in mask.

See 8412617 for the code.

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

    Why should I divide binom(len, bitCount(mask)) ? I don't understand this.Can you explain it?

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

      You're on the start state and you want to know the probability that you will reach the set of questions asked represented by mask. You will reach mask unless one of the following things happen first:

      • By asking all questions (or some of them) in mask you already know what the answer is.
      • You ask a question not in mask.

      For the first item not to happen, you need the final answer to be one of the values which is not immediately distinguishable from the replies to queries to positions in mask. By construction of the d[] array, there are bitCount(d[mask]) such values, so the probability that the answer is a "good" one for you to reach mask is .

      This leaves the second case. If the answer is a good one, it's still possible that you will ask a question not in mask, and therefore not reach it. For this not to happen, you need your first bitCount(mask) questions to be exactly the ones in mask. As you have len choose bitCount(mask) ways (or binom(len, bitCount(mask)) ways) to choose your first bitCount(mask) questions and only one of those ways is good, this is responsible for the factor.

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

What does totalGuessed[i] denote in the link given in the Div1 C- Game of Strings? http://codeforces.com/contest/483/submission/8394918

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

Why we are doing sum[r[i]]-- in the solution of Div1-B ??

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

    Instead of iterating all the intervals to set the bits to 1, he stores the beginning and end of those intervals and only iterates the whole array one time for each bit position

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

Can someone explain Div2/b with more details?

#include <iostream>

using namespace std;


int main()
{
    int cnt1,cnt2,x,y;
    cin >>cnt1 >>cnt2 >>x >>y;
    int l=1,r=INT_MAX,m;
    while(l<r){
        m=(r-l)/2+l;
        if(m-m/x>=cnt1 && m-m/y>=cnt2 && m-m/(x*y)>=cnt1+cnt2){
            r=m;
        }
        else{
            l=m+1;
        }
    }
    cout <<r;
    return 0;
}

always CE

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

Sorry, but can anyone explain to me the Div1-C method? I can't understand it well. 1. the solution says: Let's handle some mask mask. Now we should try to make one more question in position pos, which is equal to adding one more 1-bit in mask in position pos. What does it mean by saying "make one more question"? 2. what does this s = d[mask]^d[mask|(1<<pos)] mean exactly? I took it as "if I guess position pos, the remaining 1-bit(s) in s denote the string that I am not sure if the selected string is one of them". But I am not sure about this.

Please forgive my broken English...

»
9 лет назад, # |
Rev. 6   Проголосовать: нравится -14 Проголосовать: не нравится

Deleted

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

HI ,Every one.
Can you help me with pro Div1B/Div2D ?
My submission got ACCEPTED.
BUT, I have a test which it's answer should be NO.
AND my AC code print YES.
the test is:
5 2
1 5 1023
1 5 511
AND THIS IS MY SUBMISSION:
http://codeforces.com/contest/482/submission/29177333

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

      Abusing notifications, huh?

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

      Passing system test doesn't mean your program is correct. It only means it passed all tests, the author thought of. It should happen barely, but you can't get rid of it.

      For example think of a code, which does if()s for all given test cases, and prints the correct answer. Obviously it won't work generally, but it will get AC.

      It's okay if you notice this, and ask to add this to tests, but you shouldn't abuse notifications, as extraVirgin said. Also, you should fix your code at your own, to pass both system tests, and this test.

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

483A — Counterexample how did he come up with that algorithm ? can anyone please explain

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

    see ,between any two even number there is an odd number(ex:10,11,12) so if (r-l+1)>3 and l is even then the answer is l,l+1,l+2 else you have to print l+1,l+2,l+3.(please ensure that if d==3 or d<3 and l is odd then answer is -1)