Run-time error... - Codeforces

Блог пользователя red_coder

Run-time error...

Автор red_coder, 13 лет назад, По-английски

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?

-1

red_coder
13 лет назад
11

Комментарии (11)

Написать комментарий?

dalex

13 лет назад, скрыть # |

← Rev. 2 →

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.

→ Ответить

red_coder

13 лет назад, скрыть # ^ |

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

→ Ответить

DryukAlex

13 лет назад, скрыть # ^ |

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.

→ Ответить

red_coder

13 лет назад, скрыть # ^ |

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

→ Ответить

.o.

13 лет назад, скрыть # ^ |

Use arrays instead of long long..

→ Ответить

DryukAlex

13 лет назад, скрыть # ^ |

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.

→ Ответить