# biweekly-contest-72

## A

### Statement

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

- nums[0] == nums[6] 且 0 * 6 == 0 ，能被 2 整除。
- nums[2] == nums[3] 且 2 * 3 == 6 ，能被 2 整除。
- nums[2] == nums[4] 且 2 * 4 == 8 ，能被 2 整除。
- nums[3] == nums[4] 且 3 * 4 == 12 ，能被 2 整除。
``````

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

``````

• `1 <= nums.length <= 100`
• `1 <= nums[i], k <= 100`

Given a 0-indexed integer array `nums` of length `n` and an integer `k`, return the number of pairs `(i, j)` where `0 <= i < j < n`, such that `nums[i] == nums[j]` and `(i * j)` is divisible by `k`.

Example 1:

``````Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.
``````

Example 2:

``````Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.
``````

Constraints:

• `1 <= nums.length <= 100`
• `1 <= nums[i], k <= 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 countPairs(vector<int> &nums, int k) {
int res = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
++res;
}
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：num = 33

10, 11, 12 是 3 个连续整数，所以返回 [10, 11, 12] 。
``````

``````输入：num = 4

``````

• `0 <= num <= 1015`

Given an integer `num`, return three consecutive integers (as a sorted array) that sum to `num`. If `num` cannot be expressed as the sum of three consecutive integers, return an empty array.

Example 1:

``````Input: num = 33
Output: [10,11,12]
Explanation: 33 can be expressed as 10 + 11 + 12 = 33.
10, 11, 12 are 3 consecutive integers, so we return [10, 11, 12].
``````

Example 2:

``````Input: num = 4
Output: []
Explanation: There is no way to express 4 as the sum of 3 consecutive integers.
``````

Constraints:

• `0 <= num <= 1015`

### 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<long long> sumOfThree(long long num) {
if (num % 3) {
return {};
}

return {num / 3 - 1, num / 3, num / 3 + 1};
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 比方说，给你 `finalSum = 12` ，那么这些拆分是 符合要求 的（互不相同的偶整数且和为 `finalSum`）：`(2 + 10)` ，`(2 + 4 + 6)` 和 `(4 + 8)` 。它们中，`(2 + 4 + 6)` 包含最多数目的整数。注意 `finalSum` 不能拆分成 `(2 + 2 + 4 + 4)` ，因为拆分出来的整数必须互不相同。

``````输入：finalSum = 12

(2 + 4 + 6) 为最多数目的整数，数目为 3 ，所以我们返回 [2,4,6] 。
[2,6,4] ，[6,2,4] 等等也都是可行的解。
``````

``````输入：finalSum = 7

``````

``````输入：finalSum = 28

(6 + 8 + 2 + 12) 有最多数目的整数，数目为 4 ，所以我们返回 [6,8,2,12] 。
[10,2,4,12] ，[6,2,4,16] 等等也都是可行的解。
``````

• `1 <= finalSum <= 1010`

You are given an integer `finalSum`. Split it into a sum of a maximum number of unique positive even integers.

• For example, given `finalSum = 12`, the following splits are valid (unique positive even integers summing up to `finalSum`): `(2 + 10)`, `(2 + 4 + 6)`, and `(4 + 8)`. Among them, `(2 + 4 + 6)` contains the maximum number of integers. Note that `finalSum` cannot be split into `(2 + 2 + 4 + 4)` as all the numbers should be unique.

Return a list of integers that represent a valid split containing a maximum number of integers. If no valid split exists for `finalSum`, return an empty list. You may return the integers in any order.

Example 1:

``````Input: finalSum = 12
Output: [2,4,6]
Explanation: The following are some valid splits: (2 + 10), (2 + 4 + 6), and (4 + 8).
(2 + 4 + 6) has the maximum number of integers, which is 3. Thus, we return [2,4,6].
Note that [2,6,4], [6,2,4], etc. are also accepted.
``````

Example 2:

``````Input: finalSum = 7
Output: []
Explanation: There are no valid splits for the given finalSum.
Thus, we return an empty array.
``````

Example 3:

``````Input: finalSum = 28
Output: [6,8,2,12]
Explanation: The following are some valid splits: (2 + 26), (6 + 8 + 2 + 12), and (4 + 24).
(6 + 8 + 2 + 12) has the maximum number of integers, which is 4. Thus, we return [6,8,2,12].
Note that [10,2,4,12], [6,2,4,16], etc. are also accepted.
``````

Constraints:

• `1 <= finalSum <= 1010`

### 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<long long> maximumEvenSplit(long long finalSum) {
if (finalSum & 1) {
return {};
}

vector<long long> res;
for (long long i = 2;; i += 2) {
if (finalSum >= i) {
finalSum -= i;
res.push_back(i);
}

if (finalSum == 0) {
break;
}

if (res.back() >= finalSum) {
break;
}
}

if (!res.empty() && res.back() >= finalSum) {
res.back() += finalSum;
finalSum = 0;
}

if (finalSum) {
res.push_back(finalSum);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

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

``````

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

``````

• `n == nums1.length == nums2.length`
• `3 <= n <= 105`
• `0 <= nums1[i], nums2[i] <= n - 1`
• `nums1` 和 `nums2` 是 `[0, 1, …, n - 1]` 的排列。

You are given two 0-indexed arrays `nums1` and `nums2` of length `n`, both of which are permutations of `[0, 1, …, n - 1]`.

A good triplet is a set of `3` distinct values which are present in increasing order by position both in `nums1` and `nums2`. In other words, if we consider `pos1v` as the index of the value `v` in `nums1` and `pos2v` as the index of the value `v` in `nums2`, then a good triplet will be a set `(x, y, z)` where `0 <= x, y, z <= n - 1`, such that `pos1x < pos1y < pos1z` and `pos2x < pos2y < pos2z`.

Return the total number of good triplets.

Example 1:

``````Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3]
Output: 1
Explanation:
There are 4 triplets (x,y,z) such that pos1x < pos1y < pos1z. They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3).
Out of those triplets, only the triplet (0,1,3) satisfies pos2x < pos2y < pos2z. Hence, there is only 1 good triplet.
``````

Example 2:

``````Input: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
Output: 4
Explanation: The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).
``````

Constraints:

• `n == nums1.length == nums2.length`
• `3 <= n <= 105`
• `0 <= nums1[i], nums2[i] <= n - 1`
• `nums1` and `nums2` are permutations of `[0, 1, …, n - 1]`.

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

struct BIT {
vector<ll> a;
int n;
void init(int n) {
this->n = n + 10;
a = vector<ll>(this->n, 0);
}
int lowbit(int x) {
return x & -x;
}
void add(int x, ll v) {
for (int i = x; i < n; i += lowbit(i)) a[i] += v;
}
ll query(int x) {
ll ret = 0;
for (int i = x; i > 0; i -= lowbit(i)) ret += a[i];
return ret;
}
ll query(int l, int r) {
if (l > r)
return 0;
return query(r) - query(l - 1);
}
void add(int l, int r, ll v) {
if (l > r)
return;
}
} bf, bg;

class Solution {
public:
long long goodTriplets(vector<int> &nums1, vector<int> &nums2) {
int n = nums1.size();

vector<int> pos(n + 1, 0);
for (int i = 0; i < n; i++) {
pos[nums2[i]] = i;
}

bf.init(n);
bg.init(n);

vector<ll> f(n + 1, 0), g(n + 1, 0);

{
for (int i = n - 1; i >= 0; i--) {
int x = nums1[i], y = pos[x];
f[x] = bf.query(y + 1);
// dbg(i, f[x]);
}
}

{
for (int i = n - 1; i >= 0; i--) {
int x = nums1[i], y = pos[x];
g[x] = bg.query(y + 1);
// dbg(i, g[x]);
}
}

long long res = 0;
for (int i = 0; i < n; i++) {
res += g[i];
}

return res;
}
};

#ifdef LOCAL

int main() {
{
auto s = new Solution();
auto a = vector<int>{2, 0, 1, 3};
auto b = vector<int>{0, 1, 2, 3};
auto ans = s->goodTriplets(a, b);
dbg(ans);
}

return 0;
}

#endif
``````