hunterr_196's blog

By hunterr_196, history, 3 months ago, In English,

Can anyone please help me with this Codechef August Long Challenge 2018 problem QUESTION why my solution is giving Wrong Answer and for which test case it is failing and why..... solution link Solution It will be a great help for me....thank you.

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, but those 105 upper limit of constraint was a headache. I too went with the binary search for it.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah ,really ))) i forgot about that,when i was solving a problem.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Here is the link to my solution. Solution