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

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

Привет, Codeforces!

В воскресенье, 26-го апреля в 19:00 MSK состоится 300-ый регулярный раунд Codeforces.

Я поздравляю всех членов и администрацию Codeforces с этой замечательной цифрой. С момента создания платформа стала гораздо больше и круче, провела множество соревнований и предоставила возможность любому интересующемуся человеку прокачаться в знании алгоритмов и решении сложных задач. За это мы благодарим создателя платформы Codeforces MikeMirzayanov и всю команду Codeforces. Жгите дальше!

Я рад объявить, что задачи трехсотого юбилейного раунда составил я, Михаил Тихомиров (Endagorion). Возможно, вы помните прошлые раунды на моих задачах: #99, #109, #265, #283 и (частично) #295. Хочу поблагодарить координатора задач Codeforces Макса Ахмедова (Zlobober) за помощь в подготовке этого раунда и Марии Беловой (Delinur) за перевод условия на английский. Отдельное спасибо Владиславу Исенбаеву (winger), Александру Фетисову (AlexFetisov) и Павлу Кунявскому (PavelKunyavskiy) за тестирование задач и помощь в подготовке.

Раунд будет общим для обоих дивизионов и продлится два с половиной часа (как видно на странице Соревнования). В раунде будет несколько ( ≥ 6) задач, разнообразных по сложности и направленности. Надеюсь, каждый найдет задачу как раз для себя! Разбалловка будет объявлена позже.

В раунде будет разыграно 30 эксклюзивных футболок Codeforces. Футболки получат первые 15 участников по результатам раунда; кроме этого, среди остальных участников, вошедших в первые 300, мы выберем 15 случайным образом и наградим их тоже. Так что даже если вы слабо верите в то, что попадете в число самых лучших, ваши шансы на получение слонов все равно не так уж и плохи. =)

Такие дела. Приходите посоревноваться ради призов и ради удовольствия!

UPD: в контесте будет 8 задач. Разбалловка стандартная (не динамическая): 500-1000-1500-1500-2000-2500-3000-3000.

UPD2. Для определения людей, получающих футболки, будет использован следующий код на python3.4, который вы можете самостоятельно запустить во вкладке "запуск" на Codeforces. В качестве сида для инициализации генератора случайных чисел используется число, которое будет равно номеру последнего сданного во время контеста решения.


import random seed = int(input()) rnd = random.Random(seed) # all contestants except top-15 contestants = list(range(16, 301)) rnd.shuffle(contestants) tshirts = list(range(1, 16)) + contestants[:15] for x in sorted(tshirts): print(x)

UPD3: Спасибо за участие!

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

  1. bmerry
  2. Egor
  3. Petr
  4. rng_58
  5. scott_wu
  6. jqdai0815
  7. eatmore
  8. atetubou
  9. qwerty787788
  10. niyaznigmatul

Список мест, которые выигрывают футболки: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 40 46 67 75 80 102 103 144 152 161 169 198 233 243 269. Вот счастливчики, занявшие эти места: bmerry, Egor, Petr, rng_58, scott_wu, jqdai0815, eatmore, atetubou, qwerty787788, niyaznigmatul, gs12117, W4yneb0t, JoeyWheeler, zxqfl, yeputons, kcm1700 & HYPERHYPERHYPERCUBELOVER (поделили 40-е место, поэтому каждый получает по футболке), piob, Leo_Yu, matrix & Nerevar (поделили 75-ое место), Haghani, ACube, DemiGuo, etal, Emarci15, hlwt, Salvare001, dzy97, FatalEagle, gchebanov & Jimanbanashi (поделили 243-е место) и Solaris (пишите мне, если найдете ошибки). Поздравляем!

UPD4: и наконец-то появился разбор (пока что только на английском, перевод будет позже).

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

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

I really hope that such jubilee round will be awesome :)

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

Даешь условия за 300?! =)

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

can't wait more!

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

Sounds cool!

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

May I suggest that in future rounds, the i-th ranked contestant would have 1/i chance of receiving a t-shirt. Then everyone will have a chance to win t-shirts, while the expected number of t-shirts needed/given is small!

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

    The number will be about ln(n) in total which is too small.

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

    so the winners (1/1==1) would always recieve T-shirt ?)

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

    I think that even though it's a small number for a contest, there are approximately 2 contests every week; therefore, it would be a lot in total. However, this idea could be applied every 10th (or something) contest.

    Also, some users are consistently in top-15; that's why some people would get unnecessarily many t-shirts, which would be boring even for them. A time restriction (for example, you can't win a t-shirt for 3 months after you've won one) would be great. Still, some people would get the exact t-shirt more than once, and this problem could be solved by changing t-shirt design let's say every 6 months.

    Apart from these, I think this is a really cool idea.

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

    Well, I think it's not fair that e.g. 4th person gets a T-shirt while 2nd person gets nothing!

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

вероятность попасть мне в топ 300 приблизительно 1/4, вероятность в топ 15 — 0, значит вероятность получить футболку= 1/4 * (15/285)= 1/4 * (1/19)= 1/76. Не плохо, если бы это была лотерея))

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

Thanks MikeMirzayanov! Congratulate codeforces on last 300 raund!

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

Looking forward to the contest!!!!!!!!

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

After more than 1 week we have a contest :D

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

Love CF rounds by Endagorion, the problems are interesting and challenges in the editorial are also awesome! Looking forward for that one!

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

I hope the problems will be interesting and attractive.

And, I also hope will have more participants in this contest. Because this is the contest for both divisions, so it is easy to get high ratings.

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

when I felt that I lost the sense of life, I found codeforces and in general ACM contest, this really change my life, Get to work facebook, google, etc. not is a dream if you study algorithms and practice on codeforces in special. so far are 300 th contests, it is incredible thanks MikeMirzayanov and Endagorion!!!! good luck and have fun for everyone thank you codeforces!!!

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

We enjoy the 300th Round in 2015, and imagine the moment that, when we have been old, we enjoy the 2015th Round together with our children — around the year 2045.

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

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

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

Thanks MikeMirzayanov! :)

It will be really very interesting and funny :D

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

Раунд тракториста

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

I have just ended my exams and that's what I'm waiting for :D

hope not to go downrated :3

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

You are beating PrinceOfPersia in Top Contributors list! What a week! A lot of changes and too bad for Petr :D

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

How hard is the first problem expected to be? Div 1 A, Div 2 A or Div 2 B?

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

what is the probability for someone to win 2 T-shirts? (one being within top 15, another one randomly)

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

Endagorion тоже случайно стал координатором задач или на этот раз в имейлах про раунд все правильно?)

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

    Это я случайно совсем растерял внимательность. Если кто-то спросит у меня по жизни совет, то я отвечу: "Никогда, никогда не делайте рассылку на сто тысяч человек в пять утра!"

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

"The round writer is Codeforces problem coordinator Endagorion. Do not miss the round!"

Looks like Zlobober has lost his job... :P

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

I want the 300th rank!

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

Currently, there are only about 3500 participants registered in this contest.

It is too little in my thinking. I hope will have more, (about 5000 participants).

Because this is the contest for both divisions, so it is easy to get high ratings (if have more participants).

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

Mark your calendars and come back to compete for the prizes and for the fun!!! I hope the Round to be FUN like your last round #295 :D

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

hope it is ratingful!

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

Don't want Dynamic Scoring.

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

Обожаю когда Div1 и Div2 пишут один контест) хоть в этом контесте можно посоревноваться и с Div2 и с Div1))

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

I hope i become master and afsh5 aka.Sohieb w OmarHashim

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

Congrats! :D

You're now first in top contributors list.

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

NO Iphone 6 so tourist wont participate

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

it seems that the contest will be great,good luck everyone !!

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

When registering for the round, do you need to do something more than click the register button? I clicked on it yesterday, but I can't submit anything now, because apparently I'm not registered. I suppose there is no way of registering during the competition... this is so annoying.

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

    Yes; there are two separate registrations, one is to register for Codeforces (getting an account) which is done at the very first time before you have an account, and another is to register for each contest which is done every time before a contest starts.

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

The room link is busy most of the time during hacking(codeforces is temporarily unavailable), rest all links are working.

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

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

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

538B - Quasi Binary:

Do not have to print the leading zeroes in the numbers.

http://www.eclecticenglish.com/grammar/HaveTo1A.html:

Don't have to means that there isn't any obligation at all,
There is no need to do it.
Don't have to is different from shouldn't and mustn't.

So why the f#ck a solution that prints leading zeroes gets WA?

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

    Agree. Codeforces need a proper translator.

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

    Luckily during the round I guessed this was a translation error, but errors like these mustn't happen.

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

The clarification of problem A was simply enough to ruin the whole contest. :)

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

    True, with this clarification the contest went directly to hacking phase. After I got the notification I resubmitted mine solution cause I read it differently first time and then made around 13 successful hacks on all solutions in the room whose authors didn't update the code yet.

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

    Why did they feel the need to resend a part of the statement as a clarification? The word substring was present in the original statement, so whoever misread it shouldn't get any extra help...

    Edit: The clarification was the exactly once part, not the substring part. The comment still stands, though: if they thought the statement was OK, this shouldn't have been done (and if they thought the statement was not OK, they should have changed it).

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

What was the pretest 4 for B?

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

About me, there is not image to describe the problems.

Too many words to be able to understand the problems.

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

В последние 8 секунд я совершил посылку по задаче F, точнее нажал "отправить". Система не отвечала, таймер дотикал — в итоге "соревнование завершено", посылка не совершена, эх.

UPD: не прошла, так что не обидно

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

Does anyone misunderstood the problem A statement like me?

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

Сейчас все у меня упадет, чувствую я :D

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

Happiness is — when Pretests pass after 8 WAs :D (I just hope I get AC)

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

Problem D, I can't understand.

Explain for me.

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

    Fill our answer

    xxxxx xxxxx xxoxx xxxxx xxxxx

    For every cell we iterate for all figures (can all figures beat current cell). And check all crosses on table are beated.

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

What the fuck hack on problem A was ?

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

    Everyone thought it's "can cut out as many substrings as you want"

    But actually it's only allowed to cut once. (Clarification)

    So contest went directly to hacking, to hack people who didn't update their code yet

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

    CODQEFORQCES

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

    Pretests are extremely weak; most of solutions which I hacked were checking that input string contains "CODEFORCES" as a subsequence. Checking that input string contains "CODEFORCES" as a substring also passes pretests.

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

      Strong pretests take all the fun of it :)

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

      Checking that input string contains "CODEFORCES" as a substring also passes pretests.

      How does it pass the first sample test? (CODEWAITFORITFORCES)

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

        Agree, my bad. Probably I understood one of hacked solutions in a wrong way.

        However, here is another example of what can pass pretests10893468. This solution doesn't even check relative order; there is only counting of occurrences for every letter. It will say YES for test SECROFEDOC.

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

        Just cur CODE**WAITFORIT**FORCES

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

    I hacked some solutions in the end of round with tests "CODEFORCESB" and "BCODEFORCES"

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

Can someone check what is wrong with this submission for problem D : http://codeforces.com/contest/538/submission/10895720

It gives WA for pretest 1, and I can't find any move that violates the given input.

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

I will become Candidate Master. So sad

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

How to solve Problem E ?

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

    DP over subtrees, with four cases depending on which player's turn it is and which player is allowed to rearrange the numbers in the leaves beforehand.

    The number that then needs to be stored for each tree is the final result if the leaves of that subtree are labelled with the numbers from 1 to msub, where msub is the count of leaves in that subtree.

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

      Would you mind to elaborate a bit more? It's not clear to me.

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

        Let's first say we are the minimizing player and also allowed to modify the labels.

        For the subtree rooted at i, define f(i) = k if the game on that subtree ends on the k-th smallest label among the leaves in that subtree.

        There are two kinds of nodes, depending on which player's turn it is. Let's call the current node i and its children j1, ..., jt.

        Case 1: it is our turn. Let j be the child of i with minimal value of f(j). The best solution then is to rearrange the labels in the current subtree so that all the smallest labels end up in the subtree rooted at j and make our move to j. So in this case f(i) = min(f(j1), ..., f(jn)).

        Case 2: it is our opponent's turn. As he wants to maximize the result, he will move to the child j where the f(j)-th smallest label is as large as possible. We need to find a rearrangement of the labels to keep that value as small as possible, and we can see that the best we can do for that label is f(j1) + ... + f(jt). For instance, we can place the f(j1) smallest labels below j1, the next f(j2) below j2, and so on. So in this case f(i) = f(j1) + ... + f(jt).

        Let's now say we are the maximizing player. This works in fact dually, we now only have to define f(i) = k if the game on that subtree ends on the k-th largest label instead. We can even reuse the code from the minimizing case (something I didn't notice during the contest).

        Code: 10900486

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

    I figured out simplier solution: let's consider 1-st player as person we wish to win. Firsly, you can recognize, that if our palyer can get x as an answer, then he can do it for x-1.

    So you can use bin-search on answer. Let suppose your answer x, then all numbers >= x denote as 1, others 0. So you need to have 1 at the end in order to win. Let's calculate next value(dp): minimal number of 1's needed to win in current subtree. If this is vertex where you are to make move, your dp is just max of values of your childs. Else you value is simply sum of those values.

    Now the magic: we can remove bin search (which was displyed for better understanding), and replace our calculting value with something as: minimum number of large(small) numbers to win. So the answer for first would be (leafNumber + 1 - dp[root]), and dp[root] for the second.

    http://codeforces.com/contest/538/submission/10897335

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

    DFS, for each node you compute how many leaves are there in this subtree and index of a leaf to be returned (for example there are 10 leaves and this node will return 7th of them (ordered by value)), i.e. the exact values don't matter. E.g. for MAX node with two children-leaves the result is simply 2|2; for maximizing game for MAX node with children 1|3 and 1|2 the result is 4|5.

    Then figure out how to combine such values for MIN/MAX nodes, it's quite easy.

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

      I looked at your dfs code. But I can't figure out why is summing the children nodes correct for some cases? Other cases are clear though.

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

        For example in maximizing game look at MIN node. Assume children have values ai|ci, that means that in a child node i the aith element will be selected. It means we can put ai - 1 smallest elements there and they will not be selected. Sum of all ai - 1 gives us number of smallest elements we can drop away. And then it does not matter where we put the next smallest number — the MIN node will choose it, that is the index of chosen node will be sum(ai - 1) + 1.

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

How do you calculate which and how many numbers to use for B ?

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

    Maximum digit.

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

    The maximal digit is the answer to "how many". Simply generate a number which has '1' where N has nonzero digit and '0' everywhere else, then subtract it from N. Repeat this until N becomes 0. To me, this is done easier using strings, not numbers.

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

Решил 4 задачи за час. Прочитал Е, и решил что взламывать чужие решения лучше, чем пытаться её решить. За 15 минут до конца случайно понял как решать Е и опоздал на 3 минуты. В итоге 520 место до систестов.

UPD: 452 место после систестов и Е не зашла бы, ну хоть не так обидно =)

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

    Печалька, а много повзламывал?

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

      3 раза удачно и 2 раза неудачно С взломал. Причем на фигне ломал. Люди забывали, что в первый и последний дни высота могла быть любой, а они считали только между двумя соседними известными днями. И кстати, интересно, у них вообще возникал вопрос, зачем тогда им переменная N дана, просто так что ли.

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

        Я вроде все это учитывал, даже long long пропихнул, но все равно WA10 (систесты)

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

          Ну так на глаз, ты не учел, что высоты не обязательно увеличиваются, могут и уменьшаться, поэтому

          long long a = (Days[i].second - Days[i - 1].second + ...) / 2;
          
          • неверно написано.

          И еще это a нужно прибавлять к обоим концам, а не только к первому:

          if (a + Days[i - 1].second > ans)
          

          UPD: На самом деле тут всё верно, основная ошибка описана ниже.

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

          А еще кто-то криво код копирует:

          if (Days.back().second + n - Days.back().first > ans)
                  ans = Days.back().second + n - Days.back().first > ans;
          

          > ans во второй строке.

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

      задача А много ломалась на тесте CODEAFORCEBS ^3

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

        У меня в комнате был человек, который сломал всё что можно было сломать, еще до того, как я решил посмотреть как там дела в комнате обстоят.

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

Looks like I finally solved B 5 minutes past 12. :( But maybe Iam wrong. System tests are pending, so they won't accept my submission yet. Here is link . http://ideone.com/1Izsvr

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

when will system testing start ?

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

2.5 hour its too much for 8 problem.I think 10 min it's enough to write all of them ;) Why author of problem D thinking that his problem gives us something... ,becose I know how to solve problem E(and idea for F) fuck him as my brain is fucked now by '#','o','.' symbols -_- Happy 300 Round -_-

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

    easy man !!! calm down :D :D

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

    I think similar to you, you are my best friend, LashaBukhnikashvili

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

    aeiou

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

    Yes, problem D gave me something. I realized, that in some problems I need to output redundant "YES" before the solution itself and in some (other) problems you do not need to :) It cost me level up :) Nevertheless, I liked the contest and problems and do not feel that 2.5 was too short, first 4 problems were relatively easy, although not always well formulated :) Don't worry man, just have fun...

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

Am i the only one who overkilled B, with a knapsack? XD

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

Note for myself: don't solve problems starting from the hardest if the contest is for both divs.

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

F worth 2500 pts — 300 AC
G,H worth 3000 pts — <10 AC

Are you serious? One thing is that there were no "middle" problems, whole problemset was completely not balanced. Second thing is that point distribution was very badly adjusted. Problem with 300 AC can be worth at most 1500 pts, no matter what. If someone creates a contest with some very easy problems designed to easy Div2 problems than what he should do with Div1-type problems is to save the ratios of values of other problems, not their differences!

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

Last submission ID was 10896731. So the T-shirt list will be:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 40 46 67 75 80 102 103 144 152 161 169 198 233 243 269
»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Good bye Master. Good bye Orange. Good bye HaRiSK

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

.

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

Очень шустро прошло системное тестирование. А правда, что это кодфорсес стал быстрее, а не в задачах мало тестов? И спасибо за раунд, пойду GH почитаю. :)

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

lashabuknikashvili ylea?

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

The problem statement mentioned "cut out some substring from the banner" in the second paragraph, also from the last paragraph, "cut out of the banner some substring”. But I can't see where did the problem told us that just cut exactly one substring, at least in the English version.

So could someone explain to me?

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

Классный раунд, особенно понравилась задача F! К сожалению, ниасилил E и видимо не забустился из-за этого до красного :(

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

Упала C потому, что я кривой и написал это:

if (Days.back().second + n — Days.back().first > ans) ans = Days.back().second + n — Days.back().first > ans;

Мораль сей басни такова — аккуратней с копипастом длинных строк

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

aeiou

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

Последнее сданное решение -- 10896729

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

    Нет, 10896731 позже и оно было последним в списке при "Ожидание системного тестирования". Почему его сейчас нет в списке неизвестно, видимо плагиатный сабмит и его убрали из контеста.

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

Can somebody please help, I don't know why am I getting runtime error on problem B code here while it works perfectly on my machine.

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

Подскажите, как красиво решать C?

Так и не запихнул :(

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

    Там же просто моделирование ситуации. Начальному значению ответа присваиваем первый данный день+высота в первый данный день-1. И потом циклом смотрим, может ли быть ситуация в принципе(то есть разность дней больше либо равна модулю разности высот), если нет — IMPOSSIBLE и выход из программы, иначе смотрим, можно ли подняться на высоту, больше чем ans. После всех итераций цикла смотрим, если последний данный день не последний в походе в принципе, то значению последнего дня прибавляем разность кол-ва дней и последнего дня. Если больше — меняем ответ. Выводим ответ. Не думаю, что это сильно красиво, но тем не менее систесты прошло. 10893343

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

      Спасибо, в принципе делал что-то похожее.

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

in problem b 538B - Quasi Binary : in this submission 10894501 when i run the system test, the wrong test case on my machine it gives me the following:

415

5

111 101 101 101 1

here the systems says it gives

9

110 100 100 100 1 1 1 1 1

actually i have been all the contest trying to figure it out and i feel so angry can anybody tell me what is wrong with my code ???

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

    i too got the same thing..:(

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

    log10(x) is a floating point function and you should never use it for integer operations.

    Also the function has different implementations in different systems and compilers, and will give different results and/or precision errors.

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

      but i cast it as (int) ?

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

        casting, in your case, does nothing at all because your already floored the answer.

        What I am saying is that, in some systems, log10(100) may be < 2 so when you take floor, it gives 1 instead of 2.

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

My solution for B gives correct answer on ideone while it fails on codeforces server for 4th test case.linktocode

strange!!!

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

How to solve D? I was trying to check all the possible moves for various pieces, but couldn't come up with a better logic. Any pointers for it?

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

    Yes, you essentially do a brute-force check.

    For each piece (o), and for each clear space (.), you can compute the difference dx, dy. And you know that dx, dy cannot be in the set of vectors. You disallow all such dx, dy (this takes O(n^4) time).

    Now, considering the dx, dy which are not banned, you check that each "x" is indeed attacked by some piece, i.e. for each "x", there is some "o" such that the difference is not banned.

    If this is true for every "x", it is possible and you output all non-banned dx, dy. If this is false, it is impossible.

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

Are the editorials out? When and where to find them?

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

    The main blog is going to be updated when the editorial comes out.

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

    I'm terribly sorry, but the editorial will most probably not come out today. Stay tuned tomorrow, I'll update the main blog post when editorial is up.

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

In problem D in testcase 2(knight) (o..x) is invalid (I suppose we cant make this move since it forces the piece out of the board) but why in testcase 1(rook) (ox) is valid? Can anyone explain why?

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

    "If there are several possible answers, print any of them."

    o..x is a perfectly valid move in the second case, but the possibility given in the samples also correctly describes the board.

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

my dreams came true, finally I hacked a red one and became international master. Thanks Endagorion..;)

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

Как такое возможно? Код тот же самый. Вот ссылка на решение

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

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

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

My code for Probelm A fails on this testcase: MDBUW**C**ZFFZKFMJTTJFXRHTGRPRE**O**RK**D**VUXO**E**M**F**YS**O**MSQGHUKGYC**RC**VJTNDLFD**E**WF**S**

My output is YES but the answer is no. Why is it no? I can cut out the substrings in between the words needed and produce CODEFORCES as i have shown above. Where does my logic fail? Is there a catch?

http://codeforces.com/contest/538/submission/10898807

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

    2015-04-26 19:08:16 Announcement Problem A. Cutting Banner

    Note that you have to cut out the substring exactly once in this task.

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

    It was later given in announcement that you have to cut out the substring exactly once in this task.

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

Can anybody please explain why I am getting wrong answer on case 13 in C? http://codeforces.com/contest/538/submission/10891638

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

    In the hei[i] > hei[i-1] case, you want int ans=hei[i]+(k-index[i-1])/2; instead of int ans=hei[i-1]+(k-index[i-1])/2;, i.e. you want to increment the largest of the heights instead of the smallest.

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

Can someone please tell me what is wrong with following submission of Problem — B:

http://codeforces.com/contest/538/submission/10876749

It says wrong answer of test case 4 which is: "415" and the output as:

5 110 100 100 100 1

where as on my laptop the answer is:

5 111 101 101 101 1

Can someone please tell? Thanks.

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

    Don't use pow for integers. Look it: http://codeforces.com/contest/538/submission/10899576

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

    If you change ans[i] += pow(10, cur) to ans[i] += pow(10, cur)+0.01 the solution passes as pow returns a float. Be careful with floating points — the compiler flags from Catching silly mistakes with GCC would have catched that.

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

    you could write this, but it's not standard:

    #include <bits/stdc++.h>
    #include <ext/numeric>
    
    using namespace std;
    using namespace __gnu_cxx;
    
    cout << power(10, 7); // this function is fast power that works in O(log n)
    

    also you can implement your multiplication function too.

    const int mod = (int) 1e9 + 7;
    struct mul {
       long long operator()(const long long &n1, const long long &n2) const {
          return (n1 * n2) % mod;
       }
    };
    long long identity_element(const mul& m) {
       return 1LL;
    }
    cout << power(1LL, 100000, mul());
    

    read this for more info.

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

    Thank you guys!

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

Problem A sample test: BOTTOMCODER :)) Is it joke ?!

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

For task A, one of the sample cases was DOGEFORCES. Sadly, the original image post is now down: http://codeforces.com/blog/entry/9729

Does anyone have a working link?

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

Большое спасибо за контест. На мой взгляд такой формат (6-8 задач и все вместе) гораздо удачнее чем разбиение на дивизионы. Для первого дивизиона две самые лёгкие задачи стандартных раундов ничем не мешают и практически не оказывают влияния на результаты, зато помогают немного "вкатиться". Для обоих дивизионов дополнительные полчаса не лишние. Разумеется, если задачи недотягивают, стоит делать рейтинговый только для 2 дивизиона, а если, наоборот, задачи очень сложные, как в трансляциях поздних раундов турниров, то только для 1-го, но когда на стандартный раунд готовится 7 задач, то, ИМХО, лучше давать их все и проводить общий раунд для всех.

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

    Еще бы чуть более сбалансированный проблемсет был (не с переходом между задачами 401 АС -> 12 AC) и рейтинг чтобы поменьше колбасило от таких раундов, и было бы вообще супер.

    Ребята из div2, кстати, не возмущались бы, что им фэйки затащить мешают)

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

      согласен, фэйки мешают очень. нужно как-то бороться с ними.

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

      А ребята из div1 радуются, что есть много народу поломать.

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

        Даже если посмотреть с этой стороны, всем лучше. Никто не заставляет div2 засылать забагованные решения. Ну и уж если тебя ломанули, значит у тебя появился второй шанс всё-таки сдать задачу, которую бы ты всё равно зафэйлил на системном тесте, если бы тебя не хакнули.

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

if (abs(notes[i].second — notes[i — 1].second > notes[i].first — notes[i — 1].first)) {

cout << "IMPOSSIBLE" << endl; return 0;

}

I can't believe my typo in problem C passed pretests...

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

Can anyone explain why this solution fails for E? http://codeforces.com/contest/538/submission/10901544 There are four DP cases based on whos turn it is to move and who is manipulating the game. I guess I messed up one of the cases somehow...

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

I am waiting for the tutorial in this contest (especially problem D)

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

Maybe first time that BaconLi wants to be at place 269 instead of 16 :)

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

Уверены ли авторы, что генератор футболок гарантирует равновероятность выбора всех подмножеств 15 участников из 275?

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

    А равновероятно никто не обещал

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

      Вот именно. ГСЧ подкручен.

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

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

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

          А можно было просто написать на топ15, так надежнее будет :)

          Кстати, как определить зону с большей вероятностью, если у нас во время контеста даже нету информации о нашем итоговом месте?

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

wasn't able to participate live in the contest because of a worthless college exam. looks like everyone really had fun..

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

Still waiting for editorial...

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

Codeforces Round #300 (with prizes(without editorial!!)!).

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

К сожалению, не нашёл разборов(( Как решалось F?

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

    Для начала заметим, что чем больше индекс вершины, тем меньше будет максимально возможное k, так как k * (v — 1) + 2. То есть при v > sqrt(n) получаем, что k < sqrt(n). Этим можно пользоваться и считать для каждой вершины для всех возможных k, таких, что k * (v — 1) + 2 <= n. Теперь как посчитать для конкретной вершины v, какой довесок она дает в ответ для k. Для этого вомпользуемся следующим приемом:
    1) Запомним индекс каждого значения и отсортируем по возрастанию значений элемента.
    2) В позицию уже обработанного элемента в какой-нибудь структуре данных, умеющей считать сумму на отрезке и инкремент в определенной позиции (дерево Фенвика подходит идеально), делаем собственно инкремент.
    3) Теперь при обработке элемента со значением x, для всех элементов со значениями < x, проставлены единички в их позициях.
    4) После подсчета добавки для всех k, делаем инкремент в позиции текущего обрабатываемого элемента.
    5) Обрабатывать нужно пачками с одинаковым x, чтобы не было добавки элементов с тем же значением.

    Код: http://codeforces.com/contest/538/submission/10898497

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

    Перебираем k от 1 до n. Заметим, что вершин, которые не являются листьями в куче будет . Таким образом, если мы каждый k обработаем за число таких вершин, суммарно будет итераций, как сумма гармонического ряда. Научимся обрабатывать число k за . Т.к. все предки у вершины v будут на заданном отрезке, для каждой вершины нам нужно будет ответить на запрос кол-ва чисел, меньших данного на отрезке. Это можно делать за в оффлайне сортировкой запросов, сжатием и деревом Фенвика или же в онлайне персистентным деревом отрезков. Итого .

    Решение персистентным деревом отрезков: 10898177

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

      2994мс, достаточно плотно, да и по памяти 470мб.

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

        Ну, можно добавить несколько незначительных оптимизаций и получить более-менее приемлемый результат. 10911740

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

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

      Решение: 10893700

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

        Можно... А еще можно сделать частичное каскадирование, как на e-maxx описано и получить . Правда, это то ещё извращение, думаю :)

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

    Кажется, у меня какое-то уникальное решение: 10891627

    При k < sqrt(n) считаем втупую. Иначе parent-ами могут быть максимум sqrt(n) узлов. Будем хранить для каждого такого parent-узла указатели на его самого левого и самого правого потомков (в моем коде обозначены как left[parent] и right[parent]).
    Теперь будем итерироваться по всем k >= sqrt(n), параллельно сдвигая все эти указатели вправо и изменяя ответ на +/-1 при надобности. Получается как 2 указателя, только 2*sqrt(n) указателей. В сумме они сделают O(n*sqrt(n)) перемещений, что вполне устраивает.

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

    Простое решение в 30 строк за : 10889218

    Идея: при фиксированном x и всех y > 0 число может принимать не более различных значений. Значит, у i-ого элемента может быть не более различных родителей. Давайте их все переберём.

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

The first CF round that I couldn't solve problem A, although I spent more than 1 hour solving it :(

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

I had an interesting experience with problem A. i locked and then found that my submission was wrong! So what I did was that I first hacked all those solutions which were locked so that they cant hack mine! So in the end I managed 10 successful hacks ( = + 1000 ) before my solution was judged wrong answer. I hacked 5 solutions with the same hack ( = 500 points) that would give WA on my solution as well!! It was like Counter-Strike!!

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

    BTW, It's allowed (or at least was allowed) to hack if you locked before your solution was hacked

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

      basically that is why i tried to hack all the locked solutions before they hacked mine. And I won! :)