komendart's blog

By komendart, history, 4 years ago, translation, In English,

Hi!

Tomorrow, on 23rd of January at 18:35 MSK Codeforces Round #340 (Div. 2) will take place. It's my first round, hope you enjoy the problems.

Thanks to GlebsHP for his help in preparing the problems, Delinur for translations of statements and MikeMirzayanov for Codeforces and Polygon.

Good luck!

UPD Scoring 500-1000-1250-1750-2750

UPD Editorial

UPD Congrats to winners!

Div. 2

  1. AReesha

  2. Miyukine

  3. KefaaLove

  4. zhaoxinyi

  5. thatday

Div. 1

  1. anta

  2. doreamon

  3. uwi

  4. Um_nik

  5. I_love_Tanya_Romanova

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

»
4 years ago, # |
Rev. 2   Vote: I like it +95 Vote: I do not like it

I hope problem statements will be also short like this announcement.GL & HF.

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

    Let's also hope for clear and understandable problem statements.

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

    I hope problem statements will have good translation like the announcement!!

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

      What's wrong with them? I think they are quite clear to understand.

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

    So,I hope that problems will be clear and the translating of problems will be easy,Because my only translate Helper is "GooGle Translate" ;) Sorry bad English... GL & HF.

»
4 years ago, # |
  Vote: I like it +81 Vote: I do not like it

Best. Announcement. Ever.

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

    I hope you'll get a lot of points in the contest as your comment got up votes :)

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Cool. Shortest announcement ever!

»
4 years ago, # |
Rev. 3   Vote: I like it +42 Vote: I do not like it

At this rate the next round's announcement will literally be

hi
glhf

:)

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

Experince shows:

Short blog means long problem statements!

hope experince be wrong.

»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Nice short announcement.

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

It's always a great experience to read short announcement and solve short statement problems too. kudos to GlebsHP :-)

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Note that round starts at the unusual time!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Coolest announcement ever! Hope problems will as cool as the announcement :)

»
4 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Am I the only one who likes long announcements? And statements longer than one sentence?

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

    I remember that, a while ago, a guy (I don't remember his name nor his CF account), decided to tell his experiences in programming competitions in the announcement of his CF round. I think that is a good idea, is very motivating =)

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

    I don't "like" them..but I don't hate them too :D

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

    We don't mind a multiple line statement. Its the useless backdrop and cover story that is annoying, because it takes up time to read, and some people might think there's useful information hidden in all that story, so they read it slowly and carefully, and maybe they read it over and over again. Talking from div2 perspective only :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice announcement=w= BTW,do you feel the cold wave...Here in China I'm almost can't move anymore...

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Bref...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Perfect time for me :D thanks for this time. Will it be fixed for future contests? :)

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

have a good contest friends good luck

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Div. 2 only contest, which means loads of fake accounts from Div. 1 users. God I hate this :(

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Who else is joining both this round and FB Hacker Cup Round 2?

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

    I am in a dilemma here. Well, I know my limits and I know its impossible for me to advance to round 3. Yet somehow, I can't stop dreaming. I will be having a good fight with my brain I guess.

    Doing both will do no good for me. I already have exams and my brain can only take so much :/

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

      Hmm...if I was advancing to round 2, I would definitely compete in hacker cup, no dilemma there. Hacker cup comes once in a year. The problems will be tough, obviously. But what will you regret more? Not solving an intentional easy problem(if any, because so many people are advancing to round 2 this time) in hackercup because you were here, or not getting a rating rise today because you were in round 2? Remember, these rounds(are great!) but they come once in a week usually.

      Even if all of hacker cup's problems are difficult, it is still more satisfying to know you did your best in an annual thing. Trust me, if you miss hackercup, you will regret simply because it won't come again until next year.

      Extra motivation : this a div 2 only round. YKWIM :)

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

        Well I'm staying up and doing both. :)

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

          I don't know what you would have done if you had final exams in 2 days. But thumbs up for your determination :)

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

          I didn't check the contest time for FHC, but I guess the contests' duration don't clash massively then. All the best :)

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

            In my timezone, this is 11:35pm — 1:35am, FHC is 2am — 5am.

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

              Now I am a little confused why this person had a dilemma in the first place. He should've been well rested prepared and relaxed today. Besides, chances are, being cyan coder, he'll max out after 1-1.5 hour, so he'll have at least one hour to rest in between. You gotta optimize these things to work in your favor :)

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

                well, I am already being underestimated because I am cyan , eh? :v Well I may not do that well in these contests. But for your info, I don't give up until the end. If you see my previous contests, I have submitted many problems late in the contest. Its because I think of a way until the end. And do u know how I got into round 2 of FBH? I thought and coded for problem C for 12 HOURS straight. And I submitted just 2 minutes before the round ended. (Yes , I know many people would laught at this because it seemed like an easy problem to them. But I am not talented, I try to cover it with my hard work. So saying I will give up after 1-1.5 hour seems a little bit insulting. Sorry if I sound rude)

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

                  Whatever floats your boat :)

                  If I were you, I would literally stop after A,B,C. This is not because I gave up but simply because it is good strategy in my opinion. If I get 3 right, I'll have a good enough rating rise. If I solve 3, I will read D, and if I can see the solution within 5 minutes, I'll code, else, I'll just drop it. No point messing another contest because I was too stubborn with a problem outside my reach.

                  But you know, do whatever you want :)

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

                  Honestly FamisProud's strategy isn't really that good. There have been many contests where the difficulty distribution isn't even or where the order is just plain wrong. Even today, at least for me, D was about on par with, if not easier than C. Another good example is round 338, where many coders considered D, and even E to be easier than C.

                  And besides, I don't think you can really improve if you don't try to solve the hard problems.

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

                  It is good for me. I'll tell you why, so read on only if you're really interested.

                  I have a short attention span, and I get easily distracted. I have realized that resting before a serious contest improves my attention , compared to keeping my mind occupied with questions before contest. Basically, clearing my head helps me focus when it really matters. That's all.

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

        Yeah, I have already decided I would do hacker cup.

        (well, people obviously like to downvote for apparently no reason)

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

    I'm joining both. It's like a 5-hour ACM contest with 9 problems, but with a short 25-minute break, lol

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Auto comment: topic has been updated by komendart (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

What kind of contest is it?!!!!

»
4 years ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

Why div2 only contests are too easy these days? they were not that easy in the past

in my opinion it should become harder after 2nd color revolution, since poeple with rating between 1700 and 1899 became div2

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

cf lagging please extend contest a little

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The system tests, I guess, will be deadly :(

»
4 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

In the last 7 minutes, I could not able to hack.

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

    Same here

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    I think hacking attempts should be blocked in the last 5 minutes. Hackees should get a chance to defend.

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

      If you are hacked, it is hardly ever bad for you. You'd fail final testing anyway.

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

        If someone hacks me with 30 minutes on the clock, I'd be grateful. But if someone hacks me with 30 seconds on the clock, I'll be sad.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -22 Vote: I do not like it

        I've survived hacks because I had time to think and include corner cases. Why will I fail systests always? lol. If I don't include the corner case, and then fail systests, then its bad for me. So, to conclude, hacks are good in general for the hackee unless done very late with no time to correct the mistake.

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

          Yes, and they are neutral for the hackee otherwise. I still don't see why they should be blocked.

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

            So that if you are planning to hack, you'll do it by 1hr 55 mins. Then you won't. So now the hackee has a chance to correct their mistake. Geddit now? You think neutral is something they'd like after solving a problem, for maybe more than one hour(somewhat incorrectly though) ?

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

              I got it now, but I'm not planning hacks by the end of the contest for depriving the hackee of a chance to correct solution. It's just unprofitable because someone else can hack the same solution before you. Also I don't think 5 minutes will change a lot in hackers' plans: "Solve as much as you can and then hack till the end."

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

                Many people choose to swoop in and hack with seconds on the clock too. See for your yourself. The parent commentor in this thread was going to hack with 7 minutes on the clock. Although 7 minutes isn't the worst, but such late hacks are enough to cause a panic to the hackee, especially if they're onto some other problem, and are rushing to submit it. Besides, when do most people hack? When they don't think they can solve any more problems. So that tends to happen towards the end.

                Besides, I am not a big fan of passing pretest in div2A and then making a 100 successful hack attempts, even though your own solution gets hacked or fails systests, and still get a better standing than hard working guys, who diligently solve problems. Points from hacking should be the least of our concerns, and by giving hackees a chance to defend, that might be helped.

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

          if u were hacked in the last 5 minutes you will be sad

          so if hacks were blocked and u got Failed system test u will be happy ?

          what's the deference ?

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

            No, the point is that if we block hacks in the last 5 minutes, hackers will start hacking earlier, and so an incorrect solution will also be reconized earlier. Actually there is a difference, but it looks so tiny for me that I don't think it deserves a new rule.

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              I don't think it deserves a new rule

              Doesn't need a new rule. Its already happening with everybody rushing in to submit in last 5 minutes or make last minute hacks . Server goes down :D

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

                :)) However, I hacked one solution successfully on the last minute of this contest.

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

                  such contradiction much wow :D

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

                  No contradiction here. If there was the 5-minute rule, I just wouldn't hack this solution and it would fail final testing. My results would change, but not my plans.

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

                  A task takes as much time as it is given to be done :)

                  You will speed up with the solving phase. So to say, if you are stuck on a problem, and you plan on thinking till 1hr 55 mins, and then hack for last 5 mintes, you'll change to think for 1hr 50 mins, hack for 5 mins, then (maybe/maybe not)think again for 5 minutes, because this scheme is more profitable under new rule.

                  I thought you contradicted yourself, but now I see that your statement had ambiguity, so yup, no contradiction there.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

That's very unfortunate. I was about to hack a solution for D and the site went down. The hack page didn't load even for almost 3 minutes try. :/

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

For anyone curious on the hack cases for D, there were two of them:

0 0
0 2
1 4

or

0 0
0 2
1 1

I'm sad that Codeforces lagged out in the last three minutes... So many missed hacks ):

EDIT: I just realized that, for C, I accidentally used an int. I guess those hacks were for nothing.

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

    and the answer suppose to be ?

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

      2 for the first test case, 3 for the second.

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

        Maybe I misunderstood the problem properly :(

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

    what the answer for those tests?

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

      2 for the first test case, 3 for the second.

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

        They have to be both (2) !

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

          Sorry, but you're wrong. The second case is 3 because you can't get the line segments to meet at corners.

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

    is the answer for 0 0 0 2 1 4

    2

    and

    0 0 0 2 1 1

    this one 3 ?

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

    What was the faulty strategy for your first test case?

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

      Many programs went like this:

      if x1 == x2 and (y3 == y1 or y3 == y2):
          print(2)
      

      The test cases in the problem statement specifically included an example where a point was not a corner of the polyline.

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

That feeling when you was cracked on problem D three times.

»
4 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

I was just going to submit for D. Clearly knew there were like 25 seconds left when i hit submit button but it failed to even respond. So high load :\ Damnnnn Even the sites so slow to even open this blog.

Maybe a little extension would have helped.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I should have started sooner with writing hacks. In the last 10 minutes I looked at three different problem D solutions and was able to hack all three.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess there will be many failed submissions for D after system testing. :D

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

First time I hack in codeforces... +13:-1

much polyline so hack

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

    much wow! -

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

    whats the hack?

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

      For answer = 1 there is only one possibility. Tricky part is answer = 2 there will be 8 cases else the answer will be 3.

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

        Eight cases? I found only 6: x1==x2, x1==x3, x2==x3, y1==y2, y1==y3, y2==y3. In each of them additional check determinate if answer will be 2 or 3. What am I missing?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Answer will be two only when line joining any two of the points is parallel to x or y axis.

          So first lets consider there are two points such that line joining them is horizontal. Then third point has to be bottom left, bottom right, up left or up right in respect to both the points. Same goes for vertical line.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Whats the solution for E?

I imagine something related to partial sums, but 2D one won't fit in memory and I failed to made it based on couple of 1Ds (like pair of "started from" and "ended in" ones).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Found that I need to resize my integers to unsigned or long long in problem B when contest actually ended, there is no God in this damned world. =C

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

    What is the 7 test case?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1
      0
      
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Shouldn't number of ways in which I can't break it be still 1 . I mean shouldn't number of ways doing nothing be 1.

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

          According to the statement, each part must contain a nut. Therefore, in this case the number of valid ways is 0.

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

            oh didn't see the valid part . Thanx

»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Hacking Party!

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Can someone tell me why are people allowed to resubmit after their solution is hacked? They can find out the bug by seeing other correct solution. Isn't it bit unfair or am I missing something here?

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

    If you lock your solution, you can't resubmit it. If you don't lock your solution, you can't see others' solutions.

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

      i see, thank you :). Was not sure how it worked.

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

    They can see others solutions only if they locked their own one. And if they locked — they can't resubmit, even if got hacked.

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

    You can view other solutions (and hack them) after you lock the problem, which means you can't resubmit yours once it is hacked.

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

    they can't see other solutions unless blocked. And they can't resubmit a problem if they blocked it.

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

    You cannot resubmit your solution if your solution is locked. If your solution is not locked you can't view other's solutions.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    They can resubmit problem only if they didn't block problem,If problem wasn't blocked, then they couldn't see any solutions

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

    If someone is hacked he cant see the test case and to see others solutions (your room only) you need to block your solution, if you do you can not resubmit it.

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

    They haven't locked that problem, so they cannot see the solution of other people. Once they lock the problem, they cannot re-submit anymore.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    So many replies. I will add one more :P. You must have locked your problem so you can't submit again.

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

    If you decide to hack it, you need to lock your solution and you can then see other people's solutions. If your solution now gets hacked, you cannot resubmit, since you have locked it.

    If someone's solution gets hacked, they can resubmit. They can't see other's solutions till they lock their solution.

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

I'm rather angry at this codeforces round. First, although I got A in 00:00, B took me very long, due to the fact that codeforces repeatedly gave me website exceptions while submitting. Furthermore, I received rather strange verdicts. 15518610 [submission:15519407][submission:15520501][submission:15521050] 15521416

Next, I encountered significant lag on D, and I submitted the same program twice during the round.

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

    In 15518610, you allocate vector<int> a before you cin >> N, that means you possibly allocate an empty vector.

»
4 years ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

Problem B also had a nice hack (for integer overflow). The answer is something like 2^50.

100
1 0 1 0 1 0 1 0...
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the solution for C?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For each point, set that point as the farthest point from fountain 1 (so r1 is the distance between them). Loop through all other points to calulate r2. For all r1, the answer will be the minimum of r1^2 + r2^2. Runtime: O(N^2)

»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Am I the only one who hates this hackerfest? :)

What is bothering me is that 20 hacks gives like the same points as hardest task. And it seems that skills required to solve hard task and skills required to find 20 solutions failed on the same one test case is not really on the same level.

»
4 years ago, # |
  Vote: I like it +46 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

In problem C, many people forgot test cases that r1 = 0

Ex: 1 0 0 2 2 3 3

Ans: 2

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What happens for B if all are 0?

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

    ans is 0 then

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

      Any chance that was the test case 7? :?

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

        Yes, this is exctly test #7

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

          This is what happens when you arrive to contest with 20 minutes left :// :(

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

    It was in problem statement. Answer will be 0.

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

      Really? I don't see it in the statement?

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

        Well, I consider this line covers this case:

        "Please note, that if Bob doesn't make any breaks, all the bar will form one piece and it still has to have exactly one nut."

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

After system tests, solvers of C reduced to half and even D suffered 40% loss.

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Only 1 unrated in Top-20 :o

»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

bad contest :|

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

C and D are good problems for the HACKers

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That moment when you find out, that in one task you are reffering to a1 instead of a2 variable, and in second task you are reffering to a instead of b...

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Your contest f**ked me :-(

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Everytime you think the contest is easy , and next minute your solutions gets hacked

»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

All problems are very excellent and interesting. Thanks to komendart!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

maybe Chinese are more familiar with Mo's algorithm...the problem can be solved off-line.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My solution for C:

  • Every flower belongs to either fountain 1 or fountain 2
  • Try all combinations recursively O(2^n): every iteration expands either fountain1 or fountain2 to cover the flower in question
  • Optimize by processing flowers in order of furthest -> closest (eg. first the flower with the highest min(d1,d2), where d1=flower's distance to fountain 1) -> When a fountain is expanded to cover some flower really far away, it also covers all the flowers on the way there. This drasticly reduces the number of combinations we need to check.

http://codeforces.com/contest/617/submission/15530019

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

    Nice solution (Y) , were you sure it wouldn't TL ?

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

      I solved it the same way and was sure it won't TL. A bit additional note: In step 2 we skip points that is already covered.

      Important thing here is the optimization he mentioned. Because of it recursion will stop on depth 2 in every possible case.

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

    O(2^n)? Wow

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

      It's O(2^n) without the optimization. I think it's O(n log n) with optimization, but I'm not sure.

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

        Yes it is O(n log n) with optimization. And this complexity is for sorting. After that, its O(n) (instead of O(2^n)) to find a solution.

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

holy s**t :o !!! 1416 successful hacks on D! should've done better

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

when is the update of rating expected?

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope this not the part where I find out I completely misunderstood problem D. What's the answer for the following input? -931665727 768789996 234859675 808326671 -931665727 879145023

Shouldn't it be 2? 1 segment between points 1 and 3 and another segment connecting 2 to the first one. Right?

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

    The answer is 3. Any segment must connect 2 points, not a point and another segment.

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

    This doesn't work because the x-value for point 2 is in between points 1 and 3. After we connect points 1 and 3, we need to go up and to the right from point 1 to reach point 2. This results in 3 segments.

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

    In that case, wouldn't the answer for the third example be 4 segments? right and down + down and left.

    I assumed a segment can be any length and it doesn't have to start or end with a particular point. Thus, for the 3rd example you have a vertical line passing point 3 and one horizontal line for each of the other two points.

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

If you said " No response, Read the problem statement" I would take in consideration both cases, but when you reply with this I become sure that no way there is a case with no nuts -_-

»
4 years ago, # |
Rev. 5   Vote: I like it +12 Vote: I do not like it

I was so happy because i solved D first time. But i did a little mistake and that mistake went unnoticed after system test.

My submission fails for this test case.

1 1

2 2

3 3

MikeMirzayanov Please look into this.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Div2 C

http://pastebin.com/QyUVUnwt

I am unable to find the bug in my procedure :( Please help

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

    I think you have to also consider the case where r1 = 0.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

the contest had 4 unusual easy problems and very weak pretests :| almost it didn't have judge during the contest..

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

wow such a beautiful winner :) I wonder how many girls have won any competition here at codeforces ))

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hi thank you for your contest i like it