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

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

Всем привет!

Совсем скоро начнется соревнование Codeforces Round #146. Этот раунд был приготовлен YuukaKazami, MinakoKojima. Я сделал задачи для Div I, а MinakoKojima — для Div II. Как обычно, Gerald очень сильно помог нам в подготовке раунда, давая много советов по задачам. Спасибо ему за это. Традиционно спасибо Михаилу Мирзаянову (MikeMirzayanov) за прекрасные системы Codeforces и Polygon, а также Марии Беловой (Delinur) за перевод задач. Также хочется сказать спасибо donehl за тестирование задач и за его ценные комментарии к задачам.

В обоих дивизионах будет использоваться стандартная разбалловка 500-1000-1500-2000-2500.

Надеюсь вам понравятся задачи! =)

Это перевод оригинального поста автора с английского языка. Английский в комментариях приветствуется.

Прошу прощения за 10-минутную задержку. Мне очень жаль за доставленные неудобства, которые я вызвал. В качестве компенсации, я напишу хороший разбор =)

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

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

Orz .. .

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

sorry for the trouble

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

Orz WJMZBMR & xiaodao

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

That would be interesting to participate in contest made by you but unfortunately we have our Moscow ACM ICPC Quarterfinal today at the same time :-(

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

made in China... hope i can become yellow...

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

Orz

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

"давая" О_о??? Разве такое слово употребляется?

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

Ждем с нетерпением!)

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

orz

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

orz!!!!!!!

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

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

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

why isnt the time again as usual ?

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

despite this there are a lot of contesters !!

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

Может хватит "Orz" писать? 5 комментов на одну тему — не много ли?

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

Orz

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

This time is right!

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

Good luck to everybody. Have a nice exam.

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

orz

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

orz!!

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

What do these mysterious letters mean? Is it a Chinese word?

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

Let the battle begin

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

Orz

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

OMG again 10 mins delay :(

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

That was Snooze

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

Hope I can become purple.Good luck everyone!

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

нельзя так просто взять и не отодвинуть начало

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

orz....

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

OMG!!1 Is YuukaKazami a girl?

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

Too mathy for this morning...

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

A, B, C, D — math. E — strings. Very nice problemset, xiaodao, thank you.

UPD: It's not a sarcasm :D

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

    Before end of contest, it was incorrect when you told even so rough classification...

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

Автор недооценил уровень участников. Не надо нам давать такие легкие проблемсеты, мы не тупые и можем решать задачи посложнее.

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

B слишком сложная для B, но классная

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

Looks like Petr and tourist couldn't solve Div 2 problem

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

    Maybe they just worked on other high score problems, or challenging.. As a result, they earned more points than anyone who solved C.

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

Просто праздник взломов! Я взломал 9 решений по С на тесте "12".

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

А как решать Б?

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

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

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

      Да, я тоже пытался вывести пять динамик, считающихся одновременно, но довести это до конца мне не удалось =(

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

      Переход

      s11 = P*s1+P*s2+2*P*s3;
      s22 = P*s2+(1-P);
      s33 = P*(s3+s2);
      s44 = s4*P+(1-P)*dp[i-1];
      dp[i] = s44+s11+cp*(i+1)*(i+1);
      

      Где s1 — сума q_j*j^2
      s2 — сума q_j
      s3 — cума q_j*j
      s4 — сума q_j*dp[i-j-1]
      cp — вероятность угадать все
      P — вероятность угадать текущую,
      где q_j — вероятнось угадать последних j и не угадать предыдущую.

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

    Пусть мы угадали с i-м кликом. Тогда мы добавляем 1 + 2 * (кол-во предыдущих кликов подряд, которые мы тоже угадали). То есть мат ожидание от i-го клика — это pi * (1 + 2 * pi - 1 + 2 * pi - 1 * pi - 2 + ...). Ну а как это пересчитывать за O(1) на клик — очевидно

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

    Храним матожидание количества подряд идущих букв О (обозначим E) и текущий ответ (обозначим А). Переход к следующей клетке делается так. С вероятностью p ответ нужно увеличить 2 * E + 1 (потому что мы уже учли отрезок длины E в ответе, а теперь он стал E + 1), а матожидание на 1. С вероятностью 1 — p мы ничего не делаем.

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

      О, все, теперь понял. Спасибо. Как-то я не с того боку подошел к задаче =(

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

      Так люблю это ощущение — придумать правильное решение за 25 минут, но не быть уверенным в его правильности; написать его с багом; подумать "ну естественно, оно ведь не правильное..." и начать думать в другом направлении; после контеста узнать, что оно правильное, и опять подумать "отлично, у меня была правильная идея, я не совсем тупой"... Наверное, я мазохист.

      Спасибо за разбор, в такой формулировке понятней всего.

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

It seems that system testing hasn't started now.When will it start?

UPD: It has started.

UPD: It seems systest today is very slow.

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

Maths Everywhere!

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

Thank the authors for this intense thinking contest, great work! I wish the editorial would be done soon.

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

Раньше у Codeforces были две традиции: переносить начало контеста и по два часа обновлять рейтинг. Теперь появилась третья: откладывать системное тестирование на неопределенный срок.

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

Anyone can teach me how to solve "how many times does a string x occur in a string s" as mentioned in the description of Div2 E?I sucked at that point already.

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

    The fastest way is to use Knuth–Morris–Pratt algorithm. Article on Wikipedia

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

      In this problem KMP wouldn't run in time (if you get 10^5 "a" queries on a 10^6 string your running time is 10^11). You need an Aho-Corasick automaton or a suffix array. Or something using hashing.

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

        Nezzar didn't ask, how to solve this problem. He asked just, how to calculate the number of occurences of one string in another.

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

          Just saying that either Aho-Corasick or a suffix array is an out-of-the-box solution for the problem as stated, but without the cyclic rearrangements. To find one string in one other string just once you could certainly use KMP.

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

systest in 3600 .. 3599 .. 3598 .. 3597 .. 3596 .........

UPD : 3595 .. 3594 .. 3 .. 2 .. 1 .. 0. Systest!

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

going back to blue again >_<

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

When is system testing?I'm worried that my C(Div2) will fail.......

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

Well people system test in two hours, american people go to sleep!!!!

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

Я осознал, что 1-ую все делали не так как я... Разве не правда, что ответ или n*(n-1)*(n-2)/((n + 1) & 1 + 1), или (n-1)*(n-2)*(n-3)/((n & 1) + 1)?

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

finally starts

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

Правда ли, что длительность тестирования напрямую зависит только от количества тестов в первых двух задачах?

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

Seems I just have to wait for the editorial then :D

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

Is this the slowest systest ever?

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

ну нахрена в первой 100+ тестов..

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

Very slow judge :(

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

    it's good that problem E & D had less than 3 AC ,so we can imagine there is an end time for this slow system testing !

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

Problem D Div 2, I has just read some solution, but i can't understand :( Anyone help me please :D

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

    Let E[i, j] be the excepted score for clicks from i to j(inclusive). Let L[i, j] be the excepted 'o' s starts from left, of clicks from i to j. Let R[i, j] be something like L[i, j]. Then we have:

    E[i, j] = E[i, k] + E[k + 1, j] + 2 * R[i, k] * L[k+1, j]
    

    , for any i < k < j.

    Think about: If we got x 'o's in clicks [i..k], y 'o's in clicks [k+1..j], then score x^2 is calculated in E[i, k], y^2 in E[k+1, j], and we actually need (x+y)^2 = x^2+y^2+2xy. And since R[i, k] and L[k+1, j] are independent, the 2xy part is calculated as 2 * R[i, k] * L[k+1, j].

    Now we take k = j — 1, i = 0, and let e[j] = E[0, j], r[j] = R[0, j]:

    e[j] = E[0, j] = E[0, j-1] + E[j, j] + 2 * R[0, j-1] * L[j,j] 
         = e[j-1] + p[j] + 2 * r[j] * p[j]
    r[j] = (r[j-1] + 1) * p[j]
    
»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

The evil test case 61 of LCM Challenge :|

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

8 раз сдавал С, так и не сдал. Оказывается, она падает на n=4. facepalm

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

    В следующий раз потести брутфорсом. На моем компе за секунду получал ответы для n = 1..80. И вообще, полезно иногда потестить там, где реально можно потестить + всегда сомневаться даже в собственных мыслях. + если позволишь, еще совет: когда несколько частных случаев для 4 и более последовательных чисел — заводи массив, чтобы выводить ответ по индексу: res[n]

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

Ура, хоть какая-то динамика будет в моем рейтинге!)))

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

sorry for the slow judging...I put too many test in Div2B and Div1A...I didn't expect some solution are too slow T_T...anyway...the judging is done now...

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

Egor — the luckiest man of this contest

His E's submission 2402930 is only 14s to the contest end and runs 16ms to the time limit.

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

    Well,He use some interesting strategy to reduce the time, It is just...very good job to do this cool stuff.

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

    I optimized my solution until last possible moment. Actually it runs between 2950-3050 ms on server, so I got lucky indeed

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

Ratings are now updated. Log off and on to see them.

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

Can anybody tell me why Div2.C 2398837 is Runtime error on pretest 1. exit code: 13131313 It is at least not throwing any exception in my system. I suspect BigInteger#isProbablePrime but don't know why?

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

I am quite shocked. My following simple Brute Force solution for DIV 2 Problem C:LCM Challenge got Accepted.. :D

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

    This problem is very easy if you think carefully :)

    It include 3 cases

    1: n odd => result = n * ( n — 1 ) * ( n — 2 );

    2: n is not odd and ( n mod 3 = 0 ) => result = ( n — 1 ) * ( n — 2 ) * ( n — 3 );

    3: n is not odd and ( n mod 3 <> 0 ) => result = n * ( n — 1 ) * ( n — 3 );

    Brute force is quiet "buffalo" for this problem :)

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

Hi A short-solution programming contest will hold on October 24 at gpac.blog.ir

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

the link for the tutorial is: http://mirror.codeforces.com/blog/entry/5592

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

Я вот только одного не могу понять в выступлении hariprasath в виртуальном контесте — как можно копипастить коды rng_58 , Petr и hpfdf целых 10 минут, да ещё и ошибиться при посыле задачи А, послав её на В?

А если более серьёзно, я конечно понимаю, что это виртуалка, и никого не волнует, но может принимать какие-то меры против ярковыраженных случаев?

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

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

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

      А можно поподробнее, как, пожалуйста? Всё что я нашёл, это что я могу так делать в тренировках, но не нашёл как я это могу делать в виртуальных контестах официальных соревнований.

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

Тесты к задаче B Div2 не всё проверяют.Например: моя программа работает медленно на тестах с большими значениями, но как только я написал тест 100 100 100 как исключение задача прошла.Вывод:тесты к задаче не проверяют её полностью.Можно было бы добавить такие тесты как 99 99 99.Тогда бы участники придумывали более рациональные решения, что несомненно сделало бы задачу более полезной.

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

    А я могу прописать, чтобы на тесте "98 69 83" программа выдавала "-1" вместо ответа. Это авторы тоже должны учесть?

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

      Это учтут ребята из твоей комнаты.

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

      Нет.Я имел ввиду, что если бы авторы добавили тесты с большими значениями, то написать для них ответ было бы трудно.И такие решения как моё не прошли бы.

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

what does orz mean? and when when will you write editorial? I'm waiting for that :)

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

      orz is used in Japan's net-slang terms. "orz" is used to show when you are in a quick depression and sad or have given up on something.

      Before, thinking by myself what could it mean, I realized that orz denotes admiration and they thank the author in this way. But I was wrong, and now I still cannot understand why they are in a quick depression because of the round. Can anybody explain it?

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

а что такое orz???

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

Orz