hmehta's blog

Single Round Match 795
By hmehta, history, 4 years ago, In English

Single Round Match 795

Topcoder SRM 795 is scheduled to start at 12:00 UTC-5 on December 12, 2020.

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

Thanks to jy_25, majk and misof for writing the problem set. Also thanks to misof for testing and coordinating the round.

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

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

Gentle Reminder: The round begins in 35 mins.

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

    When editorial of SRM795 will be ready?

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

    hmehta I guess I am not the only one facing this problem, user in topcoder web gets logout automatically and all the topcoder tabs that were open earlier gets corrupt, I literally have to login 3-4 times a day and problem solving get's severely affected due to this. It's not an internet issue for sure.

    If this is not specific to me can you please look into this issue? Thanks.

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

    Great problem... Thanks for writing it!

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

    It looks like Um_nik and I have a different solution with slightly worse runtime (I failed because I didn't finish implementing a 2x constant factor improvement).

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

      Oh, nice solution. Didn't think of this during testing. Anyway, it would have been practically impossible to separate from the intended solution.

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

    Improving the complexity to $$$O(n2^n)$$$ DSU operations:

    Consider $$$X$$$ to be the set of first $$$n - \lfloor \sqrt{n} \rfloor$$$ nodes and $$$Y$$$ to be the set of last $$$n - \lfloor \sqrt{n} \rfloor$$$ nodes. Precompute MSTs for all subsets of $$$X$$$ and $$$Y$$$. This takes $$$O(2^n)$$$ time.

    Now, to find the discounted MST for a subset $$$S$$$ of $$$[n]$$$, consider only the edges in the MST of $$$X \cap S$$$, the edges in the MST of $$$Y \cap S$$$ and the edges with one end in the first $$$\lfloor \sqrt{n} \rfloor$$$ nodes and the other in the last $$$\lfloor \sqrt{n} \rfloor$$$ nodes. So, $$$O(n)$$$ edges. Store the discounted MST for each set $$$S$$$.

    For each $$$s$$$, maintain a set $$$h(s)$$$ of all nodes $$$t$$$ for which we don't know $$$f(s, t)$$$ yet. Iterate over $$$S$$$ in the order of the discounted MST costs. For all $$$s$$$ in $$$S$$$ and all $$$t$$$ in $$$h(s) \cap S$$$, set $$$f(s, t)$$$ to the current cost.

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

    You are probably the best TopCoder writer now

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

How to solve DIV1 300. My idea was Dynamic Programming, use $$$dp[u][v][len]$$$ to store path from $$$u$$$ to $$$v$$$ of length $$$len$$$. After building this table, I made deductions, the path will be a straight line to some node $$$next$$$ and then loop around a cycle of length say $$$l$$$ and then move to final node. I handled the case where $$$next$$$ is my initial node. However, complexity of my solution was $$$N^5$$$, which I suppose isn't good enough.

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

    O(N^5) or O(N^4lgK) is good enough. O(N^5lgK) might not fit.

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

Div1 Easy: the answer is the sum of entries of the matrix that is the minDays'th power (in the min,+ multiplication sense) of the Floyd-Warshall closure of the original matrix.

Am I right that it was a 300-pointer instead of a 250 because there are several solutions consisting of more steps than this one? Personally, it threw me off a bit: I thought that maybe I need an additional step because it cannot be so simple and surely I must be overlooking something. On the other hand, if I had come up with the harder solution first I would have submitted it earlier because the difficulty would have seemed just right.

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

    Point values are relative to other tasks and a constant challenge 50 pts value.

    That's a great idea. It reduces the complexity to (N^3lgK). During the contest, I implemented O(N^4lgK). Definitely not easy to find out. I think the point values were relatively good.

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

      Another O(n^3 log k) solution with the same code used in different order may be conceptually even simpler:

      The optimal path from U to V can be divided into the first K steps + the rest.

      Let W be the vertex where you are after exactly K steps in the optimal solution. Then what you did is that you first came optimally from U to W in exactly K steps, and then you used the shortest path to get from W to V.

      So you just need the K-th power of the given distance matrix + Floyd-Warshall for the shortest paths. For each U, V you can then try all W and pick the best one.

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

    The application of matrix multiplication might have seemed obvious to you, but it still requires much more thought than the typical graph 250 point questions I have seen till now (almost always were either straightforward Floyd-Warshall/Dijkstra/MST, or easy applications of DFS and BFS).

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

    fetetriste Can you please elaborate a bit why the sum of entries is the answer? I got what misof says, it is possible that there is a lesser weight path with greater length than that of minDays , so we should do one extra step for checking all the possible location for the minDays step and going to final position from there with least cost.

    Thanks

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

      This can be seen from a careful examination of the proof of the standard problem with paths of exactly $$$k$$$ days, i.e. why matrix multiplication has anything to do with it at all.

      The cornerstone of every solution is the assignment

      $$$c[i][j] = min(c[i][j], a[i][k] + b[k][j])$$$

      which is derived by noticing that any path — including any optimal one — from $$$i$$$ to $$$j$$$ can be seen as a conjuction of paths from $$$i$$$ to $$$k$$$ and from $$$k$$$ to $$$j$$$ for some vertex $$$k$$$, probably coinciding with $$$i$$$ or $$$j$$$ or both.

      While the syntactic structure stays the same, different semantics may be ascribed to it and the notion of optimality may vary. For example, if $$$a[i][j]$$$ and $$$b[i][j]$$$ stand for the shortest path lengths from $$$i$$$ to $$$j$$$ that take $$$x$$$ and $$$y$$$ days respectively, $$$c[i][j]$$$ will stand for the shortest path lengths that take $$$x+y$$$ days. It then remains to notice that looping over $$$k$$$ yields an operation similar to matrix multiplication and all matrix multiplication theory (in particular, the fast exponentiation part) is applicable here even though the multiplication operation is different from the canonical one (search for the term "tropical geometry" if you are intrigued by this redefinition). And also notice that the base case (shorest paths of length $$$1$$$) is exactly the given point-to-point distance matrix.

      Before reading further, make sure that you understand what is denoted by $$$a[i][j]$$$ in the Floyd-Warshall algorithm and why it is important that the $$$k$$$ loop is the outermost in its implementation.

      Spoiler

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

How to solve Div2 1000 ?

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

Hi, could somebody please explain in D1 500, why do you need to move an i-th token i units to the left, before finding the median?

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

    We want to place the tokens having sorted coordinates $$$x_0, x_1, \dots, x_{n-1}$$$ to $$$x', x' + 1, ..., x' + n - 1$$$ for some $$$x'$$$. It is optimal to take coordinate $$$x_i$$$ to position $$$i$$$, that is, $$$x' + i$$$ in the final arrangement. If we subtract $$$i$$$ from each $$$x_i$$$, the problem transforms to bringing all the transformed $$$x_i$$$, that is, all the $$$x_i - i$$$ to the same x-coordinate. This is because $$$x_i - i = x'$$$ for all $$$i$$$ implies $$$x_i = x' + i$$$, which is the arrangement that we wanted.

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

      Thanks, I finally understood!

      → Reply