# | User | Rating |
---|---|---|

1 | tourist | 3372 |

2 | mnbvmar | 3345 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | Radewoosh | 3230 |

5 | scott_wu | 3189 |

6 | Benq | 3187 |

7 | LHiC | 3171 |

8 | Um_nik | 3155 |

9 | V--o_o--V | 3152 |

10 | Petr | 3139 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 172 |

3 | rng_58 | 158 |

4 | neal | 156 |

5 | Um_nik | 155 |

6 | tourist | 154 |

7 | Petr | 152 |

7 | Ashishgup | 152 |

9 | 300iq | 150 |

9 | PikMike | 150 |

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/20/2018 21:55:17 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

it is a difficult to say why you have wrong answer ,but the main idea to solve this problem is different. You must precalculate this numbers . The size of this numbers is not big. Maximum 31*31. You can add this numbers to vector and then sort it. After that ,with binary search you must to take three numbers and then print minimum difference.

Even binary search is not required, linear search would work according to constraints.

Definitely, linear search would work here. But it's no harm to use optimisations.In the worst case (my favourite Big Oh :p), it only helps you discover something new eventually, which one never knows, might help in the future.

It is good for learning but sometimes constraints make problem and code more simple :P

Yeah, but those 10

^{5}upper limit of constraint was a headache. I too went with the binary search for it.yeah ,really ))) i forgot about that,when i was solving a problem.

Your code doesn't work for the these numbers 15 63 127 255 511 have you got the pattern? These are one less than the power of two and greater than 7. Your code returns 1 but the actual answer is 2.

Bro, just an advice. Don't go with so much complex logics. It never helps but just increases chances of getting WA as evident in your case. Even I suffered a lot because of the same habit. So try to think easy.

Coming to the code, I'll think on this and let you know if I find the mistake.

Till then. What I thought of the solution to the problem is that till 10^9, there will be at most 450 such numbers which are the sum of two numbers (different powers of 2). And note the optimal number can even exceed 10^9. So for safety take till 2*10^9. And then apply binary search to find the closest such number or the optimal number and accordingly calculate the answer.

There is really no need for such complex code or binary search. You can just iterate through the values of 2^x + 2^y for (x != y), then you simply take the minimum difference between n and the computed sum. It should run in O(30*30).

Nice, I went with binary search during the contest. I like your approach greatly. Tell me if it worked, because if I ever thought of that I would have died thinking if something near 10^8 calculation will throw TLE or not.

Bro, it's not even 30*30. It's 30C2 = (30*29)/2 = about 450.

So number of operations in the worst case = about 4.5 * 10^7

Due to still think, It will get you a TLE? :P

I agree with you. Didn't think that clearly during the contest.

Here is the link to my solution. Solution