red_coder's blog

Run-time error...
By red_coder, 13 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

»
13 years ago, hide # |
← 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
  • »
    »
    13 years ago, hide # ^ |
     
    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
    • »
      »
      »
      13 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        13 years ago, hide # ^ |
         
        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
        • »
          »
          »
          »
          »
          13 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Use arrays instead of long long..

          → Reply
        • »
          »
          »
          »
          »
          13 years ago, hide # ^ |
           
          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
    • »
      »
      »
      13 years ago, hide # ^ |
      ← 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
»
13 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 years ago, hide # |
 
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
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply