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

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

Всем привет!

Авторы сегодняшнего раунда — craus и dalex. Мы не могли просто так пропустить раунд с таким красивым номером, поэтому в 19.30 MSK вам придется решать задачи, которые Павел для вас придумал, а я подготовил.

Благодарим Gerald и Delinur за помощь в подготовке соревнования и MikeMirzayanov за то, что у нас есть Codeforces.

Систему подсчета баллов и их распределение вы узнаете вместе с началом раунда. Все равно эта информация не несет особого смысла, пока контест не начался.

Полных решений и успешных взломов!

UPD. Контест завершился, поздравляем победителей!

Div. 1:
1. Petr
2. tourist
3. Egor

Div. 2:
1. k3e18
2. tongcx1988
3. LeMieux

UPD. 2 Опубликован разбор задач.

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

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

Does that mean there will be some problems have tricks, and there will be a chance to hack for getting higher scores?:D

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

Удачи всем!

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

"Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins."

lol, I guess the setters are fed up with comments like "Only 10min/5min/30sec left before contest and there is still no updates!!"

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

Ждём раундов с "Систему подсчета баллов и их распределение вы узнаете вместе с концом раунда. Все равно эта информация не несет особого смысла, пока контест не закончился." :D

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

Best wishes to every one!!

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

Don' t have time to take part, what a pity. Anyway, wish everyone a high rating [By the way, this is the 222ed round, so I guess there will be some prblems about twos. So try to search for some information ~ . Well,just kidding ]:):)

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

Keep in mind that this will be a historic round, because today for the first time I'll become a redcoder :P.

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

Всем удачи! Желаю всем проводить 2013 год хорошим кодом на последнем рейтинговом раунде!

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

    А Good Bye — что за турнир?

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

      рейтинговом

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

        Я просто не знаю, что за турнир Good Bye. Он не обсчитывается?

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

          Скорее всего будет нерейтинговым. Обычно рейтинговые только "Codeforces Round ..."

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

            Например, ABBYY CUP или КРОК были рейтинговыми. Если он будет проходить по нормалньым правилам, а не как, например, Unknown Language Round, то скорее всего будет рейтинговым.

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

You can't wish us accepted solutions and successful hacks! That's a paradox. :D

Or maybe after we get hacked a few times we'll finally reach the good solution / program?

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

    thats always the case with wishing 'high ratings' also as it is designed in such a way that if one gains someone else loses.

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

Please vote "I like it".

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

    Is this the new trend or something? Seems like there is always somebody asking for upvote or downvote in every contest. I am kind of curious now to see how long this will continue :p

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

      I did not read related comments before, therefore I do not know that others ask for up-vote or down-vote. Just do it for fun, nothing more.

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

Yep. Good luck to me and everyone else ~

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

We wish you accepted solutions and successful hacks!

(Y)

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

"Костя — профессиональный киберспортсмен, специализирующийся на дисциплине Dota 2"

а, как сказал?

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

What's the idea behind putting STRONG pretests?! Hacking is almost impossible!

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

    Well, when hacking is "I know one tricky case, and I'll check if all solutions works on it" It's not very interesting too.

    Pretests aren't strong today BTW at least in Div1.C. My solution is absolutely wrong but passed them.

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

      Well, it's not even like this. Even the extreme cases (big input) were present in the pretests! Some people in div2 got TLE because their algorithms were not to run in time under the problem constraints, I'm amazed that such cases were included in the pretests!

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

    Possible, in Div2 A, there is no test when a = b ;)

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

    Maybe they wanted to make a more classic contest, but Codeforces is neither a classic type of contest nor an ACM type. So there is no point in very strong pretests. Problem C on Div2 could have had some cases not included in the pretests (like the case with all the matrix full, when the DFS should not be called at all).

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

      I didn't use dfs at all, my solution is kLogn + kLogm using segment tree, some people used sqrt segmentation.

      PS: failed sys test

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

Увидев авторов, сразу подумал — хотя бы одна задача про Доту будет :)

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

Хм... С действительно проще В или сейчас она полетит на систестах?..

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

    Ну, если маски какие-то перебирать, то должно быть нормально. Если считать, что надо банить лучшего — неверно. Да и всё-таки B сдали больше же.

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

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

      Претесты прошло по крайней мере Оо

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

        8 100 100 100 99 0 0 0 0 6 b 1 p 2 p 1 p 1 p 2 b 2

        Тут нужно банить 99. (нули запрещены, но можно добавить ко всем 1)

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

          И тут я понял, что сейчас ну ооочень много решений посыпется.

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

            Ну янаписал это, потом понял, что трешак, решил, что не придумаю нормального и пошел ломать. Только 1 такого заметил в комнате:(

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

          Действительно. Печально =(

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

It's fun to see a problem about Dota 2 :P

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

"C" решалась кучей, в которой храним пару <количество_свободных_соседей, номер_вершины> и на каждом шаге зачеркиваем клетку с наименьшим кол-вом свободных соседей или как-то иначе?

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

    пишем bfs или dfs. Зачеркиваем вершины, которые позже всего посетили.

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

      А стартуем с какой клетки? С любой?

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

      Считаем сколько клеток должно остаться в ответе — k. Пишем bfs/dfs из любой клетки с точкой на k шагов, все остальные клетки с точкой помечаем как X.

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

    Можно ещё выбрать любые связные s-k вершин и зачеркнуть все остальные.

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

    Считаем сколько пустых клеток изначально (пусть t) Забиваем все пустые клетки липовыми стенами и ломаем t-k рядом-стоящих липовых стен

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

the second last codeforces round of this year and nice one..

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

    Just got a popup message there is another round on 30th, which will be rated for both Divisions

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

Incredibly simple A (and impossible to hack as I've seen), simple DFS on C, hard to understand the statement on B (the explained sample though saved the day), not so hard solution (here the intuition on why it works was more important than the proof itself). Nice round for the 2nd last contest of this year. "Authors of today's round are craus and dalex" — keep up the good work.

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

In Div2 B, I forgot to make size of my array which contains merged a and b to 2 * 105. Instead the size was 105. I wonder, will it fail or not? :|

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

Забавный раунд. Я бы оценил все три из B, C и D по сложности как C.

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

    А в D есть какая-то халява? Я ее не решил, то, что после раунда рассказал Петр тоже халявой не выглядит...

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

      События + дерево отрезков для максимума, в котором надо делать операции плюс-минус на отрезке

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

      Ну, халява уровня C точно.

      Давай предположим, что самый хреновый чувак имеет уровень x, самый крутой — уровень y. Когда мы знаем точное значение пары (x, y), мы можем однозначно восстановить ответ: это количество таких i, что L[i] ≤ x ≤ V[i] ≤ y ≤ R[i]. Давай обозначим это количество как ans(x, y).

      Давай уменьшать значение x сверху вниз, поддерживая при этом дерево отрезков, в котором в ячейке y держится число, равное ans(x, y). Какие бывают события?

      Во-первых, у нас чувак может влезть в допустимые, т. е. когда V[i] = x, мы начиная с этого момента, можем чувака добавить в множество. Более конкретно, мы можем добавить в множество его только если V[i] ≤ y ≤ R[i], значит к ответам на отрезке [V[i], R[i]] надо прибавить 1.

      Во-вторых, у нас чувак может стать слишком крутым для нашего множества (в предположении, что у нас действительно окажется чувак уровня x или ниже!). Это происходит, когда x = L[i] - 1. Тогда мы должны откатить его вклад в ответ, то есть уменьшить на 1 в дереве отрезков на отрезке [V[i], R[i]].

      Так как в любой момент времени у нас поддерживается актуальная структура данных с ans(x, y), то ответ это тупо максимум по всевозможным значениям максимума дерева отрезков (т. е. значения корня). Ответ восстанавливается нетрудно по такому решению.

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

        Ну да, но я бы не стал сравнивать это с тупой динамикой за O(n22n) (которую да, пришлось из рекурсии развернуть в прямую)

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

          Ну может быть. Кстати, посоны говорят, что она на самом деле за O(n2n), потому что всегда выгодно кого-нибудь да банить, а значит каждая маска имеет смысл только на одном уровне. Но я тоже до этого не допёр.

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

          Кстати, почему O(n2·2n)? O(n·2n) же..

          UPD: Это так, потому что не банить никого равносильно забанить самого трешового

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

I am interested is problem D Solvable by (Binay Search of Answer)+(Data structure)?

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

    Let's find the amount of days we need to fix bugs with binary search. Now, let's check that k days is enough to do it. First of all sort the bugs. Then iterate through them and for each of them find a student with the minimal c that can fix(b >= a[i]) the bug using set<pair<int,int> >. And he also will fix next k — 1 bugs. If every time we have a student to do it(set is not empty) and the sum of all c is less or equals to s then we can do it. P.S for some reason my solution gets TLE on 9 test :(

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

Как надо было решать В,С?

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

    С решаем так:

    1. нам нужны только m самых сильных героев

    2. забить на пропуски хода, никогда их не будем делать

    3. динамика по маске, которая означает свободных на данный момент героев

    4. переходы: либо баним кого-нибудь, либо берем в команду к себе

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

    B: сперва бинпоиск. Как проверить, можно ли за m дней? Перебираем блоками по M заданий, начиная со сложных. Берем каждый раз самого дешевого чувака, который может их все сделать.

    Код

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

can't submit in the last 10s ? I submit my solution in the last 10s,but failed to submit

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

Wow! Amazing strong-willed victory by Petr!

Congratulations :)

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

Failed Div2 Problem D because my program output N0 instead of NO ...

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

In Div 2 A all different possible test cases is 6*6 = 36 but there is 38 test cases LOL :)

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

Thank you for the nice contest! I've enjoyed it :). By the way, I got RE on problem B div1. But I've correct output at CF server (and on my local machine), and I can't see why it got RE. Can somebody tell me what I've done?

My submission is here. => http://codeforces.com/contest/377/submission/5561801

(UPD) I've submitted same code at practice, and got AC. http://codeforces.com/contest/377/submission/5562952

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

    It seems to depends on the version of glibc.
    Using glibc with version 2.15, I got RE.

    I hope this information is useful.

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

    Using the GNU C++ library debug mode, I get

    /usr/include/c++/4.8.2/bits/stl_queue.h:483:error: attempt to access an 
        element in an empty container.
    
    Objects involved in the operation:
    sequence "this" @ 0x0xffd9f148 {
      type = St14priority_queueISt4pairIiiENSt7__debug6vectorIS1_SaIS1_EEESt7greaterIS1_EE;
    }

    on that test, which means that you attempt to access an empty priority queue.

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

    It seems you had undefined behavior as mentioned by andreyv. But New Year will be soon, so it's time for miracles. Usually I do not do it, I rejudged your solution and got OK. Ratings will be updated soon. Happy New Year!

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

    To : numa and andreyv

    Thank you for investigating environments and my code! I'll be careful from now on. I'm glad to know the reasons :).

    To : MikeMirzayanov

    Thanks for the rejudging! It seems that I was very lucky!

    And again, thanks for all whom tried to help me, and craus and dalex for helding a wonderful contest. Happy New Year for all!

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

Very Fast system test. Loved it :)

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

Таргет =) Спасибо авторам за раунд!

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

Why am I Expert with rating 1703 !?

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

Thanks :D...I do on ideone without making it private.Have to take care from next time :(

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

Div. 1

Div. 2

More info

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

Hi If you visit my profile, KiAsaGibona my rating is 1504. And when I take my mouse at the graph, it says EXPERT , But I am still Pupil . As far I know 1501-1700 is Expert range. But I am 1504 and still Pupil . I want to be blue :( :(

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

    I saw this bug in other profiles too. I think it will be fixed soon.

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

    [1500,1699] is Expert range not [1501,1700] . :)

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

      I have the same problem. My rating has changed BUT the title and color is still NOT updated yet... Hope someone could help? Thanks!

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

У tourist второе место и плюс 0 к рейтингу. Хорошо, что не упал :)

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

I took part in this contest but my rating hasn't changed (I submitted for problem A, div 2). I noticed that the ratings of other Div 2 participants has changed, but mine not. Could someone tell me why this happened?

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

Не знаю, баг это, или фича, но у меня уже более месяца висит оптимистично-удручающее сообщение "Да! У вас +100500 к рейтингу!", хотя я уже пару контестов после этого слила...
Можно это как то убрать?

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

    Эм, прочитать его? У меня оно пропало после того как я открыл это сообщение.

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

Can someone explain why DFS works for Div2 C?

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

    flood fill s-k cells, that will remain empty. Mark the rest as 'X'.

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

    @dbaluta As given graph is connected & consists of s empty cells, so, Run DFS from any empty cells & mark only (s-k) cells visited. Then, simply print the solution writing empty unmarked cell X . Thats all :)

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

    For any cell, i can delete it if i am sure it won't block the path to any other "not deleted" node.

    So from every cell (x) ,we run dfs to delete cells reachable from (x).

    After deleting them, if i want to delete more cells, then it is safe to delete cell (x).

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

    --> Consider all the blocks where you have '.' as nodes..

    --> Now as you can read in the problem description , all the '.' are initially connected..

    --> So now you have a connected component with you..

    --> You have to now turn K '.' cells into WALL so that the component is still CONNECTED..

    --> Now , the Picture of DFS comes into the mind.. DFS will traverse all the nodes and will backtrack as soon as it reaches 'LEAF' node.. If you turn those leaf nodes into WALL your graph will still be a connected one!!

    Hope it helped!! :-)

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

    i got wa on test 89 :( I had done bfs and marked levels.Then removed k nodes which have the highest levels.

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

почему у див.2 у второй половины до сих пор не обновился рейтинг?

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

Now tourist really have to be ranked FIRST if he wants to increase his rating :o

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

See these solutions : 5560186 5560332

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

Hey my raiting chnged to 1501 but y i am still graded as pupil?

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

did they made the contest unrated or what ? why are the ratings constant ?

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

As noone has already done it, I will present solution to Div1 C, because in my opinion it is pretty funny and short.

We just have to completely forget about n-m weakest heros and bruteforce remaining ones in O(2^m * m) using simple dp on masks. Why it is correct?

In short, if we pick — we pick strongest one and if we ban a "bad" hero it doesn't matter which one (from the "bad" ones) we ban. It is obvious that if someone have to pick a hero, the best choice is to pick the strongest hero from remaining ones. So in a fixed moment of the game, if players will have to make k decisions, all picks will be among k actual best heros. Let us call that other heros are bad. Bad heros will never be picked. Since that, there is no point in missing a ban, because we can ban the weakest from remaining heros and that won't affect our solution, because noone will ever want to pick it. So if we consider an optimal sequence S1 of decisions for both players we can create another sequence S2 which will be still optimal for both players and chooses heros only from those m strongest ones. If there occurs missing a ban or banning a hero which can't be banned in S2, we ban the weakest remaining hero in S2 and there is no difference between those 2 choices in future picks, so these two states are equivalent.

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

    Learn Russian, there are lots of comments with discussions of solutions after each round in our language =)

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

If I'm not mistaken E is fairly easy. I will describe a solution with assumption that everything is continuous, not like in the problem statement (it's essentially the same problem, but easier to describe). Think about a whole process in a coordinate system OX — time axis and OY — cookies axis. Firstly sort buildings due to cookies per second (= possible slopes of our cookie graph) and process them in this order. After adding each building we want to maintain a graph of "maximum number of cookies we can achieve in a time t" — this graph consists of consecutive segments of lines with ascending slopes. It can be kept in a vector. When adding a building, we have to find first moment T (by binary search) when we can afford building it and update our graph (that means, finding an intersection of our graph and line passing through (T, 0) with slope corresponding to this building production. Just pop a few last elements of vector and push_back a new one. If we won't process buildings b such that there exists a building c such that c is cheaper and has bigger production, we can achieve O(n) time not O(n log n) by omiting binary search.

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

    This is convex hull optimization right? I didn't do contest because it was too late and I was tired, but I looked at questions and that is what I thought, but I wasn't sure because it was E and I thought it must be more complicated :P

    Edit: Actually I think I was wrong.

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

Can anyone explain me how to solve Div2 C/Div1 A?

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

Can any one tell me about Good Bye — 2013 contest in detail? :)

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

Well , my solution in Div2C is based on BFS , then there has a BFS tree when we run BFS then we can disconect their leaves( this are the nodes more farthest) .

My submission. Code

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

please can any one explain how good bye round will be for both divisions !? and how the rating system will be ?

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

Wow, Zlobober became the new International Grandmaster, Congratulations! :)

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

How do you solve Div 1 Developing Game?

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

I think there is a much simpler Greedy solution to Div 2 C. For each row note the number of empty cells in that row. Now if we have to delete k of the cells then we can completely convert the initial rows to X,such that the no of cells left in the row (which u have just processed ) is more than the number of cells left to convert to X. Now if there are some cells still left to convert ,except the cells which are connected to the row just immediately down u can convert into X. This algo works since when we convert entire intial rows to X the remaining is still connected.

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

In the problem B div 1, can anyone tell me why my JAVA solution got TLE (I do it in O(nlogn^2) : (.

(http://codeforces.com/contest/377/submission/5559914)

After the contest, I tried to rewrite it in C++ and got AC in 156 ms : (

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

    Try to use classes with ints instead of Pairs of Integers and PriorityQueue instead of TreeSet.

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

      Thanks, I tried to use classes with ints instead of Pairs of Integers and got Accepted @_@.

      The objected data is so slow @_@

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

I think the test data of Div.1 E (Cookie Clicker) is not so strong for a Div.1 E problem. A simple O(n2) solution passes all the tests. In 5604868 I just deleted all the buildings which cannot be used in the optimal answer, using the method mentioned on the top of the editorial, and then used simple O(n2) dynamic programming.

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

    Thank you! It seems that in random tests this condition: if(a[q[qe-1]].v<a[i].v) is false very often.

    You have TL now.

    I've rejudged all accepted solutions that were submitted after the contest. Contest submissions are OK.