# weekly-contest-325

## A

### Statement

• 形式上， words[i] 的下一个元素是 words[(i + 1) % n] ，而 words[i] 的前一个元素是 words[(i - 1 + n) % n] ，其中 nwords 的长度。

startIndex 开始，你一次可以用 1 步移动到下一个或者前一个单词。

- 向右移动 3 个单位，到达下标 4 。
- 向左移动 2 个单位，到达下标 4 。
- 向右移动 4 个单位，到达下标 0 。
- 向左移动 1 个单位，到达下标 0 。

- 向右移动 2 个单位，到达下标 3 。
- 向左移动 1 个单位，到达下标 3 。

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i]target 仅由小写英文字母组成
• 0 <= startIndex < words.length

You are given a 0-indexed circular string array words and a string target. A circular array means that the array's end connects to the array's beginning.

• Formally, the next element of words[i] is words[(i + 1) % n] and the previous element of words[i] is words[(i - 1 + n) % n], where n is the length of words.

Starting from startIndex, you can move to either the next word or the previous word with 1 step at a time.

Return the shortest distance needed to reach the string target. If the string target does not exist in words, return -1.

Example 1:

Input: words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1
Output: 1
Explanation: We start from index 1 and can reach "hello" by
- moving 3 units to the right to reach index 4.
- moving 2 units to the left to reach index 4.
- moving 4 units to the right to reach index 0.
- moving 1 unit to the left to reach index 0.
The shortest distance to reach "hello" is 1.

Example 2:

Input: words = ["a","b","leetcode"], target = "leetcode", startIndex = 0
Output: 1
Explanation: We start from index 0 and can reach "leetcode" by
- moving 2 units to the right to reach index 3.
- moving 1 unit to the left to reach index 3.
The shortest distance to reach "leetcode" is 1.

Example 3:

Input: words = ["i","eat","leetcode"], target = "ate", startIndex = 0
Output: -1
Explanation: Since "ate" does not exist in words, we return -1.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] and target consist of only lowercase English letters.
• 0 <= startIndex < words.length

### 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>;

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

const int INF = 0x3f3f3f3f;

class Solution {
public:
int closetTarget(vector<string> &words, string target, int startIndex) {
int n = int(words.size());

int res = INF;

for (int i = 0; i < n; i++) {
auto s = words[i];
if (s == target) {
int x = startIndex;
int y = i;
if (y < x) {
swap(x, y);
}

res = min(res, y - x);
res = min(res, x + (n - y));
}
}

if (res == INF) {
res = -1;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif

## B

### Statement

• 1 <= s.length <= 105
• s 仅由字母 'a''b''c' 组成
• 0 <= k <= s.length

You are given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

Example 1:

Input: s = "aabaaaacaabc", k = 2
Output: 8
Explanation:
Take three characters from the left of s. You now have two 'a' characters, and one 'b' character.
Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters.
A total of 3 + 5 = 8 minutes is needed.
It can be proven that 8 is the minimum number of minutes needed.

Example 2:

Input: s = "a", k = 1
Output: -1
Explanation: It is not possible to take one 'b' or 'c' so return -1.

Constraints:

• 1 <= s.length <= 105
• s consists of only the letters 'a', 'b', and 'c'.
• 0 <= k <= s.length

### 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>;

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 takeCharacters(string s, int k) {
int n = int(s.size());

auto cnt = vector<int>(3, 0);
for (const auto &c : s) {
++cnt[c - 'a'];
}

if (cnt[0] < k || cnt[1] < k || cnt[2] < k) {
return -1;
}

int r = 0;
while (r < n) {
if (cnt[s[r] - 'a'] > k) {
--cnt[s[r] - 'a'];
++r;
} else {
break;
}
}

int res = n - r;

for (int i = 0; i < n; i++) {
while (r <= i) {
--cnt[s[r] - 'a'];
++r;
}

++cnt[s[i] - 'a'];

while (r < n) {
if (cnt[s[r] - 'a'] > k) {
--cnt[s[r] - 'a'];
++r;
} else {
break;
}
}

res = min(res, i + 1 + n - r);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif

## C

### Statement

• 1 <= price.length <= 105
• 1 <= price[i] <= 109
• 2 <= k <= price.length

You are given an array of positive integers price where price[i] denotes the price of the ith candy and a positive integer k.

The store sells baskets of k distinct candies. The tastiness of a candy basket is the smallest absolute difference of the prices of any two candies in the basket.

Return the maximum tastiness of a candy basket.

Example 1:

Input: price = [13,5,1,8,21,2], k = 3
Output: 8
Explanation: Choose the candies with the prices [13,5,21].
The tastiness of the candy basket is: min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8.
It can be proven that 8 is the maximum tastiness that can be achieved.

Example 2:

Input: price = [1,3,1], k = 2
Output: 2
Explanation: Choose the candies with the prices [1,3].
The tastiness of the candy basket is: min(|1 - 3|) = min(2) = 2.
It can be proven that 2 is the maximum tastiness that can be achieved.

Example 3:

Input: price = [7,7,7,7], k = 2
Output: 0
Explanation: Choosing any two distinct candies from the candies we have will result in a tastiness of 0.

Constraints:

• 1 <= price.length <= 105
• 1 <= price[i] <= 109
• 2 <= k <= price.length

### 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>;

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 maximumTastiness(vector<int> &price, int k) {
int n = int(price.size());
sort(all(price));

const auto ok = [&](int x) {
vector<int> f;
f.push_back(price[0]);

for (int i = 1; i < n; i++) {
if (price[i] - f.back() >= x) {
f.push_back(price[i]);
}
}

return f.size() >= k;
};

int l = 0, r = price.end()[-1] - price[0], res = 0;
while (r - l >= 0) {
int mid = (l + r) >> 1;
if (ok(mid)) {
l = mid + 1;
res = mid;
} else {
r = mid - 1;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif

## D

### Statement

• 1 <= nums.length, k <= 1000
• 1 <= nums[i] <= 109

You are given an array nums consisting of positive integers and an integer k.

Partition the array into two ordered groups such that each element is in exactly one group. A partition is called great if the sum of elements of each group is greater than or equal to k.

Return the number of distinct great partitions. Since the answer may be too large, return it modulo 109 + 7.

Two partitions are considered distinct if some element nums[i] is in different groups in the two partitions.

Example 1:

Input: nums = [1,2,3,4], k = 4
Output: 6
Explanation: The great partitions are: ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) and ([4], [1,2,3]).

Example 2:

Input: nums = [3,3,3], k = 4
Output: 0
Explanation: There are no great partitions for this array.

Example 3:

Input: nums = [6,6], k = 2
Output: 2
Explanation: We can either put nums[0] in the first partition or in the second partition.
The great partitions will be ([6], [6]) and ([6], [6]).

Constraints:

• 1 <= nums.length, k <= 1000
• 1 <= nums[i] <= 109

### 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>;

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

const int mod = 1e9 + 7;

class Solution {
public:
int countPartitions(vector<int> &nums, int k) {
int n = int(nums.size());

auto f = vector<vector<int>>(n + 5, vector<int>(k + 5, 0));
f[0][0] = 1;

ll total = 0;
total = accumulate(all(nums), 0ll);

int tot = 1;
for (int i = 0; i < n; i++) {
tot = tot * 2;
tot %= mod;
}

int res = 0;

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

int x = nums[i - 1];
if (x >= k) {
continue;
}

for (int j = 0; j < k; j++) {
if (x + j < k) {
f[i][x + j] += f[i - 1][j];
f[i][x + j] %= mod;
}
}
}

for (int j = 0; j < k; j++) {
res += f[n][j];
res %= mod;

if (total - j >= k) {
res += f[n][j];
res %= mod;
}
}

return (tot - res + mod) % mod;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif