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

Автор TANGRA, история, 5 лет назад, По-английски

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

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

It works normally on my laptop.

Can someone help me please?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

Error

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.....
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

https://mirror.codeforces.com/contest/377/submission/74876271