tangra's blog

By tangra, history, 2 months ago, In English,

Hello! I had run time error on this problem : https://codeforces.com/contest/377/problem/A

Here is my code : https://codeforces.com/contest/377/submission/74861444

It works normally on my laptop.

Can someone help me please?

  • Vote: I like it
  • 0
  • Vote: I do not like it

2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

No runtime error is weird. Here's what your runtime error has to say:


Clearly, you're trying to access an element that is not yours, i.e., element at index 1, whilst the size of your vector is only 1.

It works normally on my laptop.

No, it doesn't. That's the thing about C++. It lets you think you're right all the time. You may get the correct result but that may just be a fluke. I'll explain to you a little about std::vector or in general about containers in C++.

When you create a vector, even when you haven't added any elements, it has already allocated some amount of memory for you beforehand but as you haven't added anything yet, the size() method returns 0. It works this way in order to minimise the number of reallocations and copying, which also has the added benefit of making push_back() time complexity O(1) on average. Now, let's look at another case. Let's say you have a million elements in your vector and you call vector::clear(). Now, the size() method returns to you 0, but guess what? You can still access all the million elements as they are not freed from memory. Instead, when you do push_back() or emplace_back(), you re-write over the already allocated memory. The reason for this is that if you have a million elements and decide to clear all of them, there's still a chance you might wanna add a million more elements again. This method is extremely optimal as there are many benefits as compared to: allocate when necessary. One more scenario. Let's consider you have some elements in your vector and you choose to add a few more. Note that I mentioned above that the vector pre-allocates some extra memory at each re-allocation. So, you think you only have space for those "some" elements, but in reality, you have more space secretly allocated (so that inserting can be O(1) average). There is a certain load factor that determines when it is a good time for the container to reallocate with more memory. It is usually around 0.7 or 0.8 in most container implementations. The load factor is calculated as:

$$$\frac{Number Of Actual Elements Added}{Total Allocated Size (Not Known By The Programmer)}$$$

. When this factor is hit, you have re-allocation with copying, but there are other factors too that determine/predict how much extra memory should be allocated beforehand.

The reason why I explained all of the above is because sometimes you have $$$X$$$ elements in your vector, and you may, by mistake, access the $$$(X + 1)th$$$ element or the $$$(X + 10)th$$$ element which may or may not work correctly, depending on the reallocation factor. Try accessing the $$$(X + 1000)th$$$ element. An exception will be raised in the latter scenario. However, in the former ones, no exception will be raised because your vector will always have allocated some extra memory.

Moral of the story: C++ may make you think you're right but :((

Here, on CF, you have various software integrated together to catch every small mistake you make. Dr. Memory happens to be the one that checks for out-of-bounds.

The various kinds of RTEs you could possibly get: out-of-bounds-access/write, signed-integer-overflow, memory-leak, divide-by-zero, etc.

A little help I could use.....
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey zeus, thanks for the explanation it's interesting to know more about how it works.

But in my case I do not see where I am accessing an element that is not mine.

What should I do then to fix this runtime error?

  • »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Revisiting your submission, I found that the exit code is -1073741819, which means: You are trying to access memory that is not yet been allocated by you. Maybe your dfs functions does not run 'k' time as you expect it to, leaving the size of 'ans' to be less than k. But you access it continuously for 'k' indices which may or may not run without exceptions based on my above explanation. According to the message by Dr. Memory, you only push_back() once into 'ans'. But then you try to access index 1 of 'ans' in the loop which gives RTE. I'm not completely sure tho, so it's be best to wait for someone else to come along and help.

    [EDIT:] Step through your code using gdb or something and count the number of time dfs stacks up recursively. I'd do it myself but I'm busy with something else right now and it's like 5 am here, unless you don't mind waiting till the next time I'm awake as I'll be diving into bed the moment I'm done with my work.

2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey Zeus, the problem is fixed.

It was caused by some undifined behaviors of c++ by using ios::sync and tie functions with scanf and printf.