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

Автор HolkinPV, 12 лет назад, По-русски

165A - Суперцентральная точка

В этой задаче нужно было реализовать то, что написано в условии. Для каждой точки отдельно проверим, является ли она суперцентральной. Для этого переберем все остальные точки и проверим, что у неё нашелся бы один сосед с каждой из сторон. Решение можно реализовать за время O(N2).

165B - Ночная работа

Эта задача решается бинарным поиском по ответу. Очевидно, что если число v являться ответом на задачу, то и любое число w > v будет являться ответом, поскольку число написанных строк кода могло только увеличиться. Поэтому, чтобы найти минимальный ответ, воспользуемся бинарным поиском. Чтобы проверить, подходит ли конкретное число V, воспользуемся формулой, указанной в условии. В этой формуле будет O(logN) ненулевых членов. В итоге получаем решение за O(log2(N)).

165C - Еще одна строковая задача

Для начала скажем, что вместо бинарной строки у нас есть массив чисел 0 и 1. Тогда нужно посчитать количество отрезков [lf;rg] таких, что сумма чисел на них равна k. Посчитаем для этого массива частичные суммы, а именно массив sum, где sum[i] – сумма чисел в отрезке [0;i]. Ответ на задачу будем считать следующим образом. Будем двигаться по массиву слева направо. Пусть мы находимся в позиции pos. Прибавим к ответу количество отрезков, сумма на которых равна k и которые заканчиваются в позиции pos. Для этого для каждой частичной суммы будем поддерживать массив cnt, где cnt[i] – количество раз, которое встретилась частичная сумма, равная i. Тогда в данный момент к ответу нужно прибавить величину cnt[sum[pos]–k]. Решение можно реализовать за время O(N), где N – длина исходной бинарной строки.

165D - Граф-борода

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

Для каждого пути, которое отходит от корня выпишем вершины и ребра, которые в него попадают. Величину расстояния можно считать отдельно. Для каждой вершины v предподсчитаем расстояние d[v] от неё до корня. Тогда если вершины x и y находятся на разных путях, то расстояние между ними d[x] + d[y], а иначе это разница их расстояний до корня abs(d[x]–d[y]). Также для каждого пути заведем дерево отрезков, которое умеет считать сумму на отрезке и изменять значение в точке, построенное на ребрах каждого пути.

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

165E - Совместимые числа

Рассмотрим произвольное число x для которого нужно найти ответ. Инвертируем биты в числе x, назовем это число y. Теперь посмотрим на битовое представление какого-либо числа a[i] из массива. Оно будет ответом для числа x, если для каждой позиции нулевого бита числа y в этой же позиции в a[i] также будет нулевой бит. Тогда остальные нулевые биты числа a[i] можно заменить на единичные (поскольку они не повлияют на результат операции AND).

Тогда будем считать такую динамику z[mask] = {0, 1}, которая означает, можем ли мы поменять некоторые нулевые биты какого-либо числа из массива a на единичные, чтобы получить маску mask. Начальными значениями динамики будут все исходные числа массива (z[a[i]] = 1). Чтобы осуществить переход, переберем каждый бит маски mask и попробуем его заменить на единичный, если он нулевой. Ограничения в задаче таковы, что длины двоичных представлений чисел не превосходят 22.

Посчитав такую динамику, чтобы ответить на запрос YES или NO для числа x, нужно посмотреть значение динамики от числа z[(y)&((1«22)–1)], то есть инвертировать биты в числе x и сделать это число длины 22. Тогда если значение в этой ячейке равно 1, то ответ YES иначе NO. А чтобы получить само число, которое является ответом, можно просто в ячейке z[mask] хранить то число, которое породило данный ответ. Итого решение, которое работает за O(2K * K), где K – длина бинарного представления чисел (K <  = 22).

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

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

В первой задаче можно было для каждого х посчитать min y и max y, аналогично для каждого у. А потом пройтись по точкам и проверить, укладываются ли они в этот интервал. O(n)

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

    понятно что решение с перебором O(n^2) проходят, не понятно почему много кто их отправлял и в разборе алгоритм с более сложной асимптотикой

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

      Если в этой конкретной задаче можно было так сделать, то почему бы и нет. Но в обучающих целях в разборе хотелось бы видеть наиболее оптимальные решения всех задач.

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

Спасибо за оригинальный проблемсет )

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

Подскажите, пожалуйста, асимптотику вот такого решения задачи B:

http://codeforces.com/contest/165/submission/1369641

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

    NlogN видимо

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

      NlogN при n<=10^9 ?? По-моему там на порядок меньше

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

    Тоже интересно. Решал так же, интуиция подсказывает, что слишком далеко перебирать не придется, но "не слишком много" — это не самая точная оценка времени.

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

    Я такое же сдал и, на сколько я понимаю, сложность O(log N) — так как увеличение V будет мало. (лучше точно проверить, но вроде как всегда меньше 10 раз)

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

Как-то разбор С очень не понятно.Как там всплыла линейная асимптотика, если мы проходим по массивы частичных сумм-это уже линия. Но тут ладно, я наверно туплю. А вот там пишут: где i=частичной сумме, но i-это индекс.Это что заводить массив на максимум из частичных сумм?

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

Если бы в B ограничение было бы хотя бы 2<=k<=16, было бы гораздо веселее =)

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

    чем?

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

      Наверное он имел ввиду то,что при возведении в степень 16,может вылезти за пределы,но опять же эта проблема тут решается делением.

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

        Ну на самом деле переполнение возникает и при k=6 и k=9, но результат получается отрицательным и условие n/k>0 всё равно перестаёт выполняться. По крайней мере у меня был такой баг (спасибо freopen за найденную ошибку), но решение при данных ограничениях работает правильно.

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

          Значит здесь однозначно правильный выход-деление.Нам точность дробной части не важна вообще.Жаль что я дошёл до этого уже после.

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

            Я делал делением в целых числах, но сначала возводил в степень. По-моему, более простой выход — использовать long long.

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

Я лично B задачу делал с помощью формулы бесконечно убывающей прогрессии,находил сумму,отсекал дробную часть и добовлял по 1 пока не подходило.Таких добавлений очень мало,ибо изначально очень близкое значение получается.не прошло только один тест из-за того что я для проверки в степень когда возводил,вышло за пределы лонгинта,переделал с делением прошло всё.

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

По моему в задаче Б всё проще если перебором выписать ответы для некоторых Н и К то можно увидеть

зависимость что каждые элемент увеличивается на 1 а каждый К и К+1 не изменяется из этого всплывает формула что ans=N-(n div k).

Но ета формула может дать погрешность в одиницу для этого проверяем если ответ по формуле удовлетворяет условия то выводим если нет то увеличываем на одиницу то того момента когда условие будет удовлетворено.

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

    По-моему проще написать бинпоиск, хотя так тоже можно)

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

    Эта формула по сути выводится из формулы бесконечно убывающей геометрической прогрессии(ans/1-1/k)>=n => ans>=n-n/k где ans это первый элемент,1/k-знаменатель прогрессии,а n-сумма прогрессии.Говорим об одних и тех же вещах разными словами.

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

Ну было очень интересно.

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

Я решал C куда проще, по-моему. Разубедите меня, если сможете, ладно? Разделим на два случая, при k=0 и k>0. При k=0 находим длины всех последовательностей, состоящих из 0, и складываем суммы арифметических прогрессий от 1 до длин этих последовательностей (метод двух указателей, l * (l + 1) / 2). При k>0 выписываем в массив все места, на которых стоят 1. Пусть их m, Тогда идем от 1 до (m — k) и прибавляем к результату (a[i] — a[i — 1]) * (a[i + k] — a[i + k — 1]). Что-то типа того.

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    var k,s,ans:int64;
        c:char;
        sum:array [0..1001000] of longint;
     begin
      readln(k);
      sum[0]:=1;
      while not eoln do
       begin
        read(c);
        s:=s+ord(c)-ord('0');
        if s-k>=0 then ans:=ans+sum[s-k];
        inc(sum[s]);
       end;
      writeln(ans);
     end.
    

    Вот самая простая реализация на паскале...

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

      Я пишу на Паскале. Ну, можно и так. Я описал, на мой взгляд, самое интуитивное решение.

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

      Андрей, разве не проще так сделать?

      1365063

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

      Имхо, моя реализация на Python существенно понятнее:

      k = int(raw_input())
      s = raw_input()
      
      a = [len(p) + 1 for p in s.split('1')]
      
      if k == 0:
          print sum(n * (n - 1) / 2 for n in a)
      else:
          print sum(a * b for (a, b) in zip(a, a[k:]))
      
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Интересно...я в дорешивании тоже пытаюсь сдать такое решение(мне оно тоже показалось проще), но падает на 67 тесте, и, смотрю, не у меня одного. Не могу понять, почему.

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

I'm trying to solve problem D "Beard Graph". I understand the idea but i don't see how to use a segment/fenwick tree in this case. Probably my problem is on understanding what HolkinPV means by " index of path from the root where v is situated". Can anyone give me some help on this please?

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

Can anyone explain the idea behind this O(n) solution for problem C by Scott Wu: http://ideone.com/sysG1b Thanks.

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

    Actually this solution is incorrect. It gives wrong answer even on test #1, anyway idea is quite simple. If for position i sum of 1's from position 0 to i is equal s and s >= k then you need to find number of positions with sum of 1's equal s-k (let's denote it as C[s-k]) and add it to the result. We will get full result after processing all positions.

    Instead of processing each position individually we can count the number of positions with sum of 1's equal to 1, 2, ... etc. and iterate over them. Then if we are processing some sum equal s we should add to the result value C[s]*C[s-k]. This solution will not work for k = 0. In this case we should add value (C[s]-1)*C[s]/2. Why? Because if we've got C[s] positions with sum equal to s then one of this position contains 1, so we need to find how many different sub strings we can get from C[s]-1 0's.

    Correct solution: 11487947

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

      Can you please again the idea behind adding C[s]*C[s-k] to the result. This part is not clear to me.

      Why we are adding C[s-k] to the result ? What does it represent ?

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

        I will try to explain my solution using the following example:

        2

        10100100010000

        First, let's calculate prefix sums of 1's. We get the following values:

        11222333344444

        Our C table looks like this:

        C[0] = 1

        C[1] = 2

        C[2] = 3

        C[3] = 4

        C[4] = 5

        Now we iterate over C table starting from i = 2 (which is our k) to 4 (which is maximum sum of 1's). Value C[i] is the count of positions which can be right end of our substring. Now we need to find the number of positions which can be left end of the substring. Number of such positions is C[i — k]. For example for i = 3 we get the following possible left and right end positions:

        1 0 1 0 0 1 0 0 0 1 0 0 0 0

        So for any i we've got C[i — k] (left ends) * C[i] (right ends) possible substrings with k 1's. Answer is the sum of such values for all i.

        Special case is k = 0. If I have for example C[2] = 3 it means that I have one position with 1 and two positions with 0s. So what I need to do now is to count number of all substrings of these two 0's. If Let's say I have n 0s, then I will have:

        n substrings of length 1 n — 1 substrings of length 2 n — 2 substrings of length 3 ... 1 substring of length n

        so generally the number of substrings of string of length n is sum of numbers from 1 to n which is n*(n+1)/2.

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

      Please Explain why is C[0] = 1 in your solution

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

        It is needed for substrings which begin from the first character of the original string. C[0] = 1 means that I have one left end with 0 1's = the empty string. Of course if the original string begins with some 0's the value of the C[0] will be bigger.

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

Please explain 165C — Another Problem on Strings. Unable to understand approach.

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

Can anyone explain Problem -C . Not getting the approach

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

    Consider two different cases when k=0 and when k!=0; When k=0, it is simple to calculate the number of strings by storing the position of occurrence of '1' in a vector and then iterate over the string and calculate the answer.(try it yourself it is simple). When k!=0,let's assume dp[i] = number of strings ending at position i and containing k 1's. Make a vector which stores the position of occurrence of 1 and use to calculate the answer. try it yourself.

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

A lot of sources which got AC at problem D returns different answers on this input :

7 1 5 6 4 2 3 3 5 5 6 3 7 1 3 4 2

I think is a good idea to introduce this test-case as official test.

UPD : Three samples of codes which got AC : First Second Third

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

can someone explain more detail problem E?thanks.

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

    Let's suppose you have a number X and we invert the binary digits of X, now we have a number Y that has some 1s and some 0s, we want to find another number Z that has a 0 in every position where Y has a 0. It is important to note that every 0 in Y must strictly be a 0 in Z, but each 1 can be either a 1 or a 0 in Z.

    A naive solution would be for every number Y in the range [1-4*10^6] iterate over every number Z in the same range, and for every valid pair, check if that number exists in a, if it exists you found an answer for Y, otherwise it's -1. Then you can just iterate over a and look at the solutions you precalculated by inverting the bits of each a[i].

    Of course, this wouldn't work because it's too slow, time complexity would be O(2^2*maxBits) if you iterate over all numbers in the range [1-4*10^6], or O(3^maxBits) if you use bitwise operations to ignore invalid Zs. Both too slow, so we need to optimize it.

    We will take similar idea, but change it slightly, for every Y that has an answer we say that we can propagate the answer to another number W, if and only if Y&W=Y and W has exactly 1 more bit turned on compared to Y. This works because as we stated earlier, we want Z to have zeros where Y has zeros, but if Y has a 1, we don't care what we have in Z, and because W is the same as Y, except that one 0 is now a 1, we know that Z will still be valid. We code this idea with DP and it becomes O(maxBits*2^maxBits)

    http://www.codeforces.com/contest/165/submission/18102743

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

      thanks for great explanation.

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

      The man who gave such great explanation didn't get any upvote(before I gave one), but the man who thanked him for his great explanation got 5 upvotes(now 6 including mine) !! Just wow !!!

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

      can't we solve E using bit trie? But the complexity is 2^23 i guess which is less than 10^7??

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

I get the idea in problem D but i don't understand the segment tree part. Can anyone help me out with this part?

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

Worrst tutorial ever!No one couldn't understand any problem specially problem C.

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

    Read code of top rating, maybe it helps (at least for me) =))

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

Can anyone please explain Problem -B . Not getting the approach.

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

    you can use binary search as given in the editorial but i have another approach -->

    think of it as

    find min v, such that:-
    
    1) n <= v*(1 + flr(1/k) + flr(1/k^2) + flr(1/k^3) ...)         
    consider this:-
    
    2) n <= v*(1 + 1/k + 1/k^2 + 1/k^3 + ...)
    
    lets just keep lhs aside for now, think about try to keep the rhs constant on going from eq 1 to eq 2.
    like:- 
    3) v1*(1 + flr(1/k) + flr(1/k^2) + flr(1/k^3) ...) = v2*(1 + 1/k + 1/k^2 + 1/k^3 + ...)
    
    as we can easily find (1 + 1/k + 1/k^2 + 1/k^3 + ...) == (k)/(k-1) and we can see from eq 3 that v1 >= v2 as (1 + flr(1/k) + flr(1/k^2) + flr(1/k^3) ...) <= (1 + 1/k + 1/k^2 + 1/k^3 + ...)
    
    so we can find v2 very easily using v2 = n*(k-1)/(k)
    v2 is the lower limit for our ans (==v1)
    now just run a loop from v2, as soon as the sum becomes >= n, break and you have the answer
    

    please correct me if my logics wrong here is the code 83607371

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

how to solve problem C using binary search ??

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

    I just did, you can see my solution here — 87349681

    Here is my logic —

    Basically, we do a 2 pointer theorem approach, in that we find the sum of substring starting with index i with the help of binary search for all i (Maintain a prefix sum array, to easily calculate required sum in a given interval starting from i).

    When that sum is same as k, we take 'mid' element we have obtained via binary search (corresponding to the right end of the substring) and take the left and right extremities of adjacent elements having the same value as the 'mid' element in the prefix sum array (Notice that each pair of extremities would have a unique identifier as the values in prefix array are increasing).

    For better understanding, I would recommend you to see the solution