.o.'s blog

Good Bye 2014
By .o., 10 years ago, In English

Hi, Codeforces!

Welcome to the last Codeforces Round of 2014, Good Bye 2014! This round is very unusual; First, the round starts at December 30th, 18:00 MSK. Second, the round lasts for 2.5 hours. And lastly, the round will be division combined, which means Div1 contestants and Div2 contestants won't be separated.

The problems are prepared by me (.o.) and Seunghyun Jo (ainta). This is our second round at Codeforces. Because our first round caused(?) the Black Day, we hope this round won't cause any errors like before :D

Thanks to Won-seok Yoo(ainu7), who tested our round and gave us comments about the problemset.

We'd like to thank some people who were necessary to make this round: Maxim Akhmedov (Zlobober) gave us great help preparing the problems. Maria Belova (Delinur) translated problem statements in Russian. Mike Mirzayanov (MikeMirzayanov) made Codeforces and Polygon systems, which are really great. Let's give them an applause!

The score distribution will be posted just before the round starts, as usual.

We wish you all the best of luck. Happy New Year!

UPD (2014-12-30 17:33:21) The score for each problem is going to be 500-1000-1000-1500-2750-2750-3500. Thanks to Xellos for giving us some ideas.

UPD (2014-12-31 12:49:05) Round has finished, congratulations to the winners!

  1. tourist
  2. Petr
  3. rng_58
  4. HYPERHYPERHYPERCUBELOVER
  5. subscriber
  6. Merkurev
  7. al13n
  8. mmaxio
  9. mexmans
  10. GlebsHP

Also, thanks to Marcin_smu, who solved problem G after the contest for the first time.

UPD(2014-12-31 12:51:08) Editorial is published. Currently, only A-F is available, but I will add G as soon as possible. Sorry for the late editorial.

UPD(2015-01-02 21:30:44) I wrote the editorial of G. Sorry for the late update..

Announcement of Good Bye 2014
  • Vote: I like it
  • +758
  • Vote: I do not like it

Comments Comments (308)
| Write comment?
»
10 years ago, # |
← Rev. 16   Vote: I like it -153 Vote: I do not like it

Why I give -88 for this comment "Happy New Year !"?

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

    You Give negative -10...-100 :D

    → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it -84 Vote: I do not like it

Hi,Happy New Year!

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

hello Happy New Year

dis like me pls

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

    If you like ... I give it you !

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

It is rated? Happy New Year!

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

    yes :))

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

    yes

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

    2 people said "yes" one of them has -16 while the other has 0.

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

      No, there's a difference , one of them is smiling.

      talking seriously, khashi246 is just a spammer look at his previous comments

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

        I think we should stop commenting in this particular spot. It looks like there is a dislike party B)

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

does division combined that means div1 contestant can perform hacks on div2 contestants ??

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

    Yes. And div2 contestants can perform hacks on div1 contestants too)

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

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

        As far as I know, being in Div1 doesn't necessarily mean you hack better than others. See the nice summary of hacks and see how there are blues and purples mixed with oranges and reds.

        ...we need a special contest based solely on hacking.

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

          That's presumably because division 1 participants can only hack other division 1 participants, and vice versa. Most of the low division 1 crew (people like me who only get A) got to division 1 in the first place by cleaning up "easy" hacks (things like overflow, bound checking, etc.). If every contest were division-combined, I'd guess that the best hackers would be oranges with a couple of blues/low purples thrown in (i.e. those who will finish the problems they can do fairly quickly and have the ability to hack others accurately).

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

            thats exactly what im counting on after reading all problems and solving what i can solve. its just most contestant strategy is to solve the first three problems and start looking for hacks so i have to be fast. I hope for alot of green color in hacks and submissions but not in rank color :D

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

            Ah, true, Div1 contestants can only hack Div1 contestants. I forgot that difference.

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

              What if they put Div1 and Div2 contestants in separate rooms, like they do for Div2-only contests?

              I have no idea, haven't seen a contest for both divisions before.

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

          Its a positive feedback loop; remember your ecology folks!

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

Is it going to be rated?

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

    Of course!

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

    Good Bye 2014 has a lot of blogs , a separated blog only for discussing score distribution and you ask it's rated or not :D unexpected :D

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

    It was asked hour before you asked — http://mirror.codeforces.com/blog/entry/15465#comment-203696

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

      I missed it because everybody who asked that got so many negative points that they were hidden :))

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

        Not when I answered, but maybe that is the reason why I have so many downvotes :-D

        Or maybe there is a conspiracy and downvotes are the tool to hide the fact it will be rated :-D

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

Could you please tell me how many problems in this contest?

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

    There are 7 problems. I forgot to add that in the announcement. I'm sorry for that.

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

I wish score distribution will not be dynamic :)

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

I'm expected to take this contest!

But I'm little nervous I'll not perform well because it haven't programmed for half a year.

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

Good Bye 2014 — Good Bye div_2 Hello 2015 — Hello div_1 Good luck to all members of div_2 Happy new year!!!

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

    I think it will be successful contest for all. Good luck to all participants!

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

Is there a handle changing gift from Codeforces like last two years? :)

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

Bredor)) http://6.firepic.org/6/images/2014-12/30/y8v19jxmqy9q.png

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

Hope for high rating .

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

Last year in "Good Bye 2013", We get "Happy New Year!" instead of "Accepted". what about today?

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

Will we be able to change our handles this year? :)

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

wow this is...

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

At least 50% of comments are "hidden because of too negative feedback" :)) Dislike me plz ;;)

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

Happy Everyone! I think the Good Bye 2014 contest will be a interesting and funny contest. Tonight will be a while night.

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

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

Most comments are Hidden.I do not like it. Because Everyone cannot read that comments? So everyone try to Like that comment. At least no click buttom down vote::i do not like it. we see in facebook ..there is no unlike or i do not like it.

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

I'm very happy to hold this special round. Good luck for everyone!

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

Damn! I have a final exam tomorrow :( but I so wanna participate in this round.... :/

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

Will there be any souvenirs? We want T-shirts!

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

    If you win the entire contest, I will give you a t-shirt

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

      OK, I'll try!

      If I was not able not to do it, can be my goal of the new year.

      Happy new year! :D

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

YuukaKazami has registered for this contest :D http://mirror.codeforces.com/blog/entry/14798

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

    But he didn't participate, It's your fault :D

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

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░████████░███░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░█████████░░███░░░░░░░░░░░░░░ ░░░░░░░░░░░░░███████████░░░██░░░░░░░░░░░░░ ░░░░░░░░░░░░██████████░░░░░░██░░░░░░░░░░░░ ░░░░░░░░░░██████████░░░░░░░░░██░░░░░░░░░░░ ░░░░░░░░░░█████████░░░░░░░░░░░██░░░░░░░░░░ ░░░░░░░░░█████░░░░░░░░░░░░░░░░░██░░░░░░░░░ ░░░░░░░░████████░░░░░░░░░█████░██░░░░░░░░░ ░░░░░░░░░░░███████████████████░░░░░░░░░░░░ ░░░░░░░░░░░████████████████████░░░░░░░░░░░ ░░░░░░░░░░██████████████████████░░░░░░░░░░ ░░░░░░░░░████████████████████░░██░░░░░░░░░ ░░░░░░░░████████████████████░░░░██░░░░░░░░ ░░░░░░░████████████████░░░░░░░░░░██░░░░░░░ ░░░░░░████████████░░░░░░░░░░░░░░░░██░░░░░░ ░░░░░████░░██░░░░░░░░░░░░░░░░░░░░░░██░░░░░ ░░░░███████░░░░░░█████░░░░░░█████████░░░░░ ░░░░██░░████████████████████████░░░░░░░░░░ ░░░░░░░█████████████████████░░░██░░░░░░░░░ ░░░░░░███████████████████░████░░░██░░░░░░░ ░░░░██████████████████████░░░░░░░░░██░░░░░ ░░██████████████████████░░░░░░░░░░░░███░░░ ░███████████████░█░░░░░░░░░░░░░░░░░░░░██░░ █████████░█░░░░░░░░░░░░░░░░░░░░░░░███████░ ░░░░░░░███░░░░░░░███████░░░░░░██████░░░░░░ ░░░░░░░░███████████████████████████░░░░░░░ ░░░░░░███████████████████████████░██░░░░░░ ░░░░██████████████████████████████░███░░░░ ░░░█████████████████████████████░░░░░██░░░ ░░█████████████████████████░░░░░░░░░░░██░░ ░█████████████████████░█░░░░░░░░░░░░░░░██░ █████████████████░█░░░░░░░░░░░░░░░░░░░████ ░░░░░███████████░░░░░░░░███░░░░████████░░░ ░░░░░░░░░░░░░░░░███░█████░█████░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░█████░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████░░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░███████░░██░░░░██░░██░░███████░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░░░░░░██░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░░░░░░██░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ HAPPY NEW YEAR EVERYBODY !!!

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

Hmmmm I'm wondering why this contest isn't held tomorrow......

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

What are you guys hoping the problem names are?

A. New Year and Implementation

B. New Year and Sorts

C. New Year and Easy DFS

D. New Year and Maths

E. New Year and More Maths

F. New Year and Impossible Problem

G. New Year and An (Not) Easy Problem About Trees

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

In order to prepare exams, I haven't written code for a long time.

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

Note that this is also contest number 500 (id from the URL). Lots of anniversaries :)

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

number of participants is more than 6000 now. I hope that nothing happen to codeforces servers in this round :D

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

More than 6000 users are registrated for the contest! I think it will be the record.

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

wow! so many participants! i think it's the first time we have ever reached 6000

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

"Thanks to Xellos for giving us some ideas." Why do I have the feeling the contestants won't like those ideas?

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

    You can see here that my argument is tailored on a specific round, so I am equally worried about that :D

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

GOODBYE 2014!! hope 2015 a better year

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

wish a HaPpY NeW YeAr with good rating for all =D

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

Difference between the starting time of the contest and end of registration now decreased to 2 minutes :) (earlier it was 35 minutes)

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

6250 registrants! What a record! And registration ends before contest starts only 2 minutes.

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

Anyone noticed it's the 500th contest?

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

Can't submit :( Like I am not registered, though actually I am.

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

Hi, I just realized that the contest started 15 minutes ago. I didnt know that the registration closes 5 mins back as this is my first live contest. Is it possible to enter now? I have already completed problem 1 locally.

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

Good Bye 2014 and Div. 1 )))

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

    Good bye 2014 and EXPERT :D PUPIL here i come xD

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

A lot of submissions are in queue

you have to add some time ...

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

Goodbye div1 :( was fun while it lasted

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

My last submission was 5minutes before the end of the contest — after end of the contest I still didn't get the verdict :( .

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

At problem D: "It is guaranteed that wj is smaller than the current length of the rj-th road.". why?

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

    because each year when they repair a road, it gets shorter!

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

      His question was: Why does the problem need that constraint? My solution doesn't care about that.

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

        Because it makes statement more clear.

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

          No, it doesn't. It's at least 2 extra sentences.

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

            Well, without it the "after any changes Wi<=1000 will also hold" sentence must be added to clarify the upper limit of edge weights.

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

        Yes, that was my question; thanks for clarifying!

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

        Because nobody wants to make straight road bent.

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

          Not necessarily. Downhill roads in winter are overkill when straight.

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

            But they do not take much time to pass! At least in one of the directions.

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

how to solve E .

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

    Offline — just sweeplining in a smart way, one BIT helps calculate the answers.

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

      I normalized each domino — max(l[i], l[i-1]-(p[i]-p[i-1])) and use sum on segment tree <a, b-1> but it gets WA on test #7. What did I do wrong?

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

      It's also possible online.

      Let F[i] be the solution for query (i, n). First of all you compute all F[i]s and store them in minimum segment tree. It can be done in time, if you do it cleverly, going from right to left.

      Let M(a, b) be minimum of all F[i]s for . Answer for query (x, y) is F[x] - M(x, y).

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

        In fact F[] can be done in O(n) with a stack. And M(x, y) can be done by union-find sets. 9316327

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

        I don't understand why the answer is F[x]-M(x,y). Can anyone please explain?

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

          Executing plan (x, n) costs F[x] and it makes all dominoes between x and n (inclusive) fall, so it also makes y fall. Therefore, one way of executing (x, y) is to execute (x, n). However, this might be an overkill, as you may pay for dominoes that are behind y. So you need to subtract M(x, y).

          The reason why we subtract M(x, y) and not just F[y] is that there might be some domino close to y (from left side) that is much longer than y and therefore has better range than y.

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

            Thanks. I get it now.

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

            I don't think I understand your solution Baklazan. How does subtracting the minimum ensure the lowest possible value?

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

              Assume we can execute plan (x, y) for cheaper than F[x] - M(x, y). Then we can do the following:

              1. We extend some dominoes in such way, that if we push domino x after extending, domino y will eventually fall. We will do this for as cheap as possible, so it will cost less than F[x] - M(x, y). We will denote price of this step C.

              2. We find such , that F[z] is as small as possible (so F[z] = M(x, y)).

              3. We extend some dominoes in such way, that if we push z after extending, n will eventually fall. We will do it for as cheap as possible, so it will cost F[z] = M(x, y).

              4. Now we can push domino x. We are guaranteed that y will eventually fall by step 1. That means that all dominoes in range [x, y] will fall, so z will also fall. Step 3. guarantees that n will fall as well.

              Therefore we have effectively solved query (x, n) for C + M(x, y) < F[x], what contradicts the definition of F. Thus our assumption must be wrong.

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

    E can be reduced to heavy path decomposition. For each domino you should find which is the last domino that falls down if you push the current domino. Now the answers can be converted into edges in a tree (or eventually, multiple trees). You need to process some other information also, but the cost of each plan is the cost of the path between x and y in the corresponding tree.

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

I finished solution to problem F 3 minutes earlier than contest end, but failed to submit it due to network reason....... so sad to say goodbye to 2014 TAT

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

WTF with B?

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

    Union Find!

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

      BFS. FTFY

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

        BFS was within time limit? D:

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

          BFS is the fastest thing possible, it runs in O(M + N) (with M 1-s in the matrix, they're edges of the BFS'd graph). Just see my code for how it's done.

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

            I'm crying.

            Also, nice C++ Template.

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

    use to all pair shortest path to generate the new matrix where position i and position j can be swaped or not ,then just find normal two loops from 1 to n getting 1 in its lowest index and so on

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

Can't submit in the last 2 minutes :( I can't access Codeforces page quite frequently during the contest.

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

well done codeforces team :) ... today contest ran smoothly (the server didn't crashed) even in the record high participation.

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

    I frequently can't access Codeforces and missed the opportunity to submit in the last 2 minutes of the contest.

    I would not accept this contest if my rating drops to yellow because of this issue ><

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

question B was just made for hack Lol floyd warshall

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

What was the hacking case in B?

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

    3
    3 1 2
    001
    001
    110

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

    I think a lot of solutions that just swapped stuff in strange ways would fail on

    3
3 1 2
011
100
100

    The optimal series of swaps (elements, not positions) is (3,2) (1,2), not (3,1), although the latter gives a better intermediate result.

    (inb4 ninja'd)

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

      Thanks for the explanation guys. Will take this learning into 2015 — never underestimate Div2 1000 and greedy doesn't always work for apparently "easy" problems.

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

        same here lesson learned :) going to green today

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

      I was testing some of the first in the standings solutions and was wondering shouldn't this

      7
7 3 4 6 8 1 2
0010000
0001000
0000100
0000000
0000001
1000000
0000000

      have as correct output 1 3 2 6 4 7 8?

      The output I saw was 2 3 4 6 7 1 8 but the 1 could be swapped with the first number. Am I wrong ?

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

        Invalid input. The matrix has to be symmetric.

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

          you're right, I missed that from the problem statement, thanks!

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

            P[] must be a permutation, but {7, 3, 4, 6, 8, 1, 2} doesn't.

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

    I used

    3
3 1 2
011
100
100

    to hack several people who just swapped every time it would give a better result (e.g. i<j and p[i]>p[j]).

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

    7 1 3 7 4 5 6 2

    0000000

    0010001

    0100000

    0000000

    0000000

    0000000

    0100000

    wrong output: 1 2 7 4 5 6 3

    answer: 1 2 3 4 5 6 7

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

      can you help me where i got wrong . what i did was take two arrays . sort one of them .then for each A[i]!=Bi and B[i]<A[i] check if they can be swapped . if they can be .do it .else continue;

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

        Your idea is wrong; it is not always optimal to swap when possible. See the above cases.

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

          lesson learned I thought i can move out of div2 today but looks like i have to spend some more time here :)

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

    4 2 1 3 4 0001 0001 0000 1100

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

My soln to B got hacked, submitted 5 mins before end of contest and then got verdict after contest :/

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

Good Bye 2014. Hello 2015 World!

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

How I can solve problem B?

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

    You have a graph with nodes numbered 1 to n. Each node has a value.

    All you have to do is, within each connected component, sort the values.

    After that is done for all the components, just print the values in nodes 1 to n :)

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

Website crashed as I was clicking submit button in the last minute, didn't come back up until the contest was over. My solution will most likely fail but I think Codeforces stability is a serious issue. Often during the competition I couldn't access the website for a minute or so, and it would crash from time to time.

On the bright side, the queue was doing impressively fine with 5000 users solving.

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

    But this is the case in every contest I participated in last few weeks. Typically it's not problem for me, because I'm not submitting in last few minutes, but even without submitting I'm getting "too busy" message quite often...

    I think this should be solved with high priority.

    Is someone recording the contests (something like Petr's screencasts)? That could be good evidence...

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

Thank you for nice problems! And there were weak pretests at A and B so hackers enjoyed this round.

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

good buy 2014 == hello 2015 == hello newbie

dis like me pls

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

in Problem A is output case insensitive ?

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

    I suppose yes, because standard yes/no checker in polygon is case insensitive.

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

    Yes, outputs for YES/NO problems are generally case insensitive. (I knew this because I looked at Polygon, randomly browsing to its default checkers, and saw that there is a checker for "YES/NO problems, case insensitive".)

    ninja'd

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

      thank you, now everything is clear in my mind :).

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

Что такого в седьмом тесте задачи Е? Перевести ответ в рубли? Некоторые палочки замешаны в бетон и не падают?

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

In case I get a good place:

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

How to solve problem D?

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

how to solve D???and what concepts to know for it??

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

    calculate number of times an edge will be used in all the permutation. which will be equal to x+1*(n-(x+1))*(n-2) x=no of child of a node of the edge and divide it by nC3 and reflect the changes after each query

    UPD Its correct.

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

      You could also use the fact that E[X+Y] = E[X] + E[Y], coming to the fact that you only need to calculate \sum d(i,j), and calculating in a similar same way

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

    The easiest way is to notice that expected value they ask for, is just: Sum of distances between all pairs of vertices(i,j), multiplied by 3 (because there are 3 Santas) and divided by n(n-1)/2 (number of pairs of vertices)

    The only non-trivial part of the above quantity is sum of distances. It can be rewritten as: Sum of (for every edge e) cost[e]*frequency[e], where frequency[e] is number of paths in the tree that pass through that edge. Notice that if we know frequency[e] for every edge, we can easily answer every query in constant time by subtracting (change of cost of edge)*frequency[e]

    So, the only thing left is to calculate the frequencies for every edge — and they are static (do not change in time). How to do it? The way I approached this problem is by making DFS from vertex 0, that returns number of vertices in the subtree below. Then you can notice that for every edge (u,v) the numebr of paths that pass through it is: (number of vertices in the subtree) * (N-number of vertices in subtree).

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

      Great explanation! Thank you.

      For the first part, why is it that we can just multiply the sums of all distances by 3? Doesn't this mean we will count the same edge 3 times? As in, we might be choosing the same edge 3 times and associating it with a triple, whereas the only "valid" triples are those that have 3 distinct edges.

      If this doesn't make sense, I can try and clarify.

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

        Good to see somebody enjoying my explanation :) (below, I will use E(X) to denote expected value of X)

        We need to calculate

        E( d(i,j) + d(j,k) + d(i,k) ),

        where expected values are taken over every triple of distinct numbers i,j,k. Thanks to linearity of expected value (http://en.wikipedia.org/wiki/Expected_value#Linearity), we can rewrite this as:

        E(d(i,j)) + E(d(j,k)) + E(d(i,k))

        Since every of those three terms is independent of the remaining two, we can just calculate first one — the other two will be the same. Thus, what we need is actually equal to:

        E(d(i,j)) * 3

        with expected value (still) taken over every triple of distinct numbers i,j,k. But since k is absent in this equation, we may as well drop it, leaving taking average only over all PAIRS of distinct numbers i,j. Which is what I wrote above. I hope that is more clear now.

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

I submitted an answer for "D" (forgot to remove my extra cout's) but due to the huge queue, I got the judgement at the end of the contest. WA on pretest 1 on the correct logic. :'( . A bit harsh on late submitters?

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

Is the System test cases are weak in problem A? How this solution passed the system tests as it has no return word before solve function in solve function?

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

    I think the last thing that was returned remains on the stack.

    That template, omg :)

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

      I think the explanation of andreyv is more acceptable. Though he did a silly mistake but he is a great coder in real life. He is an ACM ICPC regional contestant. How strong is his precode! OMG!

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

    This solution invokes undefined behavior. Undefined behavior means that anything can happen, and in this case "anything" was to "work correctly". So, this solution just got lucky.

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

      But the solution is not perfect. As far I think, It needs just more test cases to behave "incorrectly".

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

        No, not in this case. It probably returns the value in a register(I have not read the assembly code generated for this program, but it is usually the reason why such programs work). So it always works properly on a particular machine(even though it has undefined behavior). Adding more tests cannot help here.

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

          Yeah! I think you are right! He is really lucky one! Really amazing!! :)

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

    I learned this type of coding form my Guruji sir Ananta Jalil (http://en.wikipedia.org/wiki/Ananta_Jalil). he can make impossible possible. just joking it was a silly mistake. :P

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

So many failed system test for problem B on test 15 :O

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

Has someone some smart insight why we can ignore book weights in problem C? I solved it, but I did a lot of testing before submitting, because I cannot see clearly why that works...

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

    Well, after reading any book, for the next operations, the original position is irrelevant, because it is now on top of the stack. To ensure the minimum answer, put a book B under any book A read before it, because otherwise you lift book B an extra time, and when you get to reading book B, A is on top anyway. This is my reasoning (might seem unclear), and it doesn't use the book weights except finding the actual answer.

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

    Because after a book is first used (the weight lifted at that time is independent of the book's weight), the number of times it'll be lifted is uniquely given (since the order of books above it at any time is uniquely given by the sequence of readings).

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

      I more question related to our answer

      the weight lifted at that time is independent of the book's weight

      Even if we count weight of the book, it is same problem, or not?

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

        Eh, right. It's always just +constant.

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

    No matter what happens, when we want to read book X, we are required to lift all books appearing between X in the reading order and max(beginning, last occurrence of X). If we place the books from top to bottom in order of their first appearances in the reading order, that it's easy to see that we'll be lifting only required books. Hence, we cannot do any better.

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

    The easiest way for me to see this was to look at a single pair of books i and j.

    If we only look at these two books, we will only contribute to our total cost whenever we "switch" which book is on top (i.e. if book i was on top, and book j is chosen to be read or vice versa).

    Now, clearly, the optimal ordering is one where the first book chosen is put on top first.

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

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

Any idea what is the 22nd testcase on D?

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

    While any individual member of sum (using your variable names) is up to 10^18, the whole sum is up to 10^23, so it's insufficient to store that in long long. I used long double for summation only (individual members were calculated as long long) and it passed.

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

      The answer at any point of time is

      where xi and yi is the number of vertices on both sides of edge i. You can shorten both sides by n - 2. After that both numerator and denominator can be stored in a 64-bit integer. So the only floating point operation needed is the final division.

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

1.5 hrs system test.

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

No submissions for problem G?? so hard or wrong??

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

It was the most wonderful contest in this year!!!

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

Petr will be the third target :)

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

What was testcase 15 in problem B testing? Or: what was the common mistake of those solutions that failed systest 15?

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

    I think it were test cases already discussed in this question... Or your code is working for those test cases ?

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

      My code is okay, but I'm wondering about multiple solutions in my room that I didn't hack.

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

    I hacked 6 solutions during the contest that just did the swaps greedily (if i<j, a[j] < a[i] and ok[i][j], swap). I guess test 15 is the first to fail that. There are lots of easier tests to fail that, of course (read above for lots of examples).

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

Is this rating contest?

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

http://mirror.codeforces.com/contest/500/submission/9317990 what is wrong with this problem B code

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

    This is the easiest I found your code is not working for

    5
2 4 1 3 5
00101
00010
10011
01100
10100

    Correct answer is 1 2 3 4 5 your code returns 1 3 2 4 5

    edit: wrong submission, let me check later

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

I went from blue to orange directly! WOW!!

:D :D :D :D :D

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

Nothing better than starting 2015 with 2015 rating xD

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

Petr > 3000 !!!

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

crossed 1800 mark for the first time :) ... new rating 1854

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

736-th place, +177 rating, how is it possible? I can't understand.

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

    Because most of the top rated people participated, I think. I got 505th and got +366!

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

    The inflation problem for combined division contests is even more serious than usual.

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

    Here is my idea:

    With division 2 contestants participating, it is easier for blue, purple, yellow and red to get a high ranking in percentile.

    With many top players participating, the average rating is raised.

    That's why division combined contests are mostly rating boosts.

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

      Main problem behind such assumptions is that we actually don't know how rating works :D I've heard that formulas are made in such a way that sum of ratings after round does not increase; and there are also some "magic constants" to prevent inflation, so sum of ratings after round should even decrease.

      I guess we should take a look at performance of these users who had their first rated event today — if their average rating is below 1500 now, then they may be one of the reasons of inflation; maybe some of them will not compete anymore, some other will just violate rules and create another account after bad performance today, and it's a boost for our rating.

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

    I've already told MikeMirzayanov about problem with fast rating inflation few weeks ago, and i guess that after this round he'll agree that some changes in rating formulas are needed :)

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

red-colored before 2015! (although i feel like failed in this contest)

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

    Same feeling bro.

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

      I'm in the club, 2227 — same rating here! I feel like I did my best tho ;d

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

My first submission to D failed pretests because I tried to output a long double with printf("%Lf") (it does work on my computer, but not in MinGW due to a bug), is it possible to have it accepted? (it is not my bug)

Also, I do not understand this portal, is there any way to see all the recent posts? (I can only see all the recent comments in "Recent actions")

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

    For what it's worth, you don't get penalty when your solution fails pretest 1.

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

      Yes, I know. But I got less points than I would get if it was judged as accepted (I was unable to find any bug, so I have solved E and returned to D later).

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

Hello. Would you please explain me why in here:(http://mirror.codeforces.com/contest/500/submission/9326013) output isn't in double? I casted everything to double and I don't still know why this happens.

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

    You should use std::setprecision or printf rather than std::cout when there is constraint about absolute or relative error.

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

    Default "cout" of double always prints 6 significant digits. setprecision or printf is definitely required.

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

It was a pleasure to compete together with div 1's coders. Happy new year!

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

Finished coding problem D just 1 minute after contest (wait long time until practice mode open, and submit it and got AC). Why I'm so slow to implement something, I lose my rating this time :(

Btw, happy new year.

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

Quite strange behavior of the testing system.

During systests this submission gets TL15: 9311938. The same code in upsolving gets RE15: 9326201. And in my local Unix system this buggy code runs correctly.

Small fix makes this solution Accepted: 9326316

Is there any explanation?

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

    9326834 AC using MS Compiler.

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

    The heap buffer overflow your code caused truly may lead to anything (even possibly arbitrary code execution?), including infinite-loop.

    It may also be a little bit random due to "what is next to your buffer" on different runs, so the behaviour is not strange (though getting such TLEs is rare — Congratulations! achievement unlocked :D)

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

My 8th raising up contest in a row! :D

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

For some reason using long double instead of double gives extremely weird output for me but works on CF. Output in my PC for first case is:

-26815615859885194000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000.0000000000 -2.0000000000 -0.0000000000 -2.0000000000 -0.0000000000

AC code: http://mirror.codeforces.com/contest/500/submission/9326579

Any idea what the problem is?

Edit: Actually following line gives -2 as output:

cout << (long double) 3;

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

Happy new year. I am red coder, good surprise ^-^.

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

Я продолжил прошлогоднюю традицию менять цвет после написания Goodbye. Yellow color is a good New Year's present :)

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

Nice round. One question about rating calculation: is the weight given to a new contest > 50%? The rating changes seem fairly drastic in some cases.

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

Made a small mistake in problem D (using long long to calculate the sum) and ranked only 185...But very surprised when my rating changed...2138+=92... Good Bye 2014 and Happy New Year!

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

So happy to end this year with my highest rating. I would say that Problem E is beautiful even though I made many stupid bugs. There are many solutions with different approaches.

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

WoooW I am a Master.Thanks for a great round !

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

Thank you really really thank you you've made my day :) XDD i cant be any happier

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

Why there isn't a Hello 2015 Round?? It will be nice

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

    Let's have a rest.

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

    Look at Gym.

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

      Wow, I hadn't seen it, it looks wonderful, but why are them at Gym?? aren't them regular rounds?? 3 hours long and simultaneously, uhmm?? we will see... thnks for the advise, M

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

I'm very disappointed about my result :( Hope the next contest will be orgranized soon!

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

I gained +304 points!! Is there anyone gained more points than me?

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

giant rating_increase (dreamoon_love_AA) :P

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

YouAllHaveMeizi Master in the first contest

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

Rating is broken.

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

There is something very strange behind rating formulas. While we clearly see overall rating inflation (number of red coders increased by ~10% after a single contest...), top participants got very small rating improvement today. rng_58 have +4 and Petr have +6 today; tourist have +14 only, while he had +37 in Round #282 — and today he beat both #2 and #3 of world ranking, while both of them were missing round 282.

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

    It may be that the formulas to avoid rating inflation affect very high rated coders much more than they affect the rest.

    As you said, problem with such speculation is that we don't actually know how rating works. But we do know this update was completely broken.

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

      It may be that the formulas to avoid rating inflation affect very high rated coders much more than they affect the rest.

      Isn't it how it should be?

      When more new people are registered in codeforces, there should be more red coders. If one can beat a half of red coders participating, he/she should become red too rather quickly. It would also be strange to make one yellow just because new people came. Imo, some percantage of colors needs to be maintained.

      On the other hand, it should not be that difficult to get to the top. I guess one will need to win 30-40 rounds in a row now to claim the first place(assuming tourist does not participate or takes the second place in all the rounds) in the rating, and this is probably a mistake. That is, the rating of the tops should grow slower, or else they will become unreachable if they participate often (at least, until they are alive:).

      We should probably pay less attention to the numbers being added to rating, and to look more at how consistent the percentage of the colors is. My guess is that it is reasonably consistent. The problem is that there are many people who are registering new accounts and do not participate later. Those people should probably be excluded from the rankings after some time, like it is done in topcoder, or even by resetting their rating, so that there will be no people who accidentally became red due to wrong formulas and do not participate any more. And the formulas should be revised to support the consistency within the 'active group'.

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

        I don't see why inflating top ratings is inherently a bad thing if it reflects how much better they are from the rest of us mortals. If someone is beating tourist consistently, the rating system should ensure that that person catches up to him quickly. This can be done through volatility scores, for instance -- someone that is consistently performing outside of their predicted range should be allowed to have very large rating increases. The codeforces philosophy of making rating updates independent is misguided, in my opinion.

        But I'm not entirely opposed to having small increases for top players. The point was more how drastically different the rating changes are in regular div 1 rounds and on this round, which demonstrates the rating system has failed to show any sign of consistency. Or you agree it is reasonable for tourist to gain more rating from winning #282 rather than Good Bye 2014 (with a lot more participants, and in which he beat #2 and #3)?

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

    Why the rating formulas aren't public?? Is there a special reason??

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

Hm, when is the editorial ETA (estimated time of arrival)

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

This year it was "Accepted" instead of "Happy New Year"....

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

How could I print a long double with printf? I used %Lf and got WA, is %lf correct?

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

    %Lf is correct. The problem is with Windows's C runtime, which doesn't recognize 80-bit long doubles.

    The safest way is by far to convert to double first, then print using %f, and it's what I would recommend.

    If you really want printf to print long doubles and you're not using MS C++, the compiler has its own version that seems to work, called __mingw_printf. I don't guarantee that it's decently fast, correct or available though.

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

BTW, will there be tutorials of the problems?

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

I appreciate the efforts you put in to make this contest possible but without the editorials its all useless.

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

Editorials ... please.

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

    .o. is writing editorial now. It will be posted soon.

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

      "soon" is very vague.

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

        In the past editorials have sometimes taken more than 4-5 days To appear. Be patient.

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

      Take your time guys. A good late editorial is much better then an early bad editorial.

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

    Sorry for the late editorial. It is published now.

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

There should always be a MAX pretest.

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

    Most of the bad submissions would either timeout, or give WA in such case, whichever the problem it has. What would be the use of hacks then? Moreover, max tests would overload the servers even more — and I think Codeforces are already having troubles serving so many people at once.

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

We are waiting for a perfect editorial for Good Bye 2014 yet.

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

    Sorry for the late editorial. It is published now.

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

Hello,

For B Question I first found the transitive closer of adjacency matrix then performed bubble sort greedily. Can anyone please tell me what is wrong in this? or any testcase which will give wrong result on this approach. My code is working fine for this Case also I am unable to see Testcase 15.

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

    Hi, I believe your transitive closure code is wrong. Changing the order of the variables in the loops gets AC.

    =)

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

Good Bye 2014,New Year Permutation: The test case 15 does not satisfy the constraint of the problem A[i][j] = A[j][i], kindly correct this. (When I tried submitting my code that uses only the upper triangular matrix I got wrong answer on test case 15 however when I submitted the same code with the modification to use the entire matrix for dfs it got accepted)

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

    No, the test case is correct. I just verified it.

    9399277

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

      In this case, you just said that all test cases are wrong :D

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

    Your solution was wrong, because it only checks vertices from i + 1 to j. The solution doesn't consider paths like 1-5-3, because 3 is not in the range [5 + 1, n].

    → Reply