cgy4ever's blog

Codeforces Round #270
By cgy4ever, 10 years ago, In English

Do you want to win a T-shirt? Do you want to learn how to design tasks for programming contest? Do you want to solve 7 tasks in 2.5 hours?

So Codeforces Round #270 is right for you. It was designed by me in California, Assembled in polygon (so Thank you MikeMirzayanov for the system and Gerald for organize and testing), will start on regular time this Sunday, don't miss it!

The organizers of Marathon24 decided to present gifts to the best finishers of the round! Best 25 participants will get Marathon24 tshirts! Thanks!


It is just an image to attract your attention. Real tshirts will be designed specially for Marathon24!

There are some articles introduced how to become a problem setter, like Problemsetter's Memoir and Way of problemsetter, but they focus on the process of contest preparation or high level thoughts. You might still don't know how to begin to write a contest: because you need to come up with ideas about problems in the first place.

In the last 3 years, I've designed lots of tasks, for example, there are 2 Codeforces Round by me (#190 and #228), and there are exactly 100 tasks designed by me on Topcoder. So I want to write a tutorial to share some specific ways to come up with new tasks.. Oh, wait, how about create a contest and write the tutorial in problem statement? So I get this idea: in each problem I will introduce a specific way of design, and I'll tell you how did I use this way to come up with a new task, and you need to solve that new task!

And this round will be a bit special: all contestants from Div1 and Div2 will compete in one contest, and it will contain all 7 problems! The duration is extended from 2 hours to 2.5 hours.

In the last, I'll do some self-introduction like marat.snowbear did in the announcement of last round. I'm Gaoyuan Chen from China, I lived in Beijing for 23 years till this August, and then I went to University of Southern California in Los Angeles to learn Game Design and Game Development. As a game designer, I'll try to make my round interesting and competitive. (And of course, there will be a problem about a popular game!) And I start to use Facebook after moved to US, so if you want to know more about me or want to chat with me, visit my facebook page: https://www.facebook.com/cgy4ever

More information like score distribution (so maybe we will have 3500p for last task!) will be announced later.

Good luck and have fun!

Update1 : score distribution: 500 — 1000 — 1500 — 2000 — 3000 — 3000 — 3500

Update2 : Contest ended. Thanks for participate! Any comment is welcome (you like the task? don't like it? it is too easy? too hard? Do you like the idea of Div1 and Div2 compete together? etc.).

Update3 : Editorial: http://codeforces.me/blog/entry/14028

Update4 : System test finished! Top 5 (in fact Top 6 because of a tie):

  1. Petr

  2. Egor

  3. riadwaw

  4. PavelKunyavskiy

  5. Jacob and rowdark

Update5 : Thank all of your support! I found I'm on the Top contributors list now. :)

Update6 : Statistics by DmitriyH: http://codeforces.me/blog/entry/14034

Announcement of Codeforces Round 270
  • Vote: I like it
  • +794
  • Vote: I do not like it

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

These T-shirts look a bit generic :D

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

    It is just an image to attract your attention. Real tshirts will be designed specially for Marathon24!

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

Thanks everyone who downvoted this comment . I broke a record and became last one in contribituon list . This is a big achievement in my eyes. Start upvoting now !

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

    Neither are your spam comments right for codeforces .

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

    What is the current record in most downvoted comment on Codeforces? That one here looks like a pretty good candidate :P.

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

    I missclicked upvote, how can i get my vote back(to downvote ofc)

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

      You can make another account, downvote from it and repeat as long as you find it fun :D

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

    downvoat rating: -206 (min. candidate master, -206)

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

      The amount of downvotes for his comment is below worse's rating :P.

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

        And his comments has more downvotes, than the post has upvotes :D

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

    Do we want to win a T-shirt? Yes, we do. Do we want to learn how to design tasks for programming contest? Yes, we do. Do we want to solve 7 tasks in 2.5 hours? Yes, we do.

    Do we care about your opinion? No, we don't. Do we care if you don't participate in the round? No, we don't.

    Have a nice day.

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

      wow, positive man!

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

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

        No, that is NOT how you link an image. You're linking your profile page, which is not an image.

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

      so, you want to break the record of highest up voted comment? good luck!

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

    am i the only one around here who up voted the non edited version of this comment?

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

    My pp is very cool

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

    aaahhh! my record has been broken!

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

The age of long round descriptions has started

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

Its really nice and interesting to know about the problem setters.

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

So are the top-25 of both rounds getting t-shirts?

UPD: sorry I misread, both divisions are competing in one contest

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

Oh yes, this will be very useful for me. Maybe I will learn how to write a non-math problem (!!)

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

Is this a rated event?

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

    Yes. Why not?

    This is not the first rated round for both division. (e.g. Good Bye 2013 was rated for both div, but the duration is 2:00 instead of 2:30)

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

      Just because I saw both division round for the first time. :)

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

      You introduced your self in your blog. But, Something was question to me for a long time. Why is your username cgy4ever? What does cgy means and why forever? :-)

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

        His name is Gaoyuan Chen; in China, the family name goes first, so Chen Gaoyuan (CGY).

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

          So, His username is something like : "Viva me!" ? :D

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

you are mine one of all time favourite coder , you always write code simple and understandable :) . last couple of rounds was not good for me i hope this time my rating will increase :D . it always great to compete with both division :)

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

My favourite problem setter !! I have tried to mimic/ learn problem writing by looking at his problems. Your problems are really creative and provide a lot to learn. A big thank to you cgy4ever from heart :)

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

"then I went to University of Southern California in Los Angeles to learn Game Design and Game Development."

That sounds awesome :D

Is there any game you've designed?

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

    That's a Yo Gi Oh Problem setted by him Link , maybe he was a part of the team who designed it ? =D

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

      Oh, no, Yo-Gi-Oh is not designed by me. :)

      That is indeed a great game, I played it (and watched the anime, at least first season) when I was in primary school.

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

      That's impossible timewise, the franchise is from early years of this century.

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

    Oh, so you know I just start my way to become a game designer, so don't expect some famous games designed by me at this time.

    We have a game design course this semester, and we are designing non-digital games every week. (We have not only CS student but also students from School of Cinematic Arts, and most of them don't know how to program, so we design games that do not require programming)

    That is a fun course, these pictures shows how other people are playing games that my team designed in first few weeks (it is called playtest: they play our game and give us some feedback, then we use these feedback to improve our design, and repeat this process again and again):

    http://puu.sh/bPARt/49974bf0b6.jpg | http://puu.sh/bPASe/91b97133b2.JPG

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

      I'm sure that if you do the same thing for gameplays as you do for contest problem ideas, you are almost guaranteed to discover a few game-changing ideas eventually. Good luck with that!

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

Great format: 7 broblems — more place for solving ideas and more interesting standings!

At least its my thought.

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

This round will be on my 17th birthday :) I hope this will be a great round for me and for all.

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

I do hope you provide sample implementations for the really hard problems. Its always a pleasure to read your code cgy4ever !! :D

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

I've a feeling like Codeforces is becoming more than a problem solving and programming site , I'm feeling lucky to be in this great community with brilliant minds

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

Problem setter is very interesting of facebook chat. :D

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

Just curious, do you have any special reason behind making this contest combined for both divisions?

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

    There must be some reasons but I don't know that. :)

    This decision was made by Gerald (or maybe MikeMirzayanov or some other people in codeforces side). I think this idea is great so I agreed to use it.

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

    Probably because there are prizes. It's hard to compare participants if they are given different problems.

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

Another Chinese Round arriving!

Enjoy the T-shirts:)

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

What does "cgy" in your handle mean?

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

An exciting announcement :) Wish this round success !

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

Surely the best way of creating new problems — misreading other problems. I created a lot problems that way :D.
For example: http://www.artofproblemsolving.com/Forum/viewtopic.phpp=2498536&sid=add5e05df3e05f2371cd0bee14294831#p2498536 — I misunderstood phrase "rounding down to the closest integer", I somehow ignored "down" and focused on choosing the closest integer, so 5,2 should be rounded to 5, but 5,7 should be rounded to 6. It turned out it has a really cute solution and later it that problem was posed in the most popular polish mathematical periodical "Delta" :D. Can you find the solution :)?

Lame way of creating new problems: "What can be done by using centroid decomposition?" :P.

Another fun way of creating new problems is to get inspiration from real-life situations. For example when being annoyed at people getting on the plane when they block the aisle taking care of their luggage and causing 50 people to wait. It immediately comes to mind that given time of blocking aisle when finding one's place for all people, one should firstly find an optimal arrangement, so that the summed time of waiting is minimized!

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

    Two easy ways:

    1. change one word
    2. swap input and output

    (see the problems E, I, J from our last gym contest)

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

      "change one word" -> most probably minimize to maximize or vice versa :D

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

      regarding point 2, it seems cgy4ever agrees with u. :)
      (see problem D for more context)

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

    I once created around 4 problems (for a physics competition) by naming them by quotes from Fish Fillets and creating problems based on them. Of course, it's easier to make physics problems because you just take an IRL scenario and make a simplified model if it's unsolvable :D

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

sorry

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

    There's no "yuo" on that page, so we'll still minus you.

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

“all contestants from Div1 and Div2 will compete in one contest”, does it mean a difficult way for the div2 members to get the T-shirt ?

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

    Yeah, for me too.(I always jump from div1 to div2, then back) :D

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

    I don't know how exactly the rating is calculated in codeforces contests. But from the limited number of contests I did till now, what I came to know is that my rating would increase/decrease depending on whether I got a better/worse rank than the previous contest. Since this time, Div 2 contestants will be doing the contest with Div 1 contestants, the ranking of Div 2 contestants will most probably not be better than last time. Does this mean that we (Div 2) are going to get a drop in the rating?

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

      No. The update will be adjusted to that unusual contest (I mean, formula for updating ratings covers all cases in a relatively fair way, any special treatment is needed).

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

    as difficult as for div.1

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

Жалко что с отбором Минским на ВКОШП пересекается.:(

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

ACM-ICPC rules?

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

    Score distribution is mentioned, so probably not.

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

Is this a rated contest ?

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

It was designed by me in California, Assembled in polygon

Are you mimicking Apple? haha

https://www.apple.com/designed-by-apple/

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

    Yes, I fount it in the back of my iPhone, and it looks interesting.

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

Could be 5k registrants! Fingers Crossed

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

5000+ registration and all of them are official . This is great :D

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

delayed :(

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

    i think its normal for 5000+ registration

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

      Yeah, and crashing is normal for 5000+ registrations too :D

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

    I get the feeling there site will be slow/down often...

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

Will this round rated??

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

The contest was delayed because this guy didn't registered at time

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

5419
Sorry TopCoder It's The Age Of CodeForces

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

мне интересно на сколько поднимется рейтинг worse, он сейчас на 500+ месте

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

worse solved the first 4 problems! I wonder if he is going to hack everyone again!

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

    also, i just noticed that he solved B in just 32 seconds!

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

worse solved first 4 problems!
I'm going to kill myself :D

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

    and didn't do even one unsuccessful hack! :D

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

      Oh my god, I forgot about unsuccessful hacks, what a shame... Now my rainting will increase, it wasn't in my plans, I hate myself :(

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

        You should solved all 7 problems in contest,and make many many unsuccessful challenge until your score's absolute value equals to the score when you solved 7 problems.

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

        Because you are the one in my friend list, when it came to 2 hours after starting, I was so surprised that you hadn't done any hack! And I doubted that you write the code which can pass pretest and FST. After system test, you surprised me again. In the end, I doubted you either forgot to hack (maybe you forgot it is the "worse" account) or want to make a "V" rating (decreasing and increasing). You can make another achievement that become IGM from white rating (rating below zero)~~ BTW. When I finished the problem C, I clicked the friends' rank and notice your rank is in front of mine... At that time, I felt I am worse than "worse" as well as the "worst"...

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

          I can be your friend.

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

        to be honest what ever you did for fun or anything make you as a celebrity :D today anyone from codeforces community at least know about two handle tourist and worse :D

        Btw i believe oneday you will be a red coder :) i would like to ask you a personal question how old are you ?

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

          It's a secret. I'll tell you when I become a red coder ;)

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

          "i believe oneday you will be a red coder" — done! ;)

          Thanks for your belief in me!

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

Are there maxtests in pretests? Will all those solutions pass?

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

    How do you "check" ? by doing all pair shortest paths specialized for a tree ?

    EDIT: sorry comment was meant for your MST post for problem D !

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

      yes, checking all shortest pathes by running n dfs's

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

How is problem D supposed to be solved?

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

    I found MST and then check if its correct answer.

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

      What algorithm did you use to find MST ?

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

        I used Prim's algo, but I believe Kruskal's algo will do too.

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

          Can you please tell me what do you exactly mean by "check if its correct answer." after finding the MST?

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

            Check that all pairwise distances are correct. It could be done in plenty of ways, I used dfs from each vertex.

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

      How did you find MST ? How did you derived edges from the distance matrix ?

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

    There are many ways. For example, if you pick vertices i, j, then you can recover the path between them: k is on this path iff D[i][j] = D[i][k] + D[j][k]; sorting by D[i][k] gives their order on the path. This way, if you pick i as the root and try all j, k, you have all supposed edges and are left with checking their treety.

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

Okay, I'm probably going to hang myself, but what was the idea for B ? I just didn't get it...

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

    I use this: try to send people to top floor first and use any spare capacity for the floors below. continue same downwards

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

    the idea is that you have to move to the highest floor ... so it makes sense to make a greedy approach : pick the highest k people (Fi) and transport them and come back and do the same thing again ...

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

    Okay, now I know why I didn't get it... I just didn't realize that 1st floor is really 1st, i. e. floors are not 0-based! And it was written in the statement like bazillion times and I was just wondering how they got the answers to the samples... goodbye cruel world :D

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

Are there any rules which forbid using inline assembler in C/C++ code? With it, problem G becomes super-easy...

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

    I might get a lot of downvotes for this, but I don't see which assembler magic you can use to make the brute-force approach viable, (if thats what you mean by super-easy...)

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

      Compute bit count via SSE3. (I'd like to note that even without assembler magic, __builtin_popcount results in ~7.9s for the worst case; but SSE3 bitcount results in <3s).

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

        Good job ilyakor!

        I have tested builtin_pop_count() and made sure it will fail. But it turns out many people uses cnt[x<<16] + cnt[x>>16] and passed.

        I think I should learn more knowledge about low level computer science, like assembler.

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

          More faster way is splitting 64-bit long long on 4 16-bit shorts.

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

It was difficult to hack in this round :(

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

Wonder how long System Tests are going to take with so many people and 7 problems...

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

worse'll increase +inf i think

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

Can anyone please tell how to hack a code with code generator .

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

    If your test case is too large, for example it has over 100 inputs, you can write a code to generate your test case, then codeforces compile your code and give the output to the selected code for hack.

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

    I tried to write max_tests with code generator, but did not success. Write 105 integers from 1 to 105 by hands would take to me more than 2,5 hours.

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

http://codeforces.me/blog/entry/14028 Editorial.

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

How to solve B?

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

worse is going to jump pretty high, i guess :)

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

I am more interested to see rating change of worse than mine :)

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

    i don't think he will become higher than Newbie.

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

    Maybe when you reach negative rating and white color, you will never have it possitive?

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

How to solve C? I submitted a solution which passed pretests but I am afraid that it will fail systests.

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

    Greedy. Take the minimum of 1st string according to given permutations.

    set flag=0

    Then go to all other permutations in given order and take minimum of them which is greater than the first string and make it as the current string If none of the names now has string greater than current string then break the loop and answer is NO so set a flag=1 else make current string as lower of the two strings of a permutation and do next iteration

    if(flag) ans=NO

    else answer is YES

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

he is lucky :P
submission: 7999344

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

    Isn't it correct ?

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

      when n%k equals 0, he is accessing p[-1].

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

        p[-1] is equal to zero when p is global

        Because I neglected this fact I made an unsuccessful hack today

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

          it's UB not depending on globalness of array.

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

            Sorry for getting the fact wrong. What does UB mean by the way ?

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

That's feeling, when you know that your n^3 solution won't pass system testing, but you steel can not stop hoping :|

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

i tried hacking 8002822 with n = 17, but the code (correctly) returned 8, 9 as output. can anybody explain how?

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

    I don't know why...It's strange because 8>=n/2 and he have i<n/2.That's black magic :))

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

      it's even more puzzling because i successfully hacked 7998356 with the same input n = 17.

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

        When the round started I was a bit excited to be in the same room with you, since I've noticed you're active and known in the community and also I participated in #258.

        But then i got disappointed when you hacked me ~10 minutes before the end, when my solution was locked (all because of a missing '=' sign).

        Nice find though. :)

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

          glad to know that i'm atleast a little "famous" :D

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

    Well, he reads from not unitialized variable and it's UB(may work in any way), probably it's optimized in that way that a and i are effectively the same variable, because in any correct case(when there's no UB) a and i are equal

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

    compile this code with clang++ and g++, got two random numbers 8015726

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

      did you use -O2 ?

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

        no, I didn't use

        with -O2 output is 0 17 with g++ and 8 9 with clang++

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

        In case anyone's wondering, this page lists the flags used by the compilers on CF. As for "-O2" flag, this manual explains what the flag does. In short: it's a 2nd level optimization.

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

      never use doubles with no eps.

      never use doubles if int is enough. j*j <= i

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

D problem was very pleasant for me. After a hour of thinking (and that's what I like) I discovered how to solve it, but sadly I wasn't able to implement a correct solution. Thanks for round!

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

Petr won this round with a nice margin!

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

delete

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

Can anybody tell me why this solution of mine Timed out. But this got accepted. The first one used scanf to read inputs. The second used cin with sync_with_stdio(false). I assumed both of them are comparable in the time it takes.

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

One of the best rounds I've ever participated. Congrats!

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

    My rank of contest is

    R = 2^A + Q

    where

    A is a count of my accepted solutions

    Q is a quality of problems

    didn't you noticed smth like this? :D

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

http://codeforces.me/contest/472/submission/8011195

http://codeforces.me/contest/472/submission/8015575

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

An identical problem to B was used a few weeks ago in a URI Online Judge contest. Link

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

    I have access to the identical problem in Polygon, it's too easy to be unique

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

      Even being an easy problem, it's cool to solve. It was a good choice.

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

I really enjoyed the problems, the mixed divisions was a great idea, as the problems were approachable for both divisions users. Thanks for the great contest.

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

Problem D is one of the most hard problems that I ever sent on contests (if do not take into account that I have copypasted code for DSU and Dijkstra from emaxx:)) ). Thanks for interesting problem D and interesting stories about problem creating:)

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

When ratings will be updated?

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

@admins Please can anyone tell the approx time it would take for rating update ? If it is >= 30 mins I will go to sleep :p

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

Actually, the contest was not balanced. It doesn't deserve +537, too bad that I had voted it before it started. Three easy straightforward problems that almost everyone solved, one problem that requires to think a bit, and three very complicated ones. Many people were doing nothing after they had solved D. Problem E should have been replaced.

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

    C should have been harder too . A , B , C were very easy but the jump from C to D was large for low-skilled people like me . So most of the people were able to solve all A,B,C and the ranking was solely determined by speed .

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

      Not only by speed!
      Don't forget about hacks!

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

        Oh, of course! Can you imagine how I enjoyed almost 2-hour searching for that s1.compareTo(s2) <= 1 in problem C?

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

      It was pretty much a div1+div2 round, but with 2xD instead of C+D. That's why 3 easy problems — div2 A,B,C.

      I would've removed G and put an easier problem after D.

      Alternatively, there's a nice hack that shouldn't remove the main point from F and makes the code much less tricky: providing additional 64 registers whose values at the end don't matter.

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

    Yes you are right. I found E is hard to implement few days ago, but I don't have another task to replace at that moment. Maybe we should swap E and F and don't allow x[i]^=x[i] in F (then it will be much easier: we can get 2 same bases).

    I tried to made first 2 tasks as easy as possible. (There are 7 tasks, so if you only solve 1 you will kind of feel sad, right.)

    For C and D, I think the difficulty is fine.

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

      What about my trick of using additional 64 (or any other power of 2 that doesn't give away much from the solution) registers? You can simply copy the base to them and get rid of a troublesome chunk of code.

      That is, at least my solution would be much easier :D

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

        Yes, I was thought about add a constraints like n >= 100 (so it will give you 32 registers after Gaussian elimination) , but it will be a bit strange.

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

          That constraint probably wouldn't do the trick I have in mind.

          The point is that when you have the base copied into separate registers and in reduced form (dunno if that's the right term, the one where pivot 1s are unique on their columns), constructing a vector from them (in a separate variable) is extremely easy. So when you have the idea, there's just textbook GEM and that left.

          It does look a bit strange, but it can always be wrapped in a surrealistic story :D and would most likely increase the number of successful solutions.

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

            I don't understand your reply. Since we are dealing with vectors of length <=32, rank of that matrix was <=32 and n>=100 will imply that after reducing whole matrix you will have at least n-rank>=n-32>=68>=32>=rank free registers where you can copy base and do what you have described. In the end you get rid of that copied base. Either you didn't realize what I wrote or I don't understand why that constraint wouldn't do the trick.

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

              Because these vectors will have to be edited eventually, and that'll mean you don't necessarily have a base in reduced form at some point. Think how easy it is to construct a vector from such a base.

              You don't "get rid" of the copied base, you still need to convert its vectors to desired ones (in y).

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

                1) Reduce Xs to base
                2) Reduce Ys to base (and put those operations in the end in reversed order)
                3) Copy base of X to registers with indices n-rank_x+1, ..., n
                4) Erase base of X from registers with indices 1, ..., rank_x
                5) Create Ys base in registers with indices 1, ..., rank_y using that copied base of X
                6) Erase copied base of X

                What is troublesome here? You don't need here any no longer needed vectors from base of X to newly created vectors from base of Y

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

                  Okay, with real separate registers:

                  1. reduce X to base
                  2. copy base to registers
                  3. xor each vector of Y with all necessary vectors of the base

                  You don't actually need a lot of ideas this way — no need to care about x[i]^x[i], no need to put GEM of Y in reverse order, you don't need swaps at all... I don't know if it wouldn't make the problem too easy, because there's almost no difficulty in implementation.

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

                  Hm, okay, that is a difference, but I think that this difference between what I proposed and what I proposed is 5 times smaller than between what I proposed and between actual solution xd.

                  It is true that my way demands doing operations on Y and to that we need idea of reversing which wasn't obvious for me that we can do this, but the most important thing is that we don't need to erase vectors from base X while deriving vectors from Y, what was really painful for me — we can use whole base of X all the time.

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

                  difference between what I proposed and what I proposed

                  Undoubtedly :D

                  Since I expressed the vectors of Y in the base of X, moving from one base to another became just like moving from the canonical base to another. And that's quite trivial.

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

                  OK, so you got base X and want to create base Y. You create first vector from base Y — name it y1. You have to put it somewhere, e.g. in a place of first vector from base X — name it x1. But if you needed x1 to be able to derive other vector from base Y you will have to reuse y1! And that will be OK only in case when y1 included x1 — in opposite case we are already screwed! So we have to care about what we are replacing also. How are you dealing with that problem?

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

                  Imagine it in matrix form: you start with an identity matrix (base X) and want to create a different matrix (base Y expressed in base X) by standard operations "xor i-th row by j-th". The matrix is in (this is the term) reduced row echelon form, because GEM. It should be pretty obvious by now.

                  Also, if x[i]^x[i] is not permitted, then you still need to get to reduced row echelon form with the base of Y, by sorting rows — or state that it's impossible.

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

      I think it would be the best choice to forbid x[i]^=x[i], make it worth 2500 pts instead of 3000 pts and swap E and F. Main ideas will still be included and we won't need anymore pretty ugly piece of code and have much more AC what won't cause such a big jump of difficulty between ABCD and EFG.

      It is true that we will lose not that obvious part also demanding some thinking, but sometimes it is better to give up on significant issue, because task will become less enjoyable and won't gain interest of number of people which it deserve. I learnt that once when I proposed really nice and pretty hard problem for Polish OI, but I included a bit of geometry in it and people were afraid of that even though that geometry part was pretty easy. It ended with 0 ACs, nobody even knew how to solve it, because people were omitting this task. You can see this task here: http://main.edu.pl/en/archive/oi/21/lam (though it doesn't have english version, maybe translators can do the trick).

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

        Depends on the implementation — for me, that "ugly piece of code" is 3 lines when expressing Y in the base of X.

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

          When we will forbid x[i]^=x[i], reduced bases of X and Y will have to be exactly the same. That will make whole problem much easier. I somehow don't believe that it caused a 3lined difference in your code. In my code 8018580, I wouldn't longer need that last long for loop (that starting with "for (int i = 1; i <= st_y — 1; i++) {") which caused me much more trouble than everything else here.

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

            Codes are public, so it's not really a question of believing :D

            8018626, lines (originally 3):

            for(int i =0; i < m; i++) {
	for(int j =0; j < i; j++) if(M[j][i]) 
		ans.push_back(make_pair(B[j],B[i]));
	if(!M[i][i]) ans.push_back(make_pair(B[i],B[i]));}

            If that operation was not permitted, I could've omitted only these 3 lines.

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

              Sorry to say that, but ugh, your solution looks pretty complicated and completely impossible to read, because of incredibly ugly indentation. First for loop after comment "//base" looks really ridiculous, because of places where "}" are put inside it. Is that an effect of some changes in your code while uploading it? I won't believe that it can be your standard coding style.

              If we will forbid x[i] ^= x[i] problem will be like:
              Reduce X
              Reduce Y
              Check if they are exactly the same and if so then print already generated result.

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

                Some parts of it are unnecessary, but that's unrelated to the x[i]^x[i] problem.

                Yes, that's my standard writing style — do you think CF would remove selected indents on upload in my code only? I can't read the style with 1 } on each line and not indented the same way as the loop it completes, so I understand that others can't read mine — but what do I care in a contest?

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

i think worse today will cause unexpected behavior for code-forces rating system. :-D
btw he was in my room.

[http://codeforces.me/contest/472/room/131]

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

Why was the time limit of D so tight? Even n^2logn solutions got TLE.

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

you are very good and smart!good boy,so cute~sorry my enlish is bad,hope you can understand.I don't want tell you I lost my sleep and very boring and don't known what I say,why me is so foolish ..TAT...hhhhhhhhhh,good luck and good night:D

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

Talking about records... (which I mentioned here http://codeforces.me/blog/entry/13997#comment-189548). I thought that I may have just experienced the biggest drop of rating in whole Codeforces history (-132), but it turned out that tourist got such hopeless place — 21st and got -135 to rating :P. In regular Div1 contest, not joint with Div2, it is impossible to fall below -110 even if tourist would get last place :P.

Frankly saying, I prefer regular round than those joint ones.
Additional easy A and B cause that they are worth 500 and 1000 and other tasks are each worth additional 1000 and in that case having standard D (here F) accepted in second hour is worth less than standard B (here D) accepted pretty quickly. That is obviously bad feature.

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

worse only got +319...

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

In problem D, I don't know why the first one is wrong and second one correct.

d[u][v] = d[u][LCA] + d[LCA][v] --> WA

d[u][v] = d[u][root] + d[v][root] - 2 * d[LCA][root] --> AC

Oh lala :'(

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

Anybody help figure out why my submission 8015497 of Problem D is wrong at test 9? Thx.

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

Round Stats

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

    Included it in the announcement.

    btw, congratulations for become master again!

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

      Thanks! :) And, certainly, thanks for the great round and interesting announcement!

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

Because of really good pretests, short (and quite boring) describtion of hacks can be found here.

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

Comment Deleted

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

I had a problem during the contest.My id "techboy" had been shown twice in the list which leads to same id.I solved three problems with 1 WA and 1 AC in A,1 AC in B and 1 AC in C. But it was showing that one id has got 1 WA in A and 1 AC in B while another one got 1 AC in A and 1 AC in C. So in the end i got double negative rating and also was far below in the ranklist than the position I should be in.I need help as soon as possible :(

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

I think cgy4ever in this competition put his name beside the names of all time big competitors... Just like in sample tests for problem C. :)

→ Reply