That one also gives the wrong answer for my test case.
Edit: oops, had tested the wrong one
After some more investigation it seems that the pow causes problems. pow always returns a floating point result. Instead try 1<<b[i]; which would be the same as 2^\texttt{b[i]}
Please don’t use so many macros in the code. It gets really tough to understand it.
It’s an editorial, so it should be easy for everyone to understand the code.
Floating point arithmetic is often problematic because often exact values can’t be stored as the value they represent. Take as an example: we want to store the decimal expansion of 1/3. You might now this is 0.33333333\ldots, but as the dots indicate this will repeat forever. But we have only a fixed amount of memory so at some point we have to cut it off. A similar thing happens with float and double, they are only approximations of the real value.
The fact that the value that is saved is not the value that is needed means that those small errors can compound into big problems. Each operation performed adds a little more error. In competitive programming it is adviced to not use them if possible. And if you do, comparison something like this: fabs(val1-val2)<EPS with EPS predefined to some small value like 1e-5
The tactic to avoid floating point operations is often clear from the problem statement. In this case floating point arithmetic was not needed → instead use bit operations. Some problems will want you to return a fraction a/b; and some go a step further requiring ab^{-1}\mod p where p is a large prime.
Here is my code CodeChef: Practical coding for everyone. It got AC but, I have a doubt, my code work on constraint of N greater then 1000, when I used optimized approach.
But it dodn’t work on constraint of N less then 1000, I used nested loop for it. Please help me to find where I was wrong. Thank you.
I think it was stated earlier that the “optimized” approach should have gotten WA. apparently there are test cases against it with N<1000 but not for big N.
Your approach for N<1000 is correct, but too slow for the second subtask
Your approach for N\geq1000 should not work. Try it on the example input. There the smallest value is used on the left.
Structure of input:
one test case
this case has 1001 elements
the first 1000 elements are 1,2,…,1000
the last element is 2^{10}, the first power of two larger than 1000