В качестве эксперимента мы решили сделать раунд Educational Codeforces Round 33 рейтинговым для Div. 2. ×

Автор KAN, 13 дней назад, По-русски,

Добрый день!

12-го ноября в 19:05 по московскому времени состоится Отборочный Раунд 3 олимпиады для школьников Технокубок 2018. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 19:15 до 19:35).

Зарегистрироваться на Отборочный Раунд 3 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.

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

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

Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Спасибо MrKaStep, komendart, veschii_nevstrui, bixind, AndreySergunin и DPR-pavlin за подготовку задач Технокубка, а также lewin, любезно предложившему последнюю задачу. Также спасибо zemen и AlexFetisov за тестирование раунда.

Желаем удачи на олимпиаде,
команда Технокубка.

UPD: Мы сожалеем, что из-за технических проблем не получилось провести раунд без сбоев. Раунд будет нерейтинговым. В отборе Технокубка раунд учитываться будет, кроме того, мы планируем провести еще один отборочный раунд. Надеюсь, вам понравились задачи.

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

Технокубок 2018 - Отборочный Раунд 3

  1. potapov_al
  2. gainullin.ildar
  3. qoo2p5
  4. Vosatorp
  5. manoprenko

Codeforces Round #445 (Div. 1, основан на Отборочном раунде 3 Технокубка 2018)

  1. V--o_o--V
  2. Petr
  3. Um_nik
  4. SirShokoladina
  5. LHiC

Codeforces Round #445 (Div. 2, основан на Отборочном раунде 3 Технокубка 2018)

  1. mosthenio
  2. Ingugugus
  3. paulsohn
  4. xX_ucfNOTpt_Xx
  5. OmarYasser

Опубликован разбор.

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

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

This round will be my first blue-name-contest. Good luck.

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

iS It RaTeD??

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

Hope that there would be no issues like the last "rated" contest...

»
13 дней назад, # |
  Проголосовать: нравится -66 Проголосовать: не нравится
std::string detectIsItRated(std::string comment)
{
	std::transform(comment.begin(), comment.end(), comment.begin(), ::tolower);
	return (comment.find("is it rated") != std::string::npos ? "Need Ban" : "Thanks");
}
»
13 дней назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится

iS iT rATED !?

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

First contest I'll have time to participate in for 2 months. Hopefully I'll be able to reach expert!

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

another contest! thank you!!

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

By the way, this contest round number is 445, and this contest ID is 890 in Div.2 one. (889 in Div.1) Finally, Codeforces achieved to a host y = 2x round. (Let y be the contest ID, let x be the round number)

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

So exciting about this contest! Goodluck fam!

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

Happy 11.11 festival! :D

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

Ну шо,время взломов :)

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

KAN's contests are very interesting, hope for everyone a good time and high rankings.

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

I wish all of newbies to be pupils. It is time to change colours. Good luck to all!

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

Chinese students have finished the Noip.So I'd like to enjoy this contest instead of caring my low score.XD

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

Will hope that the contest will not have any glitches and the contest will remain rated :) KAN

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

hope this round with short problem statement...

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

These days codeforces contests frequency is very low :(

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

well may be , i can reach DIV-1 today :p Let's Hope for the best :)

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

I don't want unrated contest ;(

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

Why there is no extra registration for Div.1 ?

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

laggforces

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

It Will be unrated :(

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

am I the only one who has problems to load the contest area?

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

Servers of CF , during the contest !

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

    This image is an upvote machine. Every time servers are down people are racing to post this.

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

WTF is going on with the server???

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

Will the contest be made unrated?

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

This contest should be unrated. There are way too many server issues for this round to be fair

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

Shouldn't it be unrated? Some people may take a web on the computer, and they write it when the web does not work, it's unfair~

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

KAN will this round be unrated? I really hope not but it probably will.

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

KAN will this round be unrated? I really hope not but it probabky will.

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

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

is it rated?

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

My whole contest f**ked up due to servers issue.

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

Many people couldn't submit for 1/2 hour because of "502 Gateway Timeout" and various other connection errors.

Is it rated?

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

    I believe it was a sitwide problem, so it affected everybody. Maybe because everyone was affected equally it can remain rated?

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

      i got very low score because I had to wait more than 30 minutes to submit A and B. There's no way it can be fair at this point. Within that 30 minutes, there can be huge differences in ranking if order of submitting is different for everyone.

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

        That can be adjusted though, I'm sure they have logs of when the site was down, surely anyone who submitted after it can have their time penalty adjusted to what it would be as if no issues occurred.

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

          "anyone who submitted after it can have their time penalty adjusted to what it would be as if no issues occurred"
          How would one know what this adjustment should be? I understand you had a good contest, doesn't mean it was fair for the others, man.

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

            The adjustment should be the amount of the the site was down for. It's not as if some people were only unable to access the site for 5 minutes, it was the same for everyone. As for some people not being able to see problem statements, I've already accepted that is a grey area in which some people were affected more than others. That is something the contest runners will have to decide upon. But if we're simply talking about time penalties, then yes, it can be adjusted fairly for everyone.

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

              What if someone solved a problem after 1 minute of the server problem and one after 29 minutes ? Are they going to get the same score?

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

      Also, I accidentally closed the problem page and was unable to open it for the next half an hour. There's no way this contest should be rated.

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

    It is not rated. For some reason I could not see the announcement — a friend told me.

    EDIT: Nevermind. Everybody ignore farmersrice he was trolling, we still do not know if it rated. Go spam him with downvotes too.

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

ɔopǝɟoɹɔǝs˙ɔoɯ is temporary unavailable

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

Not again, please, not again.

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

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

Codeforces in a nutshell

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

I skipped free pizza for this :|

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

I have class tomorrow QAQ . I should go sleep.

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

Two unrated in a row? PLEASE GOD NO.

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

The good old Codeforces seems to be back, the way we remember it. I like the problems, doe.

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

I know They are gonna un-rate this contest. They just tried to calm us down for now. Bluff Masters xD

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

Problem C, div2. Test 2.

What about answer: 1 -> 1 -> 1 -> 2 -> 1 -> 2

I suppose this is correct for sequence "0 1 0 1 3" in journal but requires only 2 rooms instead of 3 in official answer.

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

    emmm,in the 3rd second,the number 2 can't refer to 0

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

      actually can, cause we first time visit room 2, so it's ok to put 0 to journal.

      But anyway, thank you.

      However, My answer is wrong. In ther 4th second we cant refer to 1, cause last time we visit room 1 was at second 2.

      My bad

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

    Quick tip: Never discuss a problem during contest time, regardless it is rated or not, man.

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

Codeforces round 502

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

Уважаемый Codeforces, почему у вас всегда проблема с серверами? С чем это связанно? Из-за проблем с подвисанием я профукал начало и пришлось пропустить раунд :(

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

You can't say everyone was affected equally .

Suppose server was down from t=x to t=x+30. One solves at t=x-1 and submits it at t=x-1. And one who solves at t=x will submit at t=x+31.

Further imagine if First guy has access to read the next problem and second guy doesn't havve since he hasn't loaded the problem page of next problem .

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

    The first point can easily be fixed by simply subtracting 30 from all submissions made after x. The second point is a more complicated matter, and could go either way.

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

      The first point can't be solved either. Say the servers went down at time t. Someone may have solved a problem at time t + 5 and had been wanting to submit his code, but only got to submit it at t + 30 (when the servers were back up). However, he would receive a score equal to someone who solved it at t + 25, and submitted at t + 30, by your logic.
      And there were others like me who stopped the contest assuming it would be unrated for sure (as it was only natural to assume so).

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

        Further we can extend the issue, someone see a new problem at t=x-1 and starts solving and submits at t=x+31. No problem. But if someone wants to see the new problem after that, he will have to wait till t+31.

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

Is it only me or someone else get 502 error during the contest... Just managed to log in.

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

let's take into account that many of us left the coding arena when the site was not working only to come back later to find out that contest was extended. it's not fair at all to make this contest rated.

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

Codeforces Should Really Buy A New Server To Work When The Current One Is 502. Codeforces Should Really Buy A New Judger As An Alternative For The Stuck Judge System In The Contest. Codeforces Should Really Buy A New Set Of Problems In Compensate For Several Unrated Problems These Days.

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

I hope admins realize that extending the contest by 30 mins does not make up for the issues. Everyone was affected differently so it would be completely unfair to rate it.

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

make codeforces great again

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

Internal Server Error again :( Leaving the contest.

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

Может быть я чего-то не понимаю... Но если увеличивать время контеста, из-за того, что кф упал, то следует уменьшить время сдачи задачи участника после падения, на время "отлежки" системы. А лучше сделать анрейт и новый отбор... P.S. а еще лучше купить серверов.... #make_cf_great_again P.P.S. пишу комент во время раунда, мб что-нибудь поменяется...

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

The contest should be unrated. As many others, I thought that the codeforces is down, so I gave up. But now I can see they extended the time, which doesn't fix things.

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

You can't just extend 30 minutes and say it's rated. What about all those people who left in the middle of the contest to do something else? What about the people who solved the problem at the beginning of the downtime interval vs. at the end, are they all the same?

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

Codeforces teaching me more about Servers Breakdowns than Algorithms and Data Structures.

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

going rated anyway?)0))))

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

    Yes they should not make two consecutive contests unrated .... But Codeforces is down these days which ruins fun of contests :(

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

      That's not a valid reason at all to make the contest rated.

      1 — While the server was down some people left the problems opened hence they got extra time to find a solution.

      2 — Some open lots of Codes to hack and generated test cases while the server was down.

      3 — Some just left the contest since the servers were down for 20+ min ( Most will think " For sure it'll be unrated " and do so.

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

It's still impossible for me to perform a hack... The server is just too slow and will stuck at the hack page...

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

Alright it's time to vote.

http://www.strawpoll.me/14385815/r

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

Не понимаю, каким образом некоторые участники успевают сдать первую задачу на 00:01 или на 00:02? Я условие за одну минуту не всегда могу прочитать. Просветите, пожалуйста.

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

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

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

I am not sure if it was a DOS attack or the servers crashed for an unknown reason, if it was, we can't let the terrorists win, make it rated!

I am just saying this because I think I will go up, so don't take it seriously :P

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

Sh*t. I opened movie when CF servers gone down, and then my friend told me they are back, then wrote something for B and it is hacked now by Um_nik. Now I have to do binary search on movie for finding where I was. Really sh*t.

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

How to solve C? I can only think out some kind of DP that can't even fit memory limit.

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

    I think we can fix the value which we can get maximum value and count how many way to achieve it, i need 1 more second to submit and know whether it's correct or not

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

    1) Brute force it

    2) Search for the first two columns on OEIS

    3) Find a pattern

    4) ???

    5) Profit!

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

    In my opinion, greedy algorithm can be a fine approach. I used an array (I'll name it A): element with index i is used to store the index of the room which was last visited in minute i. (if this room is visited again in the future, the value of this element is changed back to 0).

    Then I did a linear check over all numbers in the notebook:

    Assume that the number written in minute i is x. If there was a room which was last visited in minute x, we could assume that that room is visited again in minute i (it's the easiest way to handle without adding new rooms). Assign A[x] to A[i], then assign 0 to A[x]. Otherwise, since no room was last visited (until minute i) in minute x, the man must have enter a new room. Increase the room count by 1, and assign the index of the new room to A[i].

    Hope this will help. And sorry if my expressions could be complex though...

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

    To solve Div1 C, Div2 E

    Let's calculate two functions:

    dp[i] — How many [i] permutations exists, where last element is i and will return correct maximal value.

    dpsum[i] — How many [i] permutations exists, where element i is in one of the last k positions and algorithm returns correct maximal value.

    Then we can calculate these functions in linear time:

    To calculate dp[i] we simply append i to the end of all the [i-1] permutations, where i - 1 is located in one of the last k positions and algorithm will return correct maximum value.

    dp[i] = dpsum[i - 1]

    To calculate dpsum[i] we must remove all permutations, where maximum value will be located outside the last k elements of permutation from dpsum[i - 1]. Then append new element to the end of permutation, it must be less than previous maximum value. So multiplying by (i - 1) we add this new element and increase all larger, equal permutation element values by one, so we get [i] permutations, where i is located in range [i - k + 1, i - 1]. Lastly, we must append all permutations which have maximal value i in the last position of [i] permutation, we calculated it in dp[i].

    Then we can calculate the number of all good permutations, where correct maximum value is returned by algorithm.

    Lets fix position i, where maximum value n will be located. Then first i element prefix of permutation must return correct maximal value and maximal element is in the last position of permutation formed by prefix, so we use dp[i]. We choose order of last n - i elements in (n - i)! ways. Suffix of last (n - i) elements forms a permutation.

    Then we must merge these two permutations together by merging all elements except maximal n together. This can be done in ways.

    Then the number of bad permutation is count of all [n] permutations minus good permutation count;

    answer = n! - good_perm_cnt

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

Я предлагаю 4-ый отборочный раунд, ибо этот раунд можно вообще не засчитывать из-за нестабильной работы системы...

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

This round must be rated

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

Hi, I submitted A (incorrectly) just before the website crashed, and I had to waste about half an hour waiting for it to come back on. As a result, my A was submitted 30 minutes later than it should have been, and my rating will likely fall is a result. Can this contest be unrated for me?

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

Actually I finished coding div 2 C in 32-33 mins mark. I was about to submit and the site went down then. I tried to submit for for the next 20-25 mins but coudn't due to the issues.

Also, the site was down and up,down and up at least until the 1.15 mark, and I managed to crunch in a submit during the 2-3 seconds the site was working between the lags around the 58 min mark.

And I see some people have already submitted on 28-29 mins mark. I guess this is kinda unfair.

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

Rated Please

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

Second consecutive contest of codeforces that is very bad :

  1. not clear question

  2. bad pretest and anyone can hack easily

  3. Bad Gateway

Why ?????

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

    it was not bad really . problem were pretty clear and pretests were not too weak . i was busy coding div1 B for almost the whole contest so i didnt get that gateway error at all ! however hacking was almost impossible

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

    Actually it was a good contest except the bad gateway problem. Problem statements very fairly clear and some hacks are always expected in div2A.

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

      That's right. but those could be very better. codeforces is a good and popular site as a result anyone have high expectations.

      I hope codeforces be better in the future like always! :)

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

Great contest plagued by server issues :(

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

I was unable to hack in the last 6-7 minutes, but still, let's not make the round unrated. Even the last rated round was unrated. Looks like, system issues are becoming rather common, so this way, who know when we'll have an actual rated round. Please don't make it unrated.

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

How to solve E? f(1, x) can be computed in O(log2), I'm not sure it has anything to do with real solution, though. I tried some randomization stuff but couldn't pass pretests.

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

    I thought of the same thing (you're using the fact that X halves or stays the same at each step)? You can also do something like: "if (a[i] <= a[i + 1]) delete a[i + 1] and increase the coefficient of a[i] by 1" and you get a decreasing array, with some extra coefficients. Still not very useful though:(

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

I hope they consider making it rated for those with positive rating gains and unrated for those who lose rating (as they've done in the past). This could satisfy everyone?

Edit: I don't understand why a reasonable suggestion is being downvoted.

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

My attempt on E (Div 2.):

We will construct a permutation that has the following structure: Starting with a values, then place the value, namely false_max, that will be the answer of fast_max() procedure, then k values after that, then the rest of the number. Note that the first a + k + 1 elements in this array will be <= false_max. The number of choices can be decomposed into:

  1. Choose (a + k + 1) elements from the set of [1, 2, ..., n-1] -> the answer is combinations(n-1, a + k + 1)

  2. Place the maximum element, false_max, from the above step at array[a + 1].

  3. Re-arrange the remaining numbers of the chosen elements into (a + k) spaces -> the answer is (a + k)!

  4. Re-arrange the remaining not-chosen numbers into (n - a - k - 1) spaces -> the answer is (n - a - k - 1)!

That is for one a. a will be ranged from [0, n - k - 2]. Calculate the sum of all intermediate values gives the final answer.

Here is the pseudocode:


long long answer = 0; long long mod = 1000000009; for(int a = 0; a <= n - k - 2; a++) { long long temp = mod_fac(n - a - k - 1, mod); temp *= mod_fac(a + k, mod); temp %= mod; answer += temp * nCk(n - 1, a + k + 1, mod); answer %= mod; }

I got Wrong answer on pretest 15. Is there anything wrong with my solution, or just that my implementation is so poor that it can't handle the mod part?

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

    Oh wow what a coincidence, we posted the same wrong solution at the same time!

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

      I just realized that after posting my comment, too. I spent my last 10 minutes trying to Google about nCr % p, but some copy-paste can't save me though...

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

    "temp *= mod_fac(a + k, mod);"

    its actually not (a+k)!, since in the first a numbers there must be no k consecutive decreasing values, otherwise you will stop at them and not reach the a+1th value.

    to calculate this number, let dp[i] be the number of ways to permute first i numbers such that no k are increasing. dp[i]=(dp[i-1]/(i-1)!+dp[i-2]/(i-2)!+...+dp[i-k]/(i-k)!)*(i-1)! (i is from n-k to n-1)

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

      Thanks for letting me know where I got my number wrong!

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

      Can you please explain this dp? I struggled for the whole contest to find this.

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

        Let's find dp[n]. Obviously, you can place the number n only in the last k spots, otherwise you would have more then k numbers smaller then n after n. Lets say you place number n at position i (so you have i numbers, then n, then n-i-1 numbers) (n-k<=i<=n-1). The first i numbers also have to respect the condition (of no k decreasing consecutive numbers), so there are dp[i] ways of arranging them. Also, there are C(n-1,i) number of ways of choosing the first i numbers out of the n-1 other numbers. We can arrange the last n-i-1 numbers in any way, since n will be bigger then all of them, so there are (n-i-1)! ways. Final formula:

        dp[n]=sum(dp[i]*C(n-1,i)*(n-i-1)!)=sum(dp[i]*(n-1)!/i!)=(n-1)!*sum(dp[i]/i!), where i is from n-k to n-1

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

    I think your problem might also have overlap issues. Consider the step when n = 10 and k = 1. For the permutation {1,2,4,3,5,6,10,7,8,9} and a=3 your solution would consider false_max=5, whereas the false_max should've clearly been 4.

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

How do you solve problem E? I got WA on test case 15 with this formula so I want to know if the formula was wrong or if it was something in my code.

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

    For example: n = 5, k = 1 You will count this permutation twice: 2 1 4 3 5

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

Hacks for Div 2 a?

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

    Many people checked sum/2. It get WA when sum is odd.

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

    one guy in my room checked d+e+f == c+d+e. Hacked.

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

    for who used sum/2 for checking ... 1 1 1 1 1 2

    for sorting and then grouping (0,1,5) — (2,3,4) ... 0 1 3 4 7 7

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

    There was a solution in my room which checked a[0]+a[4]+a[5]==a[2]+a[3]+a[1]. I hacked it using 1 6 7 9 10 11. Several other hacks are possible.

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

All right, go rated

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

What is the reason of this server break downs? Poor servers, DDOS or smth? Can anyone explain it?

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

How to solve Div2-D (Div1-B) ?

It'd be nice to give hints before the complete solution.

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

    Hint : Will the result contain a character more than once ?

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

    implementation

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

    is there is a solution if a character occurs twice in a string?

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

    solution will be a forest of linear trees

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

    Well i couldn't solve Div 2 D but here are some of the things that i had thought of during the contest. If someone has solved with similar assumptions then please help in how to construct a solution from here.

    1. final answer will contain each character once so length <=26
    2. if any of the input string and all its sub strings are disjoint from the other strings or their substrings then we don't have to worry about it and can simply append it to the answer.
    3. (The hard part and from here im blank) I need to find a way such that an input string joins at the either of the ends of another string or merges in the middle. final answer will be this string along with the disjoint strings appended.

    Can anyone help me create a solution from here or if my assumptions are wrong then point em out please? Thanks :)

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

      Construct from strings graph symb -  > nextsymb. This graph must be:

      1) uncycled;
      2) from each vertex there must be at most one edge;
      3) to each vertex there must be at most one edge.

      So from that graph you must iterate over vertexes that have no one edge points to them and create answer.

      Example:

      ab
      bc
      cd
      da
      Answer is NO since graph a->b->c->d->a is cycled.

      kas
      kad
      Answer is NO since from a there are two edges to s and to d.

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

        Thanks for this but i dont quite understand how the graph is being made. Can you please explain for this input

        2
        abc
        
        xyz
        

        Thanks! :') Update: I've understood thanks!

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

      Here's how I did it (With the same assumptions as you did): - Put in all the strings in a set S. - If any string has a repeating character, print NO(since this character will have more counts than the entire string). - For every character c in the alphabet, do the following: Make a set of all strings that contain this letter, say T, and while the size of this set is larger than 1, pick two strings from this set, merge them, and insert result in the set S. (Remove the original strings from S and T) If it is not possible to merge any two strings, then print NO (because the final answer has any character appearing atmost once.) To merge any two strings, check the prefix and suffix from c's position in the two strings. - Finally, you have only disjoint strings remaining in the set S. Concatenate them lexicographically and do a final check for repeating characters.

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

        suppose if the set is ab, ba then i can construct the string abba, in which all the substrings in the set occurs once and all occus exactly same amount of time. Also if it is kas and kad then kaskad is a good string right ?

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

        Wonderful explanation !! Thanks a lot :)

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

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

Lagforces servers be like

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

Я, конечно, все понимаю, но этот раунд просто обязан быть внерейтинговым

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

Let's run the system test, if i passed the D the round should be rated.

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

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

Some of us have problem with the round being rated. Because if the server wasn't down, we could have submitted our code early. But as CF was down for approximately half an hour, we got huge penalties :( which will brutally decrease our rating. If we could submit codes just in time, our rating would not be this massacre. So please make the round unrated. :(

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

CF server trying return

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

Let's run the system test. For one I'd like to know if I messed up on div. 2 ABCD. For another, I really wanna upload my updated version for problem F just to see if I did it correctly lol

Either rated or unrated, the system test shall run lol

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

such garbage these last 2 contests were. hopefully this is going to be unrated

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

I do not care if this contest is rated or unrated. I only wish discovery test case 4 for D.

UPDATE: Got AC with this case.

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  1. I don't know why but i cant see round #445 in the contest page.
  2. System Tests have still not started. Do they usually take this much time or are the setters trying to figure out whether to make the round rated or unrated and if rated then how
»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Когда решил взломать 'A' :)

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

How to solve DIV2 D ?

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

    Construct a directed forest as follows. Nodes are letters. If one letter right after another in one of the words, then there is an edge from the first letter to the second one. There must be as most one outgoing edge and one ingoing edge on every node, otherwise answer is NO.

    Tricky thing: some words have only one letter in it, one should care about that.

    Once you have a valid forest, just print the letters in the order given by the forest.

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

      Yeah, you also need to make sure there are no cycles; as an example, the answer for

      2 ab ba

      is NO

      and the answer for

      1 aa

      is also NO.

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

Codeforces became one of the most searched today websites on websitedown.info!

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

it hurts when you expect a positive rating and the round ends being un-rated.

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

    i got a notif that its undated :( Please make it undated but not unrated ;_;

    On a more serious note, how to unregister my account? I don't wanna come here anymore...

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

      Or you can just not visit the site, instead of unregistering the account altogether. As for receiving mails regarding contest announcements, you can just unsubscribe them. Is this idea that difficult to come up with?

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

        Actually I had to make a choice : 1) write a lot of true and bad things about the situation, 2) show anger and protest subtly.

        Is this that difficult to see that yourself :)

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

Проверяйте систему перед контестом... Отношение к раунду не серьезное

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

    Предотвратить такое практический не возможно. Ведь автор не виноват что Codeforces слетел.

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

My story on problem A:

  1. Thought one couldn't stay on one vertex twice.

  2. Got WA

  3. An announcement said something like "1->1->1 is invalid because of t_2 can't be equal to 1". Thought it meant "because you can't stay on one vertex twice".

  4. Never questioned my understanding, found that I couldn't pp, and gave up.

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

    You could have seen in the explanation for example 1 they give 1 -> 1 -> 2 as a possible solution.

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

    I misunderstood the statement and tried solving a slightly different problem-

    On visiting a vertex the second time, any integer between [last_visit_time, i) can be written on that vertex.

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

Rated round:

Unrated round:

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

Wut, noo, now I can't make round 446 :(

»
10 дней назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится
if(rank==good)
    cf="UNRATED";
else
    cf="RATED";
»
10 дней назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

In Div1C
I needed to calculate number of permutations p1, p2, ..., pn satisfying .
On Oeis it said that this is equal to the number of permutations where all cycles have size less than or equal to K.
I tried proving both these conditions are equivalent but found a

Counter Test


Does anyone know why these two set of permutations have equal size?

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

    Think about it this way. For your condition tu hold, the value n must within the last K positions. And you can choose the following values in ways, where is length of the suffix starting in value n. Then you have to multiply by the number of good permutations of size . That is, . This is exactly the same as choosing a cycle for element n of size at most K, and then multiplying by the number of good permutations for the remaining elements.

    I'm not sure if I understood what you mean by counter test. It's true that the permutation you show should be counted as good for the problem statement, but it does not comply with the condition you mentioned.

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

although there where a lot of technical issues and despite that i spend more time reloading pages than the time i spend on reading problems, it was one of the greatest contests i ever participated in,thank you for your efforts it was totally worth it to participate even though it wasn't rated in the end.

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

I have given up on the contest when there was more than an hour left and almost got to top 100. Suspicious.

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

How many participants from this round will be chosen to the final?

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

Some Div.2 solutions using regular expressions (in Perl): A32278803, D32280926.