Clone3's blog

By Clone3, history, 4 years ago, In English

Greetings folks, I've been struggling with the following problem:

I don't have a clear definition of the task but in most cases, it looks something like that:

You are given a squared plane (that is every vertex has integer coordinates $$$1 \le x_i, y_i \le N$$$) with some vertices disabled, edges between vertices can only go in 8 directions (chess king moves), and are always present if the vertices are present.

The task is to answer $$$Q$$$ queries, where a query asks you to remove a small number of $$$X$$$ vertices from the graph, recalculate articulation points (cutpoints) and bridges and add them back.

The constraints are something like this:

$$$1 \le Q \le 8 \cdot 10^{5}$$$ — the amount of queries

$$$4 \le X \le 40$$$ — the amount of deleted points in the query

$$$1 \le N \le 200$$$ — borders of the bounding box of the graph (number of vertices can go up to $$$N^2$$$)

I've always been struggling with biconnected components, so I'm unsure how to solve this. I've seen the algorithm that keeps DSU with biconnected components, but it was hard to comprehend and I'm not sure whether it is applicable to cutpoints.

Queries are not online, thus I felt like something like dynamic-connectivity offline which consists of rollbacking DSU would work, but I'm not really sure how exactly to apply this

Currently, my solution is $$$O(Q \cdot V \log E)$$$ which takes too long to compute without getting new hardware. That is bruteforce bridges (dfs) with set to keep track of them, probably $$$\log E$$$ is somewhat easy to remove, but it doesn't seem to help in the big picture, it feels like this problem has a better solution

The source is neither a competitive programming task nor an interview question.

Any help appreciated

Full text and comments »

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

By Clone3, history, 8 years ago, In English

Is there anyone who can prove or disprove my random-based 18809719 solution of this problem?

Short description:

visited[i] on phase j consists of all possible prefix sums that we could have met by collecting coins from left to right.

Example:

{2, 1} is a set of coins, then

visited[0..3] = {{0}, {0, 1}, {0, 2}, {0, 2, 3}}

Suppose that we are looking for value X in visited[K], if we shuffle input many times , then X is gonna be one of prefix or suffix sums on the way to K. (To consider all Suffixes, simply for every X in answer add K - X to the answer)

The question is how many times do I actually need to shuffle input so that I get all values of X with high probability?

Full text and comments »

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