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

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

Всем привет!

Раунд Codeforces #172 состоится в воскресенье, 10 марта, в 19.30 по московскому времени (23.30 по центральному поясному времени).

Это мой второй раунд на Codeforces. До этого я готовил раунд вместе с YuukaKazami. В этот раз самые сложные задачи приготовил Jiatai Huang(CMHJT), другие приготовили я с Yuping Luo (roosephu).

Наши тестеры — sevenkplus, YuukaKazami, OpalDshawn и pashka.

Сердечно благодарим Геральда Агапова Gerald Agapov(Gerald) за помощь и советы по задачам, Delinur за помощь в переводе условий на русский и MikeMirzayanov, разработавшего такую мощную платформу.

Я хотел бы лично поблагодарить сообщество Codeforces, вдохновлявшее меня на самые плодотворные идеи последние два года. Хотите – верьте, хотите – нет, но позиция Codeforces в китайском сообществе ACM укрепилась по сравнению с прошлым годом. Насколько мне известно, самые сложные задачи вошли в домашнее задание зимнего лагеря по подготовке к нашей национальной олимпиаде по информатике в этом году.

Также благодарим watashi, ftiasch и xlk. Ваши предложения и замечания очень меня вдохновили.


500 — 1000 — 1500 — 2000 — 2500.

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

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

UPD:

Соревнование закончилось, поздравления победителям:

Div1:

Div2:

Поздравления tclsm2012, кто решил задачу D!

Нам очень жаль al13n, в вашем коде задачи D есть ошибка ... и Jacob, ваше решение задачи E проходит большую часть тестов, но на самом деле оно не правильное. Расскажите нам свое решение.

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

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

Very early announcement! Excellent!

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

QAQ..

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

ymm

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

Believe me . It will be a very interesting round. So , good luck and have fun

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

They are saying that the hardest problems were created.I think it's going to be interesting!!!

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

I think it will be interesting round with 9 creators :)

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

That's how you announce a serious contest, not 2 hours before the competition! I wish everyone did the same.

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

it seems i am the only one holding a yellow handle among all the problem setters..lol

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

I'm wondering if I miscalculated or scheduled time for this round conflicts with TCO qualification round 1C?

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

oh,I wasn't aware of this page because it's not on the top...

and the discussing members & testers seems very great!! I believe the round will be an interesting one

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

It would be an interesting contest :)

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

Привет всем!!!
ни одного комментария на русском языке...... значит я первый!!!!

Всем удачи! Повышения рейтинга! хотелось бы, чтобы задачи были различными, чтобы задачи были как на придумывание, с маленькими кодами, так и задачи с большими решениями.

Ещё раз всем удачи!!!

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

.

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

Big Fans !

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

Пишите по русскому!

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

I smell a lot of mathematics.

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

Haha WTF ??? !  Picture

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

I don't know it's my browser problem or nhandi graph really have logical problem ? btw it's a beautiful bug !

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

Great! Wish we have a great night!

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

Wish you all one more "Share it!" in your profile page :)

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

ym..

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

Again 865 participants in Div 1. The record was not broken!:D

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

в 3 (див 2) задаче угол выражается целым числом или действительным?

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

    В первой строке заданы три целых числа

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

Div. 1 A is boring...

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

I absolutely don't like this contest.

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

The problems were really hard. Didn't like this contest.

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

Should swap Div1.A and Div1.B

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

    Well, I think B was harder conceptually to find algorithm, but A was harder to implement, and edge cases = annoying, also takes quite some time to solve on paper.

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

I think it's so hard for div 2

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

some ideas about D div 2 (B div 1)? I wrote rmq and rmq1 for the second maximum, but i didn't invent something faster than n*n*logn...

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

Problem Standard in DIV-2 was A,B,D,E,E :S

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

Мне почему-то не пришел попап, что мое решение взломали. Баг был тривиальный, и я бы его скорее всего исправил. В чем может быть дело?

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

I love xxx :))

I think this contest had too much mathmatical problems :|

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

Nice problems, thanks for the contest. I almost solved C, but maybe next time...

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

    My C was almost correct, I had to try to solve it immediatelly after B and not try to solve D first...

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

It's the first time I send my uncompiled code in DIV2 A Time -> 1:12 :D

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

Why doesn't system test start?

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

Codeforces, you are drunk.

Извиняюсь за оффтоп.

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

    Да, я писал об этом здесь

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

      Думаю, это все из-за кнопочки "Поделиться"? Кстати, как в неё попасть?

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

        Ээээ, по-моему вполне достаточно быть не настолько пьяным, насколько пьян CF:)

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

          Странно, я открываю график, навожу курсов на точку контеста, всплывает окошко с инфой и "поделиться". Я тащу курсор на ссыль и окошко плавно исчезает. ЧЯДНТ?

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

too much mathematics, A (div2) is nothing but a fun, and others are harder for div-2 contestants.

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

why system test is not stated yet? a lot people are going to have system failure on B (div-2) i guess.

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

В-div2 — это тернарный поиск ?

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

    я бинпоиск отправил, претесты прошел:)

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

      А как ты делал ? У меня идея была такая — для каждого знаменателя от 1 до n считать тернарником минимальное значение модуля, а потом из всех выбрать минимум.

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

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

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

      систесты не прошел:) WA тест 33

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

    перебор по знаменателю спокойно проходит. Числитель при известном знаменателе находится по простой формуле.

    UPD. систесты прошло

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

    Я тупо перебрал знаменатель. числитель выбирал один из int((i * a + 0.0) / b) и int((i * a + 0.0) / b + 0.5) сравнивал если меньше погрешность запоминал числитель и знаменатель. Самое главное если погрешность равна, а знаменатель меньше запомнить опять числитель и знаменатель.

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

Как обычно вопрос — что за 3-й тест в C div2?

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

Interesting, systests didn't start and I moved from 255. to 254. ...

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

The problemset is a little bit easier than last time. I wonder how hard the problems were last time.

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

Good problems! tnx! :)

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

I hope, there won't be 50 tests in A div.2, or else the system testing will be too long. For such a trivial problem 10 test cases are more than enough.

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

This is the hardest contest i ever participate... But i like the Problem Div.2 B.I spend almost two hours with so excitement.(Though i can't solve it yet.)

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

Thanks for interesting problemset, but it was hard)

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

Oh damn, my E solution failed on test 101...

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

    I'm so sorry...Your solution was totally wrong but accept all the random testdata...So I generated the test 101...

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

      Turns out you don't need to be a contestant in order to challenge solutions. ;)

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

        He is responsible for the problem E bcz the writer is in hospital ...

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

        In fact I'm one of the testers lol..I've mentioned it but got too much negative feedback so it's hidden T_T..

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

          Can you explain then what kind of test is that (testing log doesn't show much)?

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

            Just random data with N=6000,B-A<=1000...I didn't have thought I could make your solution WA but finally I did it..Thanks to my random data generator..Your solution got 3 WA in 10 with this kind of data.

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

              Hm, let me get this straight — you've added a test to fail Jacob's solution during or after the contest?

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

                During ... actually we want let him know about that during the contest but we can't ... His solution seems strange for us ..

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

                  Did you add test 52 for problem C too?

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

                  No..

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

                  I only make 50 tests for Problem C.I think the test 51&52 is add by challenge.The successful challenge will be check by system and if the hacked solution can pass systest, then that test will be added

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

                  I misread your answer, sorry.

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

                Please forgive a tester without experience..Next time I'll make data not too weak...T_T

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

              I think it's not good to add tests using participant solution.

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

                Believe or not,we have prepared 4 data by this generator and rest by weak generators,and he passed them all.But when we use this generator for 6 more data,he got WA in 3 of 6...This is my first time to prepare problems for CF,I only made 12 large data in 100 T_T...

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

            .. Did you have a gmail?. I'll send it to you as a gift :)

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

          I think the challenge work is up to contestants, and if a tester like you challenge someone, you should at least show him a message during the contest warning that you've challenged him. Seems to be kinda unfair.

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

            So If a wrong solution didn't get challenged then it would be considered the same as the correct one? I think it is more unfair. the basic rule in Contests like CF or TC is that the solution should be CORRECT to get the scores, if the solution is indeed wrong, then it shouldn't passed of course. You may think that the test data is weak. but It is really hard to consider all possible algorithm to generate all anti-test. As today's case, his solution is indeed an wrong greedy. A experienced coder like Petr will find this is wrong and won't try that, but if some one simply come up with it without proof and accepted, isn't that kind of unfair?

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

              Yes, you're right. But at least you should warning him during the contest, so he'll be able to see what's wrong or either find the correct solution.

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

                Umm, we indeed thought of things like that but don't know how. but anyway the systems only says that he pass the pretest,that doesn't mean anything else.passing pretest also has the chance of failing.

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

              Unfortunately there are a lot of obviously "wrong solutions" which pass system tests and got accepted. (See this, for example http://www.codeforces.com/blog/entry/5947#comment-113634 ) Of course one needs to be lucky to get points for those, but by challenging a particular one you don't give any chance to its author. Did you prove that all other submissions of all of the problems produce correct output for any valid test case?

              What solution is considered to be correct is an interesting question. As I know, if we use only subset of a functional language, we can indeed prove that the outputs of it and the correct one are identical for all possible inputs from given range efficiently. We can even write a checker for this. However, for CF/TC problems and procedural languages I always thought that solution is correct if it passes system tests.

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

                If wrong solution's passing is because of good luck then isn't wrong solution's being challenged because of bad luck?:) I apologize for this but I won't discard test 101.I believe rating second,learning first.Correct solution for E is magical and worth learning.Why don't we look forward to it instead of stuck in a wrong solution?:)

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

            I'd like to do so but I can't..because I don't know how to touch with him..I apologize for our weak data at the beginning :) In fact this kind of data(N=6000 B-A<=1000) his solution can accept 7 in 10~

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

              I'd like to know is this the first time when tests were added during contests or is it a common practise? Maybe it's a question not to you, but to Gerald

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

          I think DIV1 B has weak tests too. just run 3284652 or 3283083 with test like this:

          100000
          100001 99999 99997 ... 1 ... 99996 99998 100000 
          
          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится +24 Проголосовать: не нравится

            It's so strange for a contest with so many problem setters and problem testers (with high ratings) that has weak data in three problem out of seven. (Div1 B, C, E)

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

      For me this is unfair. One could use a random generator with a fixed seed (say, 123467) and it is always possible to find a specific test to fail this kind of solutions. Solutions using randomized algorithms based on some random assumptions (say, there are less then 100 tests) do not have to work for 100000000 tests you can generate on your own using full contest time and prepared generators to fail them.

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

    We're so sorry about this ...... )

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

      That doesn't make sense. If you're sorry, then you think you did something wrong. If you did something wrong, correct it. Is no one able to correct the results in this special case, considered unfair by many members, maybe majority?

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

        If you're sorry, then you DON'T necessarily think you did something wrong.

        people often say they are sorry when they learn someone who they just asked after had died for example )

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

          Yes, you do think you did something wrong. In your example you did that accidentally, and if you could, you would withdraw your hurting words. But you can't do anything, so you say sorry. Please don't limit yourself to saying sorry when you can revert something you did. Just do it.

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

      Now I it's apparent that you made right decision and everybody's happy. You had little time to make this decision, but you did it right. Even Jacob would be unhappy to win with incorrect solution. So you needn't be sorry :) I am sorry for my harsh words.

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

    Cool A solution BTW.

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

    it's my fault... better to say my heart trouble..?

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

Див2 должен был быть 100 — 1500 — 3000 — 3500 — 5000

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

    Да уж, в Div2 таких задач А уже давно не было, прям не интересно как-то видеть её было. Самое интересное что есть люди у которых она упала на систестах.

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

I hope the editorial be published soon, like the announcement!

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

What's up with B?

number of failed after test 10 ~ number of succeeded So, the thing is that pass rate for is well near 50%

Guys, is 10^-6 realistic for Python float?

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

    my God, hash somehow blowed the text up!

    So, the thing is that pass rate for is well near 50%

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

How to calculate eps in Bdiv2?

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

    I tried to use 1e-12 as EPS, but solution was challenged. Without EPS handling solution passed system tests.

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

    In order to avoid using float number in problem B(div2), you may can use stern-brocot tree, I think.

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

Oh, okay

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

http://www.codeforces.com/profile/Obaida

see last 4 contest in my rating graph!!! (funny BUG) :P

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

Who added test 52 for problem C? It doesn't look like prepared test case and it failed 4 people including me, because of wrong calculation of a node depth in a tree. I don't think it was a main challenge in this task and it was the last test...

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

    Well, I mean, the problem didn't say the edges had to go a certain way?

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

      Yes, but I'm just interested if test 52 is one of the successful hacks or it was also added by organizers during the contest to make solutions of 4 people fail.

      I think that it might be the successful hack made at 1:58:14, that was added to the system tests — what a fuc.ing bad luck...

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

tourist isn't codeforces target after this contest =(

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

@Admin ....my solution of D is showing Skipped final test....Is there any problem in system testing.?

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

problem b div2 test 33's answer is 1/1 but i think 2/2 , 3/3 , 4/3 are another solutions of it. :( a lot of contestants failed on test 33

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

    If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.

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

WTF? this solution gives answer 4/3 on test#33 7 6 3 why it got AC?

UPD: Link: http://codeforces.com/contest/281/submission/3277121 UPD2: I compiled this code in VS 2012

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

Waiting for comprehensive editorial from you, MinakoKojima ^_^

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

I don't know what to say... just look at this link : http://codeforces.com/bestRatingChanges/220401

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

[user:xiaoda] why is it showing skipped in final testing?? please reply..

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

Great Problems , Fantastic Contest , Amazing System Tests , Brilliant Announcements. :)

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

Спасибо за хороший контест. Настолько сильно "угадыванием" я не занимался уже недели 3, если не больше.

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

А для третьей так ничего и не смог придумать, в результате написал решалку, подождал 20 минут, пока она нашла решение, и послал его с мыслью "да ладно, действительно?". Тоже понятия не имея, почему оно работает:)

А на контесте я включил режим "Я везучий, я не хочу доказывать задачи, я хочу в первой пересекать все со всем и строить выпуклую оболочку".

Кстати, мб я старомодный и отстал от тенденций, но какой-то слишком оригинальный проблемсет сегодня получился, в плане соотношения сложности и числа решений для задач. Первая задача что-то не похожа на 500.

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

    А что за решалка такая магическая?)

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

      Если решают за 10 минут — значит, кодить там от силы минут на 5.

      Если кодить минут на 5 — значит, решение сравнительно простое. С очень небольшой вероятностью там prewritten, но тогда я уже хотя бы видел эту задачу раньше. Остаются 2 варианта — или динамика по дереву, или что-то еще проще, просто какая-то зависимость от параметров самого дерева, которая не дотягивает до самой примитивной динамики.

      Первая мысль была — так как нас интересует состояние всего дерева в конкретный момент, значит, какая-нибудь тупая динамика вряд ли. А умную динамику так быстро не пишут.

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

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

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

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

          Извините, но нет:) На самом деле, такой метод больше подходит для различных задач оптимизации — изначально я привык использовать его для этого. Но и для АСМ-задач иногда помогает.

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

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

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

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

          Кстати, здесь можно поднять вопрос по поводу того, разрешено ли во время матча использовать дополнительные вычислительные возможности в любых количествах. В данной задаче оценочная функция не слишком долго вычисляется + само решение получается простое. И, если повезет с рэндомом, то вот так за 20 минут можно его найти на своем ноутбуке:) Но мог ли я использовать для вычислений что-то супер-мега-крутое, или какой-нибудь админресурс, если у меня есть доступ к таким возможностям и это ускорило бы перебор раз в 15-20 или еще больше.

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

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

У меня вопрос чисто из интереса: можно ли задачу B Div.2 решить как-то через дерево Штерна-Броко и/или ряд Фарея? Полчаса уже голову ломаю.

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

I have an answer about test case#31 B Div2 (99997 99999 99996):

Why the answer should be 49999/50000,

if 49998/49999 is a better result, and is "nearest" to 99997/99999 ???

just try to use calc, and you will see it:

99997/99999 = 0,999979999799997999979999799998

49998/49999 = 0,999979999599991999839996799936

49999/50000 = 0,99998

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

    You're right.

    I think if this round will be retested a lot of solutions will get accepted, and my too.

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

    99997/99999 — 49998/49999 = 0,000000000200006000140003000062

    49999/50000 — 99997/99999 = 0,000000000200002000020000200002

    You're wrong, dude.

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

Can someone explain in details how problem D div2 is solved ? Thank you.

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

    Avoid floating point calculation totally, use long long etc i.e. x/y < a/b iff x*b<a*y peform binary/ternary for AC.

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

    I solved it choosing the 'easy' way, ommiting any special XOR properties. We can see that there are only O(n) candidates which we should check e.g. pairs (f, s) such that TwoHighest(l..r) = (f, s).

    Let's get some f and find the nearest, higher s on the right: f<s && S[f]<S[s] && s is minimal. Then there cannot exist such s' > s that some TwoHighest(l..r) = (f, s'), because if range (l..r) contains both f and s', then it contains s, but f<s && f<s'. Analogically for the right->left way.

    For each number, we find nearest higher number on the left and right. Then check every candidate(pairs (i, right(i)), (i, left(i))) and print the maximum result.

    How to find nearest higher number on right(left): Have the stack A after proceeded(0..f-1) numbers(top(lowest)->down(highest)). When we get S[f] = x, we look at A, erase every S[s] < x and set Right[s] = x.

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

wow i only solved A for 498 points (should have solved B too, i made a very silly mistake) and my rating increased by 140! my sincerest thanks to whoever assigned the new ratings! :) :P

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

    Aren't they assigned automatically?

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

    i'm not sure, but my point was thanks to the administrators who are in charge of assigning ratings after contests, as my rating increased drastically after solving just one problem!

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

Just curious, is there also an O(n) solution if in div2.D, the "lucky number" of S[l..r] is defined as the xor of the maximum number and the minimum number in S[l..r]?

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

    Curious about it too.

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

    http://ideone.com/vix2hL

    Sadly, on the contest I didn't see O(n), I was writing inner loop with break on bigger number found. 5 minutes after contest i've wrote this 67-line(it was simply real_i before, and it was O(n^2) on 6 1 2 3 4 5 6 test).

    Sorry for bad grammar in ideone comments. I think I should go to bed nao~.

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

    Uh, I've misread question, sorry.

    I guess minimum xor maximum is O(N^2).

    Suggest this input: 6 1 2 3 4 5 6. You need to xor 1 with 2 3 4 5 6. Then you need to xor 2 with 3 4 5 6, then you need to xor 3... You can't skip any of them.

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

      I thought about this too. But I wonder if there are any mathematical properties can be explored in XOR operations to improve performance.

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

        I think xor in this problem is like "function of two args, returns some predictable number, which is not really dependent on size of args". So large_num xor large_num doesn't allways equals large_num, and you need to cound all xor's to get the answer.

        But if there's some magical properties, it will be nice if someone explain.

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

    I guess there's an O(n) solution, as my one was O(n) and failed test #13 which offered a special case.

    Let's denote our two target values as Big and Small.

    The idea is following: at first assume that there are two numbers in the whole sequence with different positions of the first '1'in the binary form. Then the two target values should differ in that 'first-1' position. That means, that the Big has to have the first '1' at the same position as the max value of the sequence does. That means that we should look for the Big only among such values, and the Small among the rest. So, we just take the sequence as a set of intervals [ Big?, Small?, ... , Small? ] and [ Small? , ... , Small?, Big? ] and check every one of them for linear time. Total length of those intervals is less than 2n.

    The last case, which I personally failed, is when all values have the same 'first 1'position. In this case.... well, at least one could subtract a corresponding degree of 2 from each one start again.

    You can reference my code, it's rather short)

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

1D's TL should have been 3s..Then the obvious O(k^2logn) solution would get TLE.

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

tutorial for 1C,1D and 1E in Chinese https://www.13331.org/420.html

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

Well the contest was great!!! Thanks for the problem setters.

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

He is an iranian : http://codeforces.com/bestRatingChanges/6073 Faghat bara inke ma ham ye commenti dade bashim .... :D

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

Разве в задачи В div2 в первом тесте не должно быть 1 2 ???

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

There's also an issue during testing:

The Problem D has the correct solution O(mklogn) , but the constant is not small. It also has an small constant approach O(mk^2logn).

During test I suggest that the TL shouldn't be very large because the O(mk^2logn) solution may pass it.

But indeed the difference between slow Java O(mklogn) and fast C++ O(mk^2logn) is minor. So if we want Java solution passed, we can't keep C++(mk^2logn) solution TLE. As a result, some competitor passed it by an straight forward O(mk^2logn) solution, which is not really expected.

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

    So you should set k <= 100 and increase time limit and no problem...

    Edit: Or you should stress test it until you find such a test that it gets TLE.

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

      Actually during the contest,only liouzhou_101 got AC. not too bad..

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

        Above all, Orz Shenben WJMZBMR && Chairman Fotile... I'm sorry for that my solution is O(m·k^2·logn) with highly optimized. In fact, I have no ideas about a O(mklogn) solution. Just waiting for the tutorial...

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

      actually in standard solution,it takes O(logn) per update,O(klogn) per query. So limiting the sum of k to 10^5 would be ok.

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

Как решается задача C(Div2)? Попробовал разобрать различные ситуации, которые получаются в зависимости от угла. Похоже я что-то упустил. http://codeforces.com/contest/281/submission/3287389

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

Now, since some people were asking for my solution of E, I'll describe briefly the main idea.

First of all let's build a mechanical system that would solve the given problem. The system consists of:

  1. particles with coordinates y[i] along one axis.
  2. deformable string, connecting those particles to points x[i]. Their potential energy would then be (x[i] — y[i])^2
  3. hard links, connecting adjacent particles (y[i] to y[i+1]) to enforce (a <= y[i+1]-y[i] <= b)
  4. walls, preventing particles from violating constraints (1 <= y[i] <= q)

Now the problem is to model this system and find its equilibrium. The key point is to add particles one by one. Apparently particles can only interact via hard links (item 3 in system description), so new particle can either drag some of the previous particles down or up, forming a "critical interval" (with difference between adjacent y's being equal to a or b). In my solution I simply iterate through the length of the critical interval to find the moment, when it stops interacting with preceding particles.

I honestly believe, that overall my solution is correct, but most likely I missed something when accounting for wall-particle interactions. There is an obvious question arising about uniqueness of mechanical equilibrium in the described system, but in my opinion there isn't any constraint that could lock the system in a local minimum.

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

    Attention to this data:

    2 24480023 3888 4569
    628100 637054
    

    Your solution gives correct answer:

    630292.500000 634861.500000
    9614112.500000
    

    But when n=3:

    3 24480023 3888 4569
    628100 637054 637264
    

    It gives wrong answer:

    630292.500000000 634861.500000000 639103.000000000
    12996033.500000000
    

    It seems you don't put forth your strength to drag first two particles down :)

    I read your code and believe that without "derivative" it can hardly be correct..I insist that your solution was a kind of wrong greedy idea because you only focus on "critical interval",and it may not be always right.If I haven't understood your idea correctly,can you explain it again for me? Sorry for my bad English. (>_<)

    BTW,I used to think your solution only works when all the delta is close to A or B,but it proves to be incorrect :) And your idea is a bit close to our correct one.

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

      It seems I haven't properly dealt with the case when one critical interval shares one particle with another one. In that case verifying the equilibrium for that particle becomes more complicated.

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

        Whatever,you are the hero in this round! :) Can you forgive me for what I have done?

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

          From my point of view, that was absolutely valid in this particular case to do what you did.

          Since it was a clear flaw in my implementation, that test should've been there prior to the beginning of the contest (just for the reason that it's clearly rather special case) as well as many similar tests (say, a test with answer "+a +b +a +b ... "). Your only fault was to rely on random test generator instead of manually finding some interesting cases.

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

      Fixed.

      3314820

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

Well, I think the problems were very nice and easy to understand. Good job! ;)

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

Я — "Чак Норрис", я поднимаюсь, даже когда у меня -37 :D !! Картинка.

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

For div1 B...I tested the case#3 on my PC and the answer is correct,but the result is different on CF..

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

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

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

    Но только не в такой примитивной форме, как сейчас.

    Когда +-1 AC по задаче может половину таблицы перемешать.

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

      Да, например, можно было бы соединить прямыми точки [0; 3000] [n/32; 2500] [n/16; 2000] [n/8; 1500] [n/4; 1000] [n/2; 500] [n; 500].

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

When will be the tutorial published?

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

Can someone give me a hint on problem DIV1 C (Div2 E)

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

    I can tell you that the answer is the sum of 1.0/depth[v] for all vertexes in graph.

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

      Why is that correct?

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

        The answer is the sum of probabilities of direct removal of each vertex. Let's observe that in order to remove a specific vertex from the tree, you need either to remove it directly, or to remove one of its parents. All these choices are equiprobable, and their count is depth[v], so the probability of direct removal is 1 / depth[v].

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

          why__ "The answer is the sum of probabilities of direct removal of each vertex." and why " the probability of direct removal is 1 / depth[v] but not 1/n

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

          If that is correct, then the answer to example #2 should be 1+1/2+1/3=11/6 instead of 2, right??

          Edit: Forget it, I see my mistake now

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

        Using mathematical induction, suppose, that it is valid for some graph, ExpMoves = Sum{1/deep[i]}. Let add a leaf with deep V. The added leaf can be choosed with 1/V prob. So in case of 1/V prob the answer is ExpMoves + 1. And in case of (V-1)/V prob the answer remains ExpMoves. So, expected moves after adding a leaf: ExpMoves' = ExpMoves * (V-1) / V + (ExpMoves + 1) / V = ExpMoves + 1/V.

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

How to solve E(Sequence Transformation)? I think I have found an O(n^2) dp solution,but got TLE on test case 8,how to opatimization