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

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

Скоро, 24 октября, 21:00 MSK, состоится очередной Codeforces Round #275 для участников из обоих дивизионов. Обратите внимание на необычное время старта раунда!

Задачи этого раунда готовила команда Саратовского ГУ #3 в составе: Гриднев Виталий (gridnevvvit), Данил Сагунов (danilka.pro), Роман Киреев (RoKi).

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Распределение баллов:

Div1: 500 1500 1500 2000 2500

Dvi2: 500 1000 1500 2500 2500

Соревнование закончено, поздравляем победителей!

UPD:

Div1:

  1. tourist
  2. Petr
  3. subscriber
  4. uwi
  5. PavelKunyavskiy
  6. mmaxio
  7. Ra16bit

Div2:

  1. dickXD
  2. meodorewan
  3. charlie
  • Проголосовать: нравится
  • +191
  • Проголосовать: не нравится

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

Скудноватое описание. Даже страшно

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

how to solve the div2 D,please help me

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

I am really sorry to say but some of your previous contests english translation was quite really bad to understand . If possible please provide explanation of test cases . Hope this time everything will be fine and everyone will enjoy it :)

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

Zlobober — новый координатор или просто в этом раунде помогал?

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

first round after my 1700+, gl & hf!

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

Sherlock comix in prevous edit.

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

Whoa the round is at midnight in my country. Overslept is not an excuse.

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

I want to participate in the contest very much!However,it's at 1 a.m in China,we must stay up!

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

thank you!your problem is hard or easy?your contest has very good problem .!

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

Ну наконец-то раунд не в воскресенье. Пожалуй, напишу его.

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

Please short explanation for problems.

Also explanation of sample tests.

" THANKS FOR READING

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

wow I'm so happy there are so many new contests on CF these days. Hopefully this pace won't go down in the future!

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

If the time is corrected, Some of Chinese Coders may start coding from 1:00 a.m. to 3:00 a.m. and waiting the system test until 3:30 a.m. Then sleep for a while and participate the regional warm-up contest. The next day(Sunday) participate the regional onsite contest for 5 hours. What a Fighting weekend.

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

    Definitely no Chinese coders will compete in this round if they are going to participate in ICPC regional just on next day. They just need good rest.

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

      Good night~ wake up at 00:30 a.m.

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

      Alas, I (Chinese coder) really want to compete in this round, though I will not participate in ICPC regional, just the point is that our dormitory's blackout and my laptop can't afford to complete this competition …… ╮(╯▽╰)╭

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

If only the round beginning time would be advanced to regular 19:30 MSK suitable for most participants.

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

Where do i go to register for the contest. not allowing me to do so

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

Any particular reason for the unusual timing of the round ?

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

Timing is perfect for me again, thanks ;-) 19:00 CEST, typically it's 17:30 which is too early to be finished at work...

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

О! Описания уменьшаются =)

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

@gridnevvvit Your last round was a DIV2 round and the round you arranged before it was a DIV1 round . so , it's good to see you coming back with a DIV1 round once again :)

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

Было бы здорово начинать подобные контесты хотя бы на часа 1-2 раньше. Я из Новосибирска, и в этом раунде принять участие не могу (начало в 12 ночи). Я понимаю, что ориентируются на западную часть России, но начинайте по стандарту в 19:30 МСК что ли. Спасибо за внимание.

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

    Codeforces ориентируется не только на Россию (ведь, например, авторы бывают из разных стран).
    То, что неудобно вам, может показаться удобным кому-то другому (например, Betlista выше пишет, что из-за сдвига он сможет поучаствовать, а в 19:30 бы не смог).
    Из-за этого и решили уйти от "по стандарту в 19:30 МСК" — чтобы каждый пользователь смог посоревноваться в удобное для него время (пусть и не каждый раунд).
    Такая же практика и на американском TopCoder, где иногда раунды проходят в 5 утра по Москве, а иногда "нормально" — вечером.

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

Smiling:)

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

Omg the starting time of the contest is coincides with my sleeping time :))

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

There has been a lot of math in recent contests! Hope for something algorithmic! :D

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

First Div. 1 :) Gl & Hf everyone

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

I dont understand why this congruency works sometimes :

Scoring system will be announced later == Registrations are closed 5 minutes before the round. Why delay it so long as in few minutes before the contest? Why delay it anyways?? Any specific reasons that I dont know of?

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

4 часа утра... температура тела 38... посмотрим на что я способен.

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

    Итог: решил С за довольно длительное время... по D остановился на WA7. Увидел что B div2 оказалось сложной и стал думать её. И неужели не заходит вот такое решение: бинарный поиск по ответу с чекером n - a >= cnt1 && n - b >= cnt2 && n - c >= cnt1 + cnt2, где n — проверяемое количество чисел; a — количество чисел, которые не подходят первому другу; b — количество чисел, которые не подходят второму другу; c — количество чисел, которые не подходят обоим друзьям. Соответственно, a = n / x, b = n / y, c = n / ( x + y ).

    UPD Решение таки зашло. Не понимаю тогда, в чем была сложность и почему эту задачу решило около 300 человек.

    Код

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

      Не могу придумать контрпример, но кажется условия n - a >= cnt1 && n - b >= cnt2 && n - c >= cnt1 + cnt2 недостаточно для того чтобы нам хватило чисел подарить обоим дрвузьям.

      Пусть f — количество чисел, которое нужно подарить первому другу. Может оказаться, что f > b, и тогда можем получить n - b - f < cnt2, то есть для второго друга чиселок не хватит

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

        Ну так это проверяется третьим условием как раз. Первое условие — это то что нам хватит чисел для первого друга, второе — для второго друга, а третье — для них двоих.

        И пример на этот случай:

        3 3 2 3

        При n = 6: a = 6 / 2 = 3, b = 6 / 3 = 2. Тогда первые два условия выполняются (n - a >= cnt1 и n - b >= cnt2), а вот третье условие нет, так как c = 6 / ( 2 + 3 ) = 1: n - c = 5 < 3 + 3, то есть как раз то, о чем ты говорил, нам хватает чисел для первого друга и хватает чисел для второго друга, но если мы начнём их распределять некоторым способом, то в итоге нам их не хватит.

        P.S. В этой задаче при таком решении x и y могут быть любыми, а не только простыми — еще одна нелогичность этой задачи. Хотя, быть может, авторское решение обладает некоторым смыслом относительно их простоты.

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

          Да, согласен. Просто немного запутался в твоих обозначениях.

          Единственное что: c = n / (x*y), а не n / (x+y)

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

      у меня зашло линейное решение (1) первому надо много подарков, подарки 2му влазят в неподходящие 1му (n-n/x=cnt1=>n~cnt1*x/(x-1)) (2) наоборот — 2му много, 1му огрызки в промежутках 2го (3) если оба случая не подошли — пропускаем каждое 1/xy число не подходящее обоим (n~(cnt1+cnt2)*xy/(xy-1)), остальные гарантированно делятся

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

How to Solve division 2 Problem-:B ?

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

    i think with binary search

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

    i solved it recursively. consider lower bound of allowed numbers to be L. the absolute minimum numbers you need to consider is cnt1+cnt2. so you look at numbers from the range [L,cnt1+cnt2+L-1]. the numbers divisible by both x&y cant be gifted. from the remaining numbers those divisible by x were gifted to second frnd and those divisible by y were gifted to first friend. now the numbers left can be gifted to either friend.After some thinking you can argue that they should be gifted to first friend and if some are left even after that then to the second. the arguement for this is based on the fact that x < y.i am sure you can think of it :). after updating cnt1 and cnt2. apply the process recursively with new lower bound as cnt1+cnt2+L (i.e. upperbound of previous process +1).

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

      I tried a solution like that but it wasn't working for me. I ended up using the fact that for any choice of v, there will be v/x multiples of x, v/y multiples of y and v/(x*y) multiples of both x and y (since x and y are unique primes).

      You can figure out how many free choices you have left and increment v accordingly.

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

How to solve C DIV1 problem ? . Thanks in advance.

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

How to solve Div-1 A ?

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

    The first (n — k) numbers could be 1,2,3 ... (n — k) after which we print n, n — k + 1, n — 1,n — k + 2 .... for the rest of the numbers.

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

    First, follow a pattern 1, n, 2, n-1, 3, n-2, ...; do it k-1 times. Than add remaining numbers in the natural order (decreasing or increasing depending on k's parity).

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

    I printed 1 and then printed p=1+k, then decreased k by 1 and then printed p=p-k and continued the series. Like, if k=3 and and n is anything arbitrary for an instance, I printed 1 4 2 3. Notice the difference in each adjacent values. And in the end I printed all the remaining values less than n.

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

    That one's pretty easy. The task asks you to find some array of length n so that the amount of absolute value of differences of each two consecutive elements is equal to k.

    I did it that way:

    Our answer:
    1 n 2 n-1 ... n/2
    

    And if we are about to print the (k+1)-th number we just print our latest number (- OR +) 1 which will make it look that way:

    For example: N = 9, K = 3
    1 9 2 3 4 5 6 7 8
    And N = 9 K = 4
    1 9 2 8 7 6 5 4 3
    

    As you have probably noticed if K mod 2 is equal to 0 then we print our latest number - 1. Else: latest number + 1.

    Pretty easy solution and easy to write down, work time: O(n)

    edit: whoops, i think i'm late for a party

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

    Not accepted yet, but I think it will be so... :) With first k elements You just can generate something like this: 1 1+k 2 2+(k-2) 3. Every needed difference will be here, k = |1+k — 1|, k-1 = |2 — 1+k|, k-2 = |2+(k-2) — 2|, k-3 = |3 — 2+(k-2)| ... And now, after that, just write the rest, n — k elements, one by one: 1+k+1 1+k+2 1+k+3 ... n-1 n. Difference between 1+k+1 and previous element is for sure not greater than k since k>=1 and previous element has to be between 2 and 1+k. Sorry for my English :)

    EDIT: Aldiyar explained similar solution much better in his post, but it wasn't there when I was writing mine, sorry for doubling answer :)

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

So guys what do you think about the difficulty level of div2 probs?

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

    A-As Usual Difficulty. B-Very Much tricky. Perfect Problem who loves math. C seems easier to most of the div2 contestants but I got lots of pain and still not sure if it will pass. D was an awesome problem. No Idea how to solve it. E- I saw factional output — pressed ctlr+F , looked for a word "expected", found it and immateriality closed the tab.

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

Весь контест упихивал С в ТЛ.

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

    +1. Вот интересно, неужели там есть решение за 2k (k — длина строк)? Я своё за 2k·(n + k) упихивал ногами, руками и другими частями тела, и всё равно в ТЛ оно лезло только на Java8. Если у жюри решение медленнее 2k, я бы с удовольствием посмотрел, как оно работает на Java7.

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

      2k·k можно сделать, если это что-то сильно меняет

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

      В C проходит даже 2m * n * m. При этом в B у̶ ̶м̶е̶н̶я̶ ̶у̶п̶а̶л̶ ̶N̶ ̶*̶ ̶l̶o̶g̶N̶ я написал квадрат, хех.

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

        Не, на плюсах не интересно, вы мне на Java7 решение покажите. Или у авторов логика "напишем заоптимиженное решение на плюсах и поставим ТЛ пожестче"? Ну т.е. зачем ТЛ 1 секунда а не 2, какое асимптотически неправильное решение пытались этим отсечь?

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

          Ну вот, например, решение за O(n*2^k) на Java 7 — 8393928. Если что, мне такой ТЛ тоже не нравится.

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

          Переписанное на Java 7 моё решение с контеста за O(2k·k) отрабатывает за 233 мс: 8394627

          Но согласен, что было бы разумно или отсечь O(2k·n), увеличив n, и получить более сложную задачу, или ослабить TL в текущей постановке.

          EDIT: впрочем, на самом деле моё решение за O(2k·k·n) с константой 1 / 64, так что от O(2k·n) его всё равно так просто не отделить.

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

          Так моё 2m * n * m и пытались отсечь же. Оно 1.5 секунды выдавало у меня весь контест в запуске, потом я придумал массивы апдейтов предподсчитать.

          Я понимаю, что у меня на плюсах, но зато и на один множитель больше в асимптотике.

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

        double post

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

    ++

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

How to solve problem B of div2 ?

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

    Binary search

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

      can you please explain the some more, i used a different approach and would like to know how to do it with binary search :).

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

        All you need to do is to see if a particular N (1..N) can be split into the 2 sets. Let S1 and S2 be the sets for friend 1 (with prime x) and friend 2 (with prime y) respectively We can observe that in a set we can put the multiples of other prime.

        S1 = {all multiples of y — multiples of x*y} S2 = {all multiples of x — multiples of x*y} The elements that can go in either sets are: Remain = N — multiples of x — multiples of y + multiples of x*y

        So just check if using Remain you can satisfy the deficiency in S1 and S2.

        http://codeforces.com/contest/483/submission/8395374

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

      Bad, it is mathematics.

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

How was Div2 B supposed to be solved?

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

    I solved it using segment trees (sadly after the contest).

    Initially set all the values to 0 and the if a query(L,R,V) comes, update all the values in the range(L,R) with (a[i] = a[i] | V where L <= i <= R).
    while joining nodes in the segment tree do seg[node] = seg[2*node] & seg[2*node+1] and finally check for each query_range whether the bitwise and (&) of all the values equals to the required value i.e check value(L,R) = V . This got AC .

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

    Some people used binary search, I did not. My approach is as follows:

    1.Set the answer=cn1+cnt2 initially.

    2.Then you can fulfil the requirements of the first friend by giving the numbers to him which are not acceptable by the second friend and vice versa.

    3.Let the friend with more requirement of numbers be friend1(cnt1>cnt2).Then you can give the numbers in the range [1,answer] not already given to any of them to friend 1. Then if his requirement is done you can give the remaining numbers to friend 2.

    1. If you see that both friend's requirement is done then you can print the answer else you can increment answer by sum of remaining requirements of both friends and repeat from step 2.

    Code http://codeforces.com/contest/483/submission/8394005

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

    i solved taking a long long a = cnt1+cnt2, & then checking if a — (a)/(x*y)>= cnt1+cnt2; if false, then a+=(cnt1+cnt2-(a-(a)/(x*y))), and so on. becouse the numbers that are multiples of x*y cant be taken as answer in any of the two cases. You have to check in the same way if there are enough numbers int the interval that aren't divisible by x, and the same whith y.

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

      Is that working for 3 1 2 3 input?

      a = 3 + 1 = 4
      a - a/6 >= 1 + 3
      return 4
      

      but the result is 5 — it was first input from problem statement...

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

I think 1 sec for B and C is too strict.

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

so the author thinks that div1 B as hard as div1 C ?

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

    I agree.Let's hope that no source with correct idea will get TLE.It wouldn't be nice...

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

      Yeah.The hope is not enough...I took TLE with my 2^m*n complexity which works much better in practice.If this was the official complexity, than that limit is too small.In the other case, the pretests are not good(nobody took TLE on pretests)

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

        There are sources which pass the tests and have 2^m*n like mine, so, anyway, the time limit should be bigger for letting the sources which are not optimized at maximum to get AC to...the problems were very nice anyway.

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

Accepts for C is more than B in DIV2 :D

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

I dislaked A — div1 very much. f*ck math.

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

Too fast SysTest . Hope Rating update will also be this fast :D

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

I could not optimize C in time. Unfortunately it works 1.2 secs at worst case :(

UPD: Thank god, codeforces faster then my pc. :D

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

Not sure if I'm stupid or just bad at constant optimization — is a 50*20*2^20 solution supposed to pass for div 1 C?

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

Bye Bye div1 :(

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

In what world are B and C the same difficulty? :D

I'm curious what the hell did the author think

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

    Maybe it was meant to work in 50*20*2^20 =(

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

      We did not notice, that idea of solution with working time O(len·2len) (len = length of strings) is too hard.

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

      Well then 1s is a horrible time limit. And even so, I think the problem is still harder.

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

    You maybe mean "C and D".

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

      No, I meant that the author gave 1500 for both B and C while the results show their complexity to be slightly different

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

        In general, it's hard to evaluate problem difficulty once you know the solution (especially if you wrote it and tried a few variants).

        Hmm, but there are three authors... Typically, getting a couple of others to test a problem gives you a good idea about the difficulty...

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

          True that it is hard, but except the three authors there is usually a tester/helper (I guess Zlobober in this case) who should detect such miscalculations.

          I'm really curious of the solution, maybe it does look simple once you know it.

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

            Actually I found a way to improve my 50*20*2^20 solution to 20*2^20 fairly easily, but the explanation would be pretty long. The solution is that if X is a set of questions, then DP[X] is the average of DP[X|(1<<i)] for all i that aren't in X, plus the number of strings that can't be distinguished by that set of questions.

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

      No, B and C. They were worth the same number of points, and the actual gap in difference is dramatical.

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

    Not only that .This is the condition in DIV2 ->

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

      Yep, serious mistakes in complexity predictions. I guess it would've been really good to use dynamic scoring if the authors weren't too sure .

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

Мне одному кажется, что стоило в задаче С ограничить строки длиной 16 и оценить задачу в 1000 баллов?

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

Good bye Yellow!

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

Верните баллы за задачу B(div1)! Решение, посланное на контесте получило ТЛ, перепосыл этого же кода в дорешке — АС. Сейчас кину ссылки на обе посылки (как только пойму, как это делать).

UPD. Отбой, решение работает от 980 до 1000мс (тут ТЛ) в зависимости от настроения серваков КФ.

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

Wow, a lot of systest fails and hacks in C. I'm wondering if most of the failed submissions mixed up string length and n somewhere.

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

    WA22 is the case n = 1. My solution printed 1 while the answer is clearly 0. I saw lots of solutions which failed this test.

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

      Ok, this seems like a problem with a high probability for cheap mistakes. Not that I'm complaining. It is the only reason why I got such an unprecedentedly good (for me) result.

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

This contest was some difficult then other contests! Are someone explain solution of div 2 B problem??? please explain! (sorry for bad english !)

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

    Binary search the answer..... to check whether we can distribute the presents between the friends using a certain v, we can use inclusion-exclusion. this might help : there are exactly n/p numbers between 1 to n which are divisible by p.

    hope it helps.

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

8387870 Why my submission is skipped ?

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

What was the expected time complexity for problem C?

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

    I had O(N * 2 ^ string length)

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

    O(L*2^L) as mentioned in a comment above. Turns out the idea behind such solution is way harder than authors thought. I think O(N * 2^L) also passes, but most of the solutions were something like O(N*L*2^L) and failed.

    L — string length

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

I had tried to use unsigned long long and cin>> in D2B problem, but on my system it was wrong, signed long long works properly. Anybody knows why it may be?

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

Testcases in div1 C seem to use CRLF line feeds (not LF). I think it is unusual in Codeforces.

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

Can any one please explain how to solve Div-1 B ?

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

    interesting for me too, after ends I wrote O(2*m*n), so TL.

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

    I used segment tree to find possible answer and another segment tree to check that answer is correct.

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

    Segment tree with updates on segments. 8393603

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

    For each constraint ... We iterate over the bits of q ... if the ith bit is turned on ... then it means that all elements in the range (l,r) have this bit turned on as well ... else if the ith bit is turned off ... then it means that at least one element in the range(l,r) has this bit turned off.

    So for all the turned on bits ... We turn on this bit on all the elements in range(l,r)

    After that for the turned off bits ... We check that the range(l,r) contains at least one position where this bit is turned off.

    We can use either segment tree or cumulative sum and binary search to implement this idea.

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

Can anyone please tell me why WA at test case 24 for problem c div 2 . code i handle the condition k == 1 then print ( i + 1) . whats going wrong here .

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

До самого конца контеста верил и надеялся, что реально сделать В без дерева отрезков в оффлайне, посортировав запросы. Кто-то может подтвердить или опровергнуть?

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

    А зачем их сортить, кстати?

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

      Если он хотел запилить на нее корневую эвристику, то запросы определенно нужно отсортить.

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

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

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

    8385070 без сортировки и без дерева отрезков. O(30 × N)

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

Rating has been updated.. time to press F5!

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

So night before yesterday I got 4 hours sleep, I did 6 hours of exams yesterday and got < 4 hours sleep before this contest.

I went from 12th in last contest to 517th in this one.

Damn.

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

Spent whole contest trying to code D, and only now realized the solution is deceptively simple: note that the number of ways to color a subtree is the product of the number of ways to color each of its children, plus the same product for the reverse order. Or it would be, if it weren't for double-counting.

Turns out that the combinations that will be double-counted are the ones in which every painted subtree has an even number of painted vertices, or every painted subtree has an odd number of painted vertices and the number of painted children is odd.

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

Great Contest!! Finally above 1700

Btw, can anyone help me out with this http://codeforces.com/contest/483/submission/8393197

Problem D,div2

I tested it one ideone as well but it is giving runtime error there too.

I basically used bitwise range tree to solve the problem.Please help

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

Кто нибудь знает в чем секрет 9 теста, B div1?

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

Looking at number of TL's on C i realize how small is amount of coders who check their solutions in custom invocation before submit:)

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

Can anyone help me with my code for Div1-B?

My code: http://codeforces.com/contest/482/submission/8386444

I saw some solutions very similar to mine, but I am not finding any bug or seeing why my approach does not work.

Thanks.

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

First 4 minutes of contest: how I do programming and solving problems, screencast. [EDIT: now not private]

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

Задачу В можно было делать не деревом отрезков, а предподсчетом.

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

Похоже, что в Java 1.8 что-то испортили с выводом через printf :-(. На контесте решил по-старинке вывести все числа через пробел с форматом "%d " и это решение поймало TL ( # ). Если же делать два printа ( # ) или послать на Java 1.7 ( # ), то решение получает AC.

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

    Ну так printf в джаве за О(бесконечности) работает

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

После этого контеста ровно 1700 XD Удержаться бы в первом диве=)

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

In Div 2 B, I didn't do binary search but derived a direct O(1) formula based answer and it passed. Here is my code : code. Is my solution correct or were the testcases weak??

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

can someone tell me how to solve div2 D????

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

where is the editorial of the round ?

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

where is the editorial of the round ?

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

When editorial going to be published? In addition, very surprised to see that Division 2 B problem was much harder than C problem (by statistic)

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

Problem --> Interesting Array (CF Round 275): Div.1/B or Div.2/D

Tourist's code : http://ideone.com/c5dTmY

In this problem, for every set bit in query, we set the corresponding bit for all the numbers in the given range. I can't understand how he's doing that by:

s[from[k]][j]++; s[to[k] + 1][j]--;

Also, for calculating the number of set bits for a given bit position, for a given range of numbers, he's made some sort of cumulative array. Please explain its construction:

bal += s[i][j]; a[i][j] = (bal > 0); sum[i + 1][j] = sum[i][j] + a[i][j];

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

    I will try to explain by posing a different problem:

    Given m queries of the form a, b, p; Add p to each element between arr[a] to arr[b]; Length of the array is n.

    Trivial solution will do it in O(m * n);

    To optimize, what you can do is, add p to arr[b]. And add -p to arr[a-1];

    Those two units of information is enough to let you know that you want to add p from arr[a] to arr[b].

    Keep on doing that for all m such queries.

    Finally, do, something like:

    arr[n-1] += arr[n];
    arr[n-2] += arr[n-1];
    arr[n-3] += arr[n-2];
    ...
    ...
    arr[2] += arr[3];
    arr[1] += arr[2];
    arr[0] += arr[1];
    

    So, just one final loop like above can add p to all elements between arr[a] to arr[b] for all such m queries.

    Complexity is: O(m + n)

    Try it on paper.

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

What's wrong with the editorial ? i can't see it now, but some days ago i can reading it.

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

Why is the tutorial not accessible now? It was accessible a few days back..!!

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

Only solved A,but rating +13.

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

Why am I getting TLE in problem B(div 1)? My complexity is 32*nlogn*3 which is approximately 6*10^7, that I think should pass in 1 sec. My code is here