why does my code work? it runs in almost O(1) per testcase. Shouldn’t the constraints be tougher?

2 Likes

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

1 Like

yeah I meant O(tk)

Wow you are Legend…

1 Like

It is supposed to be the 2nd problem of div2. Keeping that in mind I think the constraints are fine.

1 Like

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…

1 Like

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 …?