hmehta's blog

Topcoder SRM 768 — Sponsored By Google — TCO20 Stage 1
By hmehta, history, 5 years ago, In English

Hey All!

UPD — Editorials https://www.topcoder.com/single-round-match-768-editorials/

Topcoder SRM 768 is scheduled to start at 11:00 UTC -4, Oct 10, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.

Interested in working at Google? Well as a #TCO19 sponsor, they are looking to hire folks like you! Join us for SRM 768 to opt into their exciting job opportunities!

Thanks to Errichto for writing the problems for the round. Also thanks to xudyh and misof for testing the problem set.

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

Stage 1 TCO20 Points Leaderboard | Topcoder Java Applet | Next SRM 769 — Oct 19, 07:00 UTC-4

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
  • +94
  • Vote: I do not like it

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

As I said in the other comment, I'm quite proud of problems. They should be fun to solve, so consider participating.

Also, for a moment I thought that misof finally participated in some CF round and got red :D

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

    Yeah, they were pretty nice. I wasted a lot of time on various slightly wrong assumptions in 500, then switched to 250 and all of a sudden solved both lol (I guess — I'm outside and can't open the arena onva phone).

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

    500 was nice — why do fractions instead of floats though?

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

      Because you could squeeze $$$N^3$$$ then by skipping states with low probability.

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

    Wonderful round! Thank you and congratulations.

    D1 500 especially with the bear Lemac had clean and delicious solution.

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

Hi. I know this may not be a good question but I really cannot find the registration button on Web Arena (in fact I cannot even find this match). If I remember this correctly, the upcoming SRMs would be shown in the Active Matches section but I can only find the past SRM767. Thanks for your help.

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

    Registration is only available starting 24 hours before the competition

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

How will the score for each SRM contribute in TCO20 leaderboard? And these points will be used for selection in TCO regionals like they were used in TCO19?

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

    The points will be awarded according to your placement after the match:

    Division 1:

    • 1st Place: 5 points

    • 2nd-10th Place: 4 points

    • 11th-25th Place: 3 points

    • All other positive scores: 2 points

    Division 2:

    • 1st Place: 3 points

    • 2nd-10th Place: 2 points

    • All other positive scores: 1 point

    Points you gather in the next stage((Jan — March) will be used for TCO Regionals Qualification. More on that will be announced later.

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

Gentle Reminder: The Round begins in less than 2 hours and 50 mins

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

Hints:

div1-250 MeanMedian
div1-500 PBG
div1-1050 LShape

Editorial for div1 problems: https://docs.google.com/document/d/1XbeqZMHsNjv2J3h8x0PsJnBn4IV8llJx9hT39iQkOcY/edit?usp=sharing

→ Reply
»
5 years ago, # |
← Rev. 9   Vote: I like it -27 Vote: I do not like it

_

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

Div2 1000 solution: Let $$$dp[i][s][p]$$$ be the number of ways of grading subjects from $$$i...n$$$, where sum $$$s$$$ is already achieved and $$$p$$$ denotes the number of grades >= the median. You can arbitrarily assign any grade to position $$$i$$$ and add $$$dp[i][s + grade_i][p + (grade_i >= median)]$$$ to the current dp value. Our goal is to reach a sum of $$$mean*n$$$ while keeping $$$p > n / 2$$$ Finally the answer is $$$dp[1][0][0]$$$. Code

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

I have a completely different solution for the medium: let's assume that instead of 3 types of bears, we have N types of bears! Then it's pretty straightforward to compute dp[i,j] — expected place of j-th bear in a tournament with i bears. And then we return the average of the expected places of the polar bears.

Thanks a lot for the round!

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

    My solution is basically the same, just from a bit different concept: we can choose the strength of other polar bears in such a way that Limak has $$$G+k$$$ stronger and $$$B+(P-1-k)$$$ weaker opponents; since everything is symmetrical there, the answer is the average of his expected places for all $$$k$$$. When $$$k$$$ is fixed, it's just trivial $$$O(N^2)$$$ DP, and it's the same DP for all $$$k$$$ since its states are (number of remaining stronger bears, weaker bears).

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

    It's not completely different, author's solution calculates prefix sums of the same DP.

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

      Что слишком умный? Поздравляю с 10 местом папаша. Удачи в жизни, слушайся маму и помагай родителям. Ты никого здесь не обижай. У меня папа MikeMirzayanov, я ему скажу и ты серым станешь, как я.

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

    I couldn't see any direct solution (without subtracting grizzly and brown) and later misof came up with same solution as mine, so I thought there is no reasonable alternative. It turns out that jqdai0815 had something else but we assumed it's the same thing. I'll make sure next time to ask a tester about each solution or just read their code. Maybe I would try to modify the problem a little bit to make only one solution work but well, that's all fine.

    And thanks for explaining your solution, Petr and Xellos.

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

      Your post sounds like something terrible happened and I don't understand why. It's perfectly fine that there is more than one solution unless one of them is significantly simpler than everybody expected

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

        Xd it wasn't supposed to sound that way

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

How would google know/contact if somebody is interested?

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

    We will share your profile details (like ratings, match performance etc) and contact email with Google if you opted-in — (either on google form or the arena survey you must have encountered while registering for the round).

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

      Speaking of Google, could you please fix your Chrome version website? I could have not displayed the problem archive on Chrome. Now I can't even log in. It would be nice to support the browser of your sponsor.

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

        hmehta I think that you may have something wrong with your routing. Today I was going through overall rating and was asking db queries to get me 200 handles starting from something. Suddenly your server became unavailable (obviously because of the heavy load, which I generated...) and I'm still being rerouted to the broken one, even after I refresh. When I opened an incognito window, I was redirected to the working server.

        Could you please fix your infra?

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

list of contestants who solved div1-easy with $$$O(N^2 C^3)$$$ DP after sorting d (instead of $$$O(N)$$$ greedy) sorted by rank ($$$1 \le N \le 49$$$ is the length of d and $$$C = 11$$$ is the number of possible grade)

3 tourist, 5 Um_nik, 9 lyrically, 10 IH19980412, 12 ainta, 29 mnbvmar, 33 ariacas, 34 jy_25, 70 roll_no_1, 80 fetetriste, 100 scott_wu, 101 Persian.Gulf, 103 beet, 109 zhongzihao, 129 CLown1331, 140 Foyaz05, 143 Noureldin2022, 148 seica, 149 Tsutajiro, 160 koyumeishi, 162 prprprpony, 169 kzyKT
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    xd

    Can you please tell me how did you get this list other than going through all submissions?

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

      I got this list by staying up late and OCD :)

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

        OCD people don't post a list like that...

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

    tourist's code seems more like $$$O(N^3 * C^2)$$$

    code

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

    Cool stats! Though my solution is actually $$$O(N^3C^2)$$$ and doesn't sort d.

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

Can someone please explain the solution of DIV1-medium a bit more. As suggested in editorial I have solved sushi from atcoder DP contest but even after that it is unclear to me :(

→ Reply