SebiSebi's blog

By SebiSebi, history, 5 years ago, In English

Hi!

I am trying to solve problem I from the 2017-2018 ACM-ICPC Central Europe Regional Contest (CERC 17) as indicated by the official solution. I understood the divide and conquer argument but it's not clear how to compute the left intervals and the right intervals in O(hi — lo). Basically, I cannot understand how this step in the solution works: "Starting from subsequence [mid, mid + 1], we expand it to the left, storing all intervals we encounter until we exit the [lo, hi] window". How to implement this in linear time? Can someone explain this in more detail? It seems that I am missing something which may be obvious :)

Thanks!

Full text and comments »

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

By SebiSebi, history, 9 years ago, In English

Can someone give me a hint on this problem: http://www.spoj.com/problems/PT07A/. I cannot figure out how to calculate the SG numbers.

Full text and comments »

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

By SebiSebi, 10 years ago, In English

Hello!

I'm trying to understand how the algorithm for finding the minimum path cover in DAG works. I read the description from here: http://en.wikipedia.org/wiki/Maximum_flow_problem#Minimum_path_cover_in_directed_acyclic_graph . Can someone explain to me the idea behind this algorithm and why it outputs the right answer?

Full text and comments »

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