# biweekly-contest-71

## A

### Statement

• 比方说，给你 `num = 2932` ，你拥有的数位包括：两个 `2` ，一个 `9` 和一个 `3` 。一些可能的 `[new1, new2]` 数对为 `[22, 93]``[23, 92]``[223, 9]` 和 `[2, 329]` 。

``````输入：num = 2932

``````

``````输入：num = 4009

``````

• `1000 <= num <= 9999`

You are given a positive integer `num` consisting of exactly four digits. Split `num` into two new integers `new1` and `new2` by using the digits found in `num`. Leading zeros are allowed in `new1` and `new2`, and all the digits found in `num` must be used.

• For example, given `num = 2932`, you have the following digits: two `2`'s, one `9` and one `3`. Some of the possible pairs `[new1, new2]` are `[22, 93]`, `[23, 92]`, `[223, 9]` and `[2, 329]`.

Return the minimum possible sum of `new1` and `new2`.

Example 1:

``````Input: num = 2932
Output: 52
Explanation: Some possible pairs [new1, new2] are [29, 23], [223, 9], etc.
The minimum sum can be obtained by the pair [29, 23]: 29 + 23 = 52.
``````

Example 2:

``````Input: num = 4009
Output: 13
Explanation: Some possible pairs [new1, new2] are [0, 49], [490, 0], etc.
The minimum sum can be obtained by the pair [4, 9]: 4 + 9 = 13.
``````

Constraints:

• `1000 <= num <= 9999`

### 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 lowbit(x) ((x) & (-(x)))
#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 minimumSum(int num) {
string s = to_string(num);
sort(all(s));
int res = num;

auto f = [](const string &s) {
int res = 0;
for (auto &c : s) {
res = res * 10 + (c - '0');
}

return res;
};

do {
for (int i = 0; i < 4; i++) {
int now = f(s.substr(0, i)) + f(s.substr(i, 4 - i));
chmin(res, now);
}
} while (next_permutation(all(s)));

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 所有小于 `pivot` 的元素都出现在所有大于 `pivot` 的元素 之前 。
• 所有等于 `pivot` 的元素都出现在小于和大于 `pivot` 的元素 中间 。
• 小于 `pivot` 的元素之间和大于 `pivot` 的元素之间的 相对顺序 不发生改变。
• 更正式的，考虑每一对 `pi``pj` ，`pi` 是初始时位置 `i` 元素的新位置，`pj` 是初始时位置 `j` 元素的新位置。对于小于 `pivot` 的元素，如果 `i < j` 且 `nums[i] < pivot` 和 `nums[j] < pivot` 都成立，那么 `pi < pj` 也成立。类似的，对于大于 `pivot` 的元素，如果 `i < j` 且 `nums[i] > pivot` 和 `nums[j] > pivot` 都成立，那么 `pi < pj` 。

``````输入：nums = [9,12,5,10,14,3,10], pivot = 10

``````

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

``````

• `1 <= nums.length <= 105`
• `-106 <= nums[i] <= 106`
• `pivot` 等于 `nums` 中的一个元素。

You are given a 0-indexed integer array `nums` and an integer `pivot`. Rearrange `nums` such that the following conditions are satisfied:

• Every element less than `pivot` appears before every element greater than `pivot`.
• Every element equal to `pivot` appears in between the elements less than and greater than `pivot`.
• The relative order of the elements less than `pivot` and the elements greater than `pivot` is maintained.
• More formally, consider every `pi`, `pj` where `pi` is the new position of the `ith` element and `pj` is the new position of the `jth` element. For elements less than `pivot`, if `i < j` and `nums[i] < pivot` and `nums[j] < pivot`, then `pi < pj`. Similarly for elements greater than `pivot`, if `i < j` and `nums[i] > pivot` and `nums[j] > pivot`, then `pi < pj`.

Return `nums` after the rearrangement.

Example 1:

``````Input: nums = [9,12,5,10,14,3,10], pivot = 10
Output: [9,5,3,10,10,12,14]
Explanation:
The elements 9, 5, and 3 are less than the pivot so they are on the left side of the array.
The elements 12 and 14 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [9, 5, 3] and [12, 14] are the respective orderings.
``````

Example 2:

``````Input: nums = [-3,4,3,2], pivot = 2
Output: [-3,2,4,3]
Explanation:
The element -3 is less than the pivot so it is on the left side of the array.
The elements 4 and 3 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [-3] and [4, 3] are the respective orderings.
``````

Constraints:

• `1 <= nums.length <= 105`
• `-106 <= nums[i] <= 106`
• `pivot` equals to an element of `nums`.

### 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 lowbit(x) ((x) & (-(x)))
#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

struct node {
int ix;
int num;
};

class Solution {
public:
vector<int> pivotArray(vector<int> &nums, int pivot) {
vector<node> vec;
for (int i = 0; i < nums.size(); i++) {
vec.emplace_back(node{.ix = i, .num = nums[i]});
}

const auto sgn = [&](int x) {
if (x < pivot) {
return -1;
}

if (x == pivot) {
return 0;
}

return 1;
};

sort(all(vec), [&](const node &a, const node &b) {
if (sgn(a.num) != sgn(b.num)) {
return sgn(a.num) < sgn(b.num);
}

return a.ix < b.ix;
});

vector<int> res;

for (const auto &a : vec) {
res.push_back(a.num);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 至少为 `1` 秒钟。
• 至多为 `99` 分 `99` 秒。

• 你输入 `9` `5` `4` （三个数字），被自动补足为 `0954` ，并表示 `9` 分 `54` 秒。
• 你输入 `0` `0` `0` `8` （四个数字），表示 `0` 分 `8` 秒。
• 你输入 `8` `0` `9` `0` ，表示 `80` 分 `90` 秒。
• 你输入 `8` `1` `3` `0` ，表示 `81` 分 `30` 秒。

``````输入：startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600

- 1 0 0 0 ，表示 10 分 0 秒。
手指一开始就在数字 1 处，输入 1 （代价为 1），移到 0 处（代价为 2），输入 0（代价为 1），输入 0（代价为 1），输入 0（代价为 1）。
总代价为：1 + 2 + 1 + 1 + 1 = 6 。这是所有方案中的最小代价。
- 0 9 6 0，表示 9 分 60 秒。它也表示 600 秒。
手指移到 0 处（代价为 2），输入 0 （代价为 1），移到 9 处（代价为 2），输入 9（代价为 1），移到 6 处（代价为 2），输入 6（代价为 1），移到 0 处（代价为 2），输入 0（代价为 1）。
总代价为：2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12 。
- 9 6 0，微波炉自动补全为 0960 ，表示 9 分 60 秒。
手指移到 9 处（代价为 2），输入 9 （代价为 1），移到 6 处（代价为 2），输入 6（代价为 1），移到 0 处（代价为 2），输入 0（代价为 1）。
总代价为：2 + 1 + 2 + 1 + 2 + 1 = 9 。
``````

``````输入：startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76

``````

• `0 <= startAt <= 9`
• `1 <= moveCost, pushCost <= 105`
• `1 <= targetSeconds <= 6039`

A generic microwave supports cooking times for:

• at least `1` second.
• at most `99` minutes and `99` seconds.

To set the cooking time, you push at most four digits. The microwave normalizes what you push as four digits by prepending zeroes. It interprets the first two digits as the minutes and the last two digits as the seconds. It then adds them up as the cooking time. For example,

• You push `9` `5` `4` (three digits). It is normalized as `0954` and interpreted as `9` minutes and `54` seconds.
• You push `0` `0` `0` `8` (four digits). It is interpreted as `0` minutes and `8` seconds.
• You push `8` `0` `9` `0`. It is interpreted as `80` minutes and `90` seconds.
• You push `8` `1` `3` `0`. It is interpreted as `81` minutes and `30` seconds.

You are given integers `startAt`, `moveCost`, `pushCost`, and `targetSeconds`. Initially, your finger is on the digit `startAt`. Moving the finger above any specific digit costs `moveCost` units of fatigue. Pushing the digit below the finger once costs `pushCost` units of fatigue.

There can be multiple ways to set the microwave to cook for `targetSeconds` seconds but you are interested in the way with the minimum cost.

Return the minimum cost to set `targetSeconds` seconds of cooking time.

Remember that one minute consists of `60` seconds.

Example 1:

``````Input: startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600
Output: 6
Explanation: The following are the possible ways to set the cooking time.
- 1 0 0 0, interpreted as 10 minutes and 0 seconds.
The finger is already on digit 1, pushes 1 (with cost 1), moves to 0 (with cost 2), pushes 0 (with cost 1), pushes 0 (with cost 1), and pushes 0 (with cost 1).
The cost is: 1 + 2 + 1 + 1 + 1 = 6. This is the minimum cost.
- 0 9 6 0, interpreted as 9 minutes and 60 seconds. That is also 600 seconds.
The finger moves to 0 (with cost 2), pushes 0 (with cost 1), moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1).
The cost is: 2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12.
- 9 6 0, normalized as 0960 and interpreted as 9 minutes and 60 seconds.
The finger moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1).
The cost is: 2 + 1 + 2 + 1 + 2 + 1 = 9.
``````

Example 2:

``````Input: startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76
Output: 6
Explanation: The optimal way is to push two digits: 7 6, interpreted as 76 seconds.
The finger moves to 7 (with cost 1), pushes 7 (with cost 2), moves to 6 (with cost 1), and pushes 6 (with cost 2). The total cost is: 1 + 2 + 1 + 2 = 6
Note other possible ways are 0076, 076, 0116, and 116, but none of them produces the minimum cost.
``````

Constraints:

• `0 <= startAt <= 9`
• `1 <= moveCost, pushCost <= 105`
• `1 <= targetSeconds <= 6039`

### 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 lowbit(x) ((x) & (-(x)))
#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 minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
const auto calc = [&](const string &s) -> int {
int cur = startAt;
int cost = 0;
for (const auto &c : s) {
if (cost == 0 && c == '0') {
continue;
}

int now = c - '0';
if (now != cur) {
cur = now;
cost += moveCost;
}

cost += pushCost;
}

dbg(s, cost);

return cost;
};

int a = targetSeconds / 60;
int b = targetSeconds % 60;

int cost = 99999999;

if (a <= 99) {
chmin(cost, calc(to_string(a) + ((b <= 9 ? string("0") : string("")) + to_string(b))));
}

if (a >= 1 && b <= 39) {
chmin(cost, calc(to_string(a - 1) + to_string(b + 60)));
}

return cost;
}
};

#ifdef LOCAL

int main() {
auto s = new Solution();
{
auto ans = s->minCostSetTime(5, 15, 20, 365);
assert_eq(ans, 90);
}
return 0;
}

#endif
``````

## D

### Statement

• 前面 `n` 个元素属于第一部分，它们的和记为 `sumfirst` 。
• 后面 `n` 个元素属于第二部分，它们的和记为 `sumsecond` 。

• 比方说，`sumfirst = 3` 且 `sumsecond = 2` ，它们的差值为 `1` 。
• 再比方，`sumfirst = 2` 且 `sumsecond = 3` ，它们的差值为 `-1` 。

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

- 如果我们删除 nums[0] = 3 ，数组变为 [1,2] 。两部分和的差值为 1 - 2 = -1 。
- 如果我们删除 nums[1] = 1 ，数组变为 [3,2] 。两部分和的差值为 3 - 2 = 1 。
- 如果我们删除 nums[2] = 2 ，数组变为 [3,1] 。两部分和的差值为 3 - 1 = 2 。

``````

``````输入：nums = [7,9,5,8,1,3]

``````

• `nums.length == 3 * n`
• `1 <= n <= 105`
• `1 <= nums[i] <= 105`

You are given a 0-indexed integer array `nums` consisting of `3 * n` elements.

You are allowed to remove any subsequence of elements of size exactly `n` from `nums`. The remaining `2 * n` elements will be divided into two equal parts:

• The first `n` elements belonging to the first part and their sum is `sumfirst`.
• The next `n` elements belonging to the second part and their sum is `sumsecond`.

The difference in sums of the two parts is denoted as `sumfirst - sumsecond`.

• For example, if `sumfirst = 3` and `sumsecond = 2`, their difference is `1`.
• Similarly, if `sumfirst = 2` and `sumsecond = 3`, their difference is `-1`.

Return the minimum difference possible between the sums of the two parts after the removal of `n` elements.

Example 1:

``````Input: nums = [3,1,2]
Output: -1
Explanation: Here, nums has 3 elements, so n = 1.
Thus we have to remove 1 element from nums and divide the array into two equal parts.
- If we remove nums[0] = 3, the array will be [1,2]. The difference in sums of the two parts will be 1 - 2 = -1.
- If we remove nums[1] = 1, the array will be [3,2]. The difference in sums of the two parts will be 3 - 2 = 1.
- If we remove nums[2] = 2, the array will be [3,1]. The difference in sums of the two parts will be 3 - 1 = 2.
The minimum difference between sums of the two parts is min(-1,1,2) = -1.
``````

Example 2:

``````Input: nums = [7,9,5,8,1,3]
Output: 1
Explanation: Here n = 2. So we must remove 2 elements and divide the remaining array into two parts containing two elements each.
If we remove nums[2] = 5 and nums[3] = 8, the resultant array will be [7,9,1,3]. The difference in sums will be (7+9) - (1+3) = 12.
To obtain the minimum difference, we should remove nums[1] = 9 and nums[4] = 1. The resultant array becomes [7,5,8,3]. The difference in sums of the two parts is (7+5) - (8+3) = 1.
It can be shown that it is not possible to obtain a difference smaller than 1.
``````

Constraints:

• `nums.length == 3 * n`
• `1 <= n <= 105`
• `1 <= nums[i] <= 105`

### 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 lowbit(x) ((x) & (-(x)))
#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

const ll INF = 0x3f3f3f3f3f3f3f3f;

class Solution {
public:
long long minimumDifference(vector<int> &nums) {
ll res = INF;
int n = nums.size() / 3;

vector<ll> lsum(n * 3, 0), rsum(n * 3, 0);

{
ll sum = 0;
multiset<int> s;
for (int i = 0; i <= n - 1; i++) {
sum += nums[i];
s.insert(nums[i]);
}

lsum[n - 1] = sum;
for (int i = n; i < n * 2; i++) {
int a = nums[i];
s.insert(a);
sum += a;
sum -= *(s.rbegin());
lsum[i] = sum;
s.erase(s.find(*(s.rbegin())));
}
}

{
ll sum = 0;
multiset<int> s;
for (int i = n * 3 - 1; i >= n * 2; i--) {
sum += nums[i];
s.insert(nums[i]);
}

rsum[n * 2] = sum;
for (int i = n * 2 - 1; i >= n; i--) {
int a = nums[i];
s.insert(a);
sum += a;
sum -= *(s.begin());
rsum[i] = sum;
s.erase(s.find(*(s.begin())));
}
}

dbg(lsum, rsum);

for (int i = n - 1; i < n * 2; i++) {
chmin(res, lsum[i] - rsum[i + 1]);
}

return res;
}
};

#ifdef LOCAL

int main() {
auto s = new Solution();

{
auto vec = vector<int>({3, 1, 2});
auto ans = s->minimumDifference(vec);
assert_eq(ans, ll(-1));
}

{
auto vec = vector<int>({7, 9, 5, 8, 1, 3});
auto ans = s->minimumDifference(vec);
assert_eq(ans, ll(1));
}
return 0;
}

#endif
``````