Someone submitted this solution for this problem.

The constraints are N ≤ 10^9 and the above is an O(N^2) solution. The problem’s time limit is 5 seconds (multiplier for python), and the above solution takes 0.71 seconds.

Theoretically, this is supposed to take 9999999990 seconds (Assuming 10^8 operations ≈1 second) for the worst case for each testcase. There are 1000 testcases at max.
It would take at least 10 times more as the language is python.

I wonder how it got AC.

Thanks to @anurag_bhatt for pointing this out!

3 Likes

1 Like

The testcases were weak for sure !

The C++ codes are executing in 0.00 sec

1 Like

There might no test case for which code works in worst case .

Maybe not the absolute worst case, but there are plenty of testcases that should make a naive algorithm time-out massively: e.g.

1
805306368

1 Like

Maybe i’m getting the logic wrong but isn’t it just the first one in binary or if it is a power of 2 then just the -1, so it should be O(Tlogn) which should work in 0 seconds

1 Like

But as the complexity isn’t constant, it has to take a bit more time.

Also, there are 1000 testcases If a few solutions take 0.00 seconds, it’s okay. But all the AC C++ solutions took 0.00 seconds!

Actually it’s for second-year student that is the reason test case is too easy

that doesn’t make sense

3 Likes

I put 2^{60} =1.18 \times 10^{18} in 10^5 testcases and then i got 0.01 seconds on my code for the sum. The constraints were very small. 2^{60} takes the most time to compute.

2 Likes

I’m in 9th std 2 Likes

If it the question was intended to be easy, the constraints should have been small so that those who participate won’t be misled and try solve it for the given constraints.

2 Likes

age doesnt matter , your talent matters !

The testcases are quite bad …
The problem states that if there is no number a and b can be found , print -1
But the program of yours does not have that condition …

the answer for a is always 1, 2 ,4 , … any power of 2 . .

So the complexity is O (log N) in worst case (If N is power of 2 ) and O(1) if N is odd

There is a better way to solve this
My Solution : CodeChef: Practical coding for everyone
I too a school student like you ! but not home schooling Sure, here you go CodeChef: Practical coding for everyone

I think my solution does print -1 in case there’s no answer

If you amortize the complexity, both of our solutions have the same O(log_2 n)

Also, please note that I solved the problem during the contest. After the contest ends, one can improve their solution by spending more time on it. During the contest, you’d just want to solve a problem and move on.

i agree to your point !