It_Wasnt_Me's blog

Div. 3-G can be solved with floyd ?
By It_Wasnt_Me, 4 years ago, In English

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

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

Comments Comments (26)
| Write comment?
»
4 years ago, # |
  Vote: I like it -25 Vote: I do not like it

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.

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

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      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.

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

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).

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

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

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

      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

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

        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.

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

    I got it, thanks :)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

      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.

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

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

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

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

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

    Opt. #1 from this legendary blog if I remember correctly :)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Man I really want to know .. Is this blog that u linked a joke or they are some real thing going on .. I wasted so much time to get what is going on in that blog

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

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

what is floyd?

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

    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.

    → Reply