Basic Understanding of Problem Statement

Правка en2, от meet2410shah, 2021-01-22 21:51:31

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. I have the doubt that sometimes 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. In each of those cases, 1. What should be the maximum size of the array that we can declare? 2. When we need to use the array or the set. 3. Which time complexity fits best into the given constraints. 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?

i.e (CSES Problem TLE Code: https://cses.fi/paste/c63f02b96710bdd1164250/

)

5) How to use the Modulo operator effectively to reduce the time complexity?

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en23 Английский meet2410shah 2021-04-12 09:43:42 0 (published)
en22 Английский meet2410shah 2021-04-12 09:43:08 27 Numbering change
en21 Английский meet2410shah 2021-04-12 09:42:18 0 Tiny Change
en20 Английский meet2410shah 2021-04-12 09:41:34 8 Tiny change (saved to drafts)
en19 Английский meet2410shah 2021-04-12 08:43:28 30 Link Edited
en18 Английский meet2410shah 2021-01-22 22:17:31 0 (published)
en17 Английский meet2410shah 2021-01-22 22:16:19 41
en16 Английский meet2410shah 2021-01-22 22:15:36 4 Tiny change: ' space. Thank You.' -> ' space. \n\nThank You.'
en15 Английский meet2410shah 2021-01-22 22:15:16 2 Tiny change: 'nd space. Thank You' -> 'nd space. Thank You'
en14 Английский meet2410shah 2021-01-22 22:15:00 48
en13 Английский meet2410shah 2021-01-22 22:13:40 23 Tiny change: 'M = 10000)?\n\n5. Ho' -> 'M = 10000), and the reason for it?\n\n5. Ho'
en12 Английский meet2410shah 2021-01-22 22:12:08 63
en11 Английский meet2410shah 2021-01-22 22:10:17 156
en10 Английский meet2410shah 2021-01-22 22:06:48 30
en9 Английский meet2410shah 2021-01-22 22:05:49 279
en8 Английский meet2410shah 2021-01-22 22:01:14 2 Tiny change: 'oth loops.\n ACCEP' -> 'oth loops. \n ACCEP'
en7 Английский meet2410shah 2021-01-22 22:01:00 4 Tiny change: 'oth loops. \n\n ACCEP' -> 'oth loops.\n ACCEP'
en6 Английский meet2410shah 2021-01-22 22:00:33 4 Tiny change: '55/) \n\n5) How to us' -> '55/) \n\n6. How to us'
en5 Английский meet2410shah 2021-01-22 22:00:09 18
en4 Английский meet2410shah 2021-01-22 21:59:40 672
en3 Английский meet2410shah 2021-01-22 21:52:03 16
en2 Английский meet2410shah 2021-01-22 21:51:31 11
en1 Английский meet2410shah 2021-01-22 21:50:50 985 Initial revision (saved to drafts)