hmehta's blog

TCO20 Round 2B and Parallel Round
By hmehta, history, 4 years ago, In English

TCO20 Round 2B and Parallel Round of TCO20 Algorithm Round 2A are scheduled to be held on Saturday, July 18 at 12:00 UTC -4.

Both the rounds will be rated

Please note that you must register for this round in the Arena. Registration is now open for the round in the Arena or Applet and will close 5 minutes before the match begins, so make sure that you are all ready to go. Click here to what time it starts in your area.

Members eligible to compete in Round 2B include:

Members eligible to compete in the Parallel Round include:

Don’t know how to compete in Topcoder Algorithm Competitions?

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

You can compete using:

  • 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.)
  • Topcoder Web Arena(Beta) - Please watch this video for step by step guide

Best of luck to you in the Arena!

  • Vote: I like it
  • -89
  • Vote: I do not like it

Comments Comments (76)
| Write comment?
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Members who have qualified to Round 3 from Round 2A — Members who did not qualify for Round 2
Isn't this a wrong statement due to that "Not"?

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

Members eligible to compete in Round 2A include:
I think you mean 2B.

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

Edit:Got a clean chit for round 3.

I had a rank of 105 in round 2A. But I'm not on the list. Can you please verify this?

My topcoder handle cybertron1609

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

    Hey, Your participation was found to have violated Topcoder policies against collaboration and was therefore nullified.

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

      Was it plagiarism? Can I know which to which ID it was matched?

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

How many people will qualify to r3?

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

Coding is supposed to have started, but I still can't enter a room. Yes, I am registered.

UPD: Works on latest version of the applet, but there are other bugs then.

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

    same happened with me . hmehta arena is buggy and sometimes bugs happen with applet . It is not expected in such important contests :) . Hope these issues will not be there in coming future .

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      Very true. I think, this contest should be made unrated. And these bugs should be taken care of in future contests. hmehta

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

        We are looking at the logs to see what went wrong. I think we are closer to find the issue. Apologies and we will make sure it doesn't happen again.

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

          We understand, problems might have arose, but isn't it possible to unrate this round?

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

      At least it's not a problem with the problems, but with the usual TC shit.

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

I am also unable to enter the round. I can find myself in registrants list.

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

The Arena Site is down. Can you please extend the "Challenge Phase".?

UPD: It got refreshed, just a sec before the Challenge Phase started.

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

Challenge phase: no timer visible. It says "coding phase 0:00:00". I got no notification about challenge phase starting.

I can't even hack. I can open submissions, but there are no buttons at the bottom (yes, when the window is maximised). Thx TC!

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

    Faced the same problem. It started working after re-login.

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

      But, I believe, it shouldn't be like that. It should work in the first place itself. I know, they work hard to handle issues like this. But I think, this issue should be seriously looked upon! Problems were great.

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

        I know, they work hard to handle issues like this.

        Are you sure?

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

          I assumed so, because all good CP websites do so. But, Idk why these issues aren't resolved even after so many complaints.

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

      Yeah, for me too. "Have you tried throwing the laptop out of a window, picking it back up, rebooting and re-logging in?"

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

      Same issue happens at every phase, I was stuck at "challenge phasee 0:00:00" after it ended, and after relogin it stucked at "system testing 0:00:00".

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

    Faced same hack issue in Round 2A.
    Used web arena to hack and in the end, that hack me to qualify for round 3.

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

I am not getting how to challenge someone, I opened the someone's code from my room, I scroll down the whole code and don't see challenge button.

Can anyone tell me where to find it ?

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +101 Vote: I do not like it

In my opinion terrible first two tasks.

First one, just boring, with extremly weak samples.

Second one is interesting for solving, but with totally unnecessary type of output. I do not see reason why are you making checker harder ?

I think my short trip to TC will be finsihed soon, after last two-three rounds.

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

    Shit output for 550, why not only pair of cells?

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

    Would approve thousand times -- the first problem is something my teacher would give us on a test which he attended totally unprepared. I don't even want to comment on the output on the second one, why would anybody want to make each person spend 3 more minutes typing several for loops?

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

Are you crazy? How is med supposed to be easier than hard in your opinion? Hard is just read and implement, while in med you have to think and either do some nice stuff or do some shitty construction, where both are much harder than "hard" imo.

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

    Topcoder these days — Let's pick one div2B problem. Make it implementation heavy just for the sake of it. Then use it a Medium.

    I rather preferred to quit instead of coding Med.

    A better version in my opinion -
    Ask R*C matrix of integers. Same adjacent integers denote they are in the same room.

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

      Wut, is med implementation heavy in your opinion? I hope that we both are talking about div1.

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

        For me 550 pts -
        "Ask R*C matrix of integers. Same adjacent integers denote they are in the same room." to output in Given form is just a very very boring implementation problem.
        On topcoder with no pretests, one has a very good chance of failing this problem. Hence, implementation heavy.

        Constructing rooms with K pairs were easy.
        I was in the parallel round and preferred to quit after solving 250 pts (Which later failed.)

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

          Wut? Is this construction just a boring implementation for you? What's your construction then?

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

            The current output format was very boring along with implementation heavy. That's the reason I quit. I suggested one alternative output format which in my opinion is much better if they didn't want to change the problem.

            My soln with my output format -
            1 2 3 4 5 6
            7 8 9 10 10 10
            10 10 10 10 10
            10 10 10 10 11

            Keep going in starting at last k will be 0, 1 or 2. Just create those blocks in the end.
            From this format to current format is very very boring exercise.

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

              Why this is correct?

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

                In this, you always reduce k by 1,2 or 3. Adding 8 created 2-8,7-8 and 8-10, 8-10 edges. Later you broke one 8-10 and added 3-9, 8-9, 9-10, 9-10 edges. Increase by 2.
                Going like this will make k < 3. You can add required no of rooms in the last row.

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

                  Well, there will be quite a lot of corner cases, won't it? For example R = C = N = 2.

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

                  Updated to previous revision.

                  Here you will decrease k by 1 when you create room at (1,1).
                  Then you willl always decrease by 2 (On boundary it will decrease by 1). Atlast k will be 0 or 1. If its 1 just add one room at (r,c)

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

                  But if it is in first column, it will decrease by 1, not 2. Am I right?

                  Upd. Again, if it is on the rightmost column, in will decrease by 2 (not 1 as you say now). Also, it is more convenient to reply rather then edit messages without saying anything about it.

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

          So what, you continue to think that "Constructing rooms with K pairs were easy." after that many corner cases and bugs in your construction?

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

            Quitting after submitting 250 pts was the best decision.
            Those who ACed it need a life.

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

        No matter what your solution is, it is pretty painful to code. Maybe no heavy data structures, but still a lot of tedious code. It is of course not the only difficulty here.

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

          I guess that most of the accepted solutions do not really find the connected components or run any graph searches, so I don't agree with you.

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

        Casework. And it's harder to make a solution without casework than with.

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

          Mine, in the end, is a really nice imo, but still hard. Every row has only one merged interval while prefix and suffix have small, separated rooms. For every two neighboring rows, their intervals can be either merged or not, and ofc can be merged only if their intersection is not empty. So this gives a $$$DP[row][start][end][number of pairs]$$$ DP with $$$O(n^7)$$$ transitions, where it is even more comfortable to use bitsets than to not do it.

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

            My solution:

            • let $$$C \ge R$$$, separate the case $$$R=C=N=2$$$ since it's unsolvable
            • if $$$R = 1$$$, just add walls one by one
            • if $$$R=C=2$$$, the following algorithm will solve it as a byproduct, but we could also hardcode
            • now $$$C \ge 3$$$, let $$$D = 2RC-R-C-N$$$; we're removing walls from the full state
              • first remove walls from the top row, each removal decrements $$$D$$$
              • for each next row, if $$$D \ge 2C-1$$$, remove all $$$2C-1$$$ walls for this row, since it decreases $$$D$$$ by $$$2C-1$$$
              • as soon as $$$D \lt 2C-1$$$, we want to stop after processing this row
              • if $$$D$$$ is even, remove top+left walls of rooms in this row one by one, each such pair of removed walls decreases $$$D$$$ by $$$2$$$ (except the last room, but it won't be removed since $$$D \le 2C-2$$$)
              • if $$$D \ge 3$$$ is odd, remove a wall from the top of the 2nd room in this row ($$$D$$$ drops by $$$3$$$) and repeat the above with next rooms in the row, you'll always end up with at least 1 room from the left and 1 from the right remaining since $$$D \le 2C-3$$$ and $$$C \ge 3$$$
              • if $$$D = 1$$$, remove the leftmost room in this row ($$$D = -1$$$ now) and add the rightmost room in the previous row ($$$D = 0$$$ now)
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Guess what I think about ifologies :/

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

                I'll guess that it's about the same as what I think about them.

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

            I have absolutely no idea what you are describing and I have a strong feeling you don't search the full space of room partitions and don't have a proof you cover all numbers that are possible to be achieved.

            EDIT: OK, I think I managed to understand it, but wtf is that supposed to be? Some completely random subset of search space.

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

              Yep, and I have a proof (by using asserts) that it covers all possible cases.

              I personally think that this is one of my favorite types of solutions.

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

                Well, that's not a valid proof in a way I meant. For the sake of winning with tests / getting it ACed on topcoder that's in no way better than my local search and for sure is much more complicated.

                And what is that "favourite type of problems" you are talking about cause I don't see any prevailing theme here? Is it "random shit"?

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

                  It is a proof imo. My code admits that it found a solution for all possible test cases (except $$$2$$$ $$$2$$$ $$$2$$$), as there are only O(30^4) of them.

                  By theme I mean the constructive problems where you limit yourself for some smaller space of solutions for which you are able to write some DP/something which turns out to cover all possible cases.

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

                  Ok, that kind of makes sense, but I was just triggered at the way you presented it, like it was obviously correct solution for the general case and that it is provable, without any indication that what you're doing is just keeping fingers crossed it works for some subset of search space. And of course proof in a way I meant is for general case, not restricted to n<=30 :facepalm:

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

                  Yep, ofc it proves the correctness only for the correct cases.

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

Had applet problems from the start, which seems to happen more and more in topcoder.

Also what's the goal of the contest ? If it's to differentiate between top 200 vs rest the difficulty was way to high for 550. Having weak samples for 250 adds to this issue. In these contests 550 and 950 shouldn't be solvable by so few people, then we only differentiate between speed of A.

→ Reply
»
4 years ago, # |
  Vote: I like it -65 Vote: I do not like it

Loved first problem!

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

    Is it sarcasm and you are starting to be on the bright side? xd

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

    Really? I read the problem and it was clear after a minute what is to be done. All that was left was careful implementation — avoiding off by one errors, etc (I took lot of time for testing because the samples were very weak and apparently it paid off).

    So sure, if one wants to practice implementation — only then it can be called a good problem.

    Oops, didn't get the sarcasm.

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

    IMO it's the perfect example of a problem that is ad hoc but still very boring.

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

what will happen for ties? there are 203 participants having score >= 50.

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

Where can I find a leaderboard that shows all participants (in the web arena)? If I enter the match, it shows that it's not complete, except it totally should be:

The leaderboard you are trying to view is currently unavailable. Please try again after the match is complete

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

When I submit 550 into practice room it gets through 308/309 tests correctly, stops for a few seconds and displays 550 in red as if it failed last test, but it doesn't show me failed test as it always does (but shows all previous 308 ones). Why?

EDIT: Ok, it was not the issue. I failed one test in the middle, but somehow arena didn't stop processing following tests as it always does.

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

From editorial: https://www.topcoder.com/2020-tco-round-2b-editorials/ Problem: ROOMPAIRS Question: Why we need separate corner cases for (3,2,2) and (3,2,5)? Are they solvable?

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

Med can be easily solved by local search. Too bad I lacked time cause I was 15 minutes late to the contest :(

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

Thanks for the round!

My screencast: https://youtu.be/qBhDm7C7Caw

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

My solution for med: You can always write $$$N=(2C-1)q + r$$$ where $$$|r| \leq C-1$$$ and $$$q < R$$$. Take q rows with all vertical lines. Now you have to either add or remove $$$|r| \leq C-1$$$ pairs. Which can be done in one row. Removing can be realized in the first row and adding can be realized in the last row.

ex: $$$R=4, C=3$$$, $$$N = 11 = 5 \cdot 2 + 1$$$

We start with $$$5 \cdot 2$$$

123
456
777
777

and then add one pair in the last row.

123    
456
788
788

Other example: $$$N = 9 = 5 \cdot 2 - 1$$$ We start with the same 10, and then remove one wall in the first row.

113
456
777
777

But there is an edge case where $$$q=1$$$ and $$$r<0$$$ (In such a case: removing a wall from the first row decreases the number of pairs by 2). To handle this you can assume that $$$R \geq 3$$$ and add another pair in the last row if needed. ex. $$$R=3, C=5, N = 6 = 9 \cdot 1 - 3$$$. 

11145
66666
76666
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just Curious, who was/were the author(s) of this Round?

→ Reply