hmehta's blog

TCO18 Algorithm Round 2A and Parallel Rated SRM
By hmehta, history, 6 years ago, In English

TCO18 Algorithm Round 2A and Parallel Rated SRM

TCO18 Algorithm Round 2A and Parallel Rated SRM is scheduled to start at 12:00 UTC -4 on June 2, 2018. You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.
Click here to see what time it starts in your area.

Algorithm Round 2 Qualified Competitors: https://tco18.topcoder.com/algorithm/online-round-results/ and https://tco18.topcoder.com/algorithm/byes/

Don’t know how to compete in Topcoder SRMs?

Check out this guide to successfully compete in an algorithm match.

You can compete using:

  • Topcoder Web Arena(Beta) - Please watch this video for step by step guide.
  • Topcoder Java Applet - You can refer to this guide here to set up the applet. (Note that those who have Java 8 installed on their machine will see a security issue — You will have to add Topcoder in security exceptions in Java Control Panel. Please refer to the details in the guide here)
  • Vote: I like it
  • +85
  • Vote: I do not like it

Comments Comments (37)
| Write comment?
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Is there any sever issue in Topcoder?

when I click on your link for "Check out this guide to successfully compete in an algorithm match." it gives me "Page not found" and can't login in web arena showing login timeout

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

No samples with a < n on hard was evil thing to do :)

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

    Would I disappoint you if I say that your solution didn't pass even the given samples? For (2, 2) you output (2, 4, 6) and that is not a triangle.

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

      That means I cannot read batch test results

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for competing! :) Here are the round editorials: https://www.topcoder.com/blog/2018-tco-algorithm-round-2a-editorials/

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

    That's fast work getting out the editorial! I had a different approach to the 1K, since I didn't have any ideas for constructing a solution: firstly check a few conditions to reject cases which clearly have no solution, then do a randomised search for a solution! Since there are only 1000 possible test cases I was able to check that they all work.

    The cases I checked for were: - If the sum of squares of the smallest 2n numbers is >= the sum of squares of the largest n, then it's impossible to get all triangles obtuse. - If a=1 it's impossible, because no triangle can have side length 1 with the other sides being distinct integers. - If a=5, n=2 there are no solutions, but the first check doesn't detect it. This is a special case I found when doing the check of all 1000 possible test cases.

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

      Another solution was greedy: keep checking if (i, i + k, i + 2*k) split is fine for sorted remaining lengths and while it is not remove first possible triple (lexicographically minimal).

      It doesn't work for n <= 6 sometimes but you can do full search for them

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

WOW! Intuitive without proof make me pass 500 :)

Greedy pair until less than or equal 10 vertices left. Then try all permutations.

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

    Should work until 4 vertices as well obviously since for 3 or more remaining vertices answer always exists

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

    In 500 I've used recurrent bruteforce from the very beggining.
    Select the edge with the least value, call the next edge selection, if not found, then select the next edge with the least value.
    The fails of edge selection can be only when 3-4 unassigned vertices left.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It's simpler. Check if answer exists, greedy pair until done. Whenever you try to add an edge, check if it's valid and the answer exists afterwards. Since checking if an answer exists is O(1) and checking if adding an edge is valid is O(1), this is O(N2), not O(N3) — for all but the last O(1) edges, "does answer exist?" will always return true.

    → Reply
»
6 years ago, # |
  Vote: I like it +61 Vote: I do not like it

In the TCO2018 rules, I found this line:

** To get the prize, Competitor must have positive points after Online Rounds. In the event of a tie, all competitors with that score will earn a t-shirt.

But it also says t-shirts are awarded to all round 3 participants, does this means that in order to get a t-shirt, you need to participate in round 3 and get positive score in round 3?

(It makes no sense if the "Online Round" in ** stands for any Online Round since it's not possible to advance to round 3 without any positive score.)

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

    Agree with your point. I will have this rectified and make it clear.

    However — It means that you should participate/compete in round three and if you score positive points in round 3 you will win a T-shirt.

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

      Got it!

      Thanks for your clarification.

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

      I’ve just got an email that says that all round 3 participants will receive a T-shirt. So what information is actually correct?

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

        Sorry if you found it confusing! The email says that you can refer to the complete TCO Rules (which needs to be updated to make it less confusing) :)

        To clarify: You have to score positive points in round 3 to win a T-shirt.

        The rules page will be updated very soon to make it less confusing! Sorry again for the confusion!

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

          What if you score positive in 3A but <=0 in 3B?

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anybody know how you can copy your code? I mean I can see it by entering my room. I usually don't save sources that I've submitted in online contests, so right now I'm staring at my failed source not knowing how am I supposed to take it and submit it in practice to see what test it's failing.

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

    I think you can wait for it to appear in round stats/results at TC website and copy it from there, if it isn't in the problem's coding area.

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

      I've also tried at some point to copy even older code. I can't see how to check codes from older round stats. Only top 5 or fastest or something like that appear. Could you tell me what's the procedure to see a code based on the round stats if that is really possible?

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

        I think you can find them through room stats, then individual stats for that round. If the old stats/results module wasn't deleted, it's definitely possible.

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

    Just open your code via the Select One dropdown instead of via room/div summary.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why c++ clock() doesn't work precisely in topcoder? I lost hard because of that.

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

    Also topcoder servers used to be really fast, my old slow laptop now twice faster. :)

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

      My new fast laptop is twice faster than a typical online judge (CF, Yandex...). I've already painfully learned to check code performance on the judge, not locally, if I'm not sure if it fits within TL.

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

    Came here to say the same thing :)

    My guess is there is some time scaling going on -- at least, it's very weird that TC can show a 0.5 second execution time and tell me the code does not pass 2 second time limit.

    It would be nice to know for sure, though.

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

    I remember that someday clock() was working very slow on topcoder, maybe this is the case?

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

    In TC Marathons we use rdtsc assembly instruction in C++. That is because they count the Wall time, not the CPU time. In theory C++ has an amazing std::chrono library, but in practice its system clock returns garbage on the TC servers, so the only way is to use the assembly.

    → Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Is this a bug? The order of score of problems in web arena is wrong.

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

    No, it's topcoder's feature.

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

      Sorry for the late response on this.. Unfortunately, that has been a bug. The web arena is still a Beta version. We are rebuilding a new arena to bring the best experience to you once again. Until then, I would recommend everyone to use the applet arena.

      Right now, we are trying to improve the experience daily — like timely reminders, editorials etc.

      But stick with Topcoder as we are working on improving to bring the best experience to you guys.

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

        Is it (or will be) possible to use plugins like moj in web arena?

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

          Yes! The new arena we are planning — will support plugins :)

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

            Let's hope the arena will come soon(1-2 years for topcoder) enough.

            → Reply