xyz111's blog

Codeforces Round #254
By xyz111, 10 years ago, In English

Hello everyone! Codeforces Round #254 is coming soon.

In this round, there will be a really cute boy named DZY. He loves many things, we can even say everything. He has a great passion for the gorgeous world, but he can't deal with everything he's interested in. So he needs your help, and he will present rating in return.

My thanks go to Gerald, who gave me much advice and helped about the problems. And I also would like to thank MikeMirzayanov, who created such a wonderful platform.

The problem setters are FancyCoder and me, and thank vfleaking, jqdai0815 and lsmll for testing.

Come and join us in helping DZY.

Good luck and have fun.

UPD

In Div. 1, scores for each problem will be 500-1000-2000-2000-2500.

In Div. 2, scores for each problem will be 500-1000-1500-2000-3000.

UPD

For technical reasons, the round will be delayed by 5 minutes.

UPD

The contest is over. Thanks for participating.

Congrats the winners.

Division 1:

  1. subscriber

  2. flydutchman

  3. uwi

  4. Egor

  5. stevenkplus

Division 2:

  1. lost3030

  2. laekov_

  3. JongMan

  4. Daumilas

  5. nnahas

You can find editorial here

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

Comments Comments (124)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +51 Vote: I do not like it

Finally :D

A contest announcement,after almost 20days.

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

    It will have a record high of registrants! :D

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

    I can't just believe that I had been waiting a month for this contest.

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

I wish DZY to be a MERCIFUL guy ..... Everyone Good Luck and Have FUN :)

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

From my point of view,the problems are all very interesting.Wish you high rating!

PS:DZY's CF handle is dzy493941464.

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

Hmmm chinese contest. Brave yourselves guys!!

Actually all we need is bravery :))

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

Sounds great! I love cute boys (and girls)!

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

    u love both boys and girls !!! don't confused us about your gender ;) :P

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

      well, some people are just too lovely...

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

this is the contest after more half month. FUNNY ! :D

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

the Chinese IOI team 0_0

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

Brace yourselves, DZY loves desert (http://vfleaking.blog.163.com/blog/static/174807634201422485914893/) incoming...

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

You had no decrease in your rating chart!

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

I hope I will get expert in this contest http :D

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

hope the testing system will testing quick after the contest

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

Probably won't be able to participate in the contest cause here in Bangladesh its the time for iftar(time to break fasting in the holy month of Ramadan) :( :( BTW best wishes for other participants....

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

    That doesn't prevent you from participating you can put a lot of dates with water beside you :) and continue eating after the contest.

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

      Taking food is not the problem!! The important thing is magrib prayer. Besides there is Isha prayer as well as tarawih prayer which starts within one and half hour of iftar. After all its ok cause, "To get something u have to lose something". Inshallah will enjoy plenty of contests in later days :) :)

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

How to register this competition?

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

hey DZY please grow up and try to solve your problems by yourself ! :)

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

    but then we will not have a contest, do you want to wait more for a contest after waiting two weeks? :P

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

please how i can register to the contest i'm new here

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

    Registration will be open in 3 hours. It always starts 24 hours before the start of the contest.

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

      it's now 24 hours before the start of contest, but the Contests page says that registration for the round will open in 9 more hours only.

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

Please don't use such silly names; they confuse us.

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

Why are we having so few rounds these days? Even TopCoder has only 2 SRMS planned this month :/

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

    Because the Chinese students in preparation for the final exam.//hahaha~

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

sad its timing clashes with the timing of wimbeldon finals

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

    i hope Federer wins! :)
    also, i hope that the Wimbledon final takes more than 2 hrs to finish, then we can watch it after contest is over :)

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

      same here

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

        because of round extension by 5 minutes, maybe we can even watch the first game! ;)

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

      good news. only two sets are over, and both players have won one each.
      so we still have a long way to go! :)

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

        yeah ...and hope federer wins this one

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

hey DZY take it easy !

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

WARNING: Mathy round approaching!

"DZY loves math xxx"

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

    DZY loves many things, we can even say everything.

    so he also loves DP, probability, graphs, geometry, data structures (and many more concepts) in addition to just math. ;)

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

      It seems that my prediction was wrong :p

      However, round #255 was indeed a very mathy round :D

      PS: authors of round #255 is the same as "DZY loves math" series in BZOJ(a Chinese online judge contains only very tough problems)

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

I don't have my library currently and my last contest was more than 2 months ago. My question is can I do it as a virtual contest during the same time as the official contest?

PS: For all coders who don't have an online backup for their library, do it ASAP. My laptop's HDD crashed recently and I don't even know yet if the data can be recovered.

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

    I don't think that I notice virtual contest button appear after final system test.

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

And, what about the unusual contest time??

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

From the "Urban Dictionary":

DZY

1)Complementary definition of a person, place, or thing..that epitomizes the elements of sheik, classy, cool,or just downright unique.

2) An intensifier

3) Kastration technique (????)

4) Generally used to describe a very cool person

5) Nondescript term that can be used to define anything that is awesome, over the top, and dope.

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

    4) Generally used to describe a very cool person

    Now i understand ..

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

There was a few consecutive contests without delay but I think it's back! Good Luck

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

Extended by 5 minutes.!

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

Pretty tough competition, but great fun!

I liked B a lot, though using the randomness of the simple generator felt a bit risky.

Was problem A greedy somehow?

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

    Yes; choose the edge that gives the maximum density. (The induced subgraph will have two vertices.)

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

      Oh...

      Because if we have already picked some nodes vs and edges es, and we want to add node u with e being the sum of edges from vs to u, then we must have (vs+c)/(es+e) > vs/es, but that implies c/e > (vs+c)/(es+e) so clearly just picking c and any node from vs would be a better choice.

      Thanks :D

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

        Exactly. I went on and proved that first before submitting my solution to ensure correctness. :P

        Of course, you have to pick the node in vs that is connected to c, but that's why you inspect each edge (instead of any pair of vertices) to ensure the connectivity.

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

    for A, we always had to choose two nodes and one edge. adding more edges will make the density lower.

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

Please can anyone tell me how to do Div2 C ?

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

how to solve Div-1 B?
also, why my code 7029179 gives WA#9?

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

Problem E uses Inteval Tree (Segment Tree) ?

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

Oh God, a stupid mistake, in problems B div 1 I use ios::sync_with_stdio(false) but then I use print("%d"). May my code will fail system test because that mistake ?

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

Contest is difficulty with me !

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

How solved problem B ?

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

    Put chemicals in order of DFS then caculate danger. I learnt to code DFS when contest is running LOL.

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

Fast system :D

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

Good Contest ... Thanks Authors ...

Segment Tree range updates in problem E/Div2 C/Div1 was very similar to UVA12436


if(l<=x<=r)
   You need to find where updates is zero  ... Then you have one A query and one B query
else
   You have one query like UVA-12436 A or B and one value update on segment-tree

UPD : ok ok ... DownVoters i got ... in case colors was fixed this kind of solution would be correct , but in this problem, it wont work ... I hope some days we only DownVote to rude speeches, NOT WRONG IDEAs

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

Very quickly system testing :D

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

very fast system testing! :)

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

I liked the round a lot. C was super nice , I solved it on paper with sets and an segment tree. ( but I'm not sure it's ok ) I got WA on B for something that I thought it works in O(N log N) , but got TLE. Overall , very nice round even though I think I'm going to be div2 after it. :)) Congrats for the authors !

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

Definitely, fastest system test!

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

Following my previous blog post on ranking submissions as a collaborative wisdom for picking good reference solutions, i.e. http://mirror.codeforces.com/blog/entry/12917, you can now vote your favourite submissions for this contest at:

Div1: http://hiukim.com/cfsubmissions/contest.php?contestId=444

Div2: http://hiukim.com/cfsubmissions/contest.php?contestId=445

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

Damn it. One character and I'm the first:

- if (sz(it1->second) < sz(it2->second)) swap(...)
+ if (sz(it1->second) > sz(it2->second)) swap(...)

What's even more painful is that I wrote right at first, then changed it for testing purposes and then forget to change it back.

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

This bug has costed me 100 points.I have clicked once submit.

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

I wrote lots of code for C(div 2). Than I recognized we just need two nodes and an edge. :(

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

My code got wrong answer on pretest 5 div2 A. I see the test case but I think my output is also correct. Can someone check it for me please? http://mirror.codeforces.com/contest/445/submission/7032620

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

    On the second line of your output, you have two B's next to each other.

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

      Oh I see. Thanks

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

        Next time you should take a look at checker comment before asking such questions

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

          I did but I was such in a hurry to find the wrong one and angry because of not being accepted, so I didn't see it. You're right. Thanks for your advice

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

    the fourth last line, the last two characters are the same.

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

    "wrong answer Two same chessmen stand in adjacent cells 2, 27 and 2,28" . Check those places, BB occurring there.

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

will there be any solutions posted?

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

    Editorial will be posted very soon. BTW,the contestants' solution for Div1 E was unexpected to us...Our solution was far more slower,that's why n is only 3000

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

Anyone who tried to exploit the random generator in 1B? Many solutions (including mine) depends on randomness. Problem statement blocked the unique fixed point, but there might be some small cycle which can hack these kinds of solutions.

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

    Our intended solution do depend on randomness,so we blocked that number.

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

    Oops, I forgot people might try to hack that. I was relying on the problem setters being nice :-)

    If there is a 1-cycle, probably there are also cycles of most other lengths?

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

      No, there are one 1000000006-cycle and one 1-cycle.

      Seems like authors considered such hack :-

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

        Any proof for that?

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

          1e9+7 mean nothing, brute it.

          I don't know if % (i + 1) could help create some "cool" sequence, likely not.

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

    You can get the explicit formula of this sequence, and you will find 37 is the primitive root of 10^9+7, so the cycle's length is 10^9+6.

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

How to get on the main page after the contest without actually participating. =)

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

I have used 4 Segment tree to get AC problem C (after the contest). Does anyone have better solution? Thank you.

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

waiting for editorials...

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

How to solve div2D? FFT?

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

A Div2 was harder than a usual A Div2

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

English Editorial has been posted!

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

interesting problem set, I wrote complicated solutions for C and E, and got very simple solutions after reading subscriber's code, cool!

3 bytes far from all clear orz.

- s+=(r-l+1)*abs(x-vq.back());
+ s+=(r-l+1LL)*abs(x-vq.back());

- int l=1,r=10000;
+ int l=0,r=10000;
→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Very nice round. I liked the problems even though i only managed to solve 1. Div. 1 A proved to be a nice revelation. I got the idea by thinking back to when i used to play online shooters when I wanted to maximize my kdr (Kill-Death Ratio). Say my current kdr was K/D and in a match i'd manage to get k kills and d deaths. Now if k/d > K/D then (K+k)/(D+d) > K/D and my kdr would grow or it would fall otherwise. The same thing applies to the problem at hand.

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

The TIme limit for problem C should have been 3s. My algo was correct (used sqrt-decomposition) but I had to reduce the size of each partition by a constant amount to get it accepted.

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

    What's the problem then? It's absolutely OK that some implementation details matter a lot, imho.

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

You can see the country wise standings for the contest here. In case you want to report bugs / suggest features, kindly use this blog.

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

Round Stats

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

Div1-B can be solved without regard to randomness in time. See 7031500

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

    I'm curious why do you use integers in your BitSet? For example my implementation with longs 7040099 works like 1.5 times faster than same with ints 7040106.

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

    It seems to me that and O(n2) are same, therefore there is no reason to write 32 in the denominator.

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

      Formally, they are, but in this case, the /32 factor is used to denote that the constant factor will be that much smaller.

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

      Still my notation leads to a little bit better understanding of actual solution timing, isn't it?

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

How to solve div1 C using segment tree ?

→ Reply