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

Автор maroonrk, история, 4 года назад, По-английски

I've hacked all AC solutions of this problem, which were submitted during the contest, and I believe I can hack most of upsolving solutions. Currently, I only checked that they time out on my local machine, because "Unexpected Verdict" prevents me from uphacking. I even hacked model implementation in the editorial.

Here's my latest generator. Feel free to challenge it.

Side Note: yosupo wrote a solution, which passes the above case, but I failed it with another generator.

What I want to argue is that TL of this problem is too tight, and it affected some of the competitors. For example, I got almost the same idea as the model solution during the contest. Still, I was too scared to write it because I suspected it would time out without full optimization and possibly some tweaks like shuffling vertices/edges or contracting vertices. As I proved it myself, my thought was correct. However, this observation didn't help me, and some people who didn't think of this (or believed the weakness of the test) passed F, which seems unfair to me.

I'm not saying the round should be unrated; I think there exists a really well-optimized solution that can pass all tests. But please, problem setters and coordinators, you should give careful consideration to TL of problems. Don't set the TL by how fast your solutions run on your test. I wish future CF writes and coordinators read this, and that's the reason why I posted it as a separate blog, not a comment to the round.

P.S. Please notify me when you believe your solution can pass all tests, I'll try to challenge it.

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

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

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

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

+1

TL is a part of statement and it should be set so that (at least) you'll have no doubt that intended solution will fit it TL (without actually writing it). Ideally it should be also clear that slow solutions are slow, but that's (in my opinion) less important.

In this particular problem it is clear that authors intentions are not to allow flow for each query (because it is bruteforce solution) but to allow several flows as precalculation. I, as tester, suggested to change limitations to clearly indicate intention of authors, but they decided not to. I'm sure that they had their reasons.

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

maroonrk, the destroyer of mediocre flows.

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

+1, we need to stop that "Oh, complexity seems huge? But constant is surely really small! checks on prepared tests and it runs fast Indeed I was right, good to go!"

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

maroonrk notifying: 88061960

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

I will ask the hard question: should the round be unrated MikeMirzayanov?

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

    plz unrated, sincerely AnandOza

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

    I guess it won't. Problem F kind of did its job during the round, there is only a problem what to do now.

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

      Isn't it a simple if-else answer? Instead of arguing if the problem did its job during the round or not.

      maroonrk said: "I think there exists a really well-optimized solution that can pass all tests."
      If there exists a heavily optimised soln which passes all given constraints then the round is rated otherwise it's unrated for Div.1.
      Jury's soln should pass all test cases under given constraints including the ones not added in the test cases by Jury.

      Let's wait for authors (or anyone) to write one such soln. Otherwise, declare it unrated for Div.1. Reasons — Read any comment supporting unrated #637. or CF #601.
      I can link more rounds which were unrated because no one managed to write a soln which can pass all test cases satisfying given constraints.

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

        I think that during the round almost nobody thought that these problems will go so deeply. Remember that making the round unrated will make it unrated also for all the people with A+B only, while a lot of them didn’t even try to touch F. In the mentioned round it was worse: many participants saw that E is unsolvable, while now many participants just saw that it might be too slow.

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

          No of affected participants is just a number. Should never be the basis for deciding if its unrated or not. It was 100 in that round and 10 (or just 1) in this round.

          In past rounds have been semi rated. Unrated for those who were affected by the problem if the count of such participants is low. Right now there doesn't exist an efficient method to count such participants. Except assuming only 10-20 people read Div1 F.

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

            "No of participants is just a number." I think that this number should definitely be taken into account considering whether some round should be unrated or not xd

            I mean the number of affected participants ofc. Btw, I also don't know anybody affected, if you can show me them, it'll be nice (I'll change my mind probably).

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

              also don't know anybody affected, if you can show me them

              maroonrk said: "For example, I got almost the same idea as the model solution during the contest. Still, I was too scared to write it because I suspected it would time out without full optimization and possibly some tweaks like shuffling vertices/edges or contracting vertices."

              The first point is all problems should have one correct soln satisfying given constraints. Isn't this the guarantee given to us before the start of round? This isn't the case so far. Semi unrated round (one I linked had correct solns. Just that setters soln during the contest was incorrect. Then there were different methods to deal with them.)

              If you can give me one logical reason why a round should be rated when one problem didn't have a correct soln? I will for sure change my mind.

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

                I guess that semirated rounds are sh*t to be honest and I guess that many people will agree. The better way is to try to make it unrated only for affected participants, maroonrk seems to be one of them, but it's hard to find them now.

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

                  "semirated rounds are sh*t".
                  Can't agree more.

                  Let's ask maroonrk — if he would be fine with this round unrated for him? Based on his answer we can keep it rated/unrated for him. And ask him to not hack new solns which people will come up.

                  Later we will conclude that this was the correct soln. No one managed to hack it. And keep this round rated for everyone. :)

                  I'm more inclined with my if-else answer. As long as that answer is correct I feel contest is fair. Otherwise, it wasn't.

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

                  I agree aryanc403 in that this round should be unrated if we cannot make the model solution. (I'm sure that it is possible to make the solution, though).

                  "no model solution problem" is no longer the problem of algo match, and enough reason to make the round unrated regardless of the number of affected people.

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

                  We don't live in a perfect world and thus we shouldn't follow golden rules like "unrated if there is no intended solution for a problem". Should we hypothetically make a round unrated if it was insanely hard, a winner solved just A+B, BUT there are some issues in E? Maybe several people were hurt but should we take a round away from a thousand people? It's difficult to say.

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

                  but round #637 got unrated because Div1E had wrong solution, even that number of affected contestants is small !. so if the intended solution of Div1F in last div1 is TLE, it should be unrated due to the same reason. I don't see any difference between these two situations.

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

                  Yes, in too extreme situation as you suggested, I may change the opinion (so, "regardless of the number of affected people" is exaggerated, sorry.)

                  But anyway, this situation is not so extreme, problem F was solved by 13 people and at least maroonrk affected. My opinion is that this situation is inside of my golden rule, "unrated if there is no intended solution for a problem" .

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

Finally hacked tourist.
B̶y̶ ̶c̶o̶p̶y̶ ̶p̶a̶s̶t̶i̶n̶g̶ ̶y̶o̶u̶r̶ ̶g̶e̶n̶e̶r̶a̶t̶o̶r̶.̶
"Anti You didn't even scratch me!" Unlocked. :P

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

maroonrk I compute flow here without dfs and it runs in 4.6secods, already tested on current public hacks, can you check: 88082267

Update: Not sure how to make my submission public :( Can you please resubmit:

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

    You are not allowed to view the requested page.

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

    Here it is with FastIO, 88085075 thanks aryanc403

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

      Hi, marX sol got tle on your last test because it's not cache friendly on it, I fixed it but it's almost 4am and I don't want to set it as model without checking it carefully, here is the sol in advance: 88104366 88104631

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

      Hi again it's almost 6am now :)

      This sol 88113088 (3.8 seconds) is an official sol (the one I messed up in my first comment), but doing only dfs instead of bfs + dfs for each mask and relabeling the nodes to make it more cache friendly.

      And this 88113666 (1.7 seconds) is the same, but giving priority to time consuming masks (this idea was in another official sol which I did to speed up $$$O(2^k * flow)$$$ sols)

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

        Thank you very much! These solutions look nice to me. I'll read them carefully and consider possible counter tests, but I think it's highly likely that they are "correct" solutions.

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

          hacked the first solution...

          UPD: The same generator also hacked the second one...

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

            It seems that your testcase takes advantage of how I'm traversing the graph and causing lot of cache miss.

            Passed it now :)

            88143085

            88143055

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

              I wish everyone prepared their problems following a similar iterative testing process

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

              Great Work! It seems like a strong heuristics and I haven't got an idea to hack it. I believe (and hope) that it's the "correct" solution we are looking for. (TBH I'm a bit bored with hacking the same problem again and again...)

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

88085881 anybody?

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

    I guess your Push Relabel uses three heuristics: Global labeling, Gap labeling, and Freeze Operation. I first thought it's easy to hack it because it calculates the whole maxflow $$$2^K$$$ times, but it turned out to be surprisingly fast. Thank you for letting me know the algorithm. (but I'll keep trying to hack it for some time)

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

I like how this turned into community effort to solve this problem "correctly".