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
Gentle Reminder: The round begins in 35 mins.
When editorial of SRM795 will be ready?
Here are the editorials :) https://www.topcoder.com/single-round-match-795-editorials/
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.
Consider the problem where you have to find the minimum discounted spanning tree. That is, find the minimum cost of a tree after applying discounts on edges. It is easy to prove using exchange argument that it is optimal to apply the largest discounts in order to the edges of the actual MST found using kruskal's.
Now, $$$f(s, t)$$$ can be found as: Iterate over subsets $$$S$$$ of $$$[n]$$$ containing both $$$s$$$ and $$$t$$$ and find minimum discounted spanning tree in the graph spanned by $$$S$$$. Answer is the minimum over all subsets. To prove this you can see that in any subset's discounted MST there is an $$$s-t$$$ discounted path, and for any path there is a corresponding subset $$$S$$$ (the nodes of the path.)
So, the solution is to iterate over all possible sets and find the discounted MST for them. Then, update the answer for all pairs of nodes in the set.
Complexity is $$$O(n^2 2^n)$$$ DSU operations with a very small constant and $$$O(n^2)$$$ memory. It can be optimized to $$$O(n 2^n)$$$ time and $$$O(2^n)$$$ memory by using some precomputation, but it was not required to pass.
Great problem... Thanks for writing 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).
Instead of relaxing the problem to finding an MST containing $$$s$$$ and $$$t$$$, we can relax it to finding some sub-multi-set of edges such that all vertices have even degree except $$$s$$$ and $$$t$$$. We can do this with a DP on the $$$2^n$$$ masks of the parity of the degrees. You update the dp one coupon at a time, trying using that coupon with all $$$n^2$$$ edges. The overall runtime is $$$O(n^3 2^n)$$$. You can optimize this by storing only $$$2^{n-1}$$$ states, because the total parity is always even.
Oh, nice solution. Didn't think of this during testing. Anyway, it would have been practically impossible to separate from the intended solution.
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.
You are probably the best TopCoder writer now
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.
O(N^5) or O(N^4lgK) is good enough. O(N^5lgK) might not fit.
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.
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.
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.
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).
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
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.
How to solve Div2 1000 ?
Please see the post above.
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?
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.
Thanks, I finally understood!