dsu123's blog

By dsu123, history, 6 weeks 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

»
6 weeks 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.

  • »
    »
    6 weeks 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

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

ask maxfIow about it