red_coder's blog

Run-time error...
By red_coder, 12 years ago, In English

Hey guys here is a simple problem on BFS of SPOJ. I tried to solve it but getting Run-time error. Here is my Code. At each step i am trying to pick a node from the top of Queue and insert its two children in the queue one appended with 0 and one appended with 1 back in Queue. Could u figure out the error?

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

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

I think it's overflow of long long and, as a result, reference to a negative index of the array. Or size of the array is just too small.

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

    Size of array i think is ok. Can u see the problem and tell me my error, its a very easy Problem.

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

      Why are you so sure that your answer will fit to long long? If it doesn't, you can receive negative elements in queue and, thus, p%n will be also negative.

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

        So what to do, dont have data type of bigger range than LONG LONG in C++

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

          Use arrays instead of long long..

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

          I guess this problem can't be solved in such way — even if you provide bigger data type, you'll get TL — brute force will be too slow for 1000 tests. I'd better use dp approach — for each residue 0<=K<n you can store the minimal length of number that consists of 1's and 0's and gives residue K modulo n, and last figure of this number (0 or 1). Thus you can find the minimal number giving residue 0, and it will be the answer.

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

      We need to find multiple => it will be more than our number. So, size of array isn't ok.

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

Ignore, I was out of my mind obviously. :-)

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

As you can see at link you provided, you receive RE when test is "1 9999".

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

    how u figured out that i receive RE when test is "1 9999"

    P.S.- ok i got it :)

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

finally got accepted :) Thanks to all of u for ur help

→ Reply