# biweekly-contest-74

## A

### Statement

• 每个元素 只属于一个 数对。
• 同一数对中的元素 相等 。

``````输入：nums = [3,2,3,2,2,2]

nums 中总共有 6 个元素，所以它们应该被划分成 6 / 2 = 3 个数对。
nums 可以划分成 (2, 2) ，(3, 3) 和 (2, 2) ，满足所有要求。
``````

``````输入：nums = [1,2,3,4]

``````

• `nums.length == 2 * n`
• `1 <= n <= 500`
• `1 <= nums[i] <= 500`

You are given an integer array `nums` consisting of `2 * n` integers.

You need to divide `nums` into `n` pairs such that:

• Each element belongs to exactly one pair.
• The elements present in a pair are equal.

Return `true` if nums can be divided into `n` pairs, otherwise return `false`.

Example 1:

``````Input: nums = [3,2,3,2,2,2]
Output: true
Explanation:
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.
``````

Example 2:

``````Input: nums = [1,2,3,4]
Output: false
Explanation:
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.
``````

Constraints:

• `nums.length == 2 * n`
• `1 <= n <= 500`
• `1 <= nums[i] <= 500`

### Solution

``````from typing import Counter, List

class Solution:
def divideArray(self, nums: List[int]) -> bool:
a = Counter(nums)
return all((v & 1 == 0) for v in a.values()) and (len(nums) // 2) >= len(a.keys())
``````

## B

### Statement

``````输入：text = "abdcdbc", pattern = "ac"

``````

``````输入：text = "aabb", pattern = "ab"

``````

• `1 <= text.length <= 105`
• `pattern.length == 2`
• `text` 和 `pattern` 都只包含小写英文字母。

You are given a 0-indexed string `text` and another 0-indexed string `pattern` of length `2`, both of which consist of only lowercase English letters.

You can add either `pattern` or `pattern` anywhere in `text` exactly once. Note that the character can be added even at the beginning or at the end of `text`.

Return the maximum number of times `pattern` can occur as a subsequence of the modified `text`.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1:

``````Input: text = "abdcdbc", pattern = "ac"
Output: 4
Explanation:
If we add pattern = 'a' in between text and text, we get "abadcdbc". Now, the number of times "ac" occurs as a subsequence is 4.
Some other strings which have 4 subsequences "ac" after adding a character to text are "aabdcdbc" and "abdacdbc".
However, strings such as "abdcadbc", "abdccdbc", and "abdcdbcc", although obtainable, have only 3 subsequences "ac" and are thus suboptimal.
It can be shown that it is not possible to get more than 4 subsequences "ac" by adding only one character.
``````

Example 2:

``````Input: text = "aabb", pattern = "ab"
Output: 6
Explanation:
Some of the strings which can be obtained from text and have 6 subsequences "ab" are "aaabb", "aaabb", and "aabbb".
``````

Constraints:

• `1 <= text.length <= 105`
• `pattern.length == 2`
• `text` and `pattern` consist only of lowercase English letters.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
long long maximumSubsequenceCount(string text, string pattern) {
char a = pattern;
char b = pattern;

long long ca = 0;
long long cb = 0;
long long res = 0;
for (auto &c : text) {
if (c == b) {
++cb;
res += ca;
}

if (c == a) {
++ca;
}
}

return res + max(ca, cb);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：nums = [5,19,8,1]

nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33/2 = 16.5 。

``````

``````输入：nums = [3,8,20]

nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 >= 31/2 = 16.5 。

``````

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 107`

You are given an array `nums` of positive integers. In one operation, you can choose any number from `nums` and reduce it to exactly half the number. (Note that you may choose this reduced number in future operations.)

Return the minimum number of operations to reduce the sum of `nums` by at least half.

Example 1:

``````Input: nums = [5,19,8,1]
Output: 3
Explanation: The initial sum of nums is equal to 5 + 19 + 8 + 1 = 33.
The following is one of the ways to reduce the sum by at least half:
Pick the number 19 and reduce it to 9.5.
Pick the number 9.5 and reduce it to 4.75.
Pick the number 8 and reduce it to 4.
The final array is [5, 4.75, 4, 1] with a total sum of 5 + 4.75 + 4 + 1 = 14.75.
The sum of nums has been reduced by 33 - 14.75 = 18.25, which is at least half of the initial sum, 18.25 >= 33/2 = 16.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.
``````

Example 2:

``````Input: nums = [3,8,20]
Output: 3
Explanation: The initial sum of nums is equal to 3 + 8 + 20 = 31.
The following is one of the ways to reduce the sum by at least half:
Pick the number 20 and reduce it to 10.
Pick the number 10 and reduce it to 5.
Pick the number 3 and reduce it to 1.5.
The final array is [1.5, 8, 5] with a total sum of 1.5 + 8 + 5 = 14.5.
The sum of nums has been reduced by 31 - 14.5 = 16.5, which is at least half of the initial sum, 16.5 >= 31/2 = 16.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.
``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 107`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int halveArray(vector<int> &nums) {
long double res = 0;
priority_queue<double, vector<double>, less<double>> pq;
for (auto &a : nums) {
res += a;
pq.push(a);
}

long double need = res * 1.0 / 2;
int cnt = 0;
while (res > need) {
long double a = pq.top();
pq.pop();
a /= 2;
res -= a;
pq.push(a);
cnt += 1;
}

return cnt;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• `floor[i] = '0'` 表示地板上第 `i` 块砖块的颜色是 黑色 。
• `floor[i] = '1'` 表示地板上第 `i` 块砖块的颜色是 白色 。 ``````输入：floor = "10110101", numCarpets = 2, carpetLen = 2

`````` ``````输入：floor = "11111", numCarpets = 2, carpetLen = 3

``````

• `1 <= carpetLen <= floor.length <= 1000`
• `floor[i]` 要么是 `'0'` ，要么是 `'1'` 。
• `1 <= numCarpets <= 1000`

You are given a 0-indexed binary string `floor`, which represents the colors of tiles on a floor:

• `floor[i] = '0'` denotes that the `ith` tile of the floor is colored black.
• On the other hand, `floor[i] = '1'` denotes that the `ith` tile of the floor is colored white.

You are also given `numCarpets` and `carpetLen`. You have `numCarpets` black carpets, each of length `carpetLen` tiles. Cover the tiles with the given carpets such that the number of white tiles still visible is minimum. Carpets may overlap one another.

Return the minimum number of white tiles still visible.

Example 1: ``````Input: floor = "10110101", numCarpets = 2, carpetLen = 2
Output: 2
Explanation:
The figure above shows one way of covering the tiles with the carpets such that only 2 white tiles are visible.
No other way of covering the tiles with the carpets can leave less than 2 white tiles visible.
``````

Example 2: ``````Input: floor = "11111", numCarpets = 2, carpetLen = 3
Output: 0
Explanation:
The figure above shows one way of covering the tiles with the carpets such that no white tiles are visible.
Note that the carpets are able to overlap one another.
``````

Constraints:

• `1 <= carpetLen <= floor.length <= 1000`
• `floor[i]` is either `'0'` or `'1'`.
• `1 <= numCarpets <= 1000`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
int n = floor.length();
int m = max(n, numCarpets) + 5;

vector<vector<int>> f(n + 5, vector<int>(numCarpets + 5, 0x3f3f3f3f));
for (int i = 0; i <= numCarpets; i++) {
f[i] = 0;
}

for (int i = 1; i <= n; i++) {
f[i] = f[i - 1] + (floor[i - 1] == '1');
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= numCarpets; j++) {
f[i][j] = min(f[i][j], f[max(0, i - carpetLen)][j - 1]);
f[i][j] = min(f[i][j], f[i - 1][j] + (floor[i - 1] == '1'));
f[i][j] = min(f[i][j], f[i][j - 1]);
}
}

return f[n][numCarpets];
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````