# weekly-contest-217

## A

### Statement

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

``````

``````输入：accounts = [[1,5],[7,3],[3,5]]

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

``````

• `m == accounts.length`
• `n == accounts[i].length`
• `1 <= m, n <= 50`
• `1 <= accounts[i][j] <= 100`

You are given an `m x n` integer grid `accounts` where `accounts[i][j]` is the amount of money the `i​​​​​​​​​​​th​​​​` customer has in the `j​​​​​​​​​​​th`​​​​ bank. Return the wealth that the richest customer has.

A customer's wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

Example 1:

``````Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.
``````

Example 2:

``````Input: accounts = [[1,5],[7,3],[3,5]]
Output: 10
Explanation:
1st customer has wealth = 6
2nd customer has wealth = 10
3rd customer has wealth = 8
The 2nd customer is the richest with a wealth of 10.``````

Example 3:

``````Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17
``````

Constraints:

• `m == accounts.length`
• `n == accounts[i].length`
• `1 <= m, n <= 50`
• `1 <= accounts[i][j] <= 100`

### 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 maximumWealth(vector<vector<int>> &accounts) {
vector<int> vec;
for (auto &it : accounts) vec.push_back(accumulate(it.begin(), it.end(), 0));
sort(all(vec));
return vec.back();
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：nums = [3,5,2,6], k = 2

``````

``````输入：nums = [2,4,3,3,5,4,9,6], k = 4

``````

• `1 <= nums.length <= 105`
• `0 <= nums[i] <= 109`
• `1 <= k <= nums.length`

Given an integer array `nums` and a positive integer `k`, return the most competitive subsequence of `nums` of size `k`.

An array's subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence `a` is more competitive than a subsequence `b` (of the same length) if in the first position where `a` and `b` differ, subsequence `a` has a number less than the corresponding number in `b`. For example, `[1,3,4]` is more competitive than `[1,3,5]` because the first position they differ is at the final number, and `4` is less than `5`.

Example 1:

``````Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.
``````

Example 2:

``````Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]
``````

Constraints:

• `1 <= nums.length <= 105`
• `0 <= nums[i] <= 109`
• `1 <= k <= nums.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 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:
vector<int> mostCompetitive(vector<int> &nums, int k) {
int n = nums.size();
set<PII> se;
int ix = n - k, jx = -1;
vector<int> res;
for (int i = 0; i < n - k; ++i) se.insert(PII(nums[i], i));
for (int i = n - k; i < n; ++i) {
se.insert(PII(nums[i], i));
while (1) {
auto it = *se.begin();
se.erase(it);
if (it.se <= jx)
continue;
res.push_back(it.fi);
jx = it.se;
break;
}
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

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

nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.

``````

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

``````

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

``````

• `n == nums.length`
• `2 <= n <= 105`
• `1 <= nums[i] <= limit <= 105`
• `n` 是偶数。

You are given an integer array `nums` of even length `n` and an integer `limit`. In one move, you can replace any integer from `nums` with another integer between `1` and `limit`, inclusive.

The array `nums` is complementary if for all indices `i` (0-indexed), `nums[i] + nums[n - 1 - i]` equals the same number. For example, the array `[1,2,3,4]` is complementary because for all indices `i`, `nums[i] + nums[n - 1 - i] = 5`.

Return the minimum number of moves required to make `nums` complementary.

Example 1:

``````Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.
``````

Example 2:

``````Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.
``````

Example 3:

``````Input: nums = [1,2,1,2], limit = 2
Output: 0
``````

Constraints:

• `n == nums.length`
• `2 <= n <= 105`
• `1 <= nums[i] <= limit <= 105`
• `n` is even.

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

constexpr int N = 2e5 + 10;
int n, a[N], b[N];

class Solution {
public:
int minMoves(vector<int> &nums, int limit) {
n = nums.size();
int res = n;
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
for (int i = 0, j = n - 1; i < j; ++i, --j) {
int x = nums[i], y = nums[j];
if (x > y)
swap(x, y);
++b[x + y];
++a[x + 1];
--a[y + limit + 1];
}
int dui = n / 2;
for (int i = 1; i <= limit * 2; ++i) {
a[i] += a[i - 1];
int now = a[i] - b[i] + (dui - a[i]) * 2;
chmin(res, now);
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• Difficulty: Hard
• Tag: `贪心` `数组` `有序集合` `堆（优先队列）`

• 如果元素是 偶数除以 `2`
• 例如，如果数组是 `[1,2,3,4]` ，那么你可以对最后一个元素执行此操作，使其变成 `[1,2,3,2]`
• 如果元素是 奇数乘上 `2`
• 例如，如果数组是 `[1,2,3,4]` ，那么你可以对第一个元素执行此操作，使其变成 `[2,2,3,4]`

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

``````

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

``````

``````输入：nums = [2,10,8]

``````

• `n == nums.length`
• `2 <= n <= 105`
• `1 <= nums[i] <= 109`

• Link: Minimize Deviation in Array
• Difficulty: Hard
• Tag: `Greedy` `Array` `Ordered Set` `Heap (Priority Queue)`

You are given an array `nums` of `n` positive integers.

You can perform two types of operations on any element of the array any number of times:

• If the element is even, divide it by `2`.
• For example, if the array is `[1,2,3,4]`, then you can do this operation on the last element, and the array will be `[1,2,3,2].`
• If the element is odd, multiply it by `2`.
• For example, if the array is `[1,2,3,4]`, then you can do this operation on the first element, and the array will be `[2,2,3,4].`

The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Example 1:

``````Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.
``````

Example 2:

``````Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.
``````

Example 3:

``````Input: nums = [2,10,8]
Output: 3
``````

Constraints:

• `n == nums.length`
• `2 <= n <= 105`
• `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 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

constexpr int N = 1e5 + 10;
int n, a[N];

class Solution {
public:
int minimumDeviation(vector<int> &nums) {
vector<int> vec;
set<PII> se;
for (auto &it : nums) {
vec.push_back(it);
int cnt = 0;
while (it % 2 == 0) {
it /= 2;
++cnt;
vec.push_back(it);
}
if (!cnt) {
vec.push_back(it * 2);
cnt = 1;
}
se.insert(PII(it, cnt));
}
sort(all(vec));
vec.erase(unique(all(vec)), vec.end());
ll res = INT_MAX;
for (auto &it : vec) {
int ok = 1;
while (1) {
auto pos = *se.begin();
se.erase(pos);
if (pos.fi < it) {
if (pos.se == 0) {
ok = 0;
break;
}
--pos.se;
pos.fi *= 2;
se.insert(pos);
} else {
se.insert(pos);
break;
}
}
if (!ok)
break;
auto pos = se.end();
--pos;
chmin(res, (*pos).fi - it);
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````