hogloid's blog

Codeforces Round #263
By hogloid, 10 years ago, In English

Hello everyone!

snuke, EnumerativeCombinatorics and me would like to invite you to Codeforces Round #263 for both divisions. It will be held on Tuesday, August 26th at 18:00 MSK. Note that this round starts on different time from normal rounds.

Great thanks to Gerald for helping us prepare the round, MikeMirzayanov for creating a fine platform, and Delinur for translating the statements.

You'll help men named Appleman and Toastman in this round. Good luck and have fun!

UPD. In Div.1 and Div.2, scores will be standard, that is , 500-1000-1500-2000-2500 for each problem.

Now the contest is over! Thank you for participating!

Here are the winners:

Div1.

  1. YuukaKazami

  2. sankear

  3. dreamoon_love_AA

  4. Egor

  5. Memset137

Div2.

  1. yyt16384

  2. SuzuKuma2112

  3. pawky

  4. AlexandruValeanu

  5. mosiomohsen

Congratulations on YuukaKazami, who solved all the problems !

Editorial is here

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

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

Today is Saturday, the 23rd.

Contest is on Sunday, the 26th.

OK.

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

    Oh, I missed fixing. Thanks.

    And I was surprised by how fast you found this post :)

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

      :)

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

      Seriously, What kind of contest was that?!
      Top 20 of Div2, had totally hacked 118 solutions. And so on for other contestants :|

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

    Good Job ! It's time to fight in div1 .hope to up rating ^_^

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

A Div1 + Div2 round :)) It 's time for the "newly registered army" to take off their mask ^^

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

Www,long time no see div.1

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

I think problems will be very hard and logical.

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

    Thanks for your opinion, it means so much to me!

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

      i hate to see this comment getting too much down votes!

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

        Okay, let me translate how I understood it: "STFU NOBODY CARES ABOUT THAT!". Would you not downvote it?

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

          what a coincidence!! i understood it as "STFU NOBODY CARES ABOUT THAT!" too! we have a lot of common man! you might up-voted it as i did it so.

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

Finally a round by animals (cat, wolf and squirrel, right?) from Japan!

Oh, god, the start time is 7:00 am in LA, it will be a tough round for me. :)

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

Why there's still no upcoming contest now???

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

Wow, blog is earlier than upcoming contest list.

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

Wow. So early blog post

And I like the contest time which is a bit early than usual :D don't have to stay up to midnight :D

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

At least, names of heroes are easy to pronounce this time :D

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

    Compared to other characters, they have a bit longer names, though ;)

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

OMG ..

In korea the time is 23:00.. and I'll be home at 12:30...

I can't participate this round :<

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

at last a DIV1 round after 2 contests :)

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

My first div1 round ever.. so.. lets hope for math!

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

Appleman looks much better than official Apple logo. :)

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

Let's not hope for math, and for dp and graph theory [by the way kudos to SRM 630 writers].

Also, I knew that this will be a lucky contest for me right after I saw the apple. Apples are graphs >:D.

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

    Let's also hope for clear problem statements! Sometimes I become confused reading them for the first time!

    +long editorial :)

    Good Luck.

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

      Let's also hope short problem statement , short solutions :)

      also Good Luck.

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

good time for contest :) hooooray !

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

Waiting for a great contest! Hope the problem easy to understand.

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

Continuous rating down......

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

If we fail pretests 2 times is the penalty = -(50*2) or (-50) ? Same question for failed hacks .

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

    -50 for every failed pretest (not counting failed on pretest 1), but only if you eventually solve the problem. -50 for every failed hack. So that means two failed pretests are -100 and so as two failed hacks.

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

      How much penalty for failing pretest 1 two times ?

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

        Failing pretest 1 doesn't give any penalty (because the reason might be selecting the wrong file, among other things, that is just a minor error). So failing pretest 1 twice doesn't take any points either.

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

          "selecting the wrong file". Happens with me most of the time.:/

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

IGNORED

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

    look on the bright side — then u will be able to compete in Div-2 only contests. :)

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

    All the best!. :D

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

Wow, long time no see Div1!Come on, let's enjoy it~ ^+^

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

    Solo!

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

      Come on!Who pa who!

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

        Can I join in you, if you guys don't mind?

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

          Wahaha,come on!Together if solve 0 problems then eat keyboard(or xiang?)!

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

The contest is a little early in the day than usual. Its coinciding with my mess timings for dinner! :(

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

    as a BITSian who has participated in contests at such time, let me tell u this.

    we both know that the mess food sucks. so

    • go to mess around 7, take some extras, and come back to your room.
    • do the contest, while eating/drinking the above stuff.
    • then go to ANC (very close to ur SK bhawan, AFAIK) and eat to ur heart's content. :D
    • hopefully system testing will be over by the time u return.
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      That is quite prudent. I agree.

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

      Well I think I will most probably compete then ! :) No more excuses for not participating !

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

give yuo a plus please — http://codeforces.me/blog/entry/13439 !!!

P. S. not minus me !!!

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

Oh , I missed to be Candidate master with (4) rating last contest. I hope to raise to Div1 tomorrow :)

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

"May the Odds be in your favor!" :D

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

Hope for good problem, long time no see div.1. Good luck and have fun for everyone.

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

    I hope you will not use fake account this contest

    kuangbin kuangbin1 kuangbin2 kuangbin3 kuangbin4 kuangbin5 kuangbin6 kuangbin7 kuangbin8 kuangbin9 kuangbin10

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

      we should register only one account. :)

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

      kuangbin11 and kuangbin12 also!
      probably they will become Candidate Master in the next two Div-2 only contests.

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

        Bad new for kuangbin

        kuangbin13 isn't emtpy anymore

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

          Bad news for you, if you are the one who took the handle, they may ban you :)

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

            Good news for me

            He isnt me :D

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

              HAHA, these are not my handle~~~

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

      I've seen those accounts being posted around a few times already and it's clearly against the rules to make more than one account and compete, so can someone tell me why the hell isn't he banned?

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

        we can't agree more !

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

          Well it just quite angers me. I see blogs and comments non-stop complaining "there are so many fakes in Div2, why would they do this" and then when you see someone with 10 accounts, all of them with participations only until they reach Div1, which is obviously cheating, no one really cares. I thought people wanted to reduce fakes? I mean, as JuanMata showed, he has 2 more waiting for a Div2 round, doesn't seem like he will stop doing it.

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

            ofcourse we want to reduce fakes!

            but i don't agree with no one really cares — i mean, surely one of the reasons why muratt posted these two comments was so that admins could see them and ban those accounts.

            as to why these accounts don't get banned — probably the admins want to prove without doubt that they are fakes before taking any action, lest they ban an innocent newly registered user (who will have no idea wtf just happened, and start disliking CF for wrong reasons)!

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

              I get that you post this so the admins can see it, but my point was that this is not the first time someone posts names of obvious cheaters. Thing that frustrates me is that sometimes I see posts from months ago where someone reported a cheater, and when I check the cheater's account, it is perfectly unharmed!

              Now I get the "prove without doubt" part, and I don't try to sound arrogant in some way since I'm not familiar with the things admins can do, but couldn't they simply check the IPs of the users? Surely that would still leave room for cheating as you can hide it or change it, but most of them will most likely use the same IP. Obviously if your cheating accounts have just another digit added to the end of their name, I doubt you'd go as far as hiding your IP.

              I guess you could argue further that same IP is still not reliable (a brother, a friend from your computer) but in some cases such as the above one it's just kinda obvious that cheating is going on.

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

            We care

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

      Stierlitz still was never so close to a failure...

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

      It is outraging to see this in Div. 1. Previously I thought such detestable things only occurred in Div. 2.

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

      kuangbin have really ability.He always have good rank in my contry's match！this is a evidence(recent match)：http://www.bnuoj.com/v3/contest_show.php?cid=4340#standing maybe you misunderstand him! I have studied much knowledge from his blog. so I am very like him!

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

long time no taking div2:) Ok, let me do it tonight!

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

What do you guys do before contest?

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

I have a question: Can I participate in div 2 contest? or just Div 1?

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

    If your rating is >=1700 you can not participate in Div2 contests when a div1 contest is scheduled at the same time.

    However if there is a solo div2 contest and the organizers allow , then you can participate in it, but that would be unrated for you.

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

    If you can do all problems in both, why not.

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

Wow! Amount of div1 participants is very close to amount of div2 participants. :D Amazing)

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

    1329 registrants for Div1 and 3988 for Div2.
    Yes you are right, very close :|

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

      yep last digit of two numbers 8 & 9 is very close :D

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

    How sir?

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

    When I wrote that comment, they were very close. Why --------?? You can't understand it without my hint? (Sorry for bad English :D)

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

      Nope. You wrote that comment 15 minutes before the contest started. Are you implying 2500 users registered in 10 minutes? Because I won't believe that.

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

Toastman is him.

He appears in this problem.

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

hello ~ why my B problem hack failed...

my generate program is 

print 100000,100000
a = []
for i in xrange(100000):
    a.append('A')
print "".join(a)

thx~

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

    consider endlines

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

    I think it's not good to publish a generator to B, which would break 50% of submissions, before the contest ends...

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

The worst feeling in the world — when you lock your solution to problem B for in D2 and realize minutes after that you are not going to pass the system test cases...

At least I got some points back by hacking people in the rooms. How lucky some people are! With 15 hacks on the same problem, while I only got 7...

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

I made some stupid mistake at A and B, and it results in -100p for A and -50p for B =='

Problem D & E are hard for div2 ==' btw problem B is a nice problem for hacking...

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

Awful problem statements (were they in english !?) .

It doesn't matter how good your problems are if they are not readable .

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

    it is pretty obvious when three geek red coders prepare some round. they don't speak english/japaneese/chineese or russian. they only speak c++ :p

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

      English is pretty much of a prerequisite for coding, as most of textbooks available are in English language and not in Russian! And since they are geeks, which more or less means that they have read A LOT and know A LOT, they should now English to a sufficient level (maybe ECPE is too much, but ...)!

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

        its not about knowing English sir, its about using right word at right place. its about explaining something, making something understandable to me. Except B all the problems were well written , i think. though it would be fine if the explanation of problem E would express test case one completely instead of just updates. but I think it was fair enough...

        My suggestion would be to evolve at least one purple coder to test div2 problems.

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

    totally agree.I submitted so late problems A and B because they were not clear. Wasted much time in understanding the problem statement.

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

Доминируй, властвуй, унижай!

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

:'( nah, hard problems, but I still love it :)), I love the way I can't solve this :'(

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

Hacking is really fun :D

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

Wow!

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

No simple for problem D,E Div2

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

Contest's ended. How to solve 462D - Appleman and Tree?

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

    DP on states "there's 1 black vertex in subtreee of v left" and "there's 0 black vertices in subtree of v left"

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

      Would you care to elaborate. If your solution is correct, please explain it.

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

        I'm kind of lazy here, so:

        • if you want to think about how to solve the problem, this should be enough of a hint

        • if you don't, just wait for the editorial

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

    Dynamic on tree, save two value — how many ways to get black from component with root in current vertex and how many to get white from it. Then answer will d[0].black.

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

I've never seen so many hacks..that's amazing.

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

A lot of participants in room 58 were inactive, would have been even more interesting had more people taken the contest :P

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

Nice problems... :)
And nice round for Hack Lovers... :D

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

The hack swarm had to happen :-P

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

No hacks this round. :)) Liked it though. I'm curious about A's proof, liked B and nearly finished C. Keep it up.

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

hack with OVERFLOW :)

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

C(div1) is a joke :D. Didn't have enough time to code it unfortunately. Great contest anyway.

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

I was at the blessing room. 19 successful hacks :D

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

Please make the difficulty distribution of questions more uniform. for example 1-3 were submitted by about 1500 coders and count dropped to about 100 in 4th question.

BTW enjoyed the contest. Waiting for editorial

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

Is this the correct solution for Div 2 C? http://ideone.com/AhciAN

Edit: It's not.

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

In Div,1 contest, half of submissions are for problem A. It seems that no one fail system tests on A. I think it's a quite simple problem, therefore, the number of participants today is much more than other contests.

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

982 official users in div 1
Awesome!!

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

I don't think i've ever loved integer overflow so much :D

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

Am I right saying that in Div1D 4x4 corner determines all other cells, because rows and columns have to be periodical with period 4?

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

    No, it's not true.

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

      Thanks, I realized my mistake while ago. I had to mess something during the contest.

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

    Very simple example:

    ....o...
...o.o..
..o.o.o.
.o.o.o.o
o.o.o.o.
.o.o.o..
..o.o...
...o....

    What you can do is fix the first row and then there is exactly one way to fill the rest (it's obvious that there is not more than one, and you just believe that it's always possible after looking at small cases with brute force)

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

    In fact, the first row determines all other cells. Moreover (I didn't prove that, but the brute-force showed that), it seems that each combination of white and black cells in the first row generates a correct board.

    // Oops, too late answer :D

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

      What do you mean by "each combination"? It has to be consistent with already filled cells.

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

        So you can guess that he means "for an empty board".

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

        Okay, I forgot to add that if there are no cells which are already set, then we can color the first row in any way we want and generate exactly one correct solution from it (as yeputons said).

        This observation (as long as the very similar one: if we set 'O'=1, 'X'=0, then the value (mod 2) of each cell can be computed very easily from the values of the first row). Look at the example:

        a0          a1          a2          a3          a4          a5          a6
a1          a0+a2       a1+a3       a2+a4       a3+a5       a4+a6       a5
a2          a1+a3       a0+a2+a4    a1+a3+a5    a2+a4+a6    a3+a5       a4
a3          a2+a4       a1+a3+a5    a0+a2+a4+a6 a1+a3+a5    a2+a4       a3
a4          a3+a5       a2+a4+a6    a1+a3+a5    a0+a2+a4    a1+a3       a2
a5          a4+a6       a3+a5       a2+a4       a1+a3       a0+a2       a1
a6          a5          a4          a3          a2          a1          a0

        (the addition is mod 2, i.e. the same as xor). If we count the prefix sums of the same parity (that is: 0, a0, a0+a2, a0+a2+a4, a0+a2+a4+a6, ... and 0, a1, a1+a3, a1+a3+a5, ...), we are able to write all the constraints in the form [one prefix sum] xor [another prefix sum] = (c=='o'). Number of such solution (and existence of them) can be computed/checked easily. Somehow I got WA, so maybe I'm not that right... :D

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

      Yes. We take x = 0 and o = 1. If we put ui = A[1][i], then we can write explicit formulas for A[i][j] int terms of ui. Each formula is like u2s + u2s + 2 + ... + u2t or u2s + 1 + ... + u2t + 1. So we have system of equations in F2n. We can find the number K of independet equations using Find-Union, Polish guys knows that trick from KUGLARZ (potyczki 2014).
      The answer is 2K or 0...

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

        Lool, that is indeed a Kuglarz problem :D. Nice. So bad that I messed computations and came up with other formulas, Kuglarz was so nice it would be really fun to use that task in other problem. Btw, hi Maciek :).

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

        Sorry, doubled post, CF was not responding xd.

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

Div1 — A was easy than usual and and Div1 — B was hard than usual.

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

    Why i got WA 19 div2A ? code

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

      You need to check the boundary conditions of the 2-d array. For example

      if(x[i-1][j]=='o') should be changed to

      if(i>1&&x[i-1][j]=='o').

      Similarly for all boundaries.

      Hope this helps.

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

Congratulations : — Div 1 : YuukaKazami — Div 2 : yyt16384

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

Compare Div 2 A with Div 1 D and Div 2 B with Div 1 E

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

IGNORED

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

I still see unrated genius users in Top 10 Div2...

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

I misunderstood problem C's description... This point specifically: Each time Appleman gets a group consisting of a single number, he throws this group out.

What I understood was that if the group consisted of equal numbers, then he throws that group but it turns out this meant that a group is thrown away if group consists of a single number(Just as the sentence said...). Never thought of it that way until one of my friends explained.

Just wanted to mention it so that if someone did the same, he wouldn't be puzzled too much.

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

    For the next time , look at the explanation of the test cases to avoid such mistakes :D

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

      I did indeed but the explanation was working well with my assumption :D

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

how could so many people hack problem B(div.2) solutions? mine is also hacked as well, but i can't find my mistake. can anybody please tell me why this could happen? thanks :)

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

    Integer Overflow :D

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

    overflow occurred when you calculate bonus*bonus :(

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

      ah as i expected, but the answer must be integer right? as the problem says : "print a single integer"

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

        I don't think "integer" in the problem does not mean int type

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

          i see, i will take that as a lesson for future contests :) thanks for helping me..

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

    In your code variable bonus should be long long.

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

    you have taken bonus in int and that will overflow.Imagine test case like 100000 100000 DDDDDD.....(100000) times so 100000*100000 would overflow int range

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

How long does it usually take, after the contest, to recalculate the rating of each participant? This is my first time competing on Codeforces. I was on a train for the first half of the competition, and didn't realize that the points for each problem decrease over time :\

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

    Depends. Sometimes a few minutes, sometimes a few hours.

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

I was just about to use Splay in problem C when I found interval flip operations are not really needed. ...

Anyway, the problems are nice.

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

yeputons, can you please explain how you solved 462D - Appleman and Tree?

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

    Codeforces do not send any kind of notification for mentions in comments at all.

    Algorithm: we have system of linear equations modulo 2 (each variable is one cell of the field), there are n2 equations from the statement, and k equations from the input.

    Improvements and some ideas:

    1. If we fix the first row, we can deduce the rest. There fore, only n variables and only n equations from the statement (for the last row).
    2. In turns out that if we fix the first row, there will be no problems with the last one. I checked this for small n and believed.
    3. Now we have n variables and k conditions. Each conditions can have up to variables — it's still too much to just store it.
    4. Next notice: each cell is XOR of some continuous segment of cells with fixed parity from the first row. More details are available here.
    5. Now we can easily calculate all the k equations in form 'xor of variables from L to R is V'.
    6. If we run Gaussian elimination now, it's still very slow. However, if we sort equations by (L,R) lexicographically, it's easy to see that on each step of elimination all equations are still in the form 'xor of variables from L to R...', which is cool, because we don't have any problems with memory
    7. Next thing is to make elimination without actually editing each of the segments. I use the 'merge smaller to the larger and it'll be NlogN' trick here.
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      You have answered Div1D, however dude above had asked you about Div2D which is Div1B :)

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

        Whoops. I'm sorry, didn't notice that, I saw 'D' and answered :)

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

      I am sorry, but I do not really get yours "I use the 'merge smaller to the larger and it'll be NlogN' trick here." Could you kindly clarify it? p.s. I spent come time looking into your code, but for me it looks like O(N2) :(

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

        I think the thing that confuses you in my submission (7594572) is MagicSet. This structure is a set of some items with one addition: I can append one set to another. Obviously, I can add set A to set B in by just inserting all elements of A to B. Here is the magic:

        if (sz(this->data) > sz(b.data)) this->swap(b);

        If I do the job in instead of just and I move elements instead of copying (i.e. each element can be in one set only at every moment — like in Disjoint Set Union), the whole thing works in (amortized). Analysis is very simple and similar to what is used for DSU: let's take a look at each element. When it's moved from one set to another, the 'holder' set's size is increased twice at the least. There cannot be more than of such operations for each element, therefore we have operations with sets and the whole thing takes time. I'd also like to notice that one of these logs is from amortized analysis and has very little impact on constant factor, i.e. this is rather fast.

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

          Thanks for clarification! I like your solution even more because it is clear you invented it by your own.

          btw, your trick works thanks to C++0x and its moving semantic, right? I mean this line: if (sz(this->data) > sz(b.data)) this->swap(b);

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

            it is clear you invented it by your own.

            Well, it's pretty well-known trick. In the several past years I met it dozen times, starting with summer school training camp 2011 and IOI-2011 (problem 'race') which followed it. I've also met this on some Codeforces rounds for sure, on Petrozavodsk training camp...

            btw, your trick works thanks to C++0x and its moving semantic, right?

            No, move semantics is not used here. You know the swap function from STL (like swap(a, b)), and almost every STL structure has member function with the same name: a.swap(b), which does the same in constant time (for example, to swap two vectors you just need to swap two pairs of pointers, no need to copy the content). It was in C++03 for sure. Moreover, std::swap is overloaded for some STL structures to work without copying everything too. I personally prefer using a.swap(b) in places where I definitely need constant time complexity, because I don't remember exactly whether or not std::swap is overloaded.

            If you look in my code, you can see that I implemented this swap member function myself (using set<>::swap inside)

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

              Well, it's pretty well-known trick. In the several past years I met it dozen times, starting with summer school training camp 2011 and IOI-2011 (problem 'race') which followed it. I've also met this on some Codeforces rounds for sure, on Petrozavodsk training camp...

              Could you kindly tell me a couple problems to solve? I think to really understand problem one has to solve a couple of similar ones.

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

    Wrong problem, I'm sorry.

    Well, it's very straightforward for me: if you have tree (especially rooted one) and have to select some subset of vertices/edges and minimize/maximize some function of the resulting partition, you're gonna have a tree DP.

    Usually tree DP in partition problems looks like this: you've already partioned some sub-tree and are currently constructing a component to which a root of the subtree belongs. In this particular problem the only required property of a component is whether or not it contains one black vertex. It's the state of DP. Transition is another simple DP (please don't be scared by that): you start with one obvious way (depending on subtree's root's color) and then add children one-by-one. There are several possible ways of merging a child: it either has or not black vertex already, and you and also just cut an edge leading to the child.

    You can look at my code (7583221) for details — dfs() is doing the DP. I don't store results of DP anywhere — it's just passed as return value of dfs().

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

      can you please explain how we can calculate the merging of childs , I mean if color of x is one , then we must cut all the edges to children right?cause If we add the edge then there will be an component with two black vertices. But , what are the calculations if x is white?

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

      Learned a lot from your comment, thank you ! It would be great if you can provide some related problems which uses this method. (links to OJ problems would be appreciated)

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

IGNORED

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

Nice problem! D&E is really interesting to solve :).

I am so lucky to get E right at 1:58:) ...

Also It is my 7-th CF win!(For my darling sevenkplus :) )... Many years passed since I join CF, and the pleasure I get from it never decreased :).

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

    Congratulations! <3

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

    Congratulations! Wish to enjoy yourself with 7k+~!

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

    Congratulations. Wonderful problems! Especially problem E. Although I have failed to discover the most important part :(

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

    Professional!(which is a typical way of congratulating others or just greeting in Japanese geeks. In reply to this, one usually answers "Hobby")

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

how to know what was the test case used by another person to hack my solution in the contest?

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

http://codeforces.me/blog/entry/13563 Please upvote if u agree :)

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

When will div 2 rating be updated ? Div 1 rating is already updated.

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

aah today I forgot to hack :)

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

Finally DIV1 ,Now I can RIP :D

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

    What do you want to rip so much that you'd write it in caps? :D

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

      RIP stands for "Rest In Peace" , I didn't want to rip anything Xellos :D :D

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

        I hoped the :D at the end would make it clear that I know and it's a joke. Oh well.

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

          yep I know you are joking and the same :D :D at the end of my sentence make it clear that I know you are joking and I make another joke replying to your joke :D

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

    Me too =P

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

    after 111 contests, u have finally become Div-1.
    maybe this means that ur lucky number is 1. :)

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

      Yep you are right 1 is my lucky number also I have contribution 111 on my 111 contest :D :D

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

    congratulation! :D

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

    I try to say congratulations to you, from rating update, but there is a message issue :(

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

Please can anyone give the proof for why the solution for div1 A / div2 C works ?

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

    You can prove by induction.

    Let's consider that for all arrays with sizes n' < n it is true that the next algorithm Alg is optimal:

    1) Sort an array.

    2) Divide an array from left to right, taking at each step first element.

    Suppose we have an array a and it's size n. res = Alg(a). Let's sort it and divide by any index q. By induction we know that it's optimal to use Alg for these subarrays. But it's easy to see that the result sum  ≤ res.

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

Why did I get WA even when I used long long for sum?? http://codeforces.me/contest/462/submission/7590781

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

How is Div2 E supposed to be solved?

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

What is the purpose of custom invocation ?

How can we lock our solution ? What is its advantage?

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

    Custom invocation: in case you're too lazy to actually get a compiler/interpreter of your language of choice and want to test out codes with Codeforces platform.

    Locking solution: You can now hack other solutions for possible points if you're correct.

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

This is my submission for : Div 2 C

It passed tests for similar sized inputs but failed on the 24th test case. I've used Python 2.7 to submit that. Isn't it unfair that I have been penalized just for using Python? My algorithm uses a priority queue and is O(nlogn)

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

    Here is exactly the same algorithm used in Java 8. Submission in Java 8

    I have used the SAME algorithm and it comfortably passed the tests.

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

      Yes, when you see large input, don't rely on Python. You can blame the problem setters for having no better problem to put where every language can pass, or you can try learning a faster language. I decided to pass on this contest for the same reason.

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

        Well there should be some sort of additional time for Python to process large inputs then. I lost out on a lot of points because of that. I think the organizers of the contest should look into it. Nevertheless, I think I will use Java from the next round. It's quite frustrating to lose out on points just because of a language choice!

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

          I think there was a discussion about giving time limit multiplier (so Java has double time, Python has triple time, etc) long time ago, but it hasn't been pursued ever since.

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

            That's sad! I will Java from now on.

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

              You should C++ from now on.

              I had a similar situation recently, but outside a contest. I had a simple integral and binsearching on it, written in Python. But it wasn't accurate enough (I needed to take differences of close values), so I needed to improve the precision by increasing the number of steps. But Python's slow and it would've ran for hours — so I didn't complain that the time limits are slow and instead rewrote the solution in C++, resulting in massive increase in precision (from "powerful random numbers' generator" to "sufficiently accurate") and decent time.

              Programming is about improving runtime, not increasing time limits to fit your code.

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

                Thanks for the advice!

                Is Java also too slow for programming contests on Codeforces and other platforms? I already use Java well so learning C++ will require some additional effort. If it doesn't matter that much then I would rather use Java.

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

                  edit: yet again, doublepost

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

                  It probably is, I don't really know since I don't use it, I just heard what people said here. If you can use it well, then it's okay, but it still seems to have more speed-related fails compared to C++.

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

              edit: quadruplepost due to CF not responding

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

              edit: quadruplepost due to CF not responding

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

              edit: quadruplepost due to CF not responding

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

:-) Hello

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

Some stats about hacks can be found here.

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

why my summission is skipped? Your text to link here...

→ Reply