Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

chromate00's blog

By chromate00, 17 months ago, In English

Disclaimer: If it was not clear to you already, this article is not about an algorithm which is practical on computare hardware. It is about a "natural" algorithm, working based on physical/real-life principles. It may give you some insights on algorithmic thinking, though. Either way, it's interesting to know this.

In this article, I will discuss about an interesting data structure that can deal with all of the following operations in $$$O(1)$$$ time and $$$O(V+EW)$$$ space complexity. The operations are:

  • $$$link(u,v,w)$$$: Connect two vertices $$$u$$$ and $$$v$$$ with an edge of weight $$$w$$$.
  • $$$cut(e)$$$: Cut the edge $$$e$$$.
  • $$$mpath(u,v)$$$: Find a shortest path between two vertices $$$u$$$ and $$$v$$$, if one exists.
  • $$$connected(u,v)$$$: Check if two vertices $$$u$$$ and $$$v$$$ are connected.

Here are how each operation works and are implemented.

"Base structure"

Each vertex is an object where you can tie a string on. A plastic ring should work fine. Each edge is a flexible (but not elastic!) string with a certain length. A (practically infinitely) long thread of string, and a pair of scissors is maintained for future use. This is the "base structure" of this data structure.

$$$link(u,v,w)$$$

Grab your pair of scissors, and cut out a string of length $$$w$$$, and connect vertex $$$u$$$ and $$$v$$$ with the string physically. This is practically $$$O(1)$$$ in time complexity, and contributes $$$O(W)$$$ to the space complexity.

$$$cut(e)$$$

Grab your pair of scissors, and cut the string corresponding to the edge $$$e$$$. This is $$$O(1)$$$ in time complexity, and garbage collection can work nicely as well. (Just throw away the string into the bin.)

$$$connected(u,v)$$$, $$$mpath(u,v)$$$

These two operations are basically one operation in reality. This operation can be interpreted as the following linear program.

$$$ \begin{gather*} \max X_v \\ s.t.\\ X_u = 0\\ |X_{u_e} - X_{v_e}| \le w_e \, \forall \, e \in E \end{gather*}$$$

Now, if you're accustomed to linear programming, you might realize that this is the LP formulation of shortest paths on an undirected graph. Now, what we did for each $$$link$$$ and $$$cut$$$ operation just translates to the constraints in this linear program. Because we connected $$$u_e$$$ and $$$v_e$$$ physically with a string of length $$$w_e$$$, the two vertices cannot have a distance farther than $$$w_e$$$. The only step left is to bind $$$X_u=0$$$ and maximize $$$X_v$$$.

Maximizing $$$X_v$$$ is not hard. You can just grab $$$u$$$ and pull $$$v$$$ forcefully towards some direction until you cannot pull further. Now that the linear program is complete physically, we have just found the result in $$$O(1)$$$ time. If you can pull infinitely, the linear program is unbounded, which means the two vertices are disconnected. If you cannot pull further than some distance, that distance is the shortest path, and the path connecting $$$u$$$ and $$$v$$$ in a straight line now is the shortest path.

Conclusion

With physical principles, we just found out that time complexities that seem impossible can in fact be possible in natural algorithms. How fascinating it is to know what physics can provide us in algorithms! I hope this article could give you some insights on algorithmic thinking, or at least keep you interested throughout the article.

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

»
14 months ago, # |
  Vote: I like it -15 Vote: I do not like it

pulling the two nodes apart will take O(shortest path length) time my fellow spammer

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

    Just pull harder :P

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it

    If you drop the rings to some deep well (in vacuum), gravity will move them in an acceletared rate. In particular, the lenght covered in time $$$t$$$ will be $$$s = g t^2 / 2$$$. It thus suffice to drop the rings and get the solution in $$$O(\sqrt{2 \cdot shortest\, path\, length / g})$$$.

    Note that to obtain a better constant factor it's advisable to stand on the poles rather than on the equator, as gravity is a little bit stronger there ;)

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's really nice how we can use competitive programming in real life to do many amazing things effectively. This blog is but one of many thing that can be derived from algorithmic thinking. Amazing blog. Upvoted.

»
14 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Jokes apart, this is actually a cool and clever idea, so idk why people are disliking it.

»
14 months ago, # |
  Vote: I like it +17 Vote: I do not like it

next blog: solving TSP in O(n) by using creepers and cats in Minceraft

»
14 months ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

Seems similar to quantum computing to me. Using physics to solve algorithmatic problems.

»
14 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Another physical "algorithm" of this type is sleep sort, which is the analog of counting sort.

»
14 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I can't stand someone posting more sophisticated shitposts than me