gridnevvvit's blog

Codeforces Round #284
By gridnevvvit, 9 years ago, translation, In English

Soon you are lucky to participate in Codeforces Round #284, and problems have been prepared by Vitaly Gridnev (gridnevvvit), Ilya Los (IlyaLos), Danil Sagunov (danilka.pro).

We want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring system will be dynamic. Problems will be arranged in ascending expected difficulty order.

Round finished, congratulations to winners!

Div1:

  1. yeputons
  2. rng_58
  3. Endagorion
  4. KADR
  5. Egor
  6. uwi
  7. mmaxio
  8. atetubou
  9. RAVEman

Div2:

  1. sorry_dreamoon
  2. dreamoon_love_AA
  3. dreamoon_fan

Editorial

Good luck!

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

Comments Comments (221)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

Just why on Christmas Eve?

Check out: http://polishchristmasguide.com

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

    Definitely to make you miss the round!

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

    Good luck to everyone :)

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

      Pleas accept my apology, But is the women in the picture you or someone else?

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

        Yes. Why such strange questions ?

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

          Well you see, I really didn't thought that there is/are pretty women(s) who like coding and codeforces and your actually the first one I see.

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

          sooooorrrry is not the girl she claims to be in the picture. See this: http://goo.gl/5h1gYJ — sad, everyone was so excited.

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

            - ... you or someone else?
            - Yes.

            Why do you think that she claims to be on the picture? Don't you know about "or" operator?

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

      [Fake beautiful profile picture] = UPVOTE! :)

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

        Excuse you ?

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

          Come on people, Same comment +3 !! :|

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

            Why are you still commenting and going down in contribution? :3

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

              Because, still he has +16 contribution and the girl stolen his heart! :)

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

I will just leave this here: http://codeforces.com/blog/entry/10034#comment-155087

Exactly the same situation as year before or even worse, because year ago time was not that bad, but 19:30 (17:30 in Poland) it's definitely too late. I think you shouldn't expect many Polish coders tomorrow missing one in a year feast and ignoring whole family which gathered in their home.

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

    This. I registered thinking that I have no idea whether I'll find the time to participate...

    although it's a chance for a very good (absolute) place... so much win.

    Also, working name of this contest: basement dweller check.

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

      Don't you think that in all countries except Western Europe and US/Canada nobody cares about celebrating Christmas because New Year is our national holiday? We will not miss you today, take it easy.

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

        New Year is only the main holiday in Russia (and countries with similar traditions), because Julian and Gregorian calendar. It kind of explains why there's a contest on this date, but the argument still stands for most of the world, Central Europe included.

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

        Dude watch yourself when leaving a comment in a site full of Russian.

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

    I also find completely unacceptable that so many contests on Codeforces take place on Fridays after the sunset or on Saturdays before the sunset.

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

I celebrate my birthday today. And I hope, this round will be a gift from CodeForces for me!

GL && HF!:)

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

i am new in codeforces i want to see problems in codeforces round #284

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

Your bets — will dreamoon_love_AA win div2 tomorrow? :)

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

    We 2nd division participants will make sure he doesn't

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

      Haha, div2 guys defeating international grandmaster sounded pretty hilarious, but dreamoon seems to be taking this contest seriously, cause he solved 3 problems, but you are on better position now, so I see that your words were pretty serious :D

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

    Maybe he will cha to get -inf score,and integer overflow to +inf score and get the first place

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

      You shouldn't be drinking so much during christmas .

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

      if the hack points is defined by short, he can do it... if it is int..I think codeforces may break down.... if long long...the internet of the world may break down..What a DDOS!

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

    I bet 100 Quatloos that he won't.

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

    btw,can you imagine that oneday tourist's rating overflow to -inf and worse's rating overflow to +inf?

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

      He would have to take part in atleast 58040011 contests assuming he keeps getting the first rank and the first rank fetches him a gain of 37 points like it happened for his previous contest .

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

    Maybe He/She is challenging worse !

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

Merry Christmas to everyone !

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

Good luck to everybody!

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

dis like me plz

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

Hi!
thanks gridnevvvit !
your last contest had vary nice problem (Codeforces Round #275):) thanks :)

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

Hope for high rating.

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

    why do you hope it when you always make another account? seriously dude tell me how many accounts do you have? I only know about 4 of them I guess : tourleader , Majid , contest1234 and delairer. The funny fact is in all of them your contribution is negative :)

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

      I think guys like you are the reason he has a low contribution :)))

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

      Can you give me evidence for this letter?

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

        "I guess : choghok , clashofclans , contest1234 and delairer." he guesses

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

          Of course I guess, cause there might be more :)

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

            Well i thought you meant that you "guessed" these are his accounts my bad

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

            What do you mean ?
            contest1234 => last online 3 weeks ago!
            delairer => Last visit: 5 months ago!
            tourleader => last online 3 weeks ago!

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

              Isn't that obvious? you make an account give some contests with it and then you just leave it by,

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

                It is against the rules and i never do it!

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

      I don't think Majid and contest1234 are the same . You can check out their contest history . There are 2 contests in common (273 and 277.5) and they solved different number of problems in both .

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

Christmas Round && My first CF Round ... Sounds nice ;-) But the time is not convenient for Coders at GMT+8 ... such as China. It is 00:30 to 02:30 , which means we might be very sleepy ...

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

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

Merry Christmas to all :)

All the best for the Round #284.

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

Merry Christmas! GL && HF!

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

Hope to gain some rating points this Christmas ;)

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

I hope all Specialist be candidate master (!) and all Expert be master (!!) and dreamoon_love_AA be grand master !

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

    poor pupils and newbies then ...

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

    Well don't hope cause he is challenging worse so he is going to become specialist or or if he wins the challenge maybe pupil. :)

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

      He isn't challenging worse he is trying to get first place which he didn't achieve in div1 so he's trying it in div 2

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

Merry Christmas!

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

Merry Christmas

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

Scoring system will be Dynamic , don't know is it good for me or not ! My curious mind want to know what others think ?

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

Dynamic Scoring.

while(true) System.out.println("NOOOOOOOOOOOOOOOOOOOO");

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

Hope for much [pure] math

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

    (And strong pretests!!)

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

      Eh, well it is a matter of opinion. I personally believe that hacking creates more suspense, especially right after you try to hack someone.

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

We can see about dynamic scoring system here.

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

Seems like tourist didn't register for Div.1 .Could it be that he made a Div.2 account to beat dreamoon_love_AA ? By the way, good luck to everyone, and Merry Christmas !

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

Let's Pa Pa Pa tonight. :D

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

    one more chinese say something chinglish o(╯□╰)o

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

Many Thanks to you <3

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

GL HF

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

I have seen the problems and have decided to not participate. I don't see myself solving any problem other than A and B and that's not good enough for me. Maybe, I will have better luck next time.

GG.

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

sorry_dreamoon is now at first place! dreamoon_love_AA's only chance now is to solve E quickly and find lots of hacks!

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

    Hmmm ... dreamoon_love_AA is in my room ... I can make wrong submissions so that he can hack them and get to the top ... interesting idea ... ;) :D

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

In first 2 problems(div.2) the limits of numbers were to low...

so all coders will accept them by terrible codes...

It's the reason of less hacks than other contests...

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

dreamoon_love_AA has solved all 5 problems now. He needs to find 5 hacks to get to first place. He has currently locked C. I think that is a very good choice.

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

How hard it is!!! Poor rating...

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

contest is not attractive :( without Top rank in Div2 :)

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

interesting competition between sorry_dreamoon and dreamoon

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

I just want to know who is sorry_dreamoon :P Comment guesses :D

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

Highlight of this match: will sorry_dreamoon beat dreamoon_love_AA? There's probably no way for hacks to change the current situation, but there are still pretests! What if one (or both) fail something? Resubmissions are also possible...

Find out next time, on Dragon Ball Z!

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

liymsheep on the lines of worse

Doing so many unsuccessful hacks, so the first three contestants will have dreamoon in their handle name :D

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

    It's such sad story...after letting the top 3 places to dreamoons, liymsheep fails D him/herself and becomes 10th instead of 4th :(

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

What a Christmas gift!!!

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

It was a nice contest! easy problems A & B and normal Problem C!

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

How to solve div. 1 498B - Name That Tune and 498C - Array and Operations?

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

    If I'm not mistaken, Array and Operations was a maximum matching problem (so maxflow). You separate each number into its primes, and then built a tree based on that, and find the maxflow.

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

      Wait really? This is what I did (hope it doesn't time out), but since it doesn't use the i+j is odd condition (AFAIK), I was assuming it wasn't the intended solution...

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

        @waterfalls it should be using the i+j condition...

        Well some people did it in <=7 minutes, so this may be a harder way to solve it.

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

        The i + j odd condition just enforces a bipartite graph. I don't think it was really necessary, but maybe there was a simpler solution if you took advantage of that.

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

      How is the tree built?

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

        What I did is the following:

        1. Make a supersource and supersink.

        2. Make two*n nodes, one in-node and one out-node for each number in A.

        3. Connect the supersource to all the in-nodes, and the out-nodes to the supersink, with capacities equal to the number of factors of the prime p being considered.

        4. Connect, for each pair, each in-node to each out-node, with capacity equal to the number of factors of p the number in A shares.

        5. Find the maxflow of this.

        6. Divide by 2 (everything is counted twice)

        Nooooo WA on test #26 -> took like a minute to fix it... (for those who are wondering, with big primes must run maxflow again instead of just counting pairs that work and removing, which I did because I incorrectly thought since each could only have one of a prime, it would be ok)

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

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

Div. 2 Problem C. I thought that answer is number of lines between two points. Where i am wrong?

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

    You are right, watch for overflow though.

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

      You are right too. I'm using double instead long double... what a shame...

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

        You are wrong now. Use integer arithmetics only, avoid double or long double.

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

          Actually, double will pass; I just tested it. 9262061

          Unfortunately I made some other stupid mistake which led it to fail on system test :(

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

          My solution using double passed. The fact that the points are only integers and that the house and university cannot be on the roads helps :)

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

Epic Standings . Sorry Dreamoon

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

So sad

Got D solution produced correct answer for sample case after the deadline 2 seconds !!!!

I use 60 segment trees (for all the possible modulo).

UPD: that code got Accepted T_T. Life is so harsh.

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

    SQRT decomposition is pretty bad for this problem :(

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

Is this contest too?

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

I think that sorry_dreamoon is another account of dreamoon_love_AA

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

It is a bit annoying that there are a little hacks int the 2nd division

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

Nice problem thanks gridnevvvit!

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

Happy Christmas Everyone!!

Especially to dreamoon... Awesome scoreline XD

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

The only fail of the contest factor of ax!

The most fun part of it is I asked once about it and they gave me no comments. Anyone else had the same problem?

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

How to solve DIV 2 D?

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

Look at my submission 9258135 , I forgot to remove the "freopen", surprisingly my code outputs zero instead of getting RTE on test 1. and unfortunately because the answer of first test is zero I got WA on test 2 making me lose 50 points.

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

    Next time use "define ONLINE_JUDGE".

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

      but I want to know why I didn't get RTE , I used to think that it will make RTE so it will not decrease 50 points.

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

I got 'judgement failed' on my submission for Div1 B: http://codeforces.com/contest/498/submission/9246565. What does this mean?

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

Contest in hack is not !!!

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

Mery Christmas :) Good problems!

But Today, I'm not lucky (I've been seen dinosaurs on chrome :D)

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

    Same thing happened with me, I know how it feels when you finish both the problems in 10 mins and can't submit till 20 mins due those dinosaurs, btw Merry Christmas :)

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

Poor dreamoon_love_AA, he still can't win a codeforces round...

sorry_dreamoon named all his class as Dreamoon... maybe he does love dreamoon_love_AA...

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

    he/she will be in div.1 for next contest

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

I dont know dreamoon But It's for him/her (...)

I hope best ranks in goodbye 2014 for you :D

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

Merry Christmas dreamoon_love_AA!

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

http://codeforces.com/contest/499/submission/9254466

can someone point out why its giving wrong answer?

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

I have a gut feeling that dreamoon_love_AA will again try to return to Div. 2 in the next contest.

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

dreamoon_fan is also there, is it possible to change your handle??

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

is tourist sorry_dreamoon ? Because sorry_dreamoon finished the contest in 48 minutes.

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

    Take a look at top of div1 standings. There are quite a lot of contestants who did div1A-div1C in less than 48 minutes, so it is clear that you don't need to be a tourist to solve div2 problemset in 48 minutes (even if you still need to be a strong contestant to achieve this).

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

      And the codes were is JAVA, i dont think tourist would have done that, even though thats not hard for a redcoder!!

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

    Too sad.

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

    I think sharing Personal talks publicly is not cool.

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

pls,plz,pls,plz

dis like me plz

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

Is dreamoon_love_AA girl or boy?

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

A little bug in my submission for problem A div.1 ...
I want to kill myself now :D

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

Rating Updated.

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

sorry_dreamoon . Please can you reveal yourself .

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

After 42 contests I finally reached Div1. What a great Christmas gift! :)

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

Div.1 B is really hard to understand for me... Sad story...

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

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

The amount of dreamoon_love_AA is too damn high

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

Div2 only top 3 ... Why? because... dreamoon :)

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

Many O(nT) solutions for Div.1 B get TLE...I think the time limit is a bit tight, or maybe there is a solution faster than O(nT)?

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

    That's indeed the case, TL is quite evil IMO. Many solutions encounter problem with double performance for small numbers (it is well-known that double arithmetic is much slower if numbers are very small); in this particular problem the issue results in ~2 times slower running time. E.g.: this 9261764 gets TLE, while this one 9261771 (the same with rounding numbers below 1E-200 to 0) — AC in 483ms. Moreover, compiler choice matters; the same solution in Java 7: 9261791 (I guess it's because the startup time of Java VM is accounted to TL).

    In general, many failed B's were due to TLE for random reasons, and the actual running time was borderline. Increasing TL to 2s would resolve this. So I wonder why the TL was set to 1s, what wrong solution did jury try to kill? The only TLE-incorrect solution I can think of is O(nT2), which would run forever. It's sad that even good problemsetters continue to set TL without thinking, randomly killing many correct solutions as a result.

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

Can anyone explain me Div 2 E which involves Max. Flow? I was trying the greedy approach, which is wrong. (Realized after system test. :P)

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

    Here's what I did, which isn't the same as the editorial, but I find it easier to understand. (I got WA26 due to a small bug, but got it AC after) EDIT: See here for a more detailed explanation.

    For each prime that divides some a[i], we make a flow graph and find the number of operations that can be made using only that prime. The first thing to notice is that it is best if v is always a prime, since otherwise that operation could be split into operations using v's prime factors. Then,

    1. Make a supersource and supersink.

    2. Make two*n nodes, one in-node and one out-node for each number in a.

    3. Connect the supersource to all the in-nodes, and the out-nodes to the supersink, with capacities equal to the number of factors of the prime p being considered.

    4. Connect, for each pair i,j given, each in-node to each out-node, with capacity equal to the number of factors of p the number in A shares.

    5. Find the maxflow of this. A flow from an in-node to an out-node corresponds to using some prime factors of the two numbers the nodes represent in an operation.

    6. Divide by 2 (everything is counted twice)

    I'm not sure how clear this is, so feel free to ask questions (particularly on the modelling which I didn't really explain.

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

      Actually, there is no need to make 2n nodes. According to the statement, the sum of each pair is odd, so one of the numbers is odd and another is even. That's why the given graph is bipartite, and more than that, the first part contains the numbers with odd indices, and another — with even ones. So we can make edges from superstore to the ventices with odd indices, from the vertices with even indices to supersink and the given edges, directed from odd to even vertex.

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

        Ah ok that's why i+j is always odd... (I did think if there was a way to split the nodes to avoid an in and out node, but came up with nothing)

        Why would such a condition be added if it only helped a little bit with implementation (if at all, I'm not sure it would have been easier with the cases involved)? Was there another solution that used it more?

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

          Without having i + j is odd. Graph might had triangles. That's why one can not use bipartite matching anymore.

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

          How does your flow solution ensure that if we are sending k flow down (i in) -> (j out), we are also sending exactly k flow down (j in) -> (i out)? Surely for any feasible solution they should be equal, otherwise you can do crazy things with e.g. a triangle graph and get an answer that is actually impossible.

          For example, your accepted code fails with this non-bipartite-graph test case:

          6 6
2 2 2 2 2 2
1 2
1 3
2 3
4 5
4 6
5 6

          On a bipartite graph this does not matter because your flow graph is essentially just two bipartite graphs that are equivalent (i.e. even positions on one side, odd positions on the other side, edges represent number of prime factor p shared), with one being the mirror of the other, so you are guaranteed to get 2X the correct answer.

          If it's not a bipartite graph, then the problem essentially reduces to maximum matching on a general graph, which is not solved with flow as far as I know. See 9250097 for example on solving it for the general case.

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

      Hey waterfalls, I didn't quite understand the graph making part. Let me ask some clarifications.

      For each prime that divides some a[i], we make a flow graph and find the number of operations that can be made using only that prime.

      Connect the supersource to all the in-nodes, and the out-nodes to the supersink, with capacities equal to the number of factors of the prime p being considered.

      I didn't understand those two parts properly. Would you please explain with a sample test case?

      Thank you.

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

        Here is what I did:

        (The number of p in A[i] means the number of times A[i] can be divided by p)

        1. Make a source and sink node.

        2. Add a directed edge from source to all nodes with odd index i. The capacity of each edge is the number of p in A[i].

        3. Add a directed edge from sink with all nodes to even index i. The capacity of each edge is the number of p in A[i].

        4. For each good pair (i,j), add an edge from an odd indexed node to even indexed node. (If the good pair is (3,4), add an edge from 3 to 4. If (6,7), add an edge from 7 to 6) The capacity of each edge is the number of p in gcd(A[i],A[j])

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

        Although some of my reasoning was wrong, as ikbal pointed out above, I'll try to explain this (if HidenoriS didn't already clear it up)

        Basically, you want each operation to be made on a prime. Then, split the operations into the different primes to perform them on. This results, for each prime, in a different (but similar) problem:

        Given b[i] for 1 ≤ i ≤ n, (here b[i] is the number of factors of the prime in a[i]) and m good pairs, find the number of operations you can do where each operation consists of subtracting the same number from both numbers in the pair.

        For this, use flow. Make a supersource and supersink, and (I'll use the even-odd thing now) connect the supersource to the odds, and the evens to the supersink. To ensure the flow is limited by the factors of p (which is just b[i]), make the capacity of the flow from any node representing i to the supersource/supersink equal to b[i]. Then, for each good pair connect the two nodes, with capacity equal to the minimum of the numbers of factors of p (which is (min(b[i], b[j])).

        Running maxflow on this from the supersource to the supersink gives the number of operations that can be made with a certain prime p, and repeat for all primes.

        Sample:

        3 2 8 12 8 1 2 2 3

        Here, a = {8, 12, 8}. Consider the prime p = 2. The resulting b = {3, 2, 3} (the number of factors of 2). Now, the flow graph looks like this:

        flow graph

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

          Thanks both of you! It is totally clear now. :)

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

Where are the editorial ?? :/

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

When could I get the editorial for 284 div 2?

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

.

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

    You can get partial scores on Hackerrank for test cases you got correct. But in Codeforces and Topcoder there is no partial scoring system.

    → Reply