hmehta's blog

TCO19 Round 2B
By hmehta, history, 6 years ago, In English

TCO19 Algorithm Round 2B and Parallel Rated Round is scheduled to start at 11:00 UTC -4 on June 4, 2019. Registration is open for the Round in the Arena or Applet and it 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://tco19.topcoder.com/algorithm/byes/, https://tco19.topcoder.com/algorithm/round-1a and https://tco19.topcoder.com/algorithm/round-1b) are eligible to compete in Round 2B. Those who have already qualified for Round 4 (https://tco19.topcoder.com/algorithm/round-4) from online stages are not eligible to compete.

All the best!

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

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

i have not qualified for the round 2 is there still a way to qualify for the regionals?

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

    TCO19 Algorithm Rounds are not related to regional qualification! Round 1a, Round 1b and Members who got a bye are eligible for this!

    Regionals have their separate qualification — This year performance in the period of Feb-April was used for qualifying members for the regionals :)

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

      what is the exact criteria for the qualifications to the regionals?

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

        Here are the details: https://tco19.topcoder.com/regional-events/

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

          so now there is no chance to qualify for tco ri8?

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

            Yes, however if there are seats left we will open it for members on first come first serve basis!

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

              what do you mean by that? so anyone would be able to attend the regionals?

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

                Which regional are you looking to join?

                So initially we will roll out invitation to the members on the leaderboard: -https://tco19.topcoder.com/regional-events/south-america/leaderboards

                -https://tco19.topcoder.com/regional-events/japan/leaderboards

                -https://tco19.topcoder.com/regional-events/china/leaderboards

                Later some members backout or are not able to attend then we open the leftover tickets on first come first serve basis.

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

                  i am looking for india regionals. could you pls give me a ticket if someone backs out?

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

                  It was two days ago....

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

Upvote if you didn't like first problem

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

    It take me several minutes to correct condition number_less_than_goal $$$< (n + 1) / 2$$$, number_greater_than_goal $$$\le n / 2$$$ :)

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

    I found the second problem to be much easier than the first one

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

Can Someone explain approach for 2nd Problem?? Thanks in advance.

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

    Just try all divisors of $$$n$$$. For each divisor $$$d$$$, call the same algorithm recursively on $$$n/d-1$$$. During steps other than the first, don't consider $$$d=1$$$.

    In fact, this problem is OEIS A167439.

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

      Is there any analysis for the complexity of the algorithm?

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

      Yeah, I saw that pretty quickly but then I spent over 30 minutes staring at the problem and trying to figure out what additional shortcuts needed to be done and couldn't come up with any.

      I felt pretty certain that doing that would require calling the getAllDivisors() function on too many unique values to be able to run in time because of the subtractions by 1.

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

    Let test N and N-1 separately, so we can assume that there's no 1 in sequence.

    Take a look at $$$a_0$$$, each consequent number is divisible by $$$a_0$$$, so N is also divisible by $$$a_0$$$.

    Now if we divide everything by $$$a_0$$$ we'll receive another sequence with sum of $$$\frac{N}{a_0}$$$ and first element 1. Let's drop that 1 and solve the problem for $$$\frac{N}{a_0} - 1$$$. Just build dp on top of that.

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

Is there a link for schedule of future TCO online rounds? The TCO algorithm page is absolutely unnavigatable.

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

Hard looks interesting. How to solve?

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

    Outline (I'm on the phone now):

    Obviously, optimal strategy is same for both players.

    If d is max difference, you will never play more than 2d+1 because playing 1 is at least as good for all possible choices of the other player. (This is the main observation you needed.)

    Then, write linear equations for the 2d+1 probabilities using "principle of indifference", there is a unique solution. (Some more proofs needed to argue correctness.)

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

    Based on discussion with Egor.

    Basic lemma from game theory: For all $$$p_k > 0$$$ we should have expected winning of exactly $$$0$$$ against pure strategy "say $$$k$$$".

    $$$p_1$$$ is not zero, otherwise we can shift everything to the left. So, $$$\sum_{k=2}^{d+1} p_k \ge 1/2$$$. Now it is easy to see that for all $$$k > 2d+1$$$ $$$p_k=0$$$ (because we are certainly winning strictly more than 0 against this pure strategy). Now we can see than $$$p_k=p_{2d+2-k}$$$ (because everything is symmetric), and we have $$$d+1$$$ variables and $$$d+1$$$ linear equations.

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

      Can you explain why the expected winning is exactly 0?

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

        Because the two players are symmetric? So their expected winning should be the same.

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

          No, I'm asking why the expected winning is zero against the pure strategy.

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

            The optimal strategy is a linear combination of the pure strategies. The optimal strategy scores $$$0$$$ against itself, and never less than $$$0$$$ against any strategy. The rest is linearity of expectation.

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

              That's not the complete explanation. It is not obvious that optimal strategy must not ever lose against every possible strategy, opponent don't know if we use optimal strategy or not. But nevertheless it is true, by minimax theorem.

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

      With proper eps in LP I passed the test cases (Maybe it will fail in some test case).

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

If I'm not wrong then positive score in round 3 fetches a topcoder TShirt?

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

    Right. Also looks like getting positive score was enough to qualify to Round 3 from all prev rounds. So you weren't actually competing against other people, only against yourself :D

    Upd. not really, only 200 people qualify to Round 3, I thought it was 250

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

Where we can find editorials for this round ??

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

I think it's fair that if less than 200 have positive score on round 2A (in our case 132), then on round 2B 200+(200-round_2a_qualified) go on. Proof by (incorrect) feature scaling :)

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

    That would be a clear violation of the rules!

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

      I don't see how it violates a 404 HTTP Error, but it is morally OK, as Round 2A failed to get the top 200 contestants, and I haven't checked but I'm almost sure some failed qualificants from round 2A advanced from 2B

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

Does Topcoder still have problems with sending T-shirt to Russia?

→ Reply