Weekly competition 362 (difference array, brain twisting, full permutation, matrix fast power optimization DP)

In an infinite 2D grid, you start at cell (sx, sy). Every second, you must move to any cell adjacent to the cell you were previously in.

Returns true if you can reach cell (fx, fy) in exactly t seconds later ; otherwise, return false.

A cell's neighbors are the 8 cells surrounding it that share at least one corner with it. You can access the same cell multiple times.

Example 1:

Input: sx = 2, sy = 4, fx = 7, fy = 7, t = 6
Output: true
Explanation: Starting from cell (2, 4) and passing through the cells marked above, you can reach cell (7, 7) exactly 6 seconds later.

Example 2:

Input: sx = 3, sy = 1, fx = 7, fy = 3, t = 3
Output: false
Explanation: Starting from cell (3, 1), passing through the cells marked in the figure above, it will take at least 4 seconds to reach cell (7, 3). Therefore, cell (7, 3) cannot be reached after 3 seconds.

Tip:

• 1 <= sx, sy, fx, fy <= 109
• 0 <= t <= 109

Brain twist

https://leetcode.cn/problems/determine-if-a-cell-is-reachable-at-a-given-time/solutions/2435696/zui-da-keng-dian-zai-yu-qi-dian- he-zhong-o2fg/

This question is very similar to the CF low-level sign-in question style. Note that any step can be divided into two steps. A step diagonally can be divided into a step horizontally and a step vertically. A step horizontally or vertically can also be divided into a step diagonally and then a step in the opposite direction (for example, to the right). One step can be equivalent to taking one step up and to the right and then one step down). So for general situations, as long as the minimum number of steps from the starting point to the end point does not exceed t, there is always a solution, and the excess steps can always be wasted.

class Solution {<!-- -->
    /**
    The only "unusual situation" is that there is no solution when the starting point and end point coincide and only one step can be taken.
    When the starting point and end point coincide and t>1, no matter how you take the first step, there is a way to return in the remaining t-1 steps.
 */
    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {<!-- -->
        if(sx == fx & amp; & amp; sy == fy){<!-- -->
            return t == 1 ? false : true;
        }
        int mx = Math.abs(sx - fx) + Math.abs(sy - fy); // Maximum number of steps
        int mn = Math.max(Math.abs(sx - fx), Math.abs(sy - fy)); // Minimum number of steps
        return t >= mn;
    }
}

2850. Minimum number of moves to scatter stones to the grid

medium

Give you a two-dimensional integer matrix grid of size 3 * 3, with subscripts starting from 0, representing the size of the stones in each grid. number. There are exactly 9 stones in total in the grid, and there may be multiple stones in a grid.

In each operation, you can move a stone from its current grid to an adjacent grid that shares at least one common edge.

Please return the minimum number of moves for exactly one stone in each grid.

Example 1:

Input: grid = [[1,1,0],[1,1,1],[1,2,1]]
Output: 3
Explanation: An operation sequence to allow each grid to have a stone is:
1 - Move a stone from grid (2,1) to (2,2).
2 - Move a stone from grid (2,2) to (1,2).
3 - Move a stone from grid (1,2) to (0,2).
It takes a total of 3 operations to get a stone in each grid.
The minimum number of operations to have a stone in each grid is 3.

Example 2:

Input: grid = [[1,3,0],[1,0,0],[1,0,3]]
Output: 4
Explanation: An operation sequence to allow each grid to have a stone is:
1 - Move a stone from grid (0,1) to (0,2).
2 - Move a stone from grid (0,1) to (1,1).
3 - Move a stone from grid (2,2) to (1,2).
4 - Move a stone from grid (2,2) to (2,1).
It takes a total of 4 operations to get a stone in each grid.
The minimum number of operations to have a stone in each grid is 4.

Tip:

• grid.length == grid[i].length == 3
• 0 <= grid[i][j] <= 9
• The sum of the elements in grid is 9 .

Enumeration in full order

https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/solutions/2435313/tong-yong-zuo-fa-zui-xiao-fei-yong-zui-d-iuw8/

class Solution {<!-- -->
    public int minimumMoves(int[][] grid) {<!-- -->
        List<int[]> from = new ArrayList<>();
        List<int[]> to = new ArrayList<>();
        for(int i = 0; i < grid.length; i + + ){<!-- -->
            for(int j = 0; j < grid[i].length; j + + ){<!-- -->
                if(grid[i][j] > 1){<!-- -->
                    for(int k = 1; k < grid[i][j]; k + + )
                        from.add(new int[]{<!-- -->i, j});
                }else if(grid[i][j] == 0){<!-- -->
                    to.add(new int[]{<!-- -->i, j});
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        //Full arrangement of enumeration from
        for(List<int[]> from2 : permutations(from)){<!-- -->
            int total = 0;
            for(int i = 0; i < from2.size(); i + + ){<!-- -->
                int[] f = from2.get(i);
                int[] t = to.get(i);
                total + = Math.abs(f[0] - t[0]) + Math.abs(f[1] - t[1]);
            }
            ans = Math.min(ans, total);
        }
        return ans;
    }

    private List<List<int[]>> permutations(List<int[]> arr) {<!-- -->
        List<List<int[]>> result = new ArrayList<>();
        permute(arr, 0, result);
        return result;
    }

    private void permute(List<int[]> arr, int start, List<List<int[]>> result) {<!-- -->
        if (start == arr.size()) {<!-- -->
            result.add(new ArrayList<>(arr));
        }
        for (int i = start; i < arr.size(); i + + ) {<!-- -->
            swap(arr, start, i);
            permute(arr, start + 1, result);
            swap(arr, start, i);
        }
    }

    private void swap(List<int[]> arr, int i, int j) {<!-- -->
        int[] temp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, temp);
    }
}

2851. String conversion

difficulty

You are given two strings s and t both of length n. You can perform the following operations on the string s:

• Delete the suffix string with length l (0 < l < n) and add it at the beginning of s.
  For example, s = 'abcd', then in one operation, you can remove the suffix 'cd' and add it to s At the beginning, we get s = 'cdab'.

Given an integer k, please return exactly k operations to change s into t The number of solutions.

Since the answer can be very large, return the answer pair 109 + 7 remainder.

Example 1:

Input: s = "abcd", t = "cdab", k = 2
Output: 2
explain:
The first option:
In the first operation, select the suffix starting with index = 3 and get s = "dabc" .
In the second operation, select the suffix starting with index = 3 and get s = "cdab".

Second option:
In the first operation, select the suffix starting with index = 1 and get s = "bcda" .
In the second operation, select the suffix starting with index = 1 and get s = "cdab".

Example 2:

Input: s = "ababab", t = "ababab", k = 1
Output: 2
explain:
The first option:
Select the suffix starting with index = 2 and get s = "ababab" .

Second option:
Select the suffix starting with index = 4 and get s = "ababab" .

Tip:

• 2 <= s.length <= 5 * 105
• 1 <= k <= 1015
• s.length == t.length
• Both s and t contain only lowercase English letters.

KMP + matrix fast power optimization DP

https://leetcode.cn/problems/string-transformation/solutions/2435348/kmp-ju-zhen-kuai-su-mi-you-hua-dp-by-end-vypf/

class Solution {<!-- -->
    public int numberOfWays(String s, String t, long k) {<!-- -->
        int n = s.length();
        int c = kmpSearch(s + s.substring(0, n - 1), t);
        long[][] m = {<!-- -->
            {<!-- -->c - 1, c},
            {<!-- -->n - c, n - 1 - c},
        };
        m = pow(m, k);
        return s.equals(t) ? (int) m[0][0] : (int) m[0][1];
    }

    // KMP template
    private int[] calcMaxMatch(String s) {<!-- -->
        int[] match = new int[s.length()];
        int c = 0;
        for (int i = 1; i < s.length(); i + + ) {<!-- -->
            char v = s.charAt(i);
            while (c > 0 & amp; & amp; s.charAt(c) != v) {<!-- -->
                c = match[c - 1];
            }
            if (s.charAt(c) == v) {<!-- -->
                c++;
            }
            match[i] = c;
        }
        return match;
    }

    // KMP template
    //Return how many times pattern appears in text (pattern overlap is allowed)
    private int kmpSearch(String text, String pattern) {<!-- -->
        int[] match = calcMaxMatch(pattern);
        int lenP = pattern.length();
        int matchCnt = 0;
        int c = 0;
        for (int i = 0; i < text.length(); i + + ) {<!-- -->
            char v = text.charAt(i);
            while (c > 0 & amp; & amp; pattern.charAt(c) != v) {<!-- -->
                c = match[c - 1];
            }
            if (pattern.charAt(c) == v) {<!-- -->
                c++;
            }
            if (c == lenP) {<!-- -->
                matchCnt + + ;
                c = match[c - 1];
            }
        }
        return matchCnt;
    }

    private static final long MOD = (long) 1e9 + 7;

    //Matrix multiplication
    private long[][] multiply(long[][] a, long[][] b) {<!-- -->
        long[][] c = new long[2][2];
        for (int i = 0; i < 2; i + + ) {<!-- -->
            for (int j = 0; j < 2; j + + ) {<!-- -->
                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD;
            }
        }
        return c;
    }

    //Matrix fast exponentiation
    private long[][] pow(long[][] a, long n) {<!-- -->
        long[][] res = {<!-- -->{<!-- -->1, 0}, {<!-- -->0, 1}};
        for (; n > 0; n /= 2) {<!-- -->
            if (n % 2 > 0) {<!-- -->
                res = multiply(res, a);
            }
            a = multiply(a, a);
        }
        return res;
    }


}