# weekly-contest-286

## A

### Statement

• `answer[0]``nums1` 中所有存在于 `nums2` 中的 不同 整数组成的列表。
• `answer[1]``nums2` 中所有存在于 `nums1` 中的 不同 整数组成的列表。

``````输入：nums1 = [1,2,3], nums2 = [2,4,6]

``````输入：nums1 = [1,2,3,3], nums2 = [1,1,2,2]

nums2 中的每个整数都在 nums1 中出现，因此，answer[1] = [] 。
``````

• `1 <= nums1.length, nums2.length <= 1000`
• `-1000 <= nums1[i], nums2[i] <= 1000`

Given two 0-indexed integer arrays `nums1` and `nums2`, return a list `answer` of size `2` where:

• `answer[0]` is a list of all distinct integers in `nums1` which are not present in `nums2`.
• `answer[1]` is a list of all distinct integers in `nums2` which are not present in `nums1`.

Note that the integers in the lists may be returned in any order.

Example 1:

``````Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].``````

Example 2:

``````Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].
``````

Constraints:

• `1 <= nums1.length, nums2.length <= 1000`
• `-1000 <= nums1[i], nums2[i] <= 1000`

### Solution

``````from typing import List

class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
a = set(nums1)
b = set(nums2)
return [list(a - b), list(b - a)]
``````

## B

### Statement

• `nums.length` 为偶数
• 对所有满足 `i % 2 == 0` 的下标 `i``nums[i] != nums[i + 1]` 均成立

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

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

``````

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

You are given a 0-indexed integer array `nums`. The array `nums` is beautiful if:

• `nums.length` is even.
• `nums[i] != nums[i + 1]` for all `i % 2 == 0`.

Note that an empty array is considered beautiful.

You can delete any number of elements from `nums`. When you delete an element, all the elements to the right of the deleted element will be shifted one unit to the left to fill the gap created and all the elements to the left of the deleted element will remain unchanged.

Return the minimum number of elements to delete from `nums` to make it beautiful.

Example 1:

``````Input: nums = [1,1,2,3,5]
Output: 1
Explanation: You can delete either nums[0] or nums[1] to make nums = [1,2,3,5] which is beautiful. It can be proven you need at least 1 deletion to make nums beautiful.
``````

Example 2:

``````Input: nums = [1,1,2,2,3,3]
Output: 2
Explanation: You can delete nums[0] and nums[5] to make nums = [1,2,2,3] which is beautiful. It can be proven you need at least 2 deletions to make nums beautiful.
``````

Constraints:

• `1 <= nums.length <= 105`
• `0 <= 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 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 minDeletion(vector<int> &nums) {
int n = nums.size();
int i = 0;
for (int j = 1; j < n; j++) {
if (i % 2 == 0 && nums[j] == nums[i]) {
continue;
}
nums[++i] = nums[j];
}

if (i % 2 == 0) {
--i;
}

return n - (i + 1);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：queries = [1,2,3,4,5,90], intLength = 3

101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, …

``````

``````输入：queries = [2,4,6], intLength = 4

1001, 1111, 1221, 1331, 1441 和 1551 。
``````

• `1 <= queries.length <= 5 * 104`
• `1 <= queries[i] <= 109`
• `1 <= intLength <= 15`

Given an integer array `queries` and a positive integer `intLength`, return an array `answer` where `answer[i]` is either the `queries[i]th` smallest positive palindrome of length `intLength` or `-1` if no such palindrome exists.

A palindrome is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.

Example 1:

``````Input: queries = [1,2,3,4,5,90], intLength = 3
Output: [101,111,121,131,141,999]
Explanation:
The first few palindromes of length 3 are:
101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, …
The 90th palindrome of length 3 is 999.
``````

Example 2:

``````Input: queries = [2,4,6], intLength = 4
Output: [1111,1331,1551]
Explanation:
The first six palindromes of length 4 are:
1001, 1111, 1221, 1331, 1441, and 1551.
``````

Constraints:

• `1 <= queries.length <= 5 * 104`
• `1 <= queries[i] <= 109`
• `1 <= intLength <= 15`

### 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 Max(int n) {
long long res = 0;
for (int i = 0; i < n; i++) {
res = res * 10 + 9;
}
return res;
}

long long Min(int n) {
long long res = 1;
for (int i = 1; i < n; i++) {
res *= 10;
}
return res;
}

long long Make(long long tar, int flag) {
string s = to_string(tar);
int len = s.length();
for (int i = len - 1 - flag; i >= 0; i--) {
s += s[i];
}

long long res = 0;
for (int i = 0; i < s.length(); i++) {
res = res * 10 + (s[i] - '0');
}

return res;
}

vector<long long> kthPalindrome(vector<int> &queries, int intLength) {
int q = queries.size();
auto res = vector<long long>(q, 0);
for (int i = 0; i < q; i++) {
int len = (intLength + 1) / 2;
long long r = Max(len);
long long l = Min(len);
// cout << l << " " << r << endl;
long long tot = (r - l + 1);
if (queries[i] > tot) {
res[i] = -1;
continue;
}

long long tar = l + queries[i] - 1;
res[i] = Make(tar, intLength & 1);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

``````输入：piles = [[1,100,3],[7,8,9]], k = 2

``````

``````输入：piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7

``````

• `n == piles.length`
• `1 <= n <= 1000`
• `1 <= piles[i][j] <= 105`
• `1 <= k <= sum(piles[i].length) <= 2000`

There are `n` piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.

In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.

Given a list `piles`, where `piles[i]` is a list of integers denoting the composition of the `ith` pile from top to bottom, and a positive integer `k`, return the maximum total value of coins you can have in your wallet if you choose exactly `k` coins optimally.

Example 1:

``````Input: piles = [[1,100,3],[7,8,9]], k = 2
Output: 101
Explanation:
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.
``````

Example 2:

``````Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
Output: 706
Explanation:
The maximum total can be obtained if we choose all coins from the last pile.
``````

Constraints:

• `n == piles.length`
• `1 <= n <= 1000`
• `1 <= piles[i][j] <= 105`
• `1 <= k <= sum(piles[i].length) <= 2000`

### 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 maxValueOfCoins(vector<vector<int>> &piles, int k) {
vector<int> f(k + 1, 0);

for (int i = 0; i < piles.size(); i++) {
for (int j = k; j > 0; j--) {
int v = 0;
for (int o = 0; o < piles[i].size(); o++) {
v += piles[i][o];
int w = o + 1;
if (j - w >= 0) {
f[j] = max(f[j], f[j - w] + v);
} else {
break;
}
}
}
}

return f[k];
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````