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

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

Привет, Codeforces!

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

<Здесь могла быть ваша реклама>

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

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

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

</Здесь могла быть ваша реклама>

Большое спасибо Aleksa Plavsic allllekssssa, который предложил несколько отличных задач, две из них вы увидите на раунде (задачи D и F). Также большое пользователям Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A, они совместно (через Aleksa Plavsic) предложили несколько задач. Две из них вы увидите на раунде (задачи B и E).

Подготовкой задач как всегда занимался я (Эдвард Давтян). Благодарю MikeMirzayanov мы вместе придумывали задачи A и C. Спасибо Маше Беловой Delinur за проверку английских текстов условий. Также большое спасибо Aleksa Plavsic allllekssssa, который тестировал задачи и постоянно был на связи.

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

Good luck and have fun!

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

UPD 2: Основная часть соревнования закончилась. Фаза открытых взломов открыта.

UPD 3: Разбор задач готов.

UPD 4: Соревнование закончено, результаты окончательные.

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

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

Thanks Edvard for mentioning my friends and me. I'll really tried to give good and interesting tasks for contest. Possible you will see more our tasks in future rounds, that doesn't depend on me :)

Enjoy in contest, as always I am glad to hear comments and suggestions after round.

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

Waiting for tourist with AC on last problem in 10 minutes.

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

These contests are sucks.

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

Первая задача в этот раз проще, чем обычно (я надеюсь на очень быстрые сабмиты по ней от вас)

Быстрее, чем 1-2 минуты? Или имеется ввиду среднее время сдачи задачи от всех участников?

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

    Хочется более быстрого среднего времени, а также большее количество Accepted-ов.

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

    Я был прав. First accepted на 43й секунде :-)

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

      Всегда удивляюсь как люди умудряются так быстро сдавать даже тривиальные задачки, у меня цикл прочитать_условие — создать_проект — набить_код — проверить_тестовые_примеры гарантированно больше времени занимает )

      Даже когда я стал создавать проекты под задачи заранее + вставлять готовый шаблон на ввод/вывод — все равно так быстро не получается даже если сразу же придумал решение.

      Сразу набивают на сайте, ничего не проверяя?

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

        Проект создал заренее. Условие проглянул дважды. Код не запускал и не тестировал. Сдал на 52й секунде.

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

I think it is first Turkmen contest.Good luck to everyone!And thanks to contest all problemsetters.

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

Эх, третий раз подряд уже пропускаю эти раунды из-за дополнительных занятий :( Всем Accepted'ов ! :)

И вопрос к Администрации — может проводить какие-нибудь соревнования по выходным? Можно простенькие, чтоб мозги в форме поддерживать, так сказать :)

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

На 44 минуте tourist-y уже был готов к фазе взломов!

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

So, D is solvable by binary search right?

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

Am I the only who have passed pretests in B using 7-dimensional array? :D

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

Unfortunately we gave bad constraints to the problem F. As a result some participants solved the problem in O(n2). In spite of this some participants solved the problem with better complexity. The author solution works in time.

К сожалению в задаче F мы неудачно поставили ограничения и поэтому некоторые участники сдали решение за O(n2). Несмотря на это среди решений есть решения асимптотически более быстрые, но работающие примерно столько же. Авторское решение работает за .

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

    Even author solution runtime does not explain such strange difference between limits on n and m.

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

      Actually the hidden constants for m and n is different.

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

      Sorry, I didn't answer before I had some other obligations.

      I am setter of fourth and sixth task. The number of good submissions (till now) is great and I think this round is really good for education..

      I only suggested tasks, with official solutions, so I didn't decide about final constrains for numbers and time limits. In my version(when I sent task) constrains were :

      n<=10^5 m<=10^4 Ai<=10^12

      And my estimation was that 5 seconds enough, but it is changed. Edvard is better programmer with more experience, so I beleive in his decision (and possible it is better to have more correct submissions — 8 good solutions in two hour aren't a lot of).

      I hope you enjoyed in tasks and spent 2 great hours. See you on some other round, any suggestion and opinion about tasks will be helpful.

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

    Так вот как её за 7 минут сдавать. Обидно :(

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

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

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

Nice contest overall! Russian statements was very clear, except maybe a bit lack of comments on math, like that (+) operation in F is XOR :) I know that, but I also know a lot of people who wouldn't figure out what operation it is. And they can't google for it I guess — hard to write search engine request.

The only flaw I see is difficulty gap between C and DEF. But it is probably very personal thing.

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

    Problem title can help with this

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

      Haha, nice. Well I haven't read problem title until this moment :D

      Anyway, I'm kinda used to get such comments in statement, because they are often presented in regular contests (even easily googled ones like what is tree, what is subtree, etc).

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

        I actually get to the clarification writing interface just to be sure, but when I selected problem I had to read the title

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

Что за идея в задаче D?

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

    Разбор по первым четырём задачам на русском языке уже опубликован.

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

    Я решил так:

    Сначала посчитал все возможные дельты за один ход (макс 4 * 10^6).

    Отсортировал их по возрастанию.

    Дальше в цикле прошел по каждой и бин поиском нашел парную ей такую, что бы суммарно они давали как можно ближний к 0 результат.

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

    UPD: Я допускаю, что мое решение может быть взломано тестом с большим количеством одинаковых значений. Сам думал об этом, но ни к чему придти не успел — потратил время на другие задачки.

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

      я сделал тоже самое только после бинпоиска я проходил на один элемент вверх и на один элемент вниз. Этого было достаточно

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

        Нууууу, следующие элементы вверх и вниз легко могут оказаться с той же позицией обмена, что и первая дельта. Я проходил по сути до первого элемента в каждую сторону, в котором d2.I != d1.I && d2.J != d1.J.

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

Everyone is trying so hard to hack tourist on problem A. well , my friendly advice to those desperate souls: "let it go, my fellow coders. Sad but truth is tourist can solve easy problems too beside hard ones"

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

Мой код: 15483583 tourist'a код: 15470173 Где в мире справедливость?

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

    abs из cmath возвращает double, abs из cstdlib возвращает int.

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

      В cstdlib вроде нет abs-a, причина скорее в algorithm.

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

        Есть: ссылка. А ещё есть labs и llabs для long и long long соответственно. А вот про abs из algorithm я впервые слышу.

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

    15484104

    Compiler GNU C++ WA, GNU C++11 AC.

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

      Интересно

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

        Стандарт C++ не гарантирует, какие заголовочные файлы будут использованы при реализации STL. Похоже, что реализация iostream начиная с версии С++11 от g++ включает в себя stdlib.h, и именно поэтому находится перегрузка long abs(long) вместо double abs(long). Я могу это подтвердить на своей локальной машине, но на онлайн компиляторе не получилось.

        Поиграть с заголовочниками и настройками можно тут: Coliru live.

        Проверить локально можно с помощью следующего кода:

        #include <cmath>
        #include <iostream>
        
        int main()
        {
        
        }
        
        

        Строка компиляции:

        $ g++ main.cpp --std=c++03 -E -o main.cpp.p && grep labs main.cpp.p -B 1

        Выхлоп на c++03 у меня пустой. Выхлоп на c++11 следующий:

        extern int abs (int __x) throw () __attribute__ ((__const__)) ;
        extern long int labs (long int __x) throw () __attribute__ ((__const__)) ;
        --
        
        __extension__ extern long long int llabs (long long int __x)
        --
          using ::getenv;
          using ::labs;
        --
          inline long
          abs(long __i) { return __builtin_labs(__i); }
        --
          inline long long
          abs(long long __x) { return __builtin_llabs (__x); }
        --
        
          using ::llabs;
        --
        
          using ::__gnu_cxx::llabs;
        
        

        Что подтверждает наличие перегрузки

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

I think i could not understand problem C properly. In the test case 5 2 2 3 3 3 will 3-5 be a good segment? if yes, then can a good segment contain more than two pearls of same kind, also two pearls each of two different kind?

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

Can someone share their approach for problem D

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

Will the editorial be post after the end of hacking phase?

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

how to solve D?

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

The second problem is very annoying. Otherwise very good and interesting problemset.

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

    I like how you wrote

    while (x)
                ans += ar[x%10], x /= 10;
    

    Didn't knew we could do that!

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

Hm, interesting. I've submitted two AC solutions to D. Second one was a bit more optimized. And now first one got hacked. And I got penalty as if I made one WA submission before.

Feels fair, but didn't expected such thing :)

So basically I can submit as many AC as I want, and the first one which won't be hacked will be considered as accepted solution, right? And how about hacked ones? Will I get penalty for every one or how else it works?

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

In problem E , Why am I getting a RTE on test 51 . I am using Segment Tree on Time Stamps 15485066

Moreover what is the stack limit on Code Forces? Might be recursion is causing stack overflow ..

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

    I got that problem too. You might use 2d arrays for the trees (i guess). Try using 1d arrays. I tried then time limited :D

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

During the contest i solved B casting every integer in the range [a, b] into a string (using std::to_string()) and then iterating the string with a range based for, and I got TLE (code here).

Then I removed the std::string conversion and did the same thing extracting every digit from the number, using the same complexity [ O(b — a) ], and got AC in 15 ms (code here).

Now on my pc the first solution, with the 1 1000000 tc, works in 130ms while the second one takes 40ms (I haven't got any kind of supercomputer or quantum computer and I compile with the same flags of Codeforces (C++11)). Now the question is: does codeforces hate std::string? is std::to_string() very very slow?

I got 3 TLEs for this :(

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

I wish to say few more things about tasks and whole contest till now.

First I hope you find something interesting in problemset or at least you don't hate tasks :)

This was my help to codeforces, I do this only because of the passion for programming ( and I don't have girlfriend to spend time on it :D ).

I hope to see your problems on the following educational rounds, Edvard is great guy he finished good part of preparation and certainly he would help to new problemsetters. Also I'm always here for any help and question for anything needed.

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

In problem C:

  • a submission with unordered_map fails with TL: 15496737

  • a submission with map gets AC (only one line of code changed!): 15496747

  • a submission with unordered_map and custom hash function: AC again! 15497036. Bit slower compared to map, anyway.

What exactly is test 42? Looks like someone went through the trouble to generated an extremely bad test case input that causes huge number of collisions in that specific G++ implementation of unordered map. In my opinion, it's a bit against the spirit of the competition ;)

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

    Against the spirit of the competition? Come on, it's just an unrated competition and also it's called an educational round ;) how so?

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

    Hi kfx and sgtlaugh,

    Can you please explain how having huge number of collisions give TLE? Shouldn't it give a Wrong Answer instead?

    And also can you please explain how would one generate such a test case programmatically.

    (My solution also got hacked due to the same reason)

    Thanks a lot! :)

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

Now when the hacking is finished I want to ask something. On the A problem I found a solution with O(n) complexity, e.g. there was iterating from 10^9 to -10^9. I tried to hack it using x1=10^9 and x2=-10^9 and the hacking attempt was unsuccessful. However, on my laptop it run more than 2s and the limit is 0.5s. Is the limit actually higher or am I missing something?

Thanks.