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

Getting MLE using vector but global array is working fine
Автор Pranav_20, 13 месяцев назад, По-английски

I was solving this problem, this was the code that I wrote initially in which I used vector for dp (CODE), but when I replaced it with a global array of the same size it got AC (Updated Code), Can anyone please explain what is the problem with using vector here, or an article which explains this would be helpful.

Thnaks!

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

»
13 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

vector is (data address, actual size, allocated size) + allocated items

There we assume sizeof(int) == 4, sizeof(size_t) == sizeof(pointer) == 8

vector<int> with actual size == allocated size == 2 takes 8 * 3 + 2 * 4 = 32 bytes
vector<vector<int>> 5000x2 takes 8 * 3 + 5000 * 32 = 160024 bytes
vector<vector<vector<int>>> 5000x5000x2 takes 8 * 3 + 5000 * 160024 = 800120024 bytes

800120024 bytes ~ 781367 kilobytes ~ 763 megabytes

int dp[5002][5002][2] is just 5002 * 5002 * 2 * 4 bytes = 200160032 bytes ~ 195469 kilobytes ~ 191 megabytes

Pretty easy math tells that vector 2x5000x5000 instead of 5000x5000x2 would take somewhat about 191 megabytes too.

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Some extra details.

    Creating a lot of small vectors is bad, but the size of the innermost vector is fixed in compile-time, so you can use std::array<int, 2>, which takes exactly 8 bytes. So the dp type will be vector<vector<array<int, 2>>> and it passes easily: 219843927

    Funny enough, if you just use a 2x5000x5000 vector, you will still get ML: 219843261 (extra points for guessing why :).

    → Ответить
    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Because inner 5000×5000 vector as temporary argument for construction itself takes ~90 megabytes, so for creation there is need something about 292 megabytes.

      I guess, that something like 

      vector<vector<vector<int>>> v(2);
for (int i = 0; i < 2; ++i) {
    v[i].resize(n + 2);
    for (int j = 0; j < n + 2; ++j) {
       v[i][j].assign(n + 2, -1);
    }
}

      will work (can't check now)

      → Ответить
    • »
      »
      »
      13 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Got it, creating a lot of small vectors is really bad, as balalaika calculated above it uses 800120024 bytes. whereas if we use vector<vector<array<int,2>>> —

      • array<int,2> will use exactly 8 bytes.
      • vector<array<int,2>> => 24 + 5000*8 = 40024 (here itself it made a huge optimization in memory because we used 8 bytes instead of 32 bytes)
      • vector<vector<array<int,2>> => 24 + 5000 * 40024 = 20,01,20,000 ~ 200 MB So, that's why vector<vector<vector>> is giving MLE and vector<vector<array<int,2>>> is not.
      → Ответить