Блог пользователя komendart

Автор komendart, история, 8 лет назад, По-русски

Привет!

Завтра, 23 января в 18:35 MSK состоится Codeforces Round #340 (Div. 2). Это мой первый раунд, надеюсь, вам понравятся задачи.

Спасибо GlebsHP за помощь при подготовке задач, Delinur за перевод условий и MikeMirzayanov за Codeforces и Polygon.

Всем удачи!

UPD Разбалловка 500-1000-1250-1750-2750

UPD Разбор

UPD Поздравляем победителей!

Div. 2

  1. AReesha

  2. kpw29

  3. I_love_Varechka

  4. zhaoxinyi

  5. thatday

Div. 1

  1. anta

  2. dreamoon_love_AA

  3. uwi

  4. Um_nik

  5. I_love_Tanya_Romanova

  • Проголосовать: нравится
  • +427
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +95 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +81 Проголосовать: не нравится

Best. Announcement. Ever.

»
8 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Cool. Shortest announcement ever!

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Краткость — сестра таланта.

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +42 Проголосовать: не нравится

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

hi
glhf

:)

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Experince shows:

Short blog means long problem statements!

hope experince be wrong.

»
8 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Nice short announcement.

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Думаю, длинна приветствия как-то зависит от количества человек, участвовавших в подготовке. Корреляция кажется очевидной, но это лишь на первый взгляд, мне стоит всё проверить.

komendart, надеюсь, первый раунд последним не будет :)

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Note that round starts at the unusual time!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 =)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Время раунда пересекается с ИОИП-ом. Печалька :(

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Bref...

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

    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 :/

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 :)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится +10 Проголосовать: не нравится

              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 :)

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится +16 Проголосовать: не нравится

                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)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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 :)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится

                  Honestly I_love_Captain_America'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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Прикольный раунд, столько взломов

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

What kind of contest is it?!!!!

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

cf lagging please extend contest a little

»
8 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Izi contest, izi life :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Same here

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -30 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -21 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -22 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится -15 Проголосовать: не нравится

            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) ?

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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."

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          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 ?

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +6 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              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

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  such contradiction much wow :D

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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. :/

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

Я счастлив! Это был первый раунд, на котором я взломал кого-то и первый раунд, на котором у меня прошли претесты на четырех задачах. Ни разу даже три задачи не доходили до системного тестирования. Спасибо всем, кто брал участие в организации. Получил массу удовольствия! UPD: И это первый раунд, на котором я решил три задачи. Все с чего-то начинают...)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

much polyline so hack

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    much wow! -

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    whats the hack?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Hacking Party!

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кто часто участвует, подскажите, взломы всегда так тормозят? Или это только сейчас? Или это, вообще, только у меня? Спасибо

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Мне кажется это из-за огромного числа взломов. Хотя, опять же, мне кажется что сайт тормозил еще до начала контеста.

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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...
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the solution for C?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
8 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится
»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

Ex: 1 0 0 2 2 3 3

Ans: 2

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What happens for B if all are 0?

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

поменять бы местами C и D...

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    D вообще можно вторым поставить =/

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      В решило в 3-4 раза больше людей, чем D. Так что, все как раз-таки расставлено правильно.

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

        Вообще это не совсем показатель — большая часть людей не читает сразу все задачи в поисках легких, а решают по порядку. Так что вполне вероятно, что большое количество участников банально не прочитало D.

        Я бы ну как минимум с C ее поменял местами, возможно что и с B тоже.

        Вообще вся сложность D — это найти в чем же ее сложность :D Банально добавить один тестовый пример — и ее бы все решили за 5 минут.

        А с B и C такой финт не пройдет — там хоть какой-то, да надо алгоритм придумывать.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Вы частично правы, но когда разница в четыре раза — тут уже не в том дело, что условие не читали. Отношение решивших к попытавшимся у В в два раза выше, чем у D.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            А это я готов объяснить слабостью претестов в D :)

            К тому же, возвращаясь к моему предыдущему посту — задачку B большая часть участников начала решать почти сразу (через 1? 5? 10? минут после начала), в то время как до D они с большой вероятностью добрались только к концу соревнования.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится +6 Проголосовать: не нравится

              Слабость претестов — это часть сложности. Требуется умение проверять свой алгоритм на корректность, а это, во-первых, часто не проще, чем решить задачу, во-вторых, это разумное требование к программисту, ибо в жизни всё предусматривающие тесты никто заранее не напишет. Тем не менее, между C и D дисбаланс очков заметен, это правда.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Only 1 unrated in Top-20 :o

»
8 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

bad contest :|

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

C and D are good problems for the HACKers

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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...

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В проблеме D. Тест 9:

-931665727 768789996
234859675 808326671
-931665727 879145023

дает 2 или 3?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вроде 3 должен давать, ибо за 2 без самопересечений никак.

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Your contest f**ked me :-(

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    O(2^n)? Wow

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем komendart (предыдущая версия, новая версия, сравнить).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Пропало с главной

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Не могли бы вы ответить на 2 вопроса? Этот раунд не рейтинговый? И ещё, написано что раунд див 2, а в нём также участвовали те у кого рейтинг за 1900?

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

when is the update of rating expected?

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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 -_-

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Спасибо что уделили время и ответили на мой вопрос.

»
8 лет назад, # |
Rev. 5   Проголосовать: нравится +12 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Div2 C

http://pastebin.com/QyUVUnwt

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

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

 Круто, а такие сообщения автоматом всем приходят кто рейтинг поднимает? А то я тут, относительно, новичок :)

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I finished at 7th position in Div 2 in this contest. Will i get any codeforces tshirt or something ?