hmehta's blog

By hmehta, history, 5 years ago, In English

Hey All!

Topcoder SRM 771 is scheduled to start at 11:00 UTC -5, Nov 27, 2019. Registration will open 24 hours before the start time in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to misof for writing the problems for the round

This is the fourth SRM of Stage 1 of TCO20 Algorithm Tournament.

Stage 1 TCO20 Points Leaderboard | Topcoder Java Applet | Next SRM 772 — Dec 11, 07:00 UTC-5

Some Important Links

Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)

Good luck to everyone!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

It will begin right after (25 minutes) the Educational Codeforces Round 77, will be a busy day for competitive programmers :)

Anyway, the reminder — the contest will start in 6.5 hours.

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

Sad...

I fail on 500 pts problem just because I write wrong generator code as following:

for i1 in 0 .. L0-1:
    for i0 in 0 .. L0-1:
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I failed because of MLE.

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

      I love "I failed" threads!!

      I failed because projects can take 0 workers, and they will get done on their own, apparently.

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

        This problem just had so many fails we can easily keep this thread going until messages "the thread is too long" start.

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

          I will also contribute something here.
          I started off with topcoder today. Participated in few srms last year without any plugins or anything.

          Today -
          Plugins ready. Done A. Wrote a greedy. Failed on sample test 1 and passed rest.
          Ok. Let's check how scoring works. Submitted same soln 3 times in the last 10 mins.

          Challenge phase - dreamoon challenged my B. Unsuccessful hacking attempt. dreamoon challenged my B again. Successful hacking attempt.

          fetetriste blindly challenged my A twice. Unsuccessful hacking attempt. After the challenge phase, he wrote he selected the wrong solution for the blind challenge. System test passed on A.

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

            I didn't blindly challenge you: I saw you return 1 for negative bounds and challenged against this (twice to be sure, it didn't influence my place much anyway).

            The wrong solution that I chose for blind challenge was 1000 (we had two in the room and I chose the passing one. I tried the challenge in the practice room and it works against the wrong solution).

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

            When I looked at your code and found your code pattern is far away from correct solution. So I blindly challenged you with a large random test which I had prepared before challenge phase. But your code return correct solution...

            Then I looked at your code carefully and found you just use simple greedy to solve it. I had checked this solution will get WA on sample 1 before challenge phase. So I just choose sample 1 to challenge you again. And this time It was successful. At this moment, what I think in my mind is: What a strange guy. He didn't pass the sample but still submitted it.

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

              You would be surprised to know how often people submit a code that doesn't pass all the samples. It's just weird that TC never does anything to prevent this.

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

              I saw that two people submitted nothing, then they hacked each other immediately after beginning of challenging phase :)

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

How to solve 1000? I just started with a random point and repeatedly added the closest one not yet visited until I got line that's short enough.

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

    That. It passed, so that's how you solve it. Write some simple random shit that has a good enough chance of working, it's the optimal strategy for this problem.

    For a more complicated and more bug-prone deterministic solution, the editorial link is among system messages, button "Messages".

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

      Not in the web arena I'm afraid.

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

    Split the triangle into 4 triangles with sides $$$x/2$$$ and $$$y/2$$$ and solve for them recursively. In each of the smaller triangles we will have a path of length at most $$$(x/2)^2 + (y/2)^2 = (x^2 + y^2)/4$$$. We need to add condition that our polyline starts at the right corner of triangle and ends at the upper corner and go through smaller triangles in the correct order for it to work.

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

      This is incorrect, consider the following test case:

            n = 5
         Xmax = 50
         Ymax = 1000
      Xprefix = 1,0,25,50,0
      Yprefix = 0,1,499,0,1000
      

      Instead of medians, it has to be altitudes, like in the editorial.

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

        I'm glad that we were in different rooms. :)

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

          Not only that, but also that nobody had the same solution in my room :) (successful challenges are added to system tests) The other two solutions like yours are ecnerwal's and maroon_kuri's.

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

            Omg, so there was no such test in system tests? Shameful. It's kind of enticing way to solve it, more natural than altitude, but noticing we can't make "shortcut" in an obtuse triangle and dealing with that problem is significant part of the solution.

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

        Where can I find the editorial, Could you please provide the link?

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

Can someone provide me with the link of editorial docs? I didn't save announcement link and now idk how to access that.

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

As we have been complaining a lot about TC problem quality recently, I think this round is a pretty good one. Gotta give credit where it's due.

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

    I don't like that 1000 had generated inputs, it made challenges much harder even though they were important in that problem. Otherwise, yeah, nice problems. It's not even a rare occurrence, TC is just a good punching bag.

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

What the f*** was that round?! Both majk's and aid's solutions MUST be implemented and defeated. I understand that sometimes it's hard to make good tests, BUT MAJK'S SHIT IS THE FIRST THING THAT SHOULD COME TO MIND. I see three options.

1: Problemsetters didn't mind to write this solution. Conclusion: bad problemsetters.

2: They wrote it, but were too lazy to make the test against it. Conculsion: bad problemsetters.

3: They wrote it and decided that it's almost impossible to make tests against it. Conculsion: they shouldn't use this problem, bad problemsetters.

I'm sorry about my rude words, but TC again doesn't care about contests and loses quality. (Not even talking about the system now). Guys, please, wake up! Don't be surprised that people don't want to participate.

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

    I think you're being too harsh.

    The first paragraph of the editorial mentions that "some local optimization techniques" can get accepted -- but no accepted solutions use local optimization, even though there were some attempts.

    Out of 8 accepted submissions, 2 are correct, 3 use medians instead of altitudes, and 3 use different kinds of greedy.

    It's a bit sad that one could get away with medians and greedy, but there's no way to make these solutions fail unless you know about them. The only way to have a lot of incorrect solutions is to have a lot of testers, and even this is not always enough. I, for one, didn't come up with either: if I had to implement an incorrect solution, it would be local optimization.

    Saying "you didn't think about my incorrect solution -- you're a bad problemsetter!" is not very fair.

    And then, as the editorial says:

    (Which is why I didn’t use this problem in a more serious round ;) )

    Indeed, this problem is not suitable for TCO finals, but today we had a regular SRM. I enjoyed this problem, and my enjoyment beats my frustration over accepted incorrect solutions of others. If we disallow problems without provably perfect test data, the world will be a more boring place.

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

      It's true that sometimes in order to fail some specific solution some tests are need to be created explicitly against it and coming up with this heuristic solution as a developer of a problem is required for it to fail system tests. And it's true that sometimes people come up with some random ideas that just can't be predicted. But no, this was not the case this time. Dividing by medians and greedy "go to the closest one" are things that definitely should come to a mind of a setter that knows a solutions and devotes 5 minutes to think about incorrect solutions. Maybe it's dangerous to use well-prepared version of this problem as a TCO finals problems anyway, but setter shouldn't just shrug it off and not devote any time to fail these.

      By the way on an unrelated note I am fairly confident local search should do wonders in this problem. This exact problem (with a slight difference of points being located in a square, not in a triangle) was used as an optimization problem on Polish OI camp (ONTAK 2012) and 2-OPT outperformed everything else by far.

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

        by the way, is it really dividing by medians?

        I imagine it as dividing into two triangles and each of those into two again, with three medians. But then intermediate triangles are not right, so yeah, calling it dividing into four right triangles with two midlines and a median (or a diagonal) is more natural.

        are things that definitely should come to a mind of a setter that knows a solutions and devotes 5 minutes to think about incorrect solutions

        I'm not convinced these two ideas should come to mind and are obvious to everyone who knows the solution. I respect it if it was obvious to you :)

        Is ONTAK problem also about optimizing the sum of squares of distances, not just the sum of distances?

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

          I imagine it as dividing (...)

          Ah, you replied to part of my comment which I deleted cause I realized "median" is a line that connects vertex with a midpoint of opposite side instead of line connecting two midpoints, sorry for that :P.

          Is ONTAK problem also about optimizing the sum of squares of distances, not just the sum of distances?

          Yes. Even though it was an optimization problem where contestants where expected to write heuristic solutions, Kuba Łącki (an author afair) presented a solution with provable bound $$$4s^2$$$, where $$$s$$$ was a side of a bounding square which was exactly today's problem where X=Y after dividing square with a diagonal :).

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

      Meh, maybe it's true, I'm sorry. Anyway, I wouldn't use the word "my". I just deduce that the tests were weak, and problemsetters haven't paid enough attention to the preparation. If they'd do, they'd probably come up at least with one of these solutions. It seems to happen on TC too often.

      I know that the conditions are hard. I've heard that "in TC's problemsetting system, the author is able to upload only one solution" — and ofc it should be the model solution.

      I don't know whether it's true, but if it is, guess what do I think about it. Maybe I'm not the best person, I'm too young to know the TC's era (as I started when CF was already grown-up), but due to histories, it was the best page and having Target was the highest possible glory.

      Now their system seems to have a lot of bugs, TCO is a giant mess (look at the dates in the last marathon TCO), many tasks are just tiring or badly prepared. I just think that they should try to save their good reputation. Not with e-mails and advertisements, but with quality of what they give us.

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

        I know that the conditions are hard. I've heard that "in TC's problemsetting system, the author is able to upload only one solution" — and ofc it should be the model solution.

        It also has to be in Java. More precisely, it had to be in Java last time I checked, but it's TC so these two statements are basically equivalent.

        I'm sure TC relied on challenges back then to fail bad solutions the testing didn't catch, too (successful challenges are added to systests). The problem is that with less contestants, there's less challenges, doubly so because it's less likely to have multiple submissions on hard in the same room. If you use problems that are easy to seemingly get right (any problems with weaker samples and no pretesting), this matters a lot.

        Anyways, you'd be surprised how easy it is to find problems with really stupid "machine learning" or just plain random solutions. 64856439 63687717 (seriously WTF?) 54893862 are just what I remember off the top of my head. It's surprisingly easy even for a lot of testers to miss something stupid and in particular for a class of solutions that do something random but differ in implementation or only in the seed, it's completely possible to write and break one of these solutions while still allowing a different one to pass. Having countertests to solutions that are countersolutions to tests (a.k.a. challenges) is The way to stop such wrong solutions from passing.

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

Btw the 1000 seems to be Problem 20 in this handout.