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

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

Всем доброго времени суток!

22 сентября 2015 года в 19:30 MSK состоится очередной раунд для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Авторами раунда являются я (Владислав Вишневский) и igdor99(Игорь Дорошев). Хотелось бы сказать большое спасибо Zlobober(Максиму Ахмедову) за помощь в подготовке задач, Delinur(Марии Беловой) за перевод условий на английский, MikeMirzayanov(Михаилу Мирзаянову) за замечательные системы Codeforces и Polygon, а также нашим друзьям daksenik(Дмитрию Аксенику) и irevt(Ивану Ревту) за помощь в подготовке раунда. Это наш первый раунд, и надеемся, что не последний!

Вам будет предложено 5 задач и 2 часа на их решение.

Главным героем раунда является попугай Кефа, любящий деньги и рестораны.

Всем удачи и высокого рейтинга!

UPD: Разбалловка — 750-1250-1500-2000-2500.

UPD: Разбор!

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

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

Почему раунд перенесли с 20 на 22 число? Надо было что-то переделать?

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

Ну чё ты начинаешь, нормально же общались(((

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

    Видимо эта рассылка совсем автоматическая, то есть она берет имя автора последнего поста на главной =)

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

3..2..1..Go!

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

Summary: Vladik and igdor99 would like to please Zlobober, Delinur, Mike and RevtIvan. It looks like they will have their hands full for a while.

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

    I'm sure they will all be pleased if the round goes well :)

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

      I assume Jefe tried to go for an obvious innuendo. I learn more about CF community every day.

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

        In part I wanted to point out they made an English mistake, swapping "Thank" for "Please".

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

Why no div1 :/

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

And in the hope ... That i shall get some hacks :D GL & HF :)

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

And in the hope ... that i shall get some hacks :D GL & HF :)

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

Oh it will be a magical round.

P.S : Please see the tags.

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

thanks for magical contest about parrot KEFA)

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

Do you mean Kefa ?

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

i just want raising rating .......

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

hope to see hard math problems :)

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

Div. 1 guys do not make new accounts please. :)

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

    Toooo_Simple

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

    Why did you make a new account then ?
    You're unrated and you know that some of div1 contestants make new accounts and you know the whole story, Then definitely you're not new to Codeforces and I can say that you already have another account!

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

    Why did you?

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

I hope that it does't be dynamic. How about you? Do you agree with me?

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

we want div.1 contests .

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

My last contest in summer! I'm going to school on Wednesday! Hope a good contest! Good Luck!

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

Раунд 321: цифры по убыванию

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

Почему перенесли раунд с 20.09 на 22.09?

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

I am no longer scared of fake contestants. If my rating goes down, its because I suck, and not because of anyone else.

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

Hello my friends ;)

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

dqehbfqeadnq;ekhfadxnqekfnasxdmajkefnjadlnwe

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

Scoring will be 500-1000-1500-2000-2500?

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

In my whole country adsl is down. I'll be solving this contest on mobile net :)

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

Good luck all CF guys!!!

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

750 points for div2 A :| from where that it cant be very nice i think it will be a long boring brute force :(

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

Why doesn't codeforces allow a little bigger hack files? There are solutions that will get time limit exceeded when the constraints are used but the files are bigger than 256 KB.

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

MLE on pretest 1 in D :(

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

What for the sake of God is wrong with pretest 9 Div 2 C?

Isn't it finding the longest non zero subsequence from an arbitrary vertex I with no childs?

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

A lot of pretests, yet smooth system testing and no issues. Really nice contest.

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

How to solve E problem?

It was so interesting.

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

how to solve E ?

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

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

P.S. как взламывать решения генерируемым тестом, в частности что значит "Параметры командной строки"?

P.P.S. Только через минуты 2 после конца контеста, мне показало, что мой взлом прошел.(хотя, я его пытался отправить минут 5)

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

Pretest 9th for C ?

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

I was unable to submit in the last 60 seconds because codeforces was too busy. I hate it when that happens.

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

    And I was unable to hack in the last 60 seconds.

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

    Same here :/ I tried to hack in the last 20 seconds, but the challenge wasn't submitted.

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

    same as your problem :|

    solved D but It didn't submited, also in previous contests I have this problem too!!!

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

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

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

I don't like problem scores!!! u think difference between problem C (or B) and D should be ONLY 500 (or 750).than it's same to solve A+B instead of D. May be my fault coz I solved only A,C,D(coz of not enough time),but anyway I don't think that this correct: man who solved first 3 problem is in front of me in list... D is much harder than A+B+C -_- sorry for my open mind

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

What's the problem with code generated tests ? I've got this one:

Validator 'valid.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]

Thanks in advance.

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

Спасибо за контест, мне он понравился

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

Is there anything need to pay attention to in the C problem? I failed to pass the 8th test and i can't find any mistakes.

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

Can someone suggest an approach for 2nd? I basically sorted the friends based on their money, and I was then going to group friends based on the condition and sum their friendship factor, and check which group has the most. Is there a better way to do it? or any flaw in my solution.

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

    you can read about the two pointer technique , and try solving the problem.

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

    Firstly,sort the friends based on their money.Then,enumerate every element in array and use the function "lower_bound" to find the first element which is bigger than the it.And use the sum of factor between the two element to update your answer

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

    1) sort based on money

    2) find prefix sums for friendship factors

    3) for i=1 to n
    a) use any O(log n) mechanism to find index j such that money[j]>=money[i]+d ... I used c++ map for this.
    b) ans = max (ans,prefix_sum[j-1]-prefix_sum[i-1])

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

      I had the same solution. Used std::lower_bound(a + i, a + n, a[i] + d) to find the least index ahead of i which I can not select, if I select i.

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

      Index j is also invalid so why are you doing prefix_sum[j-1] and not prefix_sum[j] ?

      Am assuming that i > j as we are considering the ith element and the old set if in [0..i-1]

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

        Assume your set starts from i. We have sorted in ascending order of money so j>i because j is the lowest index you need to exclude if the set starts from i such that money[j]>=money[i] + d ... you can set money [n+1] = INF ... Include all elements from i to j-1 in current set and to get the sum of friendship factors of such ranges/sets of in O(1), I pre-calculated prefix sums. To get sum of elements from i to j-1, you need to subtract prefix[i-1] from prefix[j-1].

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

Can someone explain D soln ?

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

    I solved it by DP, take a d[n][2^n] array,where d[i][j] means what is the best answer when last dish is i and j represents which dish I tasted before it,(1 means tasted,0 not tasted)

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

    dp[mask][j] — best answer if we finish eating at j — dish, and ate all dishes in mask. O(n^2 * 2^n)

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

    constrains of n & m are small. I think it can be solved using recursion trying all possible ways.

    UPD: it will pass only by using memoization..

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

    Well, I think it is almost the same as the Traveling Salesman Problem

    You have a graph, where the dishes are the nodes and the eating rules are the edges

    dp[y][bit_mask]:

    y is the last node you visited (dish you ate)

    bit_mask is bit mask in which if the Nth bit is set it means that somewhere along the path you visited node N (ate dish N)

    so

    dp[y][bit_mask] = max (dp[x][bit_mask — (1 << y)] + eating_rule[x][y] + a[y])

    if there isn't a eating rule between x and y than eating_rule[x][y] should be zero

    so your final answer is the best dp[y][bit_mask] where bit_mask contains exactly M ones

    you have N * 2 ^ N states and the you need O(N) for each, so total complexity is O (N^2 * 2^N)

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

Went out and could not fully participate in contest. Too bad!!!.

My thinking of how to solve Div2 B.(not sure if its correct)

  1. Sort set S by amount.

Suppose we have <n=k people already to be a company. They are K-1 of them in number.

Consider the Kth person.

Case 1 : He should be in company. This is only possible if this amount is a < S[0].a That is it is smaller than the amount of the smallest person in the group.

Case 2: His amount is bigger.

In this case, we can use binary search to find a range of numbers that conflict with the Kth person, we sum the total factors of this said group.

We have to choose between the whole group and the Kth person. Which ever increases the overall amount.

Please would this have solved the problem???

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

    I got AC using this approach

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

      OMG!!!, I can't believe i just threw away my chance of turning blue today. Oh well, i'm happy i got the approach at least. Lets wait for the next round.

      Thanks for the reply Expert Katalonecfly.

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

В чём смысл давать задачи, в которых не надо думать вообще? Задачи A-B должны быть легкими, с этим никто не спорит. Но даже легкие задачи можно попытаться сделать интересными.
Но ничего не меняется и дальше:
C — напишите DFS.
D — напишите дп по маскам.
E — чуть-чуть подумать надо, но всё же понятно, что единственный способ решить задачу с такими запросами — это дерево отрезков (или какое-нибудь другое) над хешами.
Контест кончился.

Да, задача E сложная, но думать в ней все равно не надо. Достаточно сложно придумать идею ДО над хешами, думаю, что людей, способных на такое, единицы. Так что либо ты знаешь эту идею и для тебя задача выглядит как "напишите такую-то структуру данных", либо не знаешь и не сдаешь.

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

    Справедливости ради — вот Е без хешей, 13165100 :)

    Ну это вообще проблема див2 раундов, они в 90% случаев страдают от того, что слишком стандартные. Т.е. div1C/div2E в div1 раундах преимущественно более идейные, чем div2 E в div2-only.

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

      Разве memset не даст TL при 1e5 запросов на забивание всей строки циферками?

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

      А почему это заходит?)

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

        1010 операций в 1 секунду, очевидно же должно заходить =)

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

          Еще чуть-чуть поизвращавшись (можно паковать по 2 символа в 1 байт), получаем AC за 327 мс со все той же квадратной асимптотикой.

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

          Копелович отдыхает :)

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

          Когда читаешь комментарий и решение и понимаешь, что следующий Всерос точно не сольешь

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

A — напиши стандартную штуку, или минус задача, если не умеешь
B — напиши стандартную штуку, или минус задача, если не умеешь
C — напиши стандартную штуку, или минус задача, если не умеешь
D — напиши стандартную штуку, или минус задача, если не умеешь
E — напиши стандартную штуку, или минус задача, если не умеешь

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

Сегодня рассказывал коллегам, как валить хеши по большому модулю. Придумал, как делать для двух разных модулей и оснований, написал прогу, которая проверила гипотезу. Работает! Эх, думаю, хорошо было бы, если бы на вечернем КФ была какая-нибудь простая задачка на хеши, я бы вдоволь поломал.

В общем, спасибо авторам за задачу E. И nfssdq за ресабмит с другими основаниями и возможность взломать его ещё раз, что стоило мне первого места.

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

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

    А теперь пишешь хэши по простому модулю, а их все равно ломают — получается, нужно теперь привыкать к тому, чтобы дописывать туда рэндом? :) Или как от такого защищаться?

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

      Я честно сделал оба основания рандомными, зависящим от входной строки. Собственно, вот: 13158976.

      Вроде бы я умею объяснять, почему по рандомному основанию сломать нельзя: степень многочлена — длина строки, то есть корней не больше, значит, оснований, по которым будет ноль, не более n, и вероятность угадать мала, а в случае двух разных оснований ещё меньше.

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

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

    Что значит "для двух разных модулей и оснований" ? То есть ты умеешь ломать хеш по любому двойному модулю?

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

      Умею. Выше Um_nik кинул ссылку, как можно делать, а я метод Капуна адаптировал.

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

    А достаточно менять только основания и не трогать модули? Я почему-то всегда делал наоборот (основания разные рандомные порядка 10^9, Q = 239017), но сейчас задумался, что это должно быть не оптимально.

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

Can't wait to see the rating change!!!

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

were the test case for 2nd question weak because i used upper_bound instead of lower_bound in hurry and i got AC? :P

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

    I used upper_bound in one failed submission. You're lucky :)

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

      I know why it passed coz i upper_bound on make_pair(curr+d,0). If instead of 0 it would have been a greater value it would not have passed. Yes I was lucky, coz i did not see that through.

      PS : the test cases weren't weak then i guess.

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

        The test cases were not weak, but solutions that did not consider test cases similar to yours passed. Overall, the solution is still correct and adding these test cases would've made the problem unnecessarily tricky.

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

I have this idea for D. Please tell me if you find something wrong in it.

  1. Use bitmask to find numbers with m set bits.
  2. From the k-rule directed tree, form a directed sub-tree which has only the vertices identified in step 1. Add their individual satisfaction values.
  3. Start from leaf nodes. Push them in a queue. Pop only if all children of the vertex have been popped. This way, do a Comparison for every non-leaf vertex to pick the child path that gives maximum satisfaction. So, along with all child-path satisfaction values, you add only 1 extra value for joining vertex v to its max satisfaction child.

Is it correct to start from leaf nodes?

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

Oh my god, i have disastrous bugs :'( i will cry in the bathroom.

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

I assumed that input was (parent, child) on C!!! ... silly mistake.

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

I agree with everything above and confirm that I will provide my own problems

Just a quote regarding D.

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

How can we solve problem B if every friend was associated with hia own value of 'd', the value that makes him feel poor.

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

Nice problem ( E — Kefa and Watch ). I found a solution using hashing + segment tree, but couldn't solve it in time. BTW is there any solution without using hashing?

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

kuldeepfouzdar nice trick for Unsuccessful hacking attempts on your solution, in the problem B:

#define int long long

http://mirror.codeforces.com/contest/580/submission/13163755

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

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

P.S. Если вам это поможет, поставьте этому комментарию -.

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

Hello all,

I have a question about an unsuccessful hack that I did during the contest. I hacked the following submission as I noticed that the numbers of the sequence are stored in indices of an array starting from 1 to n. The array is of size n and hence I expected that the hack will result in run time error due to the index overflow for a large input where the size of the sequence is 10^5.

Can anybody explain to me why did the hack fail? I expect it might have something to do with the unused array f but I am not sure about it.

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

    C++ doesn't have index overflow run time errors, all that happens is that it accesses memory outside the array and as long as said memory is not used for something else it will pass.

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

How come 300 div2 participants managed to solve D? In my opinion it was a pretty hard dynamic programming problem.

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

    Really ? I think that's the basic form of bitmask dynamic programming though

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

      Basic bitmask would not have arbitrary transition rules, most in div 2 fails at problems like this. I think its strange that it was solved by as many div 2 participants as this problem which is much easier:

      http://mirror.codeforces.com/contest/574/problem/D

      This problem is also easier and was solved by just 100 div 2 participants:

      http://mirror.codeforces.com/problemset/problem/540/D

      So I'm just wondering: what makes this problem easy?

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

        Rather than "easier", I would say it is more well known

        IMO, one of the most basic problem for bitmask DP is finding shortest path to travel through all vertices in the graph which is completely the same as 574D, except that the answer lie only in status 2^n - 1

        P/s : this is the first bitmask DP problem I learned so it can be just me

        UPD: I've seen some tutorials about bitmask DP (just google search, you'll find them) use above problem as sample to solve so it should be well known

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

          Ah, I see! Thanks! I had just seen it for things like edit distance and knapsack and those are way easier.

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

    Future div1 participiant ;)

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

Stand-up contest)

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

Really nice contest, can't wait for your next one.

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

When will the solutions be uploaded?

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

so many O(m(n+k)) solutions passed E 13198157

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

In Problem B, I think it should be "Print the maximum total friendship factor that can be reached." in the Output statement.