meet2410shah's blog

Some Non-intuitive Doubts
By meet2410shah, history, 4 years ago, In English

There are times when I want to predict the time complexity or space complexity of the algorithm and want to check whether it fits into the given constraints or not. It always looks like that the approach is correct but there are some architecture-level problems or rather concepts that I don't know very well.

Here are my doubts,

1) It is given that the problems need to solve in a time limit of 1 or 2 seconds and the memory limit of 256 Megabytes or 512 Megabytes. When do we need to consider those constraints while computing the complexities?

2) What should be the maximum size of the array that we can declare?

3) How to select the STL container that fits best to solve the problem? (Although it depends on the problem)

4) In case of double for loop. How do we need to access the matrix (generally in DP problems) to make sure that it will not exceed the time limit? How should I write for loops bigger one outside or the smaller one? Do we need to create a matrix of N x M or M x N (i.e., N = 100 & M = 10000), and the reason for it?

5) How writing array outside of the main helps us to reduce the time complexity?
Example CSES Problem: Coin Combinations II
TLE Code: https://cses.fi/paste/c63f02b96710bdd1164250/.
ACCEPTED CODE: https://cses.fi/paste/4098290d90c8bb29164255/.

6) How to use the Modulo operator effectively to reduce the time complexity?
Example CSES Problem: Coin Combinations I

TLE Code: https://cses.fi/paste/bd61629529d99d8b163f51/.
Modulo is written inside both loops.
ACCEPTED CODE: https://cses.fi/paste/753f06b17cbe2b761640d5/

Modulo is written outside of the inner loop.

I need help to understand the exact mathematics and concept of computer architecture behind the calculation of time and space.

Thank You.

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it
  1. I assume 2e8 operations per second to calculate time (this is really up to you, and it varies by judge, but 2e8 is a good estimate imo). For memory 1KB = 1000 bytes, 1MB = 1000KB (it's actually 1024 but 1000 is easier to calculate with). Thus 256MB = 256e6 bytes. An int is 4 bytes, long long is 8 bytes.
  2. Divide ML by memory of each element in the array.
  3. It's more like pick the right container to implement your algorithm. Just know most of the containers (stack, queue, set, priority queue, etc) and pick the one that suits your needs.
  4. When accessing an element in a 1d array, the elements around it are cached, making it faster to access them. Multidimensional arrays are stored like a 1d array, row by row, column by column. For example, in an array with dimensions n*m, arr[i][j] would actually be the i*m+jth element (assuming 0-indexed). Thus, try to access your array in a row major order. If the loop order were i, j then you should try to access it like arr[i][j].
  5. I believe the code you linked is an example of 4? I believe the two should be about the same speed.
  6. Mod is a slow operation (compared to +, -, *). Try to avoid it when you can. For example you might have a function to add two numbers under mod. 
int add(int a, int b) {
    int ret = a + b;
    return ret >= mod ? ret - mod : ret;
}
→ Reply