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

Автор Edvard, история, 8 лет назад, По-русски

Привет, Codeforces!

8 апреля 2016 года в 18:00 MSK состоится очередной одиннадцатый учебный раунд Educational Codeforces Round 11 для участников из первого и второго дивизионов.

<Изменения в последенем абзаце>

О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.

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

Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.

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

</Изменения в последенем абзаце>

Комплект задач был предложен участниками сообщества. Задачу А предложил Ali Ibrahim C137. Задачу B прислал Srikanth Bhat bharsi. Задача C предложена Mohammad Amin Raeisi Smaug. Задачу D очень давно прислал Sadegh Mahdavi smahdavi4. Задача E является последней (четвёртой) из предложенных пользователем Lewin Gan Lewin. Задача F последняя (если не ошибаюсь третья) из присланных пользователем Kamil Debowski Errichto.

Благодарю их и всех кто присылает задачи! На данный момент я прочитал и ответил всем кто мне присылал задачи (кроме, возможно, присланных в течении последней недели). Надеюсь я никому не забыл ответить, все задачи у меня записаны и я о них не забываю.

Задача F подготовлена пользователем Kamil Debowski Errichto. Остальные задачи подготовил я (Эдвард Давтян). Спасибо Маше Беловой Delinur за проверку английских текстов условий. Задачи вычитывали и тестировали пользователи, предложившие их, соответственно Ali Ibrahim C137, Srikanth Bhat bharsi, Mohammad Amin Raeisi Smaug, Sadegh Mahdavi smahdavi4, Lewin Gan Lewin, Kamil Debowski Errichto. Большое им за это спасибо!

На раунде вам по традиции будут предложено шесть задач. Надеюсь они вам понравятся! В данный момент я рассматриваю возможность повторения задачи E с большими ограничениями, в качестве задачи G. Как вы смотрите на такое?

Good luck and have fun!

P.S.: Тот самый автобус из задачи B.

UPD 1: Взломы идут полным ходом. Разбор задач на русском языке готов.

UPD 2: Соревнование закончено. Поздравляю победителей tribute_to_Ukraine_2022 и uwi! Также поздравляю halyavin с победой в гонке хакеров — 93 взлома!

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

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

After looking at bus, I thought problems will be about Scooby Doo!

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

I hope you would all benefit and learn something new from my problem :D

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

Good Luck and Have Fun!

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

Well, I barely solved all problems the last time. I will unlikely have time to solve another one.

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

    Is that a necessary condition for contest to be good to have sufficiently easy problems so that you can comfortably solve all of them :P?

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

    Actually I think this time the contest will be a little easier than usual. The problem E can be solved for larger constraints, so it is not an another one, it is the same with larger constraints :-)

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

I'm always thinking that educational round is prepared for my next rating-increasing round.

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

Я считаю, что если решения на задачу будут сильно отличаться (из-за больших ограничений) то вполне хорошая идея сделать и задачу G.

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

How to solve F?

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

How to solve E?

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

For E, wrote a bruteforce solution and looked at few answers for small values. Then found very simple relation when N increases.

res = 2 * m
for i in range(2, n + 1):
    res = res * (2 * m - 1) + m**(i - 1)
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This was the first time I wrote CHT which works correctly on the samples :D BTW, how to solve E?

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

If you want to try, attempt to find a simple closed form for E. You can then solve this if n,m <= 10^9 instead.

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

In F I was getting WA on test 29 and then changed double to long double to get accepted :(

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

    It was supposed to be solved with 64-bit integers.

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

      Yeah, I put long long after getting accepted with long double. It's just my first time with CHT and I was trying to be fast so simply put double everywhere and then I saw I need it only when computing the intersections' X coordinates :)

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

I got hacked on A for the stupidest reason ;_;

What is the largest prime <= 10^9, because gcd with primes = 1, and I completely forgot that gcd with 1 is also 1, and that gcd of largest prime with itself is not 1 lol

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

Нашел ответы для мелких тестов и подобрал формулы для динамики — понятия не имею, почему она работает так.

dp[1] = 2

dp[i] = dp[i-1] * (m*2-1) + m^(i-2)

ans[i] = m * dp[i]

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

Could anyone explain me why this code gets TLe for problem D? 17241743

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

How to solve C in O(n)?

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

    You can use two iterators — left and right border.
    You will have the best answer only if you changed zeroes such that after this action you get one long line.
    So you can move right iterator while countOfChangedElements <= k
    When countOfChangedElements is more than k you should move left iterator while countOfChangedElements > k
    On each iteration you should update an answer (if (curAnswer = r - l + 1) > maxAnswer you should update maxAnswer and maxL, maxR indexes, because you will also need to print a resulting array)

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

    Two Pointers.

    If you decide to convert segment [L , R] into all 1's , the operations required would be the count of 0 in range [L,R].

    We can then extend the right pointer until the count of 0 does not exceed K.

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

    I did it in nLogn should also pass

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

When the hacking stage will start ?

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

Забавный факт про GNU. Вот две идентичные посылки:

  1. 17243311, GNU C++11 5.1.0, >4000мс;
  2. 17243234, Visual C++ 2010, 2527 мс.

Секрет в том, что в этом коде используется std::unordered_map. Заменим std::unordered_map на std::map:

  1. 17243439, GNU C++11 5.1.0, 2901 мс;
  2. 17243425, Visual C++ 2010, 3619 мс.

Казалось бы, unordered_map должен работать немного быстрее, что и происходит на Visual C++, а вот GNU ведет себя странно.

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

    unordered_map должен работать немного быстрее

    Только при условии использования нормального хеша. Тот, что в указанном сабмите плохой.

    Пример с исправленным хешем: 17245178 (GNU C++11, 2058мс).

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

      То же самое решение работает за 1500мс в Visual C++ 2010. На самом деле основной секрет в том, что то, что заявлено как GNU C++11 — это на самом деле MinGW, и у него есть проблемы со скоростью кода.

      Кстати, есть ли причины, по которым на Codeforces нельзя использовать современный нативный С++ — компилятор? Например, Visual Studio 2015.

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

        Хэш-функция, конечно, плохая. Например, при равных X и Y у вектора, хэш будет всегда давать 0. Но это свойство не зависит от стандартной реализации хэша для int. Поэтому и возникает вопрос, почему Visual C++ справляется лучше, пусть даже на небольшом конкретном наборе тестов.

        По поводу MinGW можно пруф, для меня это новость... Это получается чекера на linux вообще не существует, и все тестируется на windows? Иначе какой смысл в MinGW?

        Касательно Visual C++ 2015, он еще не полностью стабилен, багов много, их активно фиксят в апдейтах. Хотя я бы от него не отказался. Можно было бы 2013, там поддержано значительно больше функций С++11/14. Единственный косяк, там нет поддержки move-конструктора по умолчанию (это влияет на правила генерации других конструкторов), но это не особо критично.

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

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

          Про компиляторы есть в правилах: http://codeforces.com/blog/entry/4088 Насколько я понимаю, все тестируется на windows.

          Я пишу в VS2015, каких-то очень критичных проблем в смысле спортивного программирования пока не замечал. 2015 еще хорош тем, что у него есть Community Edition. Я не юрист, но мне кажется, что его можно бесплатно использовать на Codeforces.

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

How to solve D: Number of parallelograms http://codeforces.com/contest/660/problem/D ?

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

    for every pair of points (xi, yi), (xj, yj) we find midpoint (xi + xj) / 2, (yi + yj) / 2. Now for all midpoints we make map cnt[(x, y)] — count of pair for which (x, y) — midpoint. Answer is sum (cnt[(x, y)] * (cnt[(x, y)] — 1)) / 2 for all (x, y) in map.

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

      Can you explain further more ?

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

        Hello,

        my version is almost similar, see here — function "par"

        The thought is, to do "vector addition" from all pair of points, and store them somewhere (in an array — "R" in my case).

        Here, we can sort it (or as Naduxa said, store it in the map) and find number of "pairs" which can make parallelogram. The pairs, which can do so are those pairs, which are "equal". So now, we know the number of those (from the sorted array /or/ map) and use Gauss's formula (given above) == N*(N-1)/2

        Hope it helped a little bit ^_^

        Good luck — feel free to ask additional questions :)

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

          Can you please explain how to get the formula N*(N-1)/2? Thanks

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

            The number of pairs out of N items is equal to the number of ways to choose 2 items out of N items. With knowledge of combinatorics, we get N(N-1)/2.

            There is an alternative way. Recall that 1+2+...+N equals N(N+1)/2. The first item has N-1 items to pair with. The second has N-2 items to pair with, for the first item has paired with it already. And so on, until the last item which has zero items to pair with; all of the previous items have already paired with it. Therefore, there are N(N-1)/2 pairs in total.

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

А зачем до окончания фазы взломов в тесты к задаче D добавили тесты из взломов?

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

weak test cases on A ?