Hamim99's blog

Complexity!
By Hamim99, history, 4 years ago, In English

Problem link: https://lightoj.com/problem/penguins.
I solved this problem and my verdict is Ac. My idea is: I will take every ice bar as sink and calculate max flow. If max flow equal to total number of penguins then this bar is a one where all penguins can met.I use dinic with scaling for calculating max flow. According to my solution complexity should be n*(nmlogU) here m is the number of edge and U is maximum flow value.Again m=n^2 can be possible in this problem. So total complexity considering test case should be test*n^4*logU.Which shouldn’t pass test case according to me,but my verdict is Ac. Is this happen for weak test set?

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Hamim99 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I'm not sure if the tests are weak or not and I have only glanced at the problem so maybe it's unrelated, but from my experience I'd say that we often overestimate flow algorithms complexity. Generally speaking, if the network is at least somewhat specific, not just a random graph, then you can strike out at least one linear factor because of the order in which Dinic traverses the network. I don't know how to prove this type of bounds other than proof by AC though, it'd be cool if someone explained that from mathematical point of view.

→ Reply