piaoyun's blog

Is this a Div3?
By piaoyun, history, 3 weeks ago, In English

It is the running Round 1094 Div 1 + Div 2 actually.

Every two weeks, I will be sitting in front of my pc and humiliated for three straight hours. I love post-GPT CP so much.

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

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

It's div3 for AIs of course. They think the contest is so easy with a human to help them submit.

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it +38 Vote: I do not like it

I failed C because I had an extra log factor and then proceeded to go on tilt for the rest of the contest and am probably going to get like -250

→ Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    Actually, I had an extra log in my code, but I passed this problem.

    → Reply
    • »
      »
      »
      3 weeks ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Ya, someone I know (fishy15) had the log factor and passed so I'm guessing it was right on the edge.

      I wonder why this was never caught during testing.

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

        It was caught, but the decision was made not to kill those solutions. There are several ways to find the median of every interval in O(N^2logN), just make sure you dont have a big constant factor.

        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          If n^2 log n was intended, why is the TL so tight? At least if I was a writer, I’d have set n = 2000 or so. I used a fairly simple and fast (do correct me if I’m wrong), just double for loop to sweep and ordered statistic for the median.

          I also would suspect Java or Python solutions would not pass at all.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 weeks ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Oh, i didn't mean the complexity was intended, in fact at some point there was a discussion wether to force an O(NlogN) solution or not. It's just that when the question was asked, just a couple people voted to explicitly kill O(N^2logN) solutions.

            I edited the parent comment to link my solution during testing, and you can see i tried to make the constant as small as i could, since the time limit was too tight. It's like a gamble, sometimes will work, sometimes it wont.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              Do you mean n^2 log n was decided to be allowed or not? I personally don’t agree with putting it in “constant factor limbo”, and a decision should have been made to explicitly make it pass comfortably, or make it fully dead.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, hide # ^ |
                 
                Vote: I like it 0 Vote: I do not like it

                The intended one was O(N^2) as said in the editorial. If someone went trough the trouble of squeezing a slower solution into 1 second, that was also fine.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, hide # ^ |
                   
                  Vote: I like it -8 Vote: I do not like it

                  I disagree with this approach. IIRC from codeforces guidelines, all intended solutions should run in at least half of time limit and all slow solutions should run in at least double the time limit. At least in my opinion, competitive programming should be mainly about the algorithms and not about squeezing borderline solutions to run. This would be like having the infamous welcome home chtholly problem that got cheesed with AVX which is arguably not as “in the spirit of competitive programming” as the real solution.

                  → Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

D has 2000 solves, every 1 in 4 contestant solved D. That explains the standing.

→ Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    i personally know some people, they were saying to me d was easier than b you should have tried d, bruh i think ai solved D wasily, its answer was just to print the descending order, i asked them how did you know, they did not have an answer.

    → Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I want to remind you https://mirror.codeforces.com/blog/entry/146629#comment-1311335.

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

at least you solved ABCDE, I couldn't even get the idea of D.

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

lol, i read the problems and i feel they should be directly made grandmasters lol, btw well done mate u got superb rank :)

→ Reply