Disclaimer:
I am a beginner in competitive programming, and this is me documenting my learnings. So, anything I say is just what I think at the moment and should not be taken as hard truths.
It has been a long time now that I practiced my competitive programming skills. Not super good at it. Last I practiced thoroughly was during interview preparation in July 2020.
Phase 1: Base Building
I have planned to solve at least two implementation
based problems everyday for a month starting today and additionally learning one new algorithm daily. I personally like string algorithms so I will start from there.
Problem 1: Do Not Be Distracted!
main() {
int n;
cin >> n;
string s;
cin >> s;
s.erase(unique(begin(s), end(s)), end(s));
sort(begin(s), end(s));
auto it = unique(begin(s), end(s));
if(it != end(s)) cout << "NO";
else cout << "YES";
}
Time Complexity: O(nlog(n))
Space Complexity: O(1) # not considering the space to hold the data
Another solution:
main() {
int n;
cin >> n;
string s;
cin >> s;
unordered_set<char> se;
bool yes = true;
for(int i = 0; i < n; i++) {
if(i && s[i] == s[i1]) continue;
if(se.count(s[i])) {
yes = false;
break;
}
se.insert(s[i]);
}
if(yes) cout << "YES";
else cout << "NO";
}
Time Complexity: O(n)
Space Complexity: O(n) # the unordered set
used to contain
elements for checking.
Problem 2: Black Square
main() {
vector<int> v(4);
for(auto& e: v) cin >> e;
string s;
cin >> s;
long long total = 0;
for(auto& c: s) {
int p = c  '0'  1; // additional 1 for zero based indexing
total += v[p];
}
cout << total;
}
This would be more fun to write in Python.
v = list(map(int, input().split()))
s = input()
s = [int(c)1 for c in s] # 1 for zero based indexing
total = sum(v[i] for i in s)
print(total)
I am sure we could use find STL algorithm for the C++ code.
That is all for today 2 implementation problem solving.
Let us hop on to learning one new/old string algorithm.
String Algorithm
The basic question when it comes to string is about, whether a given pattern
of length m
occurs in a text
of length n
.
The problem can be solved using naive method in O(n*m) time.
main() {
string text = "abcabc";
string pattern = "abc";
int n = text.length(), m = pattern.length();
bool found = false;
// looping through all starting position of the pattern
for(int i = 0; i < nm+1; i++) {
// checking if the substring matches
if(text.substr(i, m) == pattern) {
found = true;
break;
}
}
if(found) cout << "YES";
else cout << "NO";
}
Now there are algorithms that can solve the above pattern matching in O(n+m) time. The first one that comes in mind is the famous
Knuth Morris Pratt
or better known as KMP algorithm.
Here is a video of Donald Knuth talking about KMP algorithm.
vector<int> prefix_func(string s) {
int n = s.length();
vector<int> pi(n, 0);
for(int i = 1; i < n; i++) {
int j = pi[i1];
while(j > 0 && s[i] != s[j])
j = pi[j1];
if(s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
To use KMP algorithm, precompute the table using above prefix_func
.
So for given pattern
and text
, the string that should be passed to prefix_func
is pattern + x + text
, where 'x' is some character which doesn't belong to neither pattern nor text.
The different questions that can be answered are:
 Does the pattern occur in the text?
 How many times does the pattern occur in the text?
 If pattern occurs, find the starting position in text.
 Find maximum nonoverlapping occurrence of the pattern in the text. And many more.
Most of the time, pattern matching is used as a part for solving a problem, and not a whole problem.
Sources:

prefix_function
: cpalgorithms
Resources for additonal learning and practicing:
Dated: 13th July 2021
Top comments (0)