ash_ketchum's blog

Codeforces Round #339 (Div. 2) A. Link/Cut Tree
By ash_ketchum, history, 9 years ago, In English

Well hello guys! Below is the link to my source code for the above problem. http://codeforces.net/contest/614/submission/15376824 I am getting a WRONG_ANSWER on test case 3 after my submission on CodeForces but when I compiled and executed the testcase on my g++ compiler it gave the right answer.Can anyone please tell me why is this happening?!.Below is a screenshot of the answer that I got for testcase 3 after compiling on g++. (http://codeforces.net/predownloaded/4d/2c/4d2c56826166cb8597ec2f5249162eb3266b58b4.png)

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You shouldn't use the function pow, its return type is double. For example it may return 2.99999999 and when you cast it to int it becomes 2, while the answer actually should be 3

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

    Thanks a lot!

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

      try adding 0.5 to your answer before casting it to int, that might work ;)

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

      By the way your code has an overflow bug. The problem limits are up to 10^18. First, its wrong to cast the answer to int, it should be to unsigned long long. Second, the condition on the for loop will make an overflow with large test cases.

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

        I modified my code as you had said earlier but experienced the same problem again in test case 31 wherein my g++ output differed from that submitted to codeforces. http://codeforces.net/contest/614/submission/15377789 (http://codeforces.net/06a211/Screenshot from 2016-01-15 02:44:58.png)

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

          pow(k,i)<=r this condition is not totally correct. in large test cases you will get overflow. For example in this test case : 1 10^18 10^9 the for loop will go like : 1 10^9 10^18 and then it will try 10^26 which should break your for loop. What really happens is that 10^26 is greater than the upper limit of unsigned long long. Unsigned long long can hold a number up to 10^19 as maximum. Thus, it makes an overflow which means that pow(k,i) returns a random number.

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

          Try adding the following code at the bottom of your for loop : if((ll)(pow(k,i)+0.5) * k / k != (ll)(pow(k,i)+0.5)) break;

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

            That didn't work.Thanks for the help!I will try to figure this out.

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

              Ah your problem is that you forgat to add 0.5 to pow(k,i) at your for loop condition :D for(i=0;(ull)(pow(k,i)+0.5)<=r;i++)

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

In some cases, you have an overflow because the resulting value of k is greater than the upper limit of unsigned long long.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply