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

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

Всем привет!

Совсем скоро, 16 декабря в 19:30 MSK состоится Codeforces Round #156, автором которого являюсь я. Это мой второй раунд на Codeforces и я надеюсь, что не последний.

Спасибо Steps09, Seyaua и sdya за помощь в тестировании задач, а также Gerald за помощь в подготовке раунда. Отдельное спасибо Delinur за перевод условий на английский.

Разбалловка в первом и во втором дивизионе стандартная: 500-1000-1500-2000-2500.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

Контест окончен, надеюсь вам понравилось :)

Поздравляю победителей див1:
1). YuukaKazami
2). al13n
3). rng_58
4). Bigsophie
5). KADR

И победителей див2:
1). ShadowSong
2). ynbpdy072
3). jiaobu

Разбор задач по ссылке.

  • Проголосовать: нравится
  • +202
  • Проголосовать: не нравится

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

Настоятельно рекомендую прочитать условия ВСЕХ задач. Это значит, что они не обязательно расположены по уровню сложности??

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

    Это значит, что автор рекомендует прочитать условия всех задач.

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

    Это значит, что "сложность" — субъективная штука

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

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

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

    Это значит что скорей всего будет весело

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

More like "lack of lag and luck" — when you say it with the right accent it sounds really hilarious, but still makes sense :D

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

Seyaua и sdya теперь официальные тестеры на CodeForces? :)

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

Does this contest require any file input or output ?

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

Задачи наверно будут интересные...Желаю всем ++color.

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

Нагин — автор задач? Ну всё, прощай, мой фиолетовый ранг :(

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

    Почему ? :)

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

      Твои задачи на ДП очень трудные.. Я в этой теме итак не профи, и до решений задач C и D твоего прошлого контеста сам бы не додумался.

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

    Да не парься, больше 100 рейтинга нельзя потерять за один раунд)

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

Will the scoring be dynamic or standart?

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

    No dynamic scoring, I promise.

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

      And will it be 500-1000-1500-2000-2500, as usual?

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

        I don't know, temporary.

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

        If problems will not be sorted by difficulty, I don't think that scoring will be 500-1000-1500-2000-2500 as usual.

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

        I strongly recommend you to read ALL the problems.

        You see :D i don't think the score will be the same as usual :D

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

          As a matter of fact we have contest in both divisions and as each contester can see the others' problem so it is hard to separate problems . :D

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

Пусть контест будет интересным и запомнится всем на долго! Желаю всем удачи! P.S. С Днем Независимости Казахстан!

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

Всем желаю удовлетворительных результатов, особенно HKL)

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

It's not the first time lots of solutions are in queue =(

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

Очередь на десять страниц... :(

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

I need a clarification, the integer 'q' in div2-C is always an positive integer ?

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

In Div2C does q need to be positive, because if no then in the second test case:10 20 10 30 the example can be 4 or I am missing something?

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

hi can help me about problem c? i dont know what is say

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

    given a sequence b, find longest sequence q in the form of

    a,b,a,b,a..... where a and b are integers.

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

Well the server is tottaly trolling me. I submit on problem D and it cost more than a minute to running on test 8. I though it will TLE. Then I decided to resubmit it, When I resubmit it my last submission got passed. Now I get -50 for my submission and penalty minute.

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

    Sorry, but it was your choice. Lag is to be expected, you should've waited for the result.

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

Кто нибудь знает, из за чего D Div 2 может падать на 15 тесте?

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

How solve problem C ???

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

    Maintain a list of indices for each different value. I missed just a couple of characters in my code, and I got WA :(

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

Я, к сожалению, даже после 3 кларов не знаю, правильно ли я понимаю условие задачи D...

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

Не успел доломать решение из-за очереди в конце. А контест кайфовый.

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

Почему в задаче С для интервала от 16 до 81 число Шпрага-Гранди равно 1, а не 2?

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

Предвижу, что почти у всех Е(div 2) упадет, либо тесты будут фиговые.

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

< I spend 10 minutes to debug a mistake which I type "Furlo" to "Furio" .... Maybe I played too much WOW ...

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

Респект за задачу Е. Даёшь нетрадиционные деревья отрезков! :-)

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

    У меня вполне традиционное (только для подсчета ответа), что я делаю не так?

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

      Ну, её можно очень коротко и красиво написать со следующей идеей.

      Давайте в вершине дерева отрезков хранить значения динамики по маске (т. е. D[a][b] = количество способов заполнить отрезок, где в левом конце лежит значение a, а в после правого конца лежит значение b). Фишка в том, что мы такие динамики можно "подцеплять" одну к другой.

      По мне так очень красиво. У тебя такое же?

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

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

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

          Ну вот, нечто подобное было первое про что я подумал. Но меня конкретно заломало аккуратно разбираться с тем, что куда ставить, и искать ближайшие слева/справа значения. А в таком дереве отрезков как у меня, все запросы делаются единообразно — один раз написал функцию merge(A, B, y), которая слепляет две матрички с динамиками, соответствующие отрезкам [l; y) и [y; r) и используешь её везде — и в изменении, и в запросе ответа.

          2781042. Остаётся надеяться, что это моё добро не упадёт :-)

          UPD: Прошло!

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

What's the trick in D? Why counting a number of sequences in which number (n-k) appears exacly (n-k) times and there isn't any other number q that appears exacly q times is wrong?

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

    I guess number of i such that a[i] appears exactly a[i] times should be equal to n — k.

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

    There may be some numbers s_i such that each number s_i occurs exactly s_i times and the sum of all s_i is n-k.

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

      Let's assume n = 4 and k = 1. Does the sequence 1, 2, 2, 4 is good? There are 2 possibilities: either first person always tell the truth or second and third does. We can't know anything for sure.

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

        For the fourth person we are sure that he is lying. Each of the first three people may be telling the truth. So the sequence is correct.

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

I have some trouble understanding Div1D. If 0<k<n, then nobody can answer 0. How can Serge with such answers find out that not everybody is a liar (if everybody is a liar, then everybody can answer anything)?

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

    If X people tell the truth then exactly X people must answer X.

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

    I had the same trouble for a while.

    For example, suppose that there are two people A and B, and they answered 1 and 2, respectively. Then there are two possibilities: {A honest B liar} or {A liar B liar}. You can conclude that B is a liar, but you have no information about A. You concluded that k = 1 people (B) is a definitely liar.

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

      do you have an algorithm that does not require to make a table beforehand?

      I can only figure out a solution with time complexity n^4 :(

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

      OK, thank you! I thought Serge would be able to say that there are exactly k people lying (no matter which), not that there are exactly k people for which he knows that they are lying.

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

Понравился контест, второй дивизион. Жаль стал разрываться сразу между двумя задачами, и с и д были клевыми. Как в Е писать теорию игр на таких ограничениях не совсем понял.

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

funny!! couldn't understand div2-C in contest time. :(. i could solve it... :(

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

Did anybody use binary search in div2-D, or it's bad idea to do it?

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

    I think many people would have done it using binary search on the number of steps.

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

      I could count numbers until this wave will reach any wall, but what to do then?

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

        You can find out the number of cells filled in T steps in O(1). It is easier if you consider the simpler problem where we start filling an A*B (A<B) box starting with the bottom left cell filled.

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

        Then you should count cells switched on which are outside of board.

        These cells formulate a triangle. There are at most four triangles (one for each side). And some of them can overlap.

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

        count how much of them out of the field using arithmetic progression

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

          border1, border2, cap1, cap2 is distance to border and top from start. if cell on edge, then here coord are abs(bx — x) + abs(by — y) = step, step is current number of step, x, y from input. After we have line of fill edge cell on each side, we can calculate square with (a-1) * b /2, a-how mach cell if fill on this edge, b — is height step out borber, (step — distance to this side)

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

    I think so.

    Interval is 0..2n-2

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

    This problem was similar with last COCI exam !! Isn't it ??

    UPD: I mean solution of them were similar.

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

I must learn to read problems really. I have misunderstood DIV2-E :@ :@ Complicated it for nothing :@

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

дурацкая Б — какие-то шизофренические формулы

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

    Можно было не писать шизофренические формулы, а чуть больше подумать и накодить решение вообще без разбора случаев.

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

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

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

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

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

          Очень интересный подход :) Мое решение тоже вроде как без формул (2781504): поделил ромб на четыре треугольника, а потом считал, сколько из каждого треугольника попадает в заданную область.

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

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

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

    Да, пока пишешь на ум приходит — зачем так жить? А потом ещё и претесты не проходит.

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

So slow

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

    So obvious :P

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

    There are two reasons to try to solve a problem faster .

    1. First one is to get more points
    2. Second is to see if your solution is correct and sleep without any worries (except rating change) ! =)

    UPD: Now I can sleep and relax. No problems with my solutions. I prefer sleeping than waiting for rating change and be late for school tomorrow.

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

It seems the systest will take a big amount of time... a previous round written by me also have this problem... It is because put so much big test in problem A or B, that kind of easy problem has many submissions, so if one submit need 50 seconds, then the whole judging will last for hours :(... so I hope the later writers can take care of it :)....

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

радует сдача участником Bigsophie задачи Е на 13 минуте

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

and one thing....who is Bigsophie ?

maybe there will come someone like Petr2 or ACRush2 ? (just joking :) )

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

I got TLE when I sent Prob B div 2. I think this solution does not spend more than 2 second running. I lost 50 point in that.

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

The rate of comments in this blog is more than the rate of system testing !!!

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

из примечания задачи Б: В первом тесте изначально закрашена одна клетка, по этому ответ 0.
может, все-таки, "поэтому"?

в задаче С: Ваша задача — узнать, кто выиграет в данной игре, если и Фурло и Рубло играют оптимально.
может нужна запятая после "и Фурло"?

в задаче С: Другими словами после описанного хода игрока в выбранной кучке останется y монет.
может нужна запятая после "Другими словами"?

в задаче Д: Выведите m целых чисел — i-тое число, должно быть равно...
видимо, запятая не нужна?

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

На мой взгляд отличный контест, спасибо за это Sereja

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

Самое суровое решение задачи Div1 — D : 2777535

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

Problem A turns out to be harder than expected

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

this systest need one codeforces contest time

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

Обожаю концепцию расстановки сложности задач на Codeforces.

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

    да ладно, все-таки не так много Е решило, да и когда раунд готовишь, тяжело вот так объективно оценить: кому-то будет проще, кому-то сложнее

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

      А никто и не говорит, что легко оценить. Я даже больше тебе скажу — от автора контеста особо-то разбалловка не зависит. Я, когда давал контест, хотел сделать все задачи одной стоимости, но мне не разрешили. А хотел я дать все задачи одной стоимости именно вот из-за таких случаев.

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

        Ага, а более сложные задачи будут в итоге стоить меньше ибо их пишут позже и дольше.

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

Гыгы, а многие не заметили, что в задаче B c <= 10^9, и можно решать без бинпоиска?

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

    Есть тест с ответом 999999999

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

      Как там может быть такой тест? У нас же поле не прямоугольное, а квадратное.

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

    Я заметил, но вы наверное имеете в виду линейное решение, а у меня О(1): 2782985

    Суть в том, что количество включенных клеток изменяется с некоторой начальной скоростью (клеток за секунду) и ускорением. А ускорение изменяется только при достижении сторон и углов. То-есть мы имеем 8 контрольных точек, в которых можем сразу посчитать количество включенных клеток. И найдя из 8 интервалов времени, тот, на котором получим необходимое количество клеток, мы решаем для него квадратное уравнение, и получаем точный ответ.

    Жаль, во время контеста не успел сдать из-за багов=) Ещё и в С в одной цифре опечатался, и как результат, WA на 72-ом тесте=)

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

    Copy. Delete.

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

I passed Div2 C with O(N^3). I even had prepared a test case where I fail because of time limit. I was lucky this test was not in the systest. I just fixed the two starting numbers — O(N^2) and then greedily find the longest sequence — O(N). So totally O(N^3).

I have added this: if (many[A] + many[B] <= ans) continue; and fooled the systest. But the test 1 2 2 3 3 4 4 5 5 6 6 7 7 ..... breaks my solution with time limit exceeded.

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

    It's your luck no one hacked you. But in this case of course it's fair

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

    And my solution of O(N^2+ Hashtable search) gets TLE :(

    EDIT -> Used Hashtables to map a particular element to one of the index in between [0,4000) and then called every reference with arrays and the code gets Accepted

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

    Your solution can be easily changed to O(n^2). When you are finding the longest sequence, you can only go through the elements that are equal to the one of those two fixed (not through the whole sequence like in your submission).

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

Как повезло мне однако. Если бы ещё не пожарная тревога...

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

Интересные задачи, спасибо! :)

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

For Div 2 E , please tell whether my grundy number calculation is correct or not ??

In each step we should try to make y as large as possible. So we should try to make y to x^(1/2) in each step. We can keep doing this until we can make a move ie. 0<=y<x. finally grundy number will be the number of steps taken in this part.

please verify findXor function to calculate xor . link : http://www.codeforces.com/contest/255/submission/2782916

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

    No, we shouldn't try to make y as large is possible. Actually, if n=1 and x=25, it's better to take y=3 and win (Rublo can't change the number, because 1<3^(1/2)<2 and 1<3^(1/2)<2, there is no integer in this interval). Sprague-Grundy number of some state of the game is the minimum non-negative integer, that is not equal to Sprague-Grundy numbers of any state, which we can achieve from current state.

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

      Thank you for your reply, Now I have understood it. Actually I thought of taking sqrt(x) because I wanted to make state less. But I forgot the nice thing that I only needed to have grundy numbers upto sqrt(77777..... 12 times ) which was not so large.

      EDIT : solved the problem.

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

rating?

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

Editorial in Russian available here @ http://mirror.codeforces.com/blog/entry/6161

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

    google translate makes a good translation for this editorial .... thanks for being google-translate friendly.....

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

    It would be really helpful if anyone could provide a dynamic programming solution to Div-2 C problem.( not the code, only the idea)

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

      Well there are only N different numbers so we can sort them and lower them to the range [0, N — 1] instead of [1, 10 ^ 6]. Now we can build a matrix DP[MaxN][MaxN] where DP[i][Numbers[j]] would be equal to the maximum length of some progression that has the last two elements Numbers[j] and Numbers[i]. Since we know the last two elements we know the last three since it equals (a, b, a, b, a, b, ... ) are Numbers[i], Numbers[j], Numbers[i] so we can use something of a very simple knapsack solution. Try to update DP[i][Numbers[j]] with DP[j][Numbers[i]] + 1 and in the end write maximum of the matrix + 1.

      Code for this idea: 2775826

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

      My dp solution: take all pairs (these pairs will end of our subsequence, subsequence must be like this: x y x y x y x) and try to find answers for them. Say, pairs are : a[i] and a[j], which i > j. So d[i][j] = d[j][k] + 1, which (k < j) and (a[k] = a[i]), of course we must know answer of d[j][k]. I tried to explain to you my solution, sorry for my bad english.

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

thank you for the contest , I think that these problems have fresh ideas

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

the first and second questions of div 2 was very awful :|

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

I cant believe it. My submission number 2812603 passes the test case 11 (458754) for which it gives the answer 667496909 on my computer.

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

is there any english editorial of round 156???? I'm thirsty of it