FrozenBlood's blog

By FrozenBlood, history, 4 years ago, In English

I have been trying to learn this algorithm from this https://www.hackerearth.com/practice/math/geometry/line-intersection-using-bentley-ottmann-algorithm/tutorial/. But there is no clear implementation. I have failed to implement it. Does anyone have a good implementation. It will be very helpful.

Full text and comments »

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

By FrozenBlood, history, 4 years ago, In English

You will be given a bipartite graph, each side have N nodes where N<=10^5. There will be M<=10^5 edges between these nodes. It is guranteed that the initial graph is given in such a way that the graph has exactly N matching. How many edges are there if I remove one of them the matching of the graph will be less than N? Here is the problem https://open.kattis.com/problems/justenoughbridges.

Any idea?

Full text and comments »

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

By FrozenBlood, 4 years ago, In English

This problem seems like a regular expression problem. If the constraints were small, it could be easily handled with dynamic programming I think. But it seems almost impossible with this kind of constraints. Any idea?

Full text and comments »

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