# biweekly-contest-86

## A

### Statement

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

``````

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

``````

``````输入：nums = [0,0,0]

``````

• `2 <= nums.length <= 1000`
• `-109 <= nums[i] <= 109`

Given a 0-indexed integer array `nums`, determine whether there exist two subarrays of length `2` with equal sum. Note that the two subarrays must begin at different indices.

Return `true` if these subarrays exist, and `false` otherwise.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

``````Input: nums = [4,2,4]
Output: true
Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.
``````

Example 2:

``````Input: nums = [1,2,3,4,5]
Output: false
Explanation: No two subarrays of size 2 have the same sum.
``````

Example 3:

``````Input: nums = [0,0,0]
Output: true
Explanation: The subarrays [nums[0],nums[1]] and [nums[1],nums[2]] have the same sum of 0.
Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.
``````

Constraints:

• `2 <= nums.length <= 1000`
• `-109 <= 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 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:
bool findSubarrays(vector<int> &nums) {
int n = int(nums.size());
auto mp = std::map<int, int>();
for (int i = 1; i < n; i++) {
auto res = nums[i - 1] + nums[i];
if (mp.count(res)) {
return true;
}

mp[res] = 1;
}

return false;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：n = 9

``````

``````输入：n = 4

``````

• `4 <= n <= 105`

An integer `n` is strictly palindromic if, for every base `b` between `2` and `n - 2` (inclusive), the string representation of the integer `n` in base `b` is palindromic.

Given an integer `n`, return `true` if `n` is strictly palindromic and `false` otherwise.

A string is palindromic if it reads the same forward and backward.

Example 1:

``````Input: n = 9
Output: false
Explanation: In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.
``````

Example 2:

``````Input: n = 4
Output: false
Explanation: We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.
``````

Constraints:

• `4 <= n <= 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>;

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:
bool isStrictlyPalindromic(int n) {
auto ok = [_n = n](int b) -> bool {
int n = _n;
auto v = vector<int>();
while (n) {
v.push_back(n % b);
n /= b;
}

auto _v = v;
reverse(all(_v));
return v == _v;
};

for (int i = 2; i <= n - 2; i++) {
if (!ok(i)) {
return false;
}
}

return true;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：mat = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], cols = 2

``````

``````输入：mat = [[1],[0]], cols = 1

``````

• `m == mat.length`
• `n == mat[i].length`
• `1 <= m, n <= 12`
• `mat[i][j]` 要么是 `0` 要么是 `1` 。
• `1 <= cols <= n`

You are given a 0-indexed `m x n` binary matrix `mat` and an integer `cols`, which denotes the number of columns you must choose.

A row is covered by a set of columns if each cell in the row that has a value of `1` also lies in one of the columns of the chosen set.

Return the maximum number of rows that can be covered by a set of `cols` columns.

Example 1:

``````Input: mat = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], cols = 2
Output: 3
Explanation:
As shown in the diagram above, one possible way of covering 3 rows is by selecting the 0th and 2nd columns.
It can be shown that no more than 3 rows can be covered, so we return 3.
``````

Example 2:

``````Input: mat = [[1],[0]], cols = 1
Output: 2
Explanation:
Selecting the only column will result in both rows being covered, since the entire matrix is selected.
Therefore, we return 2.
``````

Constraints:

• `m == mat.length`
• `n == mat[i].length`
• `1 <= m, n <= 12`
• `mat[i][j]` is either `0` or `1`.
• `1 <= cols <= n`

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

class Solution {
public:
int maximumRows(vector<vector<int>> &mat, int cols) {
int m = int(mat.size());
int n = int(mat[0].size());
auto v = vector<int>();
for (int i = 0; i < m; i++) {
int res = 0;
for (int j = 0; j < n; j++) {
res = (res << 1) + mat[i][j];
}
v.push_back(res);
}
int res = 0;
for (int S = 0; S < (1 << n); ++S) {
if (__builtin_popcount(S) > cols) {
continue;
}

int _res = 0;
for (int i = 0; i < m; i++) {
_res += (((v[i] ^ S) & v[i]) == 0);
}

res = max(res, _res);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

``````输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25

``````

``````输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19

``````

• `chargeTimes.length == runningCosts.length == n`
• `1 <= n <= 5 * 104`
• `1 <= chargeTimes[i], runningCosts[i] <= 105`
• `1 <= budget <= 1015`

You have `n` robots. You are given two 0-indexed integer arrays, `chargeTimes` and `runningCosts`, both of length `n`. The `ith` robot costs `chargeTimes[i]` units to charge and costs `runningCosts[i]` units to run. You are also given an integer `budget`.

The total cost of running `k` chosen robots is equal to `max(chargeTimes) + k * sum(runningCosts)`, where `max(chargeTimes)` is the largest charge cost among the `k` robots and `sum(runningCosts)` is the sum of running costs among the `k` robots.

Return the maximum number of consecutive robots you can run such that the total cost does not exceed `budget`.

Example 1:

``````Input: chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
Output: 3
Explanation:
It is possible to run all individual and consecutive pairs of robots within budget.
To obtain answer 3, consider the first 3 robots. The total cost will be max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 which is less than 25.
It can be shown that it is not possible to run more than 3 consecutive robots within budget, so we return 3.
``````

Example 2:

``````Input: chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
Output: 0
Explanation: No robot can be run that does not exceed the budget, so we return 0.
``````

Constraints:

• `chargeTimes.length == runningCosts.length == n`
• `1 <= n <= 5 * 104`
• `1 <= chargeTimes[i], runningCosts[i] <= 105`
• `1 <= budget <= 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 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 maximumRobots(vector<int> &c, vector<int> &r, long long b) {
int n = int(c.size());

auto s = vector<ll>(n + 5, 0);
auto cc = vector<pair<int, int>>();

int res = 0;

for (int i = 0; i < n; i++) {
s[i + 1] = s[i] + r[i];
auto _c = make_pair(i, c[i]);
while (!cc.empty()) {
if (cc.back().second <= _c.second) {
cc.pop_back();
} else {
break;
}
}
cc.push_back(_c);

int l = 1, r = (i + 1), _res = 0;
while (r - l >= 0) {
int mid = (l + r) >> 1;

ll sum = s[i + 1] - s[i + 1 - mid];
int cnt = mid;
auto pos = upper_bound(all(cc), make_pair(i - mid + 1, -1));
// auto pos = cc.begin();

// 5 8 9 1

if (sum * cnt + pos->second <= b) {
l = mid + 1;
_res = mid;
} else {
r = mid - 1;
}
}

res = max(res, _res);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````