hmehta's blog

By hmehta, history, 6 weeks ago, In English

Topcoder SRM 813 is scheduled to start at 11:00 UTC-4 on Sept 17, 2021.

Registration is now open for the SRM in the Arena or Applet and closes at 10:55 UTC-4. The coding phase will start at 11:05 UTC-4, so make sure that you are all ready to go. Click here to what time it starts in your area.

Please take a look at our How to Compete guide to understand Topcoder Algorithm rounds better.

Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),

Best of luck!
- The Topcoder Team

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

»
6 weeks ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

How to solve the 600 point (div 1) problem ?

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

    $$$dp[S][C]$$$ with transitions in $$$O(n^2)$$$ — the number of ways to cover $$$S$$$ points with $$$C$$$ segments.

    For each $$$dp[i][j]$$$ count the number of bad ways to choose segments (the ones where there's at least one uncovered point), then subtract it from all ways to get the actual value.

    To count that, iterate over the position of the first uncovered point and the number of segments to the left of it. Use already calculated dp to cover everything on the left, then some easy combinatorics to place the remaining segments on the right, then cnk to choose the segments to place on the left from all segments.

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

      Thanks

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

      That is 100^4 right? Is there a 100^3 solution?

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

        Yeah, it's $$$O(n^4)$$$ but the constant is $$$\frac 1 4$$$, so it passes freely (in C++ Kappa).