TheDark_Knight's blog

Stuck with TLE for a problem
By TheDark_Knight, history, 5 years ago, In English

Hey, I have been stuck at this problem for quite long 327E - Axis Walking. According to the editorial the author specified an approach involving "meet in the middle", but my implementation caused a TLE 76646016. Then he had mentioned that a bitmask DP approach of O(n*(2^n)) somehow unintentionally manages to pass the test cases & referenced to a particular submission 4017915. I had gone through the code but once again when implemented it caused a TLE. To figure out the reason behind this I tried to step by step make my code similar to the AC submission ( 4017915 ) mentioned in the editorial but again failed at the end with my submission as: 76648464.

Any kind of help would be appreciated.

Edit: This issue has been solved by converting all long long to int everywhere.

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try using fast input output

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

    I don't think that's the problem. Look at the test case that he failed on. Does the test case even look large to you?

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

      So whats the change he needs to make ?

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

      The test case that failed has n=24 and k=2. Even when tested locally it takes a couple of minutes to run.

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

I think it's because of using long long unnecessarily. Only your dp array needs to be long long. rest everything can be int and your code should pass.Try doing it.

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

    Already tried that in my last submission 76648464 . Do notice that 'll' is defined as an int & only the DP table stores long longs.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      huzaifa242 is correct. Since you have 1ll in your code you are unnecessarily using long longs instead of ints. Simply switching all 1ll to 1 gives AC 76687064. (Just a note, your ll macro does NOT affect 1ll)

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

        Ah got it thanks!

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

          Your bug is due to stupid shit like #define ll int- I hope you learned your lesson.

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

            Nah I usually define ll to be long long in my template. And tend to use long long even when int works to be fine just to be safe from overflows.

            Especially in this case using long long caused a TLE hence tried replacing the defined value in ll but forgot to replace the const 1ll (i.e in 1ll<<j )

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

I submitted your code in C++17(64) and it passed in 2000ms

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

    If this is the case then it seems really strange, any reason which you could figure out for this peculiar behaviour?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      You uses right shift for long long, not for int. I just replaced by int and got accepted with 32-bit compiler too. Submission

      any reason

      $$$64/32=2$$$

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

        Ya probably the 32 bit compiler implements the right shift operation for long long slower than the 64 bit compiler. Instead of calculating that value (i.e 1ll<<j) a lot of times I should had cached it in an array & that would indeed save a lot of time.

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

I just changed some long long computations to int 76700036

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

Auto comment: topic has been updated by TheDark_Knight (previous revision, new revision, compare).

→ Reply