meet2410shah's blog

By meet2410shah, 10 days ago, In English

Recently, I have been exposed to Digit DP SPOJ Problems, then I realized that yes, there is a wide range of problems that can be solved using the different dynamic programming approaches. When I first encounter the problem Help Bob, I was totally clueless that how I approach that problem. Then a friend (nishant403) told me to learn the concept of Digit DP. After searching a lot get some insights into it.

There are a lot more techniques like this that are there. I need help to get the whole set of DP Techniques that can be used for Competitive Programming and tutorial related to that with the practice problems that a beginner needs to solve in order to be the tourist of DP. I also need help to determine the specific order in which one needs to learn these techniques that increase the difficulty gradually.

Here are some of the posts that I found related to Dynamic Programming.
General DP:
1. Everything About Dynamic Programming.
2. DP Tutorial and Problem List.

DP on Trees and Rerooting:
1. DP on Trees Tutorial.
2. Online Query Based Rerooting Technique.

Digit DP:
1. Digit DP.
2. DIGIT DP Tutorial [ITERATIVE].
3. Digit Dp + Matrix Chain Multiplication.

DP with Bitmasking:
1. Introduction to DP with Bitmasking.

As of now, these are the list of articles that I found on codeforces. I will keep updating the list of articles. Hope for great support. Thanks a lot to all of them who have written these useful articles that enhance the knowledge.

Thank You.

Read more »

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

By meet2410shah, history, 3 months 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.

Read more »

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