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

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

Привет, Codeforces!

25 декабря 2015 года в 18:00 MSK состоится четвертый учебный раунд Educational Codeforces Round 4 для участников из первого и второго дивизионов. С прошлого учебного раунда в этот раз прошло всего ничего. Несмотря на то, что проведение раунда мы спланировали ещё в понедельник, мы почему-то забыли включить его в расписание, поэтому в расписании раунд только появился. Таким образом, это уже четвертый и последний в этом году учебный раунд.

<Эти два абзаца может быть никогда не изменятся>

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

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

</Эти два абзаца может быть никогда не изменятся>

Подготовкой задач в этот раз занимался только я (Эдвард Давтян). Пока благодарю, только MikeMirzayanov мы вместе придумывали задачи. Через некоторое время здесь появится благодарность тестеру. Также заранее благодарю Машу Белову Delinur, которая вычитает английские тексты условий, когда они появятся :-)

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

Поздравляю всех с наступающим новым годом!!!

Good luck and have fun!

UPD 1: Первая фаза соревнования закончена, ломайте решения соперников!

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

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

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

Merry Christmas, friends!

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

I think that Tests on the first day must be weaker to Increase the number of hacks... Last Educational Round had strong tests on first day...

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

    number of hacks should be increase by weaker pretest.

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

    correct

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

    I think that hacking on educational rounds is meant to strengthen the test data, not to test your abilities with hacking. Otherwise the test data would have been called pretests.

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

I love the end of the year because it is full of contests :D

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

happy new year!!!!! best wishes for you!!!! :D

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

Сделайте уже рейтинговым, что ли

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

    Чем больше плюсов на комментарии выше, тем ближе Новый Год!

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

(она скорее всего будет самой сложной на следующем раунде)

На следующем раунде = "раунде 337 для второго дивизиона" или "предновогоднем совмещенном раунде"?

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

At codeforces educational round

me at cf educational round

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

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░████████░███░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░█████████░░███░░░░░░░░░░░░░░ ░░░░░░░░░░░░░███████████░░░██░░░░░░░░░░░░░ ░░░░░░░░░░░░██████████░░░░░░██░░░░░░░░░░░░ ░░░░░░░░░░██████████░░░░░░░░░██░░░░░░░░░░░ ░░░░░░░░░░█████████░░░░░░░░░░░██░░░░░░░░░░ ░░░░░░░░░█████░░░░░░░░░░░░░░░░░██░░░░░░░░░ ░░░░░░░░████████░░░░░░░░░█████░██░░░░░░░░░ ░░░░░░░░░░░███████████████████░░░░░░░░░░░░ ░░░░░░░░░░░████████████████████░░░░░░░░░░░ ░░░░░░░░░░██████████████████████░░░░░░░░░░ ░░░░░░░░░████████████████████░░██░░░░░░░░░ ░░░░░░░░████████████████████░░░░██░░░░░░░░ ░░░░░░░████████████████░░░░░░░░░░██░░░░░░░ ░░░░░░████████████░░░░░░░░░░░░░░░░██░░░░░░ ░░░░░████░░██░░░░░░░░░░░░░░░░░░░░░░██░░░░░ ░░░░███████░░░░░░█████░░░░░░█████████░░░░░ ░░░░██░░████████████████████████░░░░░░░░░░ ░░░░░░░█████████████████████░░░██░░░░░░░░░ ░░░░░░███████████████████░████░░░██░░░░░░░ ░░░░██████████████████████░░░░░░░░░██░░░░░ ░░██████████████████████░░░░░░░░░░░░███░░░ ░███████████████░█░░░░░░░░░░░░░░░░░░░░██░░ █████████░█░░░░░░░░░░░░░░░░░░░░░░░███████░ ░░░░░░░███░░░░░░░███████░░░░░░██████░░░░░░ ░░░░░░░░███████████████████████████░░░░░░░ ░░░░░░███████████████████████████░██░░░░░░ ░░░░██████████████████████████████░███░░░░ ░░░█████████████████████████████░░░░░██░░░ ░░█████████████████████████░░░░░░░░░░░██░░ ░█████████████████████░█░░░░░░░░░░░░░░░██░ █████████████████░█░░░░░░░░░░░░░░░░░░░████ ░░░░░███████████░░░░░░░░███░░░░████████░░░ ░░░░░░░░░░░░░░░░███░█████░█████░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░█████░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████░░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░███████░░██░░░░██░░██░░███████░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
HAPPY NEW YEAR !!!!!!!!!!!!!!!!

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

My whole life.

*Christmas. I know, ok? :D

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

Happy Halloween and Happy Solving!

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

Happy Merry Christmas! Good luck !!!!

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

I am happy because Christmas is on the way

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

I am happy because Christmas on the way

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

Problem A : WA on test 9 :(

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

Very poor English.

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

I think problem B is easier than problem A .

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

    Imo, its not easier to implement, but its easier to understand statement :)

    UPD: Actually, after checking my code, it seems B is easier in implementation too...

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

How is problem C solved? I think checking whether a given string is "good" is easy, but I was stumped with the actual problem.

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

    just useing stack

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

    It's just as easy. You can never change opening brackets and only change closing brackets to make them match. Then you just go as the regular check with a stack, if you get an opening bracket you push it in the stack, if you get a closing bracket you pop the top of the stack. If the closing bracket doesn't match the top of the stack then you increase your changes by 1.

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

    Just being greedy. Since you can't make a bracket type correct string out of a bracket type mismatch string (with the limits in statement), the only thing you can do is fix the bracket kind mismatch. The absolutely correct ones shouldn't change, or you'll make the answer worse. As for the kind mismatch pairs, fix any one of them, that will work.

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

Можете объяснить задачу D?

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

I didn't notice that the round will start at 18:00 instead of 18:05 so I missed the first five minutes.

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

    Well it's unrated and educational so 5 minutes shouldn't matter.

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

      yes, I'm just saying that it's better to mention that there's no +5 in the announcement next times

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

        Each email has exact time when contest will start. Also there is countdown in sidebar and contests page.

        ICPC-style contests do not have rooms, so we do not need 5 minutes for delay between end of registration and contest start.

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

          I don't rely on emails, and for the countdown I only used it to compute start hour but not the exact time, that's what happened with me.

          I'm not complaining since it's not big deal, I was just saying that such things might happen so in the future if you decided not to make the +5 delay in the rated rounds it's better to mention that in the announcement.

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

    I know that feel

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

Editorial will be available today or after hacks phase?

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

Couldn't get a clue about problems D and E any pointers from people who solved them ?

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

Any hints for E?

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

    D and E were completely new to me ... hints about D too would be appreciated

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

      D was somewhat simple. Just do a line sweep from right to left.

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

        The whole time i was thinking of a way to solve with segment tree, i think it's about time i read up on line sweep.. thank you

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

    Hint: convert a permutation into a graph or a cycle notation. (For example, if you have [1 3 2], write a graph with edges from 1 to 1, from 2 to 3, from 3 to 2) and before thinking about how to find a square root of permutation, observe what happens when you square a permutation. Another hint: it has something to do with the parity of the length.

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

How is Problem D solved?

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

How to solve problem E ?

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

Edit: I was wrong, I am sorry if I have misleaded any of you.

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

Привет. Вопрос по задаче D.Кто может объяснить, почему меня TL 19? Вроде я решил как все за O(nlog(n))

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

    Медленный ввод/вывод, попробуй позаменять cout/cin на printf/scanf. По крайней мере у меня из-за этого падало с TL 19.

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

My solution to problem D has the max complexity at sort but still get TLE test 19. 15018905 Is that because the memory is too large or sort sometimes can reach O(n^2) ? Can anyone help me ?

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

    It's not the problem of sort(), it's the problem of your I/O method.

    Using cin/cout will lead to a dramatically long excution time when facing such huge test cases. scanf/printf is strongly recommanded here.

    15019648

    I made a change on your I/O method, and it's now WA on test 19 with ~600ms. Hope you can figure the problem out.

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

      Thank you so much, I didn't know using cin/cout would slow down the program so much :((

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

    I also got TLE, on the same test case, see 15016054, i did it in Java. I noticed that Egor has custom input and output streams. How can i set these up with IntelliJ, CHelper plugin?

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

Can someone help me with D?

Current idea that gave WA#20: if segment is given as (L, R), put (L, 0) to vector and (R, 1) as well. Then sort, and check when interval is opened and when is closed. Meanwhile checking if total number of opened intervals is >=k.

UPD: I found out mistake.

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

good if the Educational round had (div.1) and (div.2) :-)

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

good if the Educational round had (div.1) and (div.2) :-)

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

Maybe 3 hours will be better?

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

Damn, get the idea in D, spent 1.5 hours implementing it and finished 5 mins before the end with correct algo, but TL.

Contest over, got totally different idea and now it is AC. Spent 20 mins.

Aggrhhh! First one was too complicated so I can't evaluate complexity for it, but felt like "good enough". Second one was obvious O(N * log(N)).

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

    BTW, got hacked with my new solution because of not perfect I/O. Fixed now :)

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

    mine was even worse .I thought towards the middle of the contest that I would not be able to do D so took a break.While there were 20 minutes left I came back and thought over the question for a while.An idea struck me 10 minutes prior to end of the contest and I frantically coded this and submitted with 40 odd seconds left .Result WA on case 1 (there was no time to run on local system). I was debugging the solution half an hour back and here is the correct one. If you compare the codes you'll see that there is a difference of a single character. I wrote '=' instead of '==' in an if condition.**FACEPALM**

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

I don't know why some members like to enter the contest virtually and submit prepared solutions one after another just to get high rank. It is not competitive anyway.

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

I have a question about the problem D.

For this test case:

2 1
1 3
3 5


The answer is

1
1 5


How so, if the point 3 is located on the two segments?

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

    The acceptable condition is ">= k", not "== k".

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

      My bad, forgot about that. Must be because of the pressure from the possibility of my solution getting hacked. :P

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

Hi!

I'm trying to hack a solution that should get TLE in a strong case, but you don't permit me to upload the test case (It's too heavy).

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

For problem D, I used compression, but TLE on test #16, can anyone explain why?
Code

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

    I believe your solution is of complexity O(N^2), even after compression.

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

      Can you point out that mistake please?

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

        I believe its just wrong approach. You have O(N^2) complexity when filling axis array — every segment could have the length of N. So with N segments, each one length of N you will get O(N^2) right away.

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

        Your algorithm is correct (I think) but it's too slow.

            for(int c=0;c<n;c++)
            {
                i=arr[c].first;
                j=arr[c].second;
                i=mp[i];
                j=mp[j];
                for(int k=i;k<=j;k++)
                    axis[k]++;
            }
        

        There you iterate over every segment, even after compression segments have length (in the worst case) of 2n, so that part of your code is O(n2), with n = 106 it's too slow

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

Очень понравилась задачка про квадратный корень из перестановки. Может это и баян, но решения я не знал, но удалось придумать :)

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

Привет в отсылке http://codeforces.me/contest/612/submission/15018850 Есть ответ участника, но нет ответа жюри. Ошибка ТЛЕ. В чём может быть проблема? Вывод участника 1 -99999884 99999950

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

    Скорее всего там на грани фола решение, у вас и 19е (на котором большая часть людей свалилась) прошло еле еле — 3946 ms. Там дальше есть и более требовательные тесты.

    Проблема скорее всего в медленном вводе/выводе.

    UPD: глянул код, похоже таки с вводом-выводом все в порядке, но смущают три используемых HashMap'а. Я предполагаю что для 200000 точек заполняться при чтении они будут довольно медленно. Самое простое и быстрое что можно сделать — это задать им начальную capacity (если в джаве это можно сделать) что бы избежать множественного рехешинга в процессе. А вообще лучше упростить алгоритм и избавиться от них совсем :)

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

      Спасибо. Просто смутило, что ответ был дан, а решение упало с ТЛЕ.

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

Can anybody explain why this 15030396 got TLE, while this exactly same code 15030456 got AC?

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

    I guess its because software execution time isn't very precise value :) Just improve your code to execute 2-3 times faster and it should be ok.

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

I would like to report a possible bug. If I go to standings -> div 2 and then click "friends standings" it doesn't do anything.

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

Мое решение на тесте для взлома получило TLE, хотя на этом же тесте у меня все ок. В чем может быть проблема? Решение.

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

Is system testing planned? I thought it starts automatically once hacking phase is finished.

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

The contest has been rejudged with all the successful hacks. Аpplause to the best hackers!

Hacker Hacks
halyavin 62
SlavaSSU 26
ahcl 12
Alex_2oo8 10
gepardo 9
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I think here is a little bug, but I may be mistaking. After choosing "Division 2" I cannot get back to the standings for Both divisions. Also, as already mentioned, if one chooses "Division 1" or "Division 2", then clicking on "Friends standings" shows the "Common standings".

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

Thumbs up to "recursionishell" test in problem A created by gepardo. Too bad it is not the first test where recursion solution will fail.