dsu123's blog

By dsu123, history, 3 years ago, In English

This is a query regarding the problem https://codeforces.com/contest/498/problem/C (Array and Operations). I have implemented the idea suggested in the editorial for the problem https://codeforces.com/blog/entry/15353. The maximum number of vertices in my graph is $$$O(NlogA)$$$ and the maximum number of edges is $$$O(Mlog^2A)$$$. Here $$$A$$$ is the maximum value in the array. Now, if we use Edmond Karp then the total complexity should be $$$O(NMlog^5A)$$$. This should clearly time-out. But my solution https://codeforces.com/contest/498/submission/104527559 gets AC within $$$140$$$ ms. Is there anything I have missed out?

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

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Max-flow algorithms usually work much faster than their advertised complexity. In general, it's pretty difficult to make a max-case for them.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    The thing concerning me is if you become master in your next contest, you will have to wait 1 year to become OrangeCrayon xD

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

If I recall correctly in that problem it's the same thing as I noted in last educational's problem F. Each path saturates one source/sink edge so the complexity is actually O(V*E) for these graphs. Now, a graph for a certain prime obviously has O(M + number of occurences of this prime * log) edges and the number of paths found is O(number of occurences of this prime) so in the end the complexity of the solution is actually O(N*log^3*M) for the dumb editorial solution, O(N*log^2*M) if you remove that *log from the editorial solution number of edges or O(N*max_number_of_primes(A)*M) if you code it like I did: https://codeforces.com/contest/498/submission/40045470

It's a bit different from what PurpleCrayon said. Yeah the tests might be bad but mostly these problems have some property in the network that makes it have better complexity and people cba to think about them.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

ask maxflow about it