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.
Try using fast input output
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?
So whats the change he needs to make ?
The test case that failed has n=24 and k=2. Even when tested locally it takes a couple of minutes to run.
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.
Already tried that in my last submission 76648464 . Do notice that 'll' is defined as an int & only the DP table stores long longs.
huzaifa242 is correct. Since you have
1llin your code you are unnecessarily using long longs instead of ints. Simply switching all1llto1gives AC 76687064. (Just a note, your ll macro does NOT affect1ll)Ah got it thanks!
Your bug is due to stupid shit like
#define ll int- I hope you learned your lesson.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 )
I submitted your code in C++17(64) and it passed in 2000ms
If this is the case then it seems really strange, any reason which you could figure out for this peculiar behaviour?
You uses right shift for
long long, not forint. I just replaced byintand got accepted with 32-bit compiler too. Submission$$$64/32=2$$$
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.
I just changed some long long computations to int 76700036
Thanks I got it.
Auto comment: topic has been updated by TheDark_Knight (previous revision, new revision, compare).