De Bruijn Sequence

De Bruijn Sequence is a binary sequence of order $n$ of bits $b_i \in {0, 1}$ where $b = {b_i, ..., b_{2^n}}$ such that every string of length $n$ ${a_1, ..., a_n} \in$ {0, 1} $^ n$ occurs exactly once consecutively in $b$. To generate a De Bruijn Sequence, we need to get the Euler circuit for the graph for all $n - 1$ possible stringds. For example, given $n = 4$ & $k = 2$,

We would have a sequence of length $2 ^ 4 = 16$ using Eulerian $k$-D de Bruijn graph cycle where $k = n - 1$ which is 3 in this case. Each edge will be traversed exactly once to use each of the 16 4-digit sequences exactly once.

The Eulerian path is

$$000, 000, 001, 011, 111, 111, 110, 101, 011, 110, 100, 001, 010, 101, 010, 100, 000.$$

The de Bruijn sequence is

$$0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1$$

For output sequences of length $k = 4$, we got

    {0  0  0  0} 1  1  1  1  0  1  1  0  0  1  0  1
     0 {0  0  0  1} 1  1  1  0  1  1  0  0  1  0  1
     0  0 {0  0  1  1} 1  1  0  1  1  0  0  1  0  1
     0  0  0 {0  1  1  1} 1  0  1  1  0  0  1  0  1
     0  0  0  0 {1  1  1  1} 0  1  1  0  0  1  0  1
     0  0  0  0  1 {1  1  1  0} 1  1  0  0  1  0  1
     0  0  0  0  1  1 {1  1  0  1} 1  0  0  1  0  1
     0  0  0  0  1  1  1 {1  0  1  1} 0  0  1  0  1
     0  0  0  0  1  1  1  1 {0  1  1  0} 0  1  0  1
     0  0  0  0  1  1  1  1  0 {1  1  0  0} 1  0  1
     0  0  0  0  1  1  1  1  0  1 {1  0  0  1} 0  1
     0  0  0  0  1  1  1  1  0  1  1 {0  0  1  0} 1
     0  0  0  0  1  1  1  1  0  1  1  0 {0  1  0  1}
     0} 0  0  0  1  1  1  1  0  1  1  0  0 {1  0  1 ...
 ... 0  0} 0  0  1  1  1  1  0  1  1  0  0  1 {0  1 ...
 ... 0  0  0} 0  1  1  1  1  0  1  1  0  0  1  0 {1 ...

To find Euler circuit, we can use Hierholzer’s algorithm to get it in linear time. If we randomly traverse the graph without repeating edges, it will eventually end up on the same vertex but the path may not include all the edges. Therefore, we have to remove those visited edges from the graph, which will split into several components. All the components contain Euler Circuit.

Cracking the Safe (Hard)

There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].

The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.

For example, the correct password is "345" and you enter in "012345": After typing 0, the most recent 3 digits is "0", which is incorrect. After typing 1, the most recent 3 digits is "01", which is incorrect. After typing 2, the most recent 3 digits is "012", which is incorrect. After typing 3, the most recent 3 digits is "123", which is incorrect. After typing 4, the most recent 3 digits is "234", which is incorrect. After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.

What is the string of minimum length that will unlock the safe at some point of entering it? For example, $n = 2, k = 2$, one of the possible answers is $01100$ because we can type $01$ from the $1st$ digit, $11$ from the $2nd$ digit, $10$ from the $3rd$ digit, and $00$ from the $4th$ digit.

Solution

class Solution {
public:
    string ans;
    vector<vector<int>> vis;
    int n, k, v;

    void dfs(int u) {
        for(int i = 0; i < k; i++) {
            if(!vis[u][i]) {
                vis[u][i] = 1;
                dfs((u * k + i) % v);
                ans += '0' + i;
            }
        }    
    }

    string crackSafe(int n, int k) {
        if(k == 1) return string(n, '0');
        this->n = n, this->k = k;
        v = pow(k, n - 1);
        // vis[k ^ (n - 1)][k]
        vis.resize(v, vector<int>(k));
        dfs(0);
        return ans + ans.substr(0, n - 1);
    }
};

LeetCode - Paint House

These problems are basically same except the constraints. In the first question, k is always 3. If we solve the second problem, then we can also solve the first problem. Therefore, let's think about the case when k is not fixed.

Paint House (Medium)

Paint House (Medium)

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Return the minimum cost to paint all houses.

Paint House II (Hard)

Paint House II (Hard)

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x k cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Return the minimum cost to paint all houses.

Solution 1 : Dynamic Programming

Supposing we got 5 houses and 6 colors (red, green, blue, yellow, purple, orange).

Starting from the second, we can only choose the different color from the previous row. For example, if costs[1][0] is selected, then the only possible color to be chosen from the previous row must be from column 1 to column 5 and pick the minimum costs[0][j] where $j \neq 0$ in this example.

Therefore, we iterate each color in the current row and compare it from the previous row to find the minimum cost. The following solution gives $O(n * k ^ 2)$ time complexity and $O(k)$ space complexity.

def minCostII(self, costs: List[List[int]]) -> int:
    n = len(costs)
    k = len(costs[0])
    prev_row = costs[0]
    for house in range(1, n):
        cur_row = [0] * k
        for cur_color in range(k):
            prev_best = math.inf
            for prev_color in range(k):
                if cur_color == prev_color:
                    continue
                prev_best = min(prev_best, prev_row[prev_color])
            cur_row[cur_color] += prev_best + costs[house][cur_color]
        prev_row = cur_row
    return min(prev_row)

which can be written in a cleaner way.

def minCostII(self, costs: List[List[int]]) -> int:
    k = len(costs[0])
    prev_row = [0] * k
    for cur_row in costs:
        prev_row = [cur_row[i] + min(prev_row[:i] + prev_row[i + 1:]) for i in range(k)]
    return min(prev_row)

Solution 2: Markov Chain

If n and k are set to $500$, then Solution 1 will exceed time limit. Here's another solution using the idea of Markov Chain. Given that k states (colors) and n stages, we can update the matrix to find out the optimal value for each state at the current stage. The idea is to find out the first and the second minimum cost for each stage. For the next stage, we can update each cost by adding either the first minimum cost or the second one. The reason we need two minimum cost is that we cannot paint the same color. If the index of the first minimum cost from the previous stage is i and we have to use the second minimum cost for the current stage, and vice versa.

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        k = len(matrix[0])
        for house in range(1, n):
            first_mi_color = second_mi_color = None
            # find first & second min color
            for color in range(k):
                cost = matrix[house - 1][color]
                if first_mi_color is None or cost < matrix[house - 1][first_mi_color]:
                    second_mi_color = first_mi_color
                    first_mi_color = color
                elif second_mi_color is None or cost < matrix[house - 1][second_mi_color]:
                    second_mi_color = color
            # update matrix for the current row
            for color in range(k):
                if color == first_mi_color:
                    matrix[house][color] += matrix[house - 1][second_mi_color]
                else:
                    matrix[house][color] += matrix[house - 1][first_mi_color]
        return min(matrix[-1])

Here's the shorter version.

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        n, k = len(costs), len(costs[0])
        for house in range(1, n):
            first_mi_cost = min(costs[house - 1])
            idx = costs[house - 1].index(first_mi_cost)
            second_mi_cost = min(costs[house - 1][:idx] + costs[house - 1][idx + 1:])
            for color in range(k):
                if color == idx:
                    costs[house][color] += second_mi_cost
                else:
                    costs[house][color] += first_mi_cost
        return min(costs[-1])

Codeforces - Deltix Round, Summer 2021 - 1556D. Take a Guess

https://codeforces.com/contest/1556/problem/D

Problem

This is an interactive task

William has a certain sequence of integers $a_1, a_2, ..., a_n$ in his mind, but due to security concerns, he does not want to reveal it to you completely. William is ready to respond to no more than 2⋅𝑛 of the following questions:

What is the result of a bitwise AND of two items with indices 𝑖 and 𝑗 (𝑖≠𝑗) What is the result of a bitwise OR of two items with indices 𝑖 and 𝑗 (𝑖≠𝑗) You can ask William these questions and you need to find the 𝑘-th smallest number of the sequence.

Formally the 𝑘-th smallest number is equal to the number at the 𝑘-th place in a 1-indexed array sorted in non-decreasing order. For example in array [5,3,3,10,1] 4th smallest number is equal to 5, and 2nd and 3rd are 3.

Input

It is guaranteed that for each element in a sequence the condition 0≤𝑎𝑖≤109 is satisfied.

Interaction

In the first line you will be given two integers 𝑛 and 𝑘 (3≤𝑛≤104,1≤𝑘≤𝑛), which are the number of items in the sequence 𝑎 and the number 𝑘.

After that, you can ask no more than 2⋅𝑛 questions (not including the "finish" operation).

Each line of your output may be of one of the following types:

"or i j" (1≤𝑖,𝑗≤𝑛,𝑖≠𝑗), where 𝑖 and 𝑗 are indices of items for which you want to calculate the bitwise OR.

"and i j" (1≤𝑖,𝑗≤𝑛,𝑖≠𝑗), where 𝑖 and 𝑗 are indices of items for which you want to calculate the bitwise AND.

"finish res", where 𝑟𝑒𝑠 is the 𝑘th smallest number in the sequence. After outputting this line the program execution must conclude.

In response to the first two types of queries, you will get an integer 𝑥, the result of the operation for the numbers you have selected.

After outputting a line do not forget to output a new line character and flush the output buffer. Otherwise you will get the "Idleness limit exceeded". To flush the buffer use:

fflush(stdout) in C++

System.out.flush() in Java

stdout.flush() in Python

flush(output) in Pascal

for other languages refer to documentation

If you perform an incorrect query the response will be −1. After receiving response −1 you must immediately halt your program in order to receive an "Incorrect answer" verdict.

Explanation

In short, we can retrieve the first 3 numbers first by asking 3 OR questions and 3 AND questions using the fact that

$$a + b = (a \lor b) + (a \land b)$$

After that we can fix the first number to find the rest of them. Once we have all the numbers, we sort the array and find the $k-th$ one.

The first 3 numbers can be obtained by the following approach. First we

• ask or 1 0 and and 1 0 to get $a_{01}$
• ask or 1 2 and and 1 2 to get $a_{12}$
• ask or 0 2 and and 0 2 to get $a_{02}$

Now we know that

$$a_{01} = a_0 + a_1$$ $$a_{12} = a_1 + a_2$$ $$a_{02} = a_0 + a_2$$

We can use these 3 numbers to obtain the first 3 numbers in the array.

$$a_0 = \frac{(a_{01} + a_{02} - a_{12})}{2}$$ $$a_1 = \frac{(a_{01} + a_{12} - a_{02})}{2}$$ $$a_2 = \frac{(a_{02} + a_{12} - a_{01})}{2}$$

Starting from $i = 3$, we can fix the first number to find out $a_i$.

• ask or 0 i and and 0 i to get $a_{0i}$

so that we will have

$$a_i = a_{0i} - a_0$$

Solution

long long OR(int i, int j) {
    cout << "or " << i + 1 << " " << j + 1 << endl;
    long long x; cin >> x;
    return x;
}

long long AND(int i, int j) {
    cout << "and " << i + 1 << " " << j + 1 << endl;
    long long x; cin >> x;
    return x;
}


void solve() {
    long long n, k; cin >> n >> k;
    vector<long long> a(n);
    long long a_01 = OR(0, 1) + AND(0, 1);
    long long a_12 = OR(1, 2) + AND(1, 2);
    long long a_02 = OR(0, 2) + AND(0, 2);
    a[0] = (a_01 + a_02 - a_12) / 2;
    a[1] = (a_01 + a_12 - a_02) / 2;
    a[2] = (a_02 + a_12 - a_01) / 2;
    for(int i = 3; i < n; i++) {
        long long a_0i = OR(0, i) + AND(0, i);
        a[i] = a_0i - a[0];
    }
    sort(a.begin(), a.end());
    cout << "finish " << a[k - 1] << endl;
}

BinarySearch - Set Bits

https://binarysearch.com/problems/Set-Bits

Problem

Given an integer n, return the total number of set bits in all integers between 1 and n inclusive.

Constraints

$n ≤ 2 ^ {27}$

Solution

The i-th least significant bit can be calculate as

$$(\frac{n}{2 ^ i}) * 2 ^{i - 1} + n \bmod 2 ^ {i} - (2 ^ {i - 1} - 1)$$

if and only if

$$n \bmod ( 2 ^ {i} ) >= (2 ^ {i - 1} - 1)$$

int solve(int n) {
    int two = 2, ans = 0;
    int tmp = n;
    while (tmp) {
        ans += (n / two) * (two >> 1);
        if ((n & (two - 1)) > (two >> 1) - 1) ans += (n & (two - 1)) - (two >> 1) + 1;
        two <<= 1, tmp >>= 1;
    }
    return ans;
}

BinarySearch - Increasing Subsequences of Size K

https://binarysearch.com/problems/Increasing-Subsequences-of-Size-K

Problem

Given a list of integers nums and an integer k, return the number of subsequences of size k that are strictly increasing.

Mod the result by 10 ** 9 + 7.

Constraints

0 ≤ n ≤ 1,000 where n is the length of nums. 1 ≤ k ≤ 10

Solution

Use Dynamic Programming.

Define dp[i][j] to store the count of increasing subsequences of size i ending with element nums[j].

$dp[i][j] = 1$, where $i = 1$ and $1 <= j <= n$

$dp[i][j] = dp[i][j] + dp[i - 1][j]$, where $1 < i <= k$, $i <= j <= n$ and $nums[m] < nums[j]$ for $(i - 1) <= m < j$.

Time Complexity: $O(k * n ^ 2)$

Space Complexity: $O(k * n)$

int solve(vector<int>& nums, int k) {
    int n = (int)nums.size(), dp[k][n], ans = 0, mod = 1e9 + 7;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) dp[0][i] = 1;
    for (int l = 1; l < k; l++) {
        for (int i = l; i < n; i++) {
            dp[l][i] = 0;
            for (int j = l - 1; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[l][i] = (dp[l][i] + dp[l - 1][j]) % mod;
                }
            }
        }
    }
    for (int i = k - 1; i < n; i++) {
        ans = (ans + dp[k - 1][i]) % mod;
    }
    return ans;
}

BinarySearch - Longest Increasing Path

https://binarysearch.com/problems/Longest-Increasing-Path

Problem

Given a two-dimensional integer matrix, find the length of the longest strictly increasing path. You can move up, down, left, or right.

Constraints

n, m ≤ 500 where n and m are the number of rows and columns in matrix

Solution

DFS Approach.

dp[i][j] means the length of longest increasing path starting from (i,j). Traverse four directions iff the next cell is in the bound and the value is greater than the current one. Calculate it recursively and store it back to dp[i][j]. If dp[i][j] has been calculated, return the cached result directly.

int m, n;
vector<vector<int>> dp;

int dfs(vector<vector<int>>& matrix, int i, int j) {
    if (dp[i][j]) return dp[i][j];
    int v = 1;
    if (i + 1 < m && matrix[i + 1][j] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i + 1, j));
    if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i - 1, j));
    if (j + 1 < n && matrix[i][j + 1] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i, j + 1));
    if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i, j - 1));
    dp[i][j] = v;
    return dp[i][j];
}

int solve(vector<vector<int>>& matrix) {
    m = matrix.size(), n = matrix[0].size();
    dp = vector<vector<int>>(m, vector<int>(n, 0));
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, dfs(matrix, i, j));
        }
    }
    return ans;
}

BinarySearch - One Edit Distance

https://binarysearch.com/problems/One-Edit-Distance

Problem

Given two strings s0 and s1 determine whether they are one or zero edit distance away. An edit can be described as deleting a character, adding a character, or replacing a character with another character.

Constraints

n ≤ 100,000 where n is the length of s0. m ≤ 100,000 where m is the length of s1.

Solution

Short and clean.

Find the first index i that s0[i] is not equal to s1[i]

Based on the length of s0 and s1, compare the rest of the sub string are same or not.

bool solve(string s0, string s1) {
    int m = s0.size(), n = s1.size();
    for (int i = 0; i < min(m, n); i++) {
        if (s0[i] != s1[i]) {
            if (m == n)
                return s0.substr(i + 1) == s1.substr(i + 1);
            else if (m < n)
                return s0.substr(i) == s1.substr(i + 1);
            else
                return s0.substr(i + 1) == s1.substr(i);
        }
    }
    return abs(m - n) <= 1;
}

BinarySearch - Escape-Maze

https://binarysearch.com/problems/Escape-Maze

Problem

You are given a two dimensional integer matrix, representing a maze where 0 is an empty cell, and 1 is a wall. Given that you start at matrix[0][0], return the minimum number of squares it would take to get to matrix[R - 1][C - 1] (where R and C are the number of rows and columns in the matrix).

If it's not possible, return -1.

Constraints

n, m ≤ 250 where n and m are the number of rows and columns in matrix

Solution

Use standard BFS.

Check if the matrix[0][0] and matrix[m-1][n-1] is 1 or not. If so, return -1.

Then we need a queue to store the coordinates and the local count.

Starting from (0,0), go for four directions and check if the target cell is valid or not. If so, update matrix[xx][yy] so that we won't visit it again and add it to the queue. If xx and yy reaches m-1 and n-1, check if the count is the minimal.

int ans = INT_MAX, m, n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
bool ok(int i, int j) {
    return !(i < 0 || i > m - 1 || j < 0 || j > n - 1);
}
int solve(vector<vector<int>>& matrix) {
    m = matrix.size(), n = matrix[0].size();
    if (matrix[0][0] == 1 || matrix[m - 1][n - 1] == 1) return -1;
    queue<pair<pair<int, int="">, int>> q;  // i, j, cnt
    q.push({{0, 0}, 1});
    matrix[0][0] = 1;
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        int x = p.first.first, y = p.first.second, cnt = p.second;
        if (x == m - 1 && y == n - 1) ans = min(ans, cnt);
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (ok(xx, yy) && matrix[xx][yy] == 0) {
                matrix[xx][yy] = 1;
                q.push({{xx, yy}, cnt + 1});
            }
        }
    }
    return ans == INT_MAX ? -1 : ans;
}

BinarySearch - Sum of Two Numbers

https://binarysearch.com/problems/Sum-of-Two-Numbers

Problem Statement

Given a list of numbers nums and a number k, return whether any two elements from the list add up to k. You may not use the same element twice.

Note: Numbers can be negative or 0.

Constraints

n ≤ 100,000 where n is the length of nums

Solution

Use unordered_map to store the complement. If it is found, return true. If not, update m[nums[i]].

bool solve(vector<int>& nums, int k) {
    unordered_map<int, int=""> m;
    for (int i = 0; i < nums.size(); i++) {
        if (m.count(k - nums[i])) return true;
        m[nums[i]] = i;
    }
    return false;
}

BinarySearch - Largest Island Area

https://binarysearch.com/problems/Largest-Island-Area

Problem

You are given a two-dimensional integer matrix of 1s and 0s. A 1 represents land and 0 represents water, so an island is a group of 1s that are neighboring whose perimeter is surrounded by water. You can assume that the edges of the matrix are surrounded by water.

Return the area of the largest island in matrix.

Constraints

n, m ≤ 250 where n and m are the number of rows and columns in matrix

Solution

Textbook flood fill. Search the cell with value 1 to perform dfs. For each dfs, mark all visited cells to 0 so that it won't be visited again. Compare the return value with ans and take the max one.

int dfs(vector<vector<int>>& matrix, int i, int j) {
    if (i < 0 || i > matrix.size() - 1 || j < 0 || j > matrix[0].size() - 1 || matrix[i][j] == 0) return 0;
    matrix[i][j] = 0;
    return 1 + dfs(matrix, i + 1, j) + dfs(matrix, i - 1, j) + dfs(matrix, i, j + 1) + dfs(matrix, i, j - 1);
}
int solve(vector<vector<int>>& matrix) {
    int ans = 0;
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[i].size(); j++) {
            if (matrix[i][j] == 1) {
                ans = max(ans, dfs(matrix, i, j));
            }
        }
    }
    return ans;
}