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

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

Всем привет)

Сегодня состоится очередной раунд Codeforces #163 для участников Div. 2. Как обычно, остальные могут поучаствовать в нем вне конкурса.

Задачи для вас подготовили авторы: Артем Рахов (RAD), Кудряшов Игорь (Igor_Kudryashov), Павел Холкин (HolkinPV) и Геральд Агапов (Gerald). Традиционно хочется поблагодарить Михаила Мирзаянова (MikeMirzayanov) за систему Codeforces, а также Марию Белову (Delinur), которая перевела условия задач.

UPD: В раунде будет использована динамическая система оценки задач. Задачи отсортированы, по мнению авторов, по предполагаемому порядку увеличения сложности.

Надеемся, что соревнование окажется удачным для всех участников. Желаем высокого рейтинга и хорошего настроения)

UPD2: соревнование завершилось, надеемся оно вам понравилось)

Поздравляем победителей:

1) Aharon

2) marcoskwkm

3) ChaosLogic

4) Imsbuno

5) Conny

UPD3: разбор задач можно найти здесь)

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

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

А почему пост не на главной?

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

За последние 5 раундов(включая этот) 3 раунда были Павла.

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

    Это не лично мои раунды, у нас целая команда, которая иногда отличается своим составом) Мы все придумываем задачи, обсуждаем и делимся идеями, в общем стараемся для сообщества)

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

Надеюсь задачи будут интересные!

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

всем успешных взломов

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

Im first, so i need most of neg votes.

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

last CF round of this month :(

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

I wish everyone good luck and high rating too! ;)

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

I think that this round is going to be great. Good luck to everyone!!!

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

Are you the wall sockets guy?

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

everyone's waiting for score distribution. wish well for all participants.

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

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

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

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

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

      То есть на прошлом Div1 / Div2 раунде тоже тестировалось все еще во время контеста, тогда почему же такая разница в скорости, неужели из за тестирования на взломах? И даже если только из за тестирования на взломам, то неужели их по 100+ было. И еще один вопрос, а почему бы не тестировать и на взломах заранее тоже? Ну то есть после каждого успешного взлома, прогонять все AC на работоспособность на этом взломе. Тогда в течении тестирования, вообще ничего не надо будет тестировать, а просто быстро открыть результаты.

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

what do you mean by dynamic scoring system??

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

good luck evryone! :)

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

Ithink some of people from countries expect iran doesnt like iranian people:( becausa they give all iranian people negetive mark!

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

    Don'be so nationalistic-thinking! first of all, that's international community. Secondly, there's no flags around your ava — that's is not the main question! :)

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

almost 2800 Registered participants (including ones who are not in the competition). I think this round is the one having the highest number of participants (counting people registered before contests only). anyway good luck

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

Всем хорошего настроения вне зависимости от результата! Всем Удачи! =)

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

А зачем при динамической оценке сложности сортировать также по сложности с точки зрения авторов? Интересней было-бы, если бы они были перемешаны.

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

очень интересная D :)

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

it was a awful contest x(

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

Worst contest ever,

Top 30+ solved only A, B

and guess what?! from top 30+ down to the last ranked contestant, all have solved A, B only!

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

    i think problems are very interesting, but hard.

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

    It is not the worst contest ever! It just too hard to Div2, but problems were realy interesing.

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

      So when the first two problems are fucking easy and the rest three focking hard is normal?:D

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

      I think too. It`s not worst, but for most of Div 2 participants not interesting, because they compete only in speed of coding.

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

      It is not the worst contest ever! It just too hard

      Looks like the very definition of the worst contest (ok, ok, not worst ever, just very bad)

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

Why am I unable to see the pretest values in which my submissions failed? Did i miss something in the newsfeed?

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

2200 participants during the contest with 0 Successful hacking attempt,system testing will be so fast :)

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

    I saw one around 5th page in standings (althrough that was from Div 1 coder)

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

Congratulations for the contest, the difference between place 1300 and place 100 is less than a 100 points.

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

как решили задачу C. Ниже диагонали

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

    Я решил в лоб. Расставлял единички снизу вверх, справа-налево, причём, количество единичек в строке i+1 должно быть >= чем в строке i

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

    Я для каждой строчки запомнил самый левый элемент, отсортировал. Затем для каждого столбца запомнил самый верхний и тоже отсортировал.

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

A-B-E-E-E...

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

    I think that hardest problem was div1 E level.

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

      Not really. Quite straightforward interval tree, but requires some coding. Good for Div 1 D

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

        I don't know how can we multiplicate all numbers by (i-l+1)^k quickly. That numbers are distinct and they are not some good sequence, as for me.

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

      I think C, D, E have the correct letters assigned, but for Div 1.

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

Can anyone tell the algorithm for D? Be free to answer in English as well as in Russian

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

    Интересует тот же вопрос. Вначале я просчитывал путь от каждой вершины до каждой Флойдом, затем пытался расположить кафе на всех дорогах наилучшим способом. Сначала тернарником. Работал медленно + ВА10. Потом написал вычисления наилучшего способа вручную. ВА9

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

      Тернарник не работает, потому, что функция не выпукла. Там получается кусочно-линейная функция (зубчатая). Я думаю, что мое решение достаточно понятно для чтения

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

Только не говорите мне, что С-шка очевидная халява!

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

Что за 10 тест в задаче D?:(

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

Контест хороший, но не сбалансированный.

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

    да авторы уже давно не говорят что он сбалансированный? думаешь почему они динамическую систему делают?) последние раунды див2, задачи выглядят ABDDE

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

Traditionally authors wish Successful Hacks .. Is this the first round I am seeing with no successful hacks ??

Hats off to the author for problem C. Looks so interesting and yet is so difficult to think.

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

D — поиск абсолютного центра?

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

прочитал С — подумал, какая-то мразь, а не задача, но потом норм, классная задача, жаль сдать не успел.

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

Расскажите решение С пожалуйста

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Отсортировать столбцы по количеству 1ц, чем больше единиц в столбце тем он ближе к началу.
    2. Затем в каждой строке найти самый правый элемент равный 1це.
    3. И отсортировать строки по индексу самых правых 1ц в строке.
    4. Запомнить изменения и вывести.

    Может как-то проще можно.

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

      подозревал что решение не сложное и почти дошол до этого

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

Unexpected difficulty level was unexpected.

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

actually in problem C we just need to sort all rows as increasing amount of 1's and sort the columns as increasing amount of 1's

note that sorting columns won't change any thing in rows and vise versa

so we don't need more than 2000 move

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

    I missed a really important constraint no of cells having ones are no more than n — 1. :(

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

    Sigh, I missed the second part...

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

    Actually you can not sort in O(n) time , you have to also tell the positions which were swapped. For the second part , you can sort by any trivial algorithm for sorting in O(n*n). Note that I was missing one important thing , No of ones in columns won't change if I swap the rows. So I can just count no of ones in columns also and do the same thing as done to rows.

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

    i think we don't need more than n-1 moves.

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    • 00000
    • 00010
    • 00100
    • 01000
    • 10000

    it has been sorted, but it's not a correct answer.

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

Why ternary search is incorrect in D?

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

    Read above Egor's comment

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

    Because function within edge is not convex. It is segment-linear, with segments alternating y = x + b and y = -x + b

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

      Please explain the second part y = x + b and y = -x + b ??

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

        Function for each edge is segment-linear (i. e. edge can be divided into segments, and on each segment function would be linear). Generally linear function is y = kx + b, but in this case k is always either 1 or -1, and this values alternate throught edge

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

Как-то очень странно похожи решения задачи D двох лидирующих участников 2 дивизиона...

http://codeforces.me/contest/266/submission/2989351

http://codeforces.me/contest/266/submission/2992482

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

Пахнет командной работой. 2989351 2992482

UPD: Уже наказали.

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

I think these div2-only contests are not really for div2 participants, only. I mean, they're more likely generic ICPC contests, with very easy problems and very hard problems. The final scoreboard today clearly shows that problems C,D and E are not equivalent to div1-A,B and C, as they usually are in regular, div1&2, 7-problems contest. For instance, problem D, that should be equivalent to a div1-B, was solved by 8 coders only — 6 of them were div1, out-of-competition ones. Although we know most div1 coders don't register for div2-only contests, we won't see only 6 coders solving problem B in a regular contest. So I think these div2-only contests are not really equivalent to div2 regular contests. Should they be?

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

edited

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

请使用英语。

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

после этого контеста, у меня вознимает вопрос: через какое место/как написаны вектора? получил тле по Д, заменил вектора на массив — < 0.5 сек, я пихал 4n элементов в худшем случае, где-нибудь можно прочитать, как работает вектор?

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

How long does it usually take for ratings to update?

It's a matter of high blood sugar, or rather it's gonna be.

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

Как повезло то! Не успел дорешать третью, но все равно перешел в див1!

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

Решил А и В -> Перешел в 1-ый дивизион. Как-то неловко и стыдно даже

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

    Аналогично, причем я знаю что мой уровень это не Див1, скорость набора решает )

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

    решил три, остался во 2-ом дивизионе:)

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

I think this contest is really a coding speed test for div 2 participants. I finished the first two problems less than 10 minutes. After that, I read the description of problem E. At the first glance, I thought it had something to do with segment tree. However, right after looking at the sigma notation, I just gave up. I played 2 games of League of Legends.

And surprisingly my rating still increased after the contest.

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

Could anyone tells me, why dis the problem D can not use Ternary Search Algorithm ? I alawys get wrong answer on test 36 ! Many thanks ! this is my

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

почему, например, этот код не получает RE при n=50? код. у меня он падает на MS VS C++ 2008

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

    ? Массив от 0 до 49 включительно, при n=50 цикл покрывает четко эти границы — от 0 до 49.

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

      там же при i=49 обращаются к элементу a[i+1], т.е. к a[50]. Разве нет?

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

      ну ну, а '\0' символ? для строк нужно выделять len+1 массив, последний элемент — как раз для нулевого символа

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

There is a grammar mistake in problem C. Some cells (n - 1 cells in total) of the the matrix are filled with ones, the remaining cells are filled with zeros. We can apply the following operations to the matrix:

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

please give me some hint about problem D ?

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

Geralt' черт соска не красива делает