Day 1: Rebooting the competitive programming drive-拾光赋

Day 1: Rebooting the competitive programming drive

4年前发布

0439

Competitive Programming (8 Part Series)

1 Day 1: Rebooting the competitive programming drive
2 Day 5: Inconsistent days
… 4 more parts…
3 Competitive Programming Goals
4 CP Template
5 Day 8: Stacking up
6 Day 9: Uping the problem rating
7 Type Conversion in C++
8 Day 34: Slowly Building Up

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!


<span>main</span><span>()</span> <span>{</span>
  <span>int</span> <span>n</span><span>;</span>
  <span>cin</span> <span>>></span> <span>n</span><span>;</span>
  <span>string</span> <span>s</span><span>;</span>
  <span>cin</span> <span>>></span> <span>s</span><span>;</span>
  <span>s</span><span>.</span><span>erase</span><span>(</span><span>unique</span><span>(</span><span>begin</span><span>(</span><span>s</span><span>),</span> <span>end</span><span>(</span><span>s</span><span>)),</span> <span>end</span><span>(</span><span>s</span><span>));</span>
  <span>sort</span><span>(</span><span>begin</span><span>(</span><span>s</span><span>),</span> <span>end</span><span>(</span><span>s</span><span>));</span>
  <span>auto</span> <span>it</span> <span>=</span> <span>unique</span><span>(</span><span>begin</span><span>(</span><span>s</span><span>),</span> <span>end</span><span>(</span><span>s</span><span>));</span>
  <span>if</span><span>(</span><span>it</span> <span>!=</span> <span>end</span><span>(</span><span>s</span><span>))</span> <span>cout</span> <span><<</span> <span>"NO"</span><span>;</span>
  <span>else</span> <span>cout</span> <span><<</span> <span>"YES"</span><span>;</span>
<span>}</span>
<span>main</span><span>()</span> <span>{</span>
  <span>int</span> <span>n</span><span>;</span>
  <span>cin</span> <span>>></span> <span>n</span><span>;</span>
  <span>string</span> <span>s</span><span>;</span>
  <span>cin</span> <span>>></span> <span>s</span><span>;</span>
  <span>s</span><span>.</span><span>erase</span><span>(</span><span>unique</span><span>(</span><span>begin</span><span>(</span><span>s</span><span>),</span> <span>end</span><span>(</span><span>s</span><span>)),</span> <span>end</span><span>(</span><span>s</span><span>));</span>
  <span>sort</span><span>(</span><span>begin</span><span>(</span><span>s</span><span>),</span> <span>end</span><span>(</span><span>s</span><span>));</span>
  <span>auto</span> <span>it</span> <span>=</span> <span>unique</span><span>(</span><span>begin</span><span>(</span><span>s</span><span>),</span> <span>end</span><span>(</span><span>s</span><span>));</span>
  <span>if</span><span>(</span><span>it</span> <span>!=</span> <span>end</span><span>(</span><span>s</span><span>))</span> <span>cout</span> <span><<</span> <span>"NO"</span><span>;</span>
  <span>else</span> <span>cout</span> <span><<</span> <span>"YES"</span><span>;</span>
<span>}</span>
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";
}

Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(nlog(n))
Space Complexity: O(1) # not considering the space to hold the data

Another solution:


<span>main</span><span>()</span> <span>{</span>
  <span>int</span> <span>n</span><span>;</span>
  <span>cin</span> <span>>></span> <span>n</span><span>;</span>
  <span>string</span> <span>s</span><span>;</span>
  <span>cin</span> <span>>></span> <span>s</span><span>;</span>
  <span>unordered_set</span><span><</span><span>char</span><span>></span> <span>se</span><span>;</span>
  <span>bool</span> <span>yes</span> <span>=</span> <span>true</span><span>;</span>
  <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>;</span> <span>i</span><span>++</span><span>)</span> <span>{</span>
    <span>if</span><span>(</span><span>i</span> <span>&&</span> <span>s</span><span>[</span><span>i</span><span>]</span> <span>==</span> <span>s</span><span>[</span><span>i</span><span>-</span><span>1</span><span>])</span> <span>continue</span><span>;</span>
    <span>if</span><span>(</span><span>se</span><span>.</span><span>count</span><span>(</span><span>s</span><span>[</span><span>i</span><span>]))</span> <span>{</span>
      <span>yes</span> <span>=</span> <span>false</span><span>;</span>
      <span>break</span><span>;</span>
    <span>}</span>
    <span>se</span><span>.</span><span>insert</span><span>(</span><span>s</span><span>[</span><span>i</span><span>]);</span>
  <span>}</span>
  <span>if</span><span>(</span><span>yes</span><span>)</span> <span>cout</span> <span><<</span> <span>"YES"</span><span>;</span>
  <span>else</span> <span>cout</span> <span><<</span> <span>"NO"</span><span>;</span>
<span>}</span>
<span>main</span><span>()</span> <span>{</span>
  <span>int</span> <span>n</span><span>;</span>
  <span>cin</span> <span>>></span> <span>n</span><span>;</span>
  <span>string</span> <span>s</span><span>;</span>
  <span>cin</span> <span>>></span> <span>s</span><span>;</span>
  <span>unordered_set</span><span><</span><span>char</span><span>></span> <span>se</span><span>;</span>
  <span>bool</span> <span>yes</span> <span>=</span> <span>true</span><span>;</span>
  <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>;</span> <span>i</span><span>++</span><span>)</span> <span>{</span>
    <span>if</span><span>(</span><span>i</span> <span>&&</span> <span>s</span><span>[</span><span>i</span><span>]</span> <span>==</span> <span>s</span><span>[</span><span>i</span><span>-</span><span>1</span><span>])</span> <span>continue</span><span>;</span>
    <span>if</span><span>(</span><span>se</span><span>.</span><span>count</span><span>(</span><span>s</span><span>[</span><span>i</span><span>]))</span> <span>{</span>
      <span>yes</span> <span>=</span> <span>false</span><span>;</span>
      <span>break</span><span>;</span>
    <span>}</span>
    <span>se</span><span>.</span><span>insert</span><span>(</span><span>s</span><span>[</span><span>i</span><span>]);</span>
  <span>}</span>
  <span>if</span><span>(</span><span>yes</span><span>)</span> <span>cout</span> <span><<</span> <span>"YES"</span><span>;</span>
  <span>else</span> <span>cout</span> <span><<</span> <span>"NO"</span><span>;</span>
<span>}</span>
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[i-1]) continue;
    if(se.count(s[i])) {
      yes = false;
      break;
    }
    se.insert(s[i]);
  }
  if(yes) cout << "YES";
  else cout << "NO";
}

Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(n)
Space Complexity: O(n) # the unordered set used to contain
elements for checking.

Problem 2: Black Square


<span>main</span><span>()</span> <span>{</span>
  <span>vector</span><span><</span><span>int</span><span>></span> <span>v</span><span>(</span><span>4</span><span>);</span>
  <span>for</span><span>(</span><span>auto</span><span>&</span> <span>e</span><span>:</span> <span>v</span><span>)</span> <span>cin</span> <span>>></span> <span>e</span><span>;</span>
  <span>string</span> <span>s</span><span>;</span>
  <span>cin</span> <span>>></span> <span>s</span><span>;</span>
  <span>long</span> <span>long</span> <span>total</span> <span>=</span> <span>0</span><span>;</span>
  <span>for</span><span>(</span><span>auto</span><span>&</span> <span>c</span><span>:</span> <span>s</span><span>)</span> <span>{</span>
    <span>int</span> <span>p</span> <span>=</span> <span>c</span> <span>-</span> <span>'0'</span> <span>-</span> <span>1</span><span>;</span>  <span>// additional -1 for zero based indexing</span>
    <span>total</span> <span>+=</span> <span>v</span><span>[</span><span>p</span><span>];</span>
  <span>}</span>
  <span>cout</span> <span><<</span> <span>total</span><span>;</span>
<span>}</span>
<span>main</span><span>()</span> <span>{</span>
  <span>vector</span><span><</span><span>int</span><span>></span> <span>v</span><span>(</span><span>4</span><span>);</span>
  <span>for</span><span>(</span><span>auto</span><span>&</span> <span>e</span><span>:</span> <span>v</span><span>)</span> <span>cin</span> <span>>></span> <span>e</span><span>;</span>
  <span>string</span> <span>s</span><span>;</span>
  <span>cin</span> <span>>></span> <span>s</span><span>;</span>
  <span>long</span> <span>long</span> <span>total</span> <span>=</span> <span>0</span><span>;</span>
  <span>for</span><span>(</span><span>auto</span><span>&</span> <span>c</span><span>:</span> <span>s</span><span>)</span> <span>{</span>
    <span>int</span> <span>p</span> <span>=</span> <span>c</span> <span>-</span> <span>'0'</span> <span>-</span> <span>1</span><span>;</span>  <span>// additional -1 for zero based indexing</span>
    <span>total</span> <span>+=</span> <span>v</span><span>[</span><span>p</span><span>];</span>
  <span>}</span>
  <span>cout</span> <span><<</span> <span>total</span><span>;</span>
<span>}</span>
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;
}

Enter fullscreen mode Exit fullscreen mode

This would be more fun to write in Python.


<span>v</span> <span>=</span> <span>list</span><span>(</span><span>map</span><span>(</span><span>int</span><span>,</span> <span>input</span><span>().</span><span>split</span><span>()))</span>
<span>s</span> <span>=</span> <span>input</span><span>()</span>
<span>s</span> <span>=</span> <span>[</span><span>int</span><span>(</span><span>c</span><span>)</span><span>-</span><span>1</span> <span>for</span> <span>c</span> <span>in</span> <span>s</span><span>]</span>  <span># -1 for zero based indexing </span><span>total</span> <span>=</span> <span>sum</span><span>(</span><span>v</span><span>[</span><span>i</span><span>]</span> <span>for</span> <span>i</span> <span>in</span> <span>s</span><span>)</span>
<span>print</span><span>(</span><span>total</span><span>)</span>
<span>v</span> <span>=</span> <span>list</span><span>(</span><span>map</span><span>(</span><span>int</span><span>,</span> <span>input</span><span>().</span><span>split</span><span>()))</span>
<span>s</span> <span>=</span> <span>input</span><span>()</span>
<span>s</span> <span>=</span> <span>[</span><span>int</span><span>(</span><span>c</span><span>)</span><span>-</span><span>1</span> <span>for</span> <span>c</span> <span>in</span> <span>s</span><span>]</span>  <span># -1 for zero based indexing </span><span>total</span> <span>=</span> <span>sum</span><span>(</span><span>v</span><span>[</span><span>i</span><span>]</span> <span>for</span> <span>i</span> <span>in</span> <span>s</span><span>)</span>
<span>print</span><span>(</span><span>total</span><span>)</span>
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)

Enter fullscreen mode Exit fullscreen mode

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.


<span>main</span><span>()</span> <span>{</span>
  <span>string</span> <span>text</span> <span>=</span> <span>"abcabc"</span><span>;</span>
  <span>string</span> <span>pattern</span> <span>=</span> <span>"abc"</span><span>;</span>
  <span>int</span> <span>n</span> <span>=</span> <span>text</span><span>.</span><span>length</span><span>(),</span> <span>m</span> <span>=</span> <span>pattern</span><span>.</span><span>length</span><span>();</span>
  <span>bool</span> <span>found</span> <span>=</span> <span>false</span><span>;</span>
  <span>// looping through all starting position of the pattern</span>
  <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>-</span><span>m</span><span>+</span><span>1</span><span>;</span> <span>i</span><span>++</span><span>)</span> <span>{</span>
    <span>// checking if the substring matches</span>
    <span>if</span><span>(</span><span>text</span><span>.</span><span>substr</span><span>(</span><span>i</span><span>,</span> <span>m</span><span>)</span> <span>==</span> <span>pattern</span><span>)</span> <span>{</span>
      <span>found</span> <span>=</span> <span>true</span><span>;</span>
      <span>break</span><span>;</span>
    <span>}</span>
  <span>}</span>
  <span>if</span><span>(</span><span>found</span><span>)</span> <span>cout</span> <span><<</span> <span>"YES"</span><span>;</span>
  <span>else</span> <span>cout</span> <span><<</span> <span>"NO"</span><span>;</span>
<span>}</span>
<span>main</span><span>()</span> <span>{</span>
  <span>string</span> <span>text</span> <span>=</span> <span>"abcabc"</span><span>;</span>
  <span>string</span> <span>pattern</span> <span>=</span> <span>"abc"</span><span>;</span>
  <span>int</span> <span>n</span> <span>=</span> <span>text</span><span>.</span><span>length</span><span>(),</span> <span>m</span> <span>=</span> <span>pattern</span><span>.</span><span>length</span><span>();</span>
  <span>bool</span> <span>found</span> <span>=</span> <span>false</span><span>;</span>
  <span>// looping through all starting position of the pattern</span>
  <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>-</span><span>m</span><span>+</span><span>1</span><span>;</span> <span>i</span><span>++</span><span>)</span> <span>{</span>
    <span>// checking if the substring matches</span>
    <span>if</span><span>(</span><span>text</span><span>.</span><span>substr</span><span>(</span><span>i</span><span>,</span> <span>m</span><span>)</span> <span>==</span> <span>pattern</span><span>)</span> <span>{</span>
      <span>found</span> <span>=</span> <span>true</span><span>;</span>
      <span>break</span><span>;</span>
    <span>}</span>
  <span>}</span>
  <span>if</span><span>(</span><span>found</span><span>)</span> <span>cout</span> <span><<</span> <span>"YES"</span><span>;</span>
  <span>else</span> <span>cout</span> <span><<</span> <span>"NO"</span><span>;</span>
<span>}</span>
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 < n-m+1; i++) {
    // checking if the substring matches
    if(text.substr(i, m) == pattern) {
      found = true;
      break;
    }
  }
  if(found) cout << "YES";
  else cout << "NO";
}

Enter fullscreen mode Exit fullscreen mode

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.


<span>vector</span><span><</span><span>int</span><span>></span> <span>prefix_func</span><span>(</span><span>string</span> <span>s</span><span>)</span> <span>{</span>
  <span>int</span> <span>n</span> <span>=</span> <span>s</span><span>.</span><span>length</span><span>();</span>
  <span>vector</span><span><</span><span>int</span><span>></span> <span>pi</span><span>(</span><span>n</span><span>,</span> <span>0</span><span>);</span>
  <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>1</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>;</span> <span>i</span><span>++</span><span>)</span> <span>{</span>
    <span>int</span> <span>j</span> <span>=</span> <span>pi</span><span>[</span><span>i</span><span>-</span><span>1</span><span>];</span>
    <span>while</span><span>(</span><span>j</span> <span>></span> <span>0</span> <span>&&</span> <span>s</span><span>[</span><span>i</span><span>]</span> <span>!=</span> <span>s</span><span>[</span><span>j</span><span>])</span>
        <span>j</span> <span>=</span> <span>pi</span><span>[</span><span>j</span><span>-</span><span>1</span><span>];</span>
    <span>if</span><span>(</span><span>s</span><span>[</span><span>i</span><span>]</span> <span>==</span> <span>s</span><span>[</span><span>j</span><span>])</span>
        <span>j</span><span>++</span><span>;</span>
    <span>pi</span><span>[</span><span>i</span><span>]</span> <span>=</span> <span>j</span><span>;</span>
  <span>}</span>
  <span>return</span> <span>pi</span><span>;</span>
<span>}</span>
<span>vector</span><span><</span><span>int</span><span>></span> <span>prefix_func</span><span>(</span><span>string</span> <span>s</span><span>)</span> <span>{</span>
  <span>int</span> <span>n</span> <span>=</span> <span>s</span><span>.</span><span>length</span><span>();</span>
  <span>vector</span><span><</span><span>int</span><span>></span> <span>pi</span><span>(</span><span>n</span><span>,</span> <span>0</span><span>);</span>
  <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>1</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>;</span> <span>i</span><span>++</span><span>)</span> <span>{</span>
    <span>int</span> <span>j</span> <span>=</span> <span>pi</span><span>[</span><span>i</span><span>-</span><span>1</span><span>];</span>
    <span>while</span><span>(</span><span>j</span> <span>></span> <span>0</span> <span>&&</span> <span>s</span><span>[</span><span>i</span><span>]</span> <span>!=</span> <span>s</span><span>[</span><span>j</span><span>])</span>
        <span>j</span> <span>=</span> <span>pi</span><span>[</span><span>j</span><span>-</span><span>1</span><span>];</span>
    <span>if</span><span>(</span><span>s</span><span>[</span><span>i</span><span>]</span> <span>==</span> <span>s</span><span>[</span><span>j</span><span>])</span>
        <span>j</span><span>++</span><span>;</span>
    <span>pi</span><span>[</span><span>i</span><span>]</span> <span>=</span> <span>j</span><span>;</span>
  <span>}</span>
  <span>return</span> <span>pi</span><span>;</span>
<span>}</span>

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[i-1];
    while(j > 0 && s[i] != s[j])
        j = pi[j-1];
    if(s[i] == s[j])
        j++;
    pi[i] = j;
  }
  return pi;
}

Enter fullscreen mode Exit fullscreen mode

To use KMP algorithm, pre-compute 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 non-overlapping 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 :- cp-algorithms

Resources for additonal learning and practicing:

usaco.guide

Dated: 13th July 2021

Competitive Programming (8 Part Series)

1 Day 1: Rebooting the competitive programming drive
2 Day 5: Inconsistent days
… 4 more parts…
3 Competitive Programming Goals
4 CP Template
5 Day 8: Stacking up
6 Day 9: Uping the problem rating
7 Type Conversion in C++
8 Day 34: Slowly Building Up

原文链接：Day 1: Rebooting the competitive programming drive

展开阅读全文

© 版权声明

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END

Python（EN）
# python # cpp # documenting # competitveprogramming

喜欢就支持一下吧

Don't look back, you're not going that way.

别回头，你要走的不是那条路

评论抢沙发

请登录后发表评论

暂无评论内容