CHONQ - EDITORIAL

Thanks @l_returns that helps.

1 Like

Yes, test cases did not have maximal constraint. This TL limit felt really bad to me.

1 Like

anytime @viiju123 :smiley:

@aryanc403 XD

1 Like

Time complexity ignores constant optimizations :stuck_out_tongue:

@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 am pretty much sure its because you used only 1 division @swapnil159

I learned that it is bad to use ceilā€¦ even wrote in the solution CodeChef: Practical coding for everyone :smiley:

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

2 Likes

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.

@thesmartguy dope code man!! Really liked your idea!

1 Like

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

1 Like

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

1 Like

But still, isnā€™t it O(N3 ) ?? for N = 2000, how is it stil passing ?

1 Like