Educational Codeforces Round 49 (Rated for Div. 2) D. Mouse Hunt

Technocup 2019 - Elimination Round 3 C. Playing Piano

2573. Find the String with LCP

We define the lcp matrix of any 0-indexed string word of n lowercase English letters as an n x n grid such that:

• lcp[i][j] is equal to the length of the longest common prefix between the substrings word[i,n-1] and word[j,n-1].

Given an n x n matrix lcp, return the alphabetically smallest string word that corresponds to lcp. If there is no such string, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, “aabd” is lexicographically smaller than “aaca” because the first position they differ is at the third letter, and ‘b’ comes before ‘c’.

2572. Count the Number of Square-Free Subsets

You are given a positive integer 0-indexed array nums.

A subset of the array nums is square-free if the product of its elements is a square-free integer.

A square-free integer is an integer that is divisible by no square number other than 1.

Return the number of square-free non-empty subsets of the array nums. Since the answer may be too large, return it modulo 109 + 7.

A non-empty subset of nums is an array that can be obtained by deleting some (possibly none but not all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.

2571. Minimum Operations to Reduce an Integer to 0

You are given a positive integer n, you can do the following operation any number of times:

• Add or subtract a power of 2 from n.

Return the minimum number of operations to make n equal to 0.

A number x is power of 2 if x == 2i where i >= 0.

2570. Merge Two 2D Arrays by Summing Values

You are given two 2D integer arrays nums1 and nums2.

• nums1[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.
• nums2[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.

Each array contains unique ids and is sorted in ascending order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

• Only ids that appear in at least one of the two arrays should be included in the resulting array.
• Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays then its value in that array is considered to be 0.

Return the resulting array. The returned array must be sorted in ascending order by id.

2568. Minimum Impossible OR

You are given a 0-indexed integer array nums.

We say that an integer x is expressible from nums if there exist some integers 0 <= index1 < index2 < … < indexk < nums.length for which nums[index1] | nums[index2] | … | nums[indexk] = x. In other words, an integer is expressible if it can be written as the bitwise OR of some subsequence of nums.

Return the minimum positive non-zero integer that is not expressible from nums.

2567. Minimum Score by Changing Two Elements

You are given a 0-indexed integer array nums.

• The low score of nums is the minimum value of |nums[i] - nums[j]| over all 0 <= i < j < nums.length.
• The high score of nums is the maximum value of |nums[i] - nums[j]| over all 0 <= i < j < nums.length.
• The score of nums is the sum of the high and low scores of nums.

To minimize the score of nums, we can change the value of at most two elements of nums.

Return the minimum possible score after changing the value of at most two elements of nums.

Note that |x| denotes the absolute value of x.

2566. Maximum Difference by Remapping a Digit

You are given an integer num. You know that Danny Mittal will sneakily remap one of the 10 possible digits (0 to 9) to another digit.

Return the difference between the maximum and minimum values Danny can make by remapping exactly one digit in num.

Notes:

• When Danny remaps a digit d1 to another digit d2, Danny replaces all occurrences of d1 in num with d2.
• Danny can remap a digit to itself, in which case num does not change.
• Danny can remap different digits for obtaining minimum and maximum values respectively.
• The resulting number after remapping can contain leading zeroes.
• We mentioned “Danny Mittal” to congratulate him on being in the top 10 in Weekly Contest 326.

2569. Handling Sum Queries After Update

You are given two 0-indexed arrays nums1 and nums2 and a 2D array queries of queries. There are three types of queries:

1. For a query of type 1, queries[i] = [1, l, r]. Flip the values from 0 to 1 and from 1 to 0 in nums1 from index l to index r. Both l and r are 0-indexed.
2. For a query of type 2, queries[i] = [2, p, 0]. For every index 0 <= i < n, set nums2[i] = nums2[i] + nums1[i] * p.
3. For a query of type 3, queries[i] = [3, 0, 0]. Find the sum of the elements in nums2.

Return an array containing all the answers to the third type queries.