# weekly-contest-307

## A

### Statement

``````输入：initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]

- 你的精力与经验都超过第 0 个对手，所以获胜。
精力变为：11 - 1 = 10 ，经验变为：5 + 2 = 7 。
- 你的精力与经验都超过第 1 个对手，所以获胜。
精力变为：10 - 4 = 6 ，经验变为：7 + 6 = 13 。
- 你的精力与经验都超过第 2 个对手，所以获胜。
精力变为：6 - 3 = 3 ，经验变为：13 + 3 = 16 。
- 你的精力与经验都超过第 3 个对手，所以获胜。
精力变为：3 - 2 = 1 ，经验变为：16 + 1 = 17 。

``````

``````输入：initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]

``````

• `n == energy.length == experience.length`
• `1 <= n <= 100`
• `1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100`

You are entering a competition, and are given two positive integers `initialEnergy` and `initialExperience` denoting your initial energy and initial experience respectively.

You are also given two 0-indexed integer arrays `energy` and `experience`, both of length `n`.

You will face `n` opponents in order. The energy and experience of the `ith` opponent is denoted by `energy[i]` and `experience[i]` respectively. When you face an opponent, you need to have both strictly greater experience and energy to defeat them and move to the next opponent if available.

Defeating the `ith` opponent increases your experience by `experience[i]`, but decreases your energy by `energy[i]`.

Before starting the competition, you can train for some number of hours. After each hour of training, you can either choose to increase your initial experience by one, or increase your initial energy by one.

Return the minimum number of training hours required to defeat all `n` opponents.

Example 1:

``````Input: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
Output: 8
Explanation: You can increase your energy to 11 after 6 hours of training, and your experience to 5 after 2 hours of training.
You face the opponents in the following order:
- You have more energy and experience than the 0th opponent so you win.
Your energy becomes 11 - 1 = 10, and your experience becomes 5 + 2 = 7.
- You have more energy and experience than the 1st opponent so you win.
Your energy becomes 10 - 4 = 6, and your experience becomes 7 + 6 = 13.
- You have more energy and experience than the 2nd opponent so you win.
Your energy becomes 6 - 3 = 3, and your experience becomes 13 + 3 = 16.
- You have more energy and experience than the 3rd opponent so you win.
Your energy becomes 3 - 2 = 1, and your experience becomes 16 + 1 = 17.
You did a total of 6 + 2 = 8 hours of training before the competition, so we return 8.
It can be proven that no smaller answer exists.
``````

Example 2:

``````Input: initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
Output: 0
Explanation: You do not need any additional energy or experience to win the competition, so we return 0.
``````

Constraints:

• `n == energy.length == experience.length`
• `1 <= n <= 100`
• `1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100`

### Solution

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

#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 minNumberOfHours(int initialEnergy, int initialExperience, vector<int> &energy, vector<int> &experience) {
int res = 0;
int tot_eng = accumulate(energy.begin(), energy.end(), 1);
res += max(0, tot_eng - initialEnergy);

// sort(experience.begin(), experience.end());
for (const auto &e : experience) {
if (e >= initialExperience) {
res += e + 1 - initialExperience;
initialExperience = e + 1;
}

initialExperience += e;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 无需 使用 `num` 中的所有数字，但你必须使用 至少 一个数字。
• 数字可以重新排序。

``````输入：num = "444947137"

``````

``````输入：num = "00009"

``````

• `1 <= num.length <= 105`
• `num` 由数字（`0 - 9`）组成

You are given a string `num` consisting of digits only.

Return the largest palindromic integer (in the form of a string) that can be formed using digits taken from `num`. It should not contain leading zeroes.

Notes:

• You do not need to use all the digits of `num`, but you must use at least one digit.
• The digits can be reordered.

Example 1:

``````Input: num = "444947137"
Output: "7449447"
Explanation:
Use the digits "4449477" from "444947137" to form the palindromic integer "7449447".
It can be shown that "7449447" is the largest palindromic integer that can be formed.
``````

Example 2:

``````Input: num = "00009"
Output: "9"
Explanation:
It can be shown that "9" is the largest palindromic integer that can be formed.
Note that the integer returned should not contain leading zeroes.
``````

Constraints:

• `1 <= num.length <= 105`
• `num` consists of digits.

### Solution

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

#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:
string largestPalindromic(string num) {
auto f = vector<int>(15, 0);
for (const auto &c : num) {
f[c - '0']++;
}

int m = -1;
string res = "";
for (int i = 9; i >= 0; i--) {
int c = f[i];
if (m == -1 && (c & 1)) {
m = i;
}
c /= 2;

res += string(c, char(i + '0'));
}

if (res.empty()) {
return string(1, char(m + '0'));
}

if (res[0] == '0') {
if (m != -1) {
return string(1, char(m + '0'));
}

return "0";
}

string _res = res;
reverse(_res.begin(), _res.end());

if (m != -1) {
res += char(m + '0');
}

res += _res;
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 节点此前还没有感染。
• 节点与一个已感染节点相邻。

``````输入：root = [1,5,3,null,4,10,6,9,2], start = 3

- 第 0 分钟：节点 3
- 第 1 分钟：节点 1、10、6
- 第 2 分钟：节点5
- 第 3 分钟：节点 4
- 第 4 分钟：节点 9 和 2

``````

``````输入：root = [1], start = 1

``````

• 树中节点的数目在范围 `[1, 105]`
• `1 <= Node.val <= 105`
• 每个节点的值 互不相同
• 树中必定存在值为 `start` 的节点

You are given the `root` of a binary tree with unique values, and an integer `start`. At minute `0`, an infection starts from the node with value `start`.

Each minute, a node becomes infected if:

• The node is currently uninfected.
• The node is adjacent to an infected node.

Return the number of minutes needed for the entire tree to be infected.

Example 1:

``````Input: root = [1,5,3,null,4,10,6,9,2], start = 3
Output: 4
Explanation: The following nodes are infected during:
- Minute 0: Node 3
- Minute 1: Nodes 1, 10 and 6
- Minute 2: Node 5
- Minute 3: Node 4
- Minute 4: Nodes 9 and 2
It takes 4 minutes for the whole tree to be infected so we return 4.
``````

Example 2:

``````Input: root = [1], start = 1
Output: 0
Explanation: At minute 0, the only node in the tree is infected so we return 0.
``````

Constraints:

• The number of nodes in the tree is in the range `[1, 105]`.
• `1 <= Node.val <= 105`
• Each node has a unique value.
• A node with a value of `start` exists in the tree.

### Solution

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

#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

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/

#ifdef LOCAL

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

#endif

class Solution {
public:
map<int, vector<int>> G;
int max_dep;

void dfs(TreeNode *root) {
if (!root) {
return;
}

if (root->left) {
G[root->val].push_back(root->left->val);
G[root->left->val].push_back(root->val);
dfs(root->left);
}

if (root->right) {
G[root->val].push_back(root->right->val);
G[root->right->val].push_back(root->val);
dfs(root->right);
}
}

void dfs2(int root, int fa, int dep) {
// cout << root << endl;

max_dep = max(max_dep, dep);

for (const auto &u : G[root]) {
if (u == fa) {
continue;
}

dfs2(u, root, dep + 1);
}
}

int amountOfTime(TreeNode *root, int start) {
G.clear();
max_dep = 0;
dfs(root);
dfs2(start, start, 0);
return max_dep;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

``````输入：nums = [2,4,-2], k = 5

- 6、4、4、2、2、0、0、-2

``````

``````输入：nums = [1,-2,3,4,-10,12], k = 16

``````

• `n == nums.length`
• `1 <= n <= 105`
• `-109 <= nums[i] <= 109`
• `1 <= k <= min(2000, 2n)`

You are given an integer array `nums` and a positive integer `k`. You can choose any subsequence of the array and sum all of its elements together.

We define the K-Sum of the array as the `kth` largest subsequence sum that can be obtained (not necessarily distinct).

Return the K-Sum of the array.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Note that the empty subsequence is considered to have a sum of `0`.

Example 1:

``````Input: nums = [2,4,-2], k = 5
Output: 2
Explanation: All the possible subsequence sums that we can obtain are the following sorted in decreasing order:
- 6, 4, 4, 2, 2, 0, 0, -2.
The 5-Sum of the array is 2.
``````

Example 2:

``````Input: nums = [1,-2,3,4,-10,12], k = 16
Output: 10
Explanation: The 16-Sum of the array is 10.
``````

Constraints:

• `n == nums.length`
• `1 <= n <= 105`
• `-109 <= nums[i] <= 109`
• `1 <= k <= min(2000, 2n)`

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

struct node {
ll sum;
int ix;

node(ll sum, int ix) : sum(sum), ix(ix) {}

bool operator<(const node &other) const {
return sum < other.sum;
}
};

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

ll sum = 0;
for (auto &a : nums) {
if (a >= 0) {
sum += a;
} else {
a = -a;
}
}

sort(nums.begin(), nums.end());

priority_queue<node> pq;
pq.push(node(sum - nums[0], 0));

ll res = sum;
--k;

while (k--) {
auto tp = pq.top();
pq.pop();

ll sum = tp.sum;
int ix = tp.ix;

res = sum;

if (ix + 1 < n) {
pq.push(node(sum - nums[ix + 1] + nums[ix], ix + 1));
pq.push(node(sum - nums[ix + 1], ix + 1));
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````