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

Div. 3-G can be solved with floyd ?
Автор It_Wasnt_Me, 4 года назад, По-английски

I've solved the problem using dijkstra then I found icecuber's submission 96123320

while floyd is $$$n^3$$$ and $$$n <= 1000$$$, the idea fit in time how that possible ?

aslo see this comment

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

»
4 года назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

Try running 10 ^ 9 loop in C++. It runs within 1 second! This happened with my friend as well who had prepared a contest for our college students. Peeps submitted brute force and got AC.

Perhaps this is simply a benefit of using C++. I mean you can't do that on any other language like Python.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    maybe the time limit wasn't 1 sec so your friends solution passed.

    running empty loop for 10^9 in C++ runs in less 1 sec even 10^18, so this is not the reason why the above solution has passed

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      It was one second. And I agree with others here. The constants being real small helps but in general do not write such code. Surprised to see red people doing this.

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

Let's say we have two codes. The first one is iterating from $$$1$$$ to $$$n$$$ doing just an adding operation and the second one is iterating from $$$1$$$ to $$$n$$$ but it's doing a lot of calculations (like $$$10$$$ adding and multiplying operations). We both agree that both codes have $$$O(n)$$$ time complexity, but will they consume the exact same time? Of course not.

That's why there is something called the constant. The first code (in the example above) has a very small constant since we only have an adding operation, while the second one has a larger constant. More operations means larger constant.

Floyd has a very small constant since you just have to take the minimum between two numbers. So it's not weird that it passes the $$$1$$$ second time limit. We usually consider a $$$O(n^3)$$$ solution when $$$n \le 1000$$$ as a TLE solution because most solutions require enough operations to make the constant large enough to make it a TLE solution.

So don't risk coding a $$$O(n^3)$$$ code when $$$n \le 1000$$$ unless you have no other idea or the constant is so small (like in Floyd).

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    So in general can we do the same in other competition websites or it varies how the compiler is implemented?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      its better to not do it unless you have no other option.

      or maybe if the time limit is more than 4s with only 1 test per testcase

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +30 Проголосовать: не нравится

        This mention is just to get you notified ma_da_fa_ka.

        It varies from one website to another of course. Like in Codeforces, when a solution gets TLE, they run it several times on the same testcase and if all of them were TLEs then the solution gets TLE on that testcase, otherwise it passes. Because the time consumed on running the same code on the same testcase on the same server may vary in some milliseconds so by that they guarantee it won't pass.

        One technique I use is when I have no better approach than a risky one, I code it and then comment all cin and scanf statements and assign worst case values to the input variables and then run it on the custom invocation, which will give me the time consumed by the server on running this code. I then compare the time consumed with the time limit and if it's lower then it's safe.

        Like in problem G, I could've coded the Floyd fast and compared it because coding it is much faster than $$$n$$$ Dijkstra but that didn't come to my mind. I thought it will be TLE too. If I did so and let's say it didn't pass, I'll then erase it then get back to the $$$n$$$ Dijkstra.

        I know I may waste time coding some TLE code, but when I have no better approach or I have a better approach but I want to try something risky but way easier than the main approach, then it's much better than getting TLE.

        Sorry for the long comment.

        → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    I got it, thanks :)

    → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

Since you tagged my comment may as well clarify, note that I said:

is not likely to work here

Key word — likely, I've seen Floyd-Warshall pass in under a second for n = 800 but its still not a given, especially in Java / Python. As Naseem17 mentioned Floyd-Warshall has a really small constant factor and is also pretty cache friendly in general so it can sometimes pass for 1e9-2e9 simple operations, but its probably not a great idea to bet on that.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ExplodingFreeze If we can find All-Pair Shortest Paths using Dijkstras in O(N^2 logN), then what is the need for Floyd-Warshall algorithm which runs in O(N^3) ? We can just stick with Dijkstras always right? Can somebody answer? I am sorry if my question was stupid.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      Because All Pairs Dijkstra will run in $$$O(n * m * log(n))$$$, not $$$O(n^{2} log(n))$$$. So for a dense graph with no restriction, the number of edges ($$$m$$$) can be up to $$$\frac{(n * (n - 1))}{2}$$$. So Dijkstra written like this will run in $$$O(n ^ 3 log(n))$$$ which is worse than Floyd-Warshall's $$$O(n ^ 3)$$$.

      Dijkstra can also be written to run in $$$O(n^{2} + m)$$$ per source vertex, so All Pairs Dijkstra can be made to run in $$$O(n^{3})$$$ total, but since the operations in Floyd-Warshall are both fewer and simpler, in practice Floyd-Warshall should still run faster. Also in general if both are going to run in $$$O(n ^ 3)$$$ Floyd-Warshall is far easier to code. There are also some rarer scenarios like cycles with a net negative weight that Floyd-Warshall can handle but Dijkstra can't.

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://mirror.codeforces.com/contest/1433/submission/96279407 i dont now why but only 15 ms lol

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Floyd Varšal algorithm runs in O(N ^ 2) as of 2017.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

The constant factor of Floyd–Warshall is very small, so we can do more than a billion operations per second. During the contest I did a custom invocation maxtest before submitting to make sure that it was fast enough on the codeforces server.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Way to go!

    If not sure, take an effort and measure the freaking thing. Not just memorize some arcane recipe like "Floyd works in 1s for 800 but not 850"... it will be different the next time you try.

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

what is floyd?

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    It's an algorithm to find shortest paths for all possible pairs of vertices in a graph. It's time complexity is $$$O(N^3)$$$ where $$$N$$$ is the number of vertices in the graph.

    You can read more here.

    → Ответить