Блог пользователя dsu123

Автор dsu123, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

ask maxflow about it