Zakaas's blog

186 (Div. 2) A — Power function failure
By Zakaas, 12 years ago, In English

During the round I got 6 WA for problem A. This is my solution 3804729.

I was using math pow function for generating a number from it's digits. Simply like this - pow(10, j), 0 < j < number of digits.

After the contest I found that each time pow was returning floor results. So I used for loop instead of pow and it worked 3804738.

And most frustrating thing is that first solution is giving correct result for each test case on my PC. Can anyone please tell me why pow function failed in this case?

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You should notice that you can only remove the last digit and the one before it. Math is a great solution if we can remove anyone all digits.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually problem is not about removal of digits, it is about failure of power function. I am removing last digit by this 'n/10' and using power function to remove the digit before last.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok fine…… i misunderstand sth and got it now

      → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The pow function works as it should. It doesn't compute precise integer powers, but rather a floating point result, which may differ slightly from the true value.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay, got it!

    Then what will be the alternative for pow function to calculate integer powers? for loop is not always efficient.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      There is no standard alternative. A for loop is good enough, because with standard integer types you can't do too many iterations without overflow. If you use long arithmetic or have to compute large powers modulo something, then use binary exponentiation: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Fast exponentiation or precalculation should work for you. The latter, for example, can help in polynomial hashing.

      Here is an example of non-recursive implementation of binary exponentiation:

      int a = 10, b = 5;
int res = 1;
for (; b; b >>=1, a *= a)
  if (b & 1) res *= a;
printf("10^5=%d", res);
      → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Instead of pow function , you should use powf function and you will then see that it will work absolutely fine..

→ Reply