MinakoKojima's blog

Codeforces Round #172
By MinakoKojima, 12 years ago, In English

Hello there!

Codeforces Round #172 will take place on Sunday, March 10th at 19:30 MSK(23:30 CST).

This is my second time participating in prepration a Codeforces Round. Last time assist with YuukaKazami is an unforgettable experience. This time, the hardest problems were created by Jiatai Huang(CMHJT) and others by me and Yuping Luo(roosephu).

Testers are sevenkplus, YuukaKazami, pashka and Seter.

We gratefully acknowledge Gerald Agapov(Gerald) for his help in giving advise about the problems, Delinur for her help in translating the problems to Russian, and MikeMirzayanov, who has designed such a powerful platform.

Here let me express my personal thanks to the Codeforces community, which has given me so much gleamy idea in the past two years.

Believe it or not, Codeforces has kept her feet in China's ACM community since last year. AFAIK, some of the hardest problems have been used as this year's Winter Camp homework for our National Olympiad in Informatics.

Also thanks to watashi, ftiasch and xlk. Discussing problem with all of you, has inspired me a lot.

500 — 1000 — 1500 — 2000 — 2500.

We are going to use a standard score distribution in both divisions.

The problemset is a little bit easier than last time, but we still believe, getting all of those five problems accepeted will be a challenging mission even for an seasoned International Grandmaster. The problemset has been marriaged with variety flavor. Take a glance over all five problems before going to coding might be a wise strategy.

UPD:

The contest is over, congratulations to the winners:

Div1:

Div2:

Congratulation to tclsm2012, who also solve the problem D!

We feel so pity to al13n, your last optimization for problem D is wrong. Problem D has a O(mklogn) algorithm. And we are extremely sorry to Jacob, your solution for problem E can pass most of the random tests but actually is wrong.

Jacob... can you explain your solution for us :)

We need collect some feedback about this round .. So the editorial will appear after a period of time.

UPD:

I used to hate those guys who set problems, but didn't write editorial at all! But when things turn to myself, I found it is really difficult to cover all cases. Anyway, it has been done.

  • Vote: I like it
  • +186
  • Vote: I do not like it

Comments Comments (242)
| Write comment?
»
12 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Very early announcement! Excellent!

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

QAQ..

→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

ymm

→ Reply
»
12 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    you have no chance to attend this contest. look at me!!!!!!! = = TAT(it's terrible to zhuangbi)

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ... Only setters and testers have saw the problems.)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      What about translator?!:) She translated and she didn't see the problems?! WOW...Perfect:)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 6   Vote: I like it +1 Vote: I do not like it

        Well, you are right .. Delinur isn't going to participate the contest after all .. We'll try our best on the confidential work of the problems, to ensure the competition run fairly. You can trust us on this point, seriously ~~ ... )

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe 4 problem-setter

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        ... Why not participate ? .. (I am definitely sure you will lost your red handle after this round.) Uw, actually we are short of men right now... How about helping us test one or two of them? 　(′▽`〃)

        → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    lol.. I think you can easily become red if you're willing to.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      yes, maybe, but not this time, because he isnt participating :D

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    And you have created the hardest problem I've ever seen...lol

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Because I'm the lost thing lol

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    your avatar ... Can't look directly <_<

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    TCO round is scheduled for Saturday, not for Sunday.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Ouch... probably, I should sleep more. Thanks!

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No , it doesn't . TCO round 1C is on Saturday March 9th and codeforces round 172 is on Sunday 10th March .

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    We intended to set on Saturday .. .

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      So is it going to be on Saturday which is today or on Sunday???

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        Why can't you read the topic before asking such questions?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          or see the timer on top-right part of the page, which shows how much is left till the contest.

          → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +22 Vote: I do not like it

It would be an interesting contest :)

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Big Fans !

→ Reply
»
12 years ago, # |
  Vote: I like it -65 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I smell a lot of mathematics.

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +29 Vote: I do not like it

Haha WTF ??? ! Picture

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    There is the same problem with my graph.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Wow you guys have interesting graphs!!!

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      and also ruban

      I think anybody participate in code forces rounds #170 & #171 simultaneously have same problem . maybe for a little mistake in set history of code forces #170

      → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Great! Wish we have a great night!

→ Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ym..

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Div. 1 A is boring...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Div. 2 C is boring, too...

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -35 Vote: I do not like it

      Is it joke? Don't you know, that those problems are same?

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    why boring? I've spent about an hour without any result :(

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But you had not solved it, right?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could somebody explain me, how to solve it without formulas divination?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For example, you can divide shaded figure into 8 triangles.

        → Reply
»
12 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I absolutely don't like this contest.

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Should swap Div1.A and Div1.B

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think it's so hard for div 2

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think author's solution has O( n * log( 10^9 ) ) complexity

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      There is easy O(n) solution using stack to find first next greater number for each number.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What a shame, I thought it is O(n^2) and didn't solve this problem...

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There's an O(N) solution based on all nearest smaller values. I think it's a shame the constraints weren't higher.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        10^5 is enough to forbid O(n^2) solution

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I was thinking about this too, but N^2 for N = 10^5 is too slow for sure...

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I use only one rmq, each time fix a max, find second max in left and right, then recursively on each side. which gives O(n * log(n) * log(n)) algorithm. http://codeforces.me/contest/281/submission/3284484

    → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -15 Vote: I do not like it

I love xxx :))

I think this contest had too much mathmatical problems :|

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Why doesn't system test start?

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Div2 B is rather easy

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      isn't it a ternary search problem?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        No need, you can try every denominator and binary search to find the numerator.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i did it, and get wa on 6th pretest, then i checked for numerator, numerator+1, numerator-1 for every denominator. i m sure of getting system failure :(

          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          or you can calculate numerator directly in O(1)

          → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        It was not necessary,easy math in O(N) :)

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A bruteforce setting the denominator and approximating the numerator in small iterations passes the test.

        CODE

        → Reply
»
12 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -23 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it -12 Vote: I do not like it

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

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +68 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    :D

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even tourist solved only A&B....

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      No, he did A B C in 33 minutes and is 7th.

      Edit: Sorry, I talk about current contest.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I think it's harder than last time, this time the Problem E is too hard to have an correct solution,but the Problem C is simpler.

    → Reply
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Good problems! tnx! :)

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Just enumerate the denominator....you can calculate numerator quickly...O(deno) You may find it interesting if you have noticed Python's Fraction.limit_denominator method...O(log deno)

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for interesting problemset, but it was hard)

→ Reply
»
12 years ago, # |
  Vote: I like it +52 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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..

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it +34 Vote: I do not like it

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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it -13 Vote: I do not like it

                  Did you add test 52 for problem C too?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it +9 Vote: I do not like it

                  No..

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  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

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  I misread your answer, sorry.

                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

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

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it +44 Vote: I do not like it

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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                ← Rev. 2   Vote: I like it +20 Vote: I do not like it

                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...

                → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 2   Vote: I like it +42 Vote: I do not like it

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

            → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +30 Vote: I do not like it

            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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it -7 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it +19 Vote: I do not like it

                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.

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
              ← Rev. 6   Vote: I like it +11 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                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?:)

                → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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~

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it -9 Vote: I do not like it

              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

              → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it +10 Vote: I do not like it

          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
          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +24 Vote: I do not like it

            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)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it -12 Vote: I do not like it

              What is the problem with tests to the task C?

              → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 5   Vote: I like it +23 Vote: I do not like it

      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.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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 )

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Cool A solution BTW.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my God, hash somehow blowed the text up!

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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to calculate eps in Bdiv2?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Or just implement your own fraction class.

      → Reply
»
12 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Oh, okay

→ Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

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

→ Reply
»
12 years ago, # |
  Vote: I like it -24 Vote: I do not like it

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...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it -8 Vote: I do not like it

      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...

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Wait, does this work like topcoder such that successful hacks get added to the system tests?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          yes.All successful hack would be added in sys-test.

          → Reply
»
12 years ago, # |
  Vote: I like it -14 Vote: I do not like it

tourist isn't codeforces target after this contest =(

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What solution are you talking about?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u tell me the meaning of Skipped final test.?

      → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Waiting for comprehensive editorial from you, MinakoKojima ^_^

→ Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    You're right.

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

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    99997/99999 — 49998/49999 = 0,000000000200006000140003000062

    49999/50000 — 99997/99999 = 0,000000000200002000020000200002

    You're wrong, dude.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was talking about D :)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        lol,you can use stack to get next max after a number using stack.O(n) algo.

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Aren't they assigned automatically?

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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]?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Curious about it too.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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~.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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...

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +73 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            It's so kind of you!Thanks!Now I feel much better :)

            → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Fixed.

      3314820

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can try comparing double numbers as fractions with equal dominators.

    → Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

When will be the tutorial published?

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is that correct?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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].

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

          → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        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.

        → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply