Thanks @l_returns that helps.
Yes, test cases did not have maximal constraint. This TL limit felt really bad to me.
anytime @viiju123
Time complexity ignores constant optimizations
@vijju123 I got passed in 0.66
I feel it is because of the way you are using difference arrays
i used one division operation though
You can see my solution if you want-> CodeChef: Practical coding for everyone
I learned that it is bad to use ceilā¦ even wrote in the solution CodeChef: Practical coding for everyone
Agreed. Either the TL should have been more relaxed, or they should have included testcases for maximum constraints.
Yes, please can someone tell if we can do some trick for floor function for using FFT or karatsuba?
Codechef is cheating xD
I just created a sample input with maximum constaints (with random arrays). Testerās solution takes 2.056 secs, but mine is 0.4 secs (Code::blocks execution time). A little partial score would be nice. Here is my easy solution on C++: CodeChef: Practical coding for everyone
I did something similar to this. Made use of the fact that the floating point division can at max be larger than the floor division by N. But I couldnāt get an AC on all test cases. TLE on 2 while all others passed in 0.23.
This question deserves a lot of respect. I never thought that a basic arithmetic operation could cause that much of trouble. I could work on debugging because I read here that division is a costly operator otherwise had no hope to solve this question.
can we use binary search to find the least value?
Hi, Since your answer got AC I wonder what is the time complexity of your solution.
For each test-case Two nested for-loops with a lower bound should result in O(N2log(n)), or better say O(N3) if insert at line 40 is expected to be O(N). Is there something that I am missing out here ? @anyone ??
notice that the solution I shared is of SUBPRNJL and not CHONQ
lol. I was going to attack you for saying vector inserts are not O(N)
hehe ā¦removed it ā¦it is O(N^3) ā¦i think it passed only because of weak tcs and optimization as it took me a lot of time to solve itā¦I know the reason now
But still, isnāt it O(N3 ) ?? for N = 2000, how is it stil passing ?