“Think twice, code once”

Two pointers

This technique is usually used in an array. We have a pointer to the first element of the array and to the last. The first pointer will be increasing and the other one decreasing (you may also find variations of this idea). In practice, intead of using a pointer, a int variable to keep track of the index is usually enough.

Let’s see this technique with an example:

Problem: You are given an array \(a\) of \(n\) elements. You should output the minimum number of intervals \([l_i, r_i] \mid a_i = a_j \forall \, i, j \in [l_i, r_i]\) \([l_1, r_1] \cup [l_2, r_2] \cup \dots \cup [l_m, r_m] = [1, n]\).

\[1 \leq n \leq 10^5\]

Example:

Input:

\(n = 7\)

\(a = 1\ 1\ 1\ 2\ 2\ 3\ 3\)

Output:

\(1\ 3\)

\(4\ 5\)

\(6\ 7\)

First implementation

vector <pair <int, int>> solution1 (const vector <int>& arr) {
  int n = arr.size();
  vector <bool> vis(n, false);
  vector <pair <int, int>> ret;
  for (int l = 0; l < n; l++) {
    if (vis[l]) continue;
    int L = l;
    int R = l;
    for (int r = l; r < n and arr[l] == arr[r]; r++) {
      vis[r] = true;
      R = r;
    }
    ret.push_back({1 + L, 1 + R});
  }
  return ret;  
}

Second implementation

vector <pair <int, int>> solution2 (const vector <int>& arr) {
  int n = arr.size();
  vector <pair <int, int>> ret;
  int l = 0;
  while (l < n) {
    int r = l;
    while (r + 1 < n and arr[l] == arr[r + 1]) r++;
    ret.push_back({1 + l, 1 + r});
    l = r + 1;
  }
  return ret;  
}

Full code

The time complexity of both solutions is \(O(n)\).

Let’s use this technique in this problem:

Problem (2 sum problem): You are given an array \(a\) of \(n\) positive elements and an integer \(target\). You should output two numbers \(i, j \mid i \not = j \land a_i + a_j = target\). It is garantee that a solution always exits.

\[1 \leq n \leq 10^5\] \[1 \leq target \leq 10^9\]

We can use the same technique and sorting to solve the problem in \(O(n \log n)\).

First, let’s sort the array and initiate with \(l = 0 \land r = n - 1\). \(l\) would just increase and \(r\) would just decrease. Then, by the trichotomy property there are three cases:

  • \(a[l] + a[r] == target\)

    Then, we have and answer and our program can finish

  • \(a[l] + a[r] < target\)

    In this case we need to get a greater sum. Decreasing \(r\) the sum may keep the same or smaller. Increasing \(l\) the sum may keep the same or greater. Then, we need to increase \(l\).

  • \(a[l] + a[r] > target\)

    Similar to the previous case, we need to decrease the sum, then we decrease \(r\).

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector <pair <int, int>> arr;
        int index = 0;
        for (int elem: nums) {
            arr.push_back({elem, index});
            index++;
        }
        sort(begin(arr), end(arr));
        int n = nums.size();
        int l = 0, r = n - 1;
        vector <int> ans;
        while (l < r) {
            if (arr[l].first + arr[r].first == target) {
                ans = {arr[l].second, arr[r].second};
                break;
            }
            if (arr[l].first + arr[r].first < target) l++;
            else r--;
        }
        return ans;
    }
};

Extra: This is another solution using STL + fixing variables in \(O(n \log n)\):

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector <int> ans;
        map <int, vector <int>> pos;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            pos[nums[i]].push_back(i);
        }
        for (int x = 0; x < n; x++) {
            int k = target - nums[x];
            if (pos.count(k)) {
                int cnt = 0;
                for (int y: pos[k]) {
                    if (y != x) {
                        ans = {x, y};
                    }
                    cnt++;
                    if (cnt == 2) break;
                }
            }
        }
        return ans;
    }
};

How could you solve the same problem if you need to find three numbers \(x, y, z \mid x \not = y \not = z \land a_x + a_y + a_z = target\) ?

Recursion

Imagine you have a funtion \(f\) that solves a problem in this way:

  • When we are in a state with a specific property, we know how to directly solve the problem.
  • If we are not in a state with the specific property, we can solve the problem using different states of \(f\).

For example:

\[f(n) = 1 \times 2 \times 3 \times \dots \times n\]

We want to compute \(f(n)\) in a recursive way. Then we need:

  • Identify a state with a specific property that we can solve easily.

    If \(n = 0 \to f(0) = 1\).

  • Identify how to solve \(f(n)\) using different states of \(f\) (that are ‘closer’ to the states with a specific property of the above point). For instance:

\[f(n) = \underbrace{1 \times 2 \times 3 \times \dots \times (n - 1)}_{\text{f(n - 1)}} \times n\] \[f(n) = n \times f(n - 1)\]

Then, we are basically saying that if \(n = 0\) we know how to solve the problem, else if we have the answer of \(f(n - 1)\) we can use it to solve \(f(n)\).

In code it is something like this:

ll f (int n) {
  if (n == 0) return 1;
  return n * f(n - 1);
}

What is nice about recursion is that we can think in a recursive way. Thinking in this way the problem may become easier. For example you can say:

Let \(f\) be a function that solves the problem I am trying to solve. Then, you may say. I have no idea how to solve \(f(state)\), but if somehow I would have the answer of \(f(state'), f(state''), f(state'''), \dots\) then I can solve \(f(state)\) and I know how to solve the problem in specific states.

Then, in code, recursive solutions usually have have the form:

T f(state):
  if (state have a specific property):
    solve the problem for this state and return something
  else:
    get the answer of f(state'), f(state''), f(state'''), ...
    and using these answers compute f(state) and return something

For example, let’s solve the problem of the towers of Hanoi.

The tower of Hanoi

Image taken from Wikipedia

Problem: You have 3 rods, and a pile of \(n\) disks in one rod. Each disk have different diameter, the disks are in order in the stack, the greatest in the button and the smallest on the top. We want to move all the disks to another rod. We can only move the top disk of a stack to another rod if the other rod is empty or the diameter of its top element is greater that the one we are moving. Can you give a sequence of movements to solve this problem ?

Let’s say we have the function \(f\) such that \(f(source, target, pivot, n)\) moves the \(n\) disks that are in the source rod to the target rod. Then, we can say:

If I want to move the \(n\) disks from source rod to the target rod, first I need to move \(n - 1\) disks from source to pivot, then I move the last disk in source to target. After that, we need to move the \(n - 1\) disks in pivot to target and we are done. Moreover, if there is only one disk we can direcly move it to target. Then, we can write \(f\) in this way:

void f(source, target, pivot, n):
  if n == 1:
    move the disk in source to target
    return
  # move the top n - 1 disks in source to pivot
  f(source, pivot, target, n - 1)
  # move the last disk in source to target
  f(source, target, pivot, 1)
  # move the n - 1 disks in pivot to target
  f(pivot, target, source, n - 1)

And that’s all. It solves the problem!

Exercises

Write recursive functions to compute:

  • \(fib(n)\)
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll fib (int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

int main () {
  int n = 40;
  cout << fib(n) << '\n';
  return (0);
}

  • Sum of digits of a number \(n\)
#include <bits/stdc++.h>

using namespace std;

int sumOfDigits (int n) {
  if (n == 0) return 0;
  return (n % 10) + sumOfDigits(n / 10);
}

int main () {
  int n = 999;
  cout << sumOfDigits(n) << endl;
  return (0);
}

  • \(C(n, k)\)
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll comb (int n, int m) {
  if (m == 0) return 1;
  if (n == m) return 1;
  return comb(n - 1, m - 1) + comb(n - 1, m);
}

int main () {
  cout << comb(4, 2) << '\n';
  return (0);
}

  • Determinant of a matrix
// This is your challenge

Modular arithmetic

When we are doing a division we are basically computing:

\[a = b \cdot \lfloor a / b \rfloor + r\] \[0 \leq r < b\]

Now, we say:

\[a \equiv r \mod b \lor r \equiv a \mod b\]

That is \(x \equiv y \mod m\) iff \((x - y) | m\).

Note: \(r\) is what we get when we compute \(a \% b\).

When working with modular arithmetic, that set of values our numbers can take is \(0, 1, 2, \dots, m - 1\), where \(m\) is a constant. So each number \(x\) is represented as \(x \mod m\).

For example, if \(m = 12 \to x = 20\) is represented as \(x \mod 12 = 8\).

In some problems you will be asked to output the answer module \(m\). For doing this you may just solve your problem and in the end output \(your\_answer \% m\). Nevertheless, what happend if \(m= 10^9 + 7\) and you have:

int m = 1e9 + 7; // 10^9 + 7
long long a = 1e10; // 10^10
long long your_answer = (a * a) % m;

Althought we know that the \(\%\) operator will give us a result less than \(m\), \(a * a\) can not fit in a long long (\(10^{20} > 2^{63}\)), so we have overflow. In order to fix that, we can use the properties of modular arithmetic:

\[(x + y) \mod m = (x \mod m + y \mod m) \mod m\] \[(x - y) \mod m = (x \mod m - y \mod m) \mod m\] \[(x \times y) \mod m = (x \mod m \times y \mod m) \mod m\] \[x^n \mod m = (x \mod m)^n \mod m\]

So, we can fix the above code in this way:

long long your_answer = ((a % m) * (a % m)) % m;

From the above properties we have:

\(x \mod m = x \mod m + 0 = x \mod m + m \mod m = (x + m) \mod m\)

The last equation will be useful because in C++ the result of \(\%\) can be in \((-m, m)\). For example:

cout << (-4) % 5 << '\n'; // -4

Then, the subtraction should be:

\[(x - y) \mod m = ((x \mod m - y \mod m) \mod m + m) \mod m\]

Now, the result will always be in \([0, m)\).

Binary exponenciation

\(a^b\) can be expressed in a recursive way.

\[ \text{power}(a, b) = \begin{cases} 1 & \quad \text{If } b = 0 \\ \text{power}(a, \lfloor b / 2 \rfloor) ^ 2 & \, \text{if } b \mod 2 = 0 \\ a \times \text{power}(a, \lfloor b / 2 \rfloor) ^ 2 & \, \text{if } b \mod 2 = 1 \end{cases} \]

Moreover, from the properties of modular arithmetic, we can get \(a^b \mod m\) as:

\[ \text{binpow}(a, b) = \begin{cases} 1 & \quad \text{If } b = 0 \\ \text{binpow}(a, \lfloor b / 2 \rfloor) ^ 2 \mod m & \, \text{if } b \mod 2 = 0 \\ (a \times \text{binpow}(a, \lfloor b / 2 \rfloor) ^ 2) \mod m & \, \text{if } b \mod 2 = 1 \end{cases} \]

In code:

const ll m = 1e9 + 7;

ll binpow (ll a, ll b) {
  if (b == 0) return 1;
  a %= m;
  ll res = binpow(a, b / 2);
  res = (res * res) % m;
  if (b % 2 == 1) res = (a * res) % m;
  return res;
}

The above code compute \(a^b \mod m\) in \(O(\log b)\).

This function will be really useful, but before using it, we need to know one theorem.

Fermat’s little theorem

If \(m\) is prime and \(0 < a < m\), we have:

\[a^{m - 1} \equiv 1 \mod m\]

Moreover, we say the the inverse of \(a\) is \(b\) if:

\[ab \equiv 1 \mod m\]

\(b\) is written as \(a^{-1}\).

And as \(a^{m - 1} = a \cdot a^{m - 2}\)

Using Fermat’s little theorem we have that the inverse of \(a\) is \(a^{m - 2}\) if \(m\) is prime.

Now, we can mention one more property of modular arithmetic (if \(b^{-1}\) exists).

\[\frac{a}{b} \mod m = ((a \mod m) \times (b^{-1} \mod m)) \mod m\]

Let’s see how it is useful in this problem.

Problem: Compute \(S = (1 + a + a^2 + a^3 + \dots + a^k) \mod m\).

\[m = 10^9 + 7 \text{ (is prime)}\] \[1 \leq a \leq 10^{18}\] \[1 \leq k \leq 10^{18}\]

If \(a = 1 \to S = (k + 1) \mod m\)

If \(a > 1 \to S = \frac{a^{k + 1} - 1}{a - 1} \mod m\)

Then, we can use the above properties to compute that.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll m = 1e9 + 7;

ll add (ll a, ll b) { return ((a % m) + (b % m)) % m; }
ll sub (ll a, ll b) { return (((a % m) - (b % m)) + m) % m; }
ll mul (ll a, ll b) { return ((a % m) * (b % m)) % m; }

ll binpow (ll a, ll b) {
  if (b == 0) return 1;
  a %= m;
  ll res = binpow(a, b / 2);
  res = mul(res, res);
  if (b % 2 == 1) res = mul(a, res);
  return res;
}

ll inverse (ll a) { return binpow(a, m - 2); }

int main () {
  ll a, k;
  cin >> a >> k;
  if (sub(a, 1) == 0) {
    cout << add(k, 1) << '\n';
  } else {
    cout << mul(sub(binpow(a, k + 1), 1), inverse(a - 1)) << '\n';
  }
  return (0);
}

Recommended readings:

Contest

You can find the contest here.

Brutality

The optimal strategy is to take equal consecutive elements and take the \(k\) highest values. We can implement this idea with two pointers and sorting in \(O(n \log n)\).

#include <bits/stdc++.h>

#define all(X) begin(X), end(X)

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  ll n, k;
  cin >> n >> k;
  vector <ll> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  string s;
  cin >> s;
  ll ans = 0;
  for (int i = 0; i < n;) {
    vector <ll> tmp;
    tmp.push_back(a[i]);
    int j = i + 1;
    while (j < n and s[i] == s[j]) tmp.push_back(a[j]), j++;
    sort(rbegin(tmp), rend(tmp));
    int cnt = 0;
    for (ll elem: tmp) {
      if (cnt == k) break;
      ans += elem;
      cnt++;
    }
    i = j;
  }
  cout << ans << endl;
  return (0);
}

Fox and Snake

There is a pattern every four rows.

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;
     
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int r = 0; r < n; r++) {
    if (r % 4 == 0 or r % 4 == 2) {
      cout << string(m, '#') << '\n';
    } else if (r % 4 == 1) {
      cout << string(m - 1, '.') + '#' << '\n';
    } else {
      cout << '#' + string(m - 1, '.') << '\n';
    }
  }
  return (0);
}

Counting Chaos

Just try all options.

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;

bool isPalindrome (int hh, int mm) {
  int val = hh * 100 + mm;
  string s = to_string(val);
  string rs = s;
  reverse(all(rs));
  return s == rs;
}

int val (char ch) { return ch - '0'; }

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    string s;
    cin >> s;
    int hh = val(s[0]) * 10 + val(s[1]);
    int mm = val(s[3]) * 10 + val(s[4]);
    do {
      mm++;
      if (mm == 60) mm = 0, hh++;
      if (hh == 24) hh = 0;
    } while (!isPalindrome(hh, mm));
    cout << setfill('0') << setw(2) << hh << ":";
    cout << setfill('0') << setw(2) << mm << "\n";
  }
  return (0);
}

Mirror, Mirror

Just implement what the problem says. Be careful with the implementation.

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;

vector <string> rotate90 (const vector <string>& a) {
  int n = sz(a);
  vector <string> b = a;
  for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
      b[c][n - 1 - r] = a[r][c];
    }
  }
  return b;
}

vector <string> reflect (const vector <string>& a) {
  int n = sz(a);
  vector <string> b = a;
  for (int r = 0; 2 * r < n; r++) {
    swap(b[r], b[n - 1 - r]);
  }
  return b;
}

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc = 0;
  int n;
  while (cin >> n) {
    vector <string> a(n);
    vector <string> b(n);
    for (int r = 0; r < n; r++) cin >> a[r] >> b[r];
    cout << "Pattern " << ++tc << " was ";
    if (a == b) {
      cout << "preserved.\n";
      continue;
    }
    int rotate = 0;
    vector <string> cur = a;
    for (int i = 1; i < 4; i++) {
      cur = rotate90(cur);
      if (cur == b) {
        rotate = 90 * i;
        break;
      }
    }
    if (rotate != 0) {
      cout << "rotated " << rotate << " degrees.\n";
      continue;
    }
    rotate = 0;
    cur = reflect(a);
    if (cur == b) {
      cout << "reflected vertically.\n";
      continue;
    }
    for (int i = 1; i < 4; i++) {
      cur = rotate90(cur);
      if (cur == b) {
        rotate = 90 * i;
        break;
      }
    }
    if (rotate != 0) {
      cout << "reflected vertically and rotated " << rotate << " degrees.\n";
      continue;
    }
    cout << "improperly transformed.\n";
  }
  return (0);
}

Fractal

You can create a matrix filled with spaces, select a position and start doing the recursion to store the fractal in the matrix. The choice or the initial position and how to do the transition can be obtained by getting a pattern with the first values of \(n\).

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

vector <string> grid;
int DR[] = {-1, -1, 1, 1, 0};
int DC[] = {1, -1, 1, -1, 0};

void print () {
  for (int i = 0; i < grid.size(); i++) {
    string& row = grid[i];
    int j = row.size() - 1;
    while (row[j] == ' ') row.erase(row.begin() + j);
    cout << row << endl;
  }
  cout << '-' << endl;
}

void rec (int r, int c, int step) {
  if (step == 0) {
    grid[r][c] = 'X';
    return;
  }
  for (int d = 0; d < 5; d++) {
    rec(r + DR[d] * step, c + DC[d] * step, step / 3);
  }
}

int main () {
  int n;
  while (cin >> n, n != -1) {
    int gridSize = int(pow(3, n - 1));
    grid = vector <string> (gridSize, string(gridSize, ' '));
    int initial = (n == 1) ? 0 : gridSize / 3 + gridSize / 6; 
    int step = gridSize / 3;
    rec(initial, initial, step);
    print();
  }
  return (0);
}

Next

Previous