dipta007's blog

Negative number in if condition giving TLE
By dipta007, history, 7 years ago, In English

In the last CSAcademy Round 53, Problem Number C, My this submission gives me TLE

My TLE Code

But after the contest I have changed my code and submitted and that was accepted.

My Accepted Code

The change was on line 144 and 161. On the first code (TLE) I checked if the propagate value is not equal to 0 by the following code

if( tree[node].prop )

On the accepted code I checked the same thing by this following code:

if( tree[node].prop != 0 )

But I think there is no difference in the two codes. Please explain me if I am wrong.

I have already posted on CSAcademy. But haven't got any reply till now. So I posted here for getting more response. You can check my blog by the following link: My Blog on CSAcademy

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

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Your AC solution runs in 912ms. I resubmitted your TLE solution and it was accepted. Run time might differ slightly even if the code stays exactly the same.

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

    I didn't see someone so unlucky :(

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

      Actually the intended solution is O(n), while your solution is O(nlog2(n)). So you are pretty lucky that your second solution passed :P

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

        n = 100000, log(n) = 17, nlog2(n) = 17*17*100000 = 2.89*10^7, I think it can run in 1 second theoretically. Right?

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

          You're right, I didn't check the constraints, just the complexity.

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

            Now you should agree with me :p — I didn't see someone so unlucky!!

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

    BTW, thanks for your help. It saves my night sleep. :)

    → Reply