why does my code work? it runs in almost O(1) per testcase. Shouldn’t the constraints be tougher?
Did you meant O(tk)
t : number of test case & k is constant
Damn I thought how did he solved in O(1)
Yes, you are right the constraints should be more tough. Even my code which is not O(1) runs in very less time which is 0.08. mysol
yeah I meant O(tk)
Wow you are Legend…
It is supposed to be the 2nd problem of div2. Keeping that in mind I think the constraints are fine.
True, but such a nice problem could’ve been swapped with greedy ones like CONSADD MARCH21B
Yeah Absolutely correct.
- Contraints are decided so that all possible feasible approaches can be used with them… not everyone will think of an O(tk) solution but it’s great if you did it like that.
- O(tnk) approach is also quite fast and takes less than 0.5 secs which is practically good so its also a feasible solution…
I optimized my N^2 solution and it worked although I could not prove why it worked, if someone can prove that would be helpful
can you share …?