Блог пользователя hmehta

Автор hmehta, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Gentle Reminder: The round begins in 35 mins.

»
4 года назад, # |
  Проголосовать: нравится +169 Проголосовать: не нравится
1000
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    Great problem... Thanks for writing it!

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +63 Проголосовать: не нравится

    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
    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится

    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
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +151 Проголосовать: не нравится

    You are probably the best TopCoder writer now

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2 1000 ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.