Thank you so much for participating in our round! We really hope you enjoyed it. For us, it was an amazing and educational experience, and we look forward to the possibility that we could one day help to or hold a round again. Thanks again to abc864197532 and Vladithur for making the process so smooth and enjoyable.
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int maxw = 0, maxh = 0;
for (int i=0; i<n; i++) {
int w, h;
cin >> w >> h;
maxw = max(maxw, w);
maxh = max(maxh, h);
}
cout << 2 * (maxw + maxh) << "\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> A(n);
for (int i=0; i<n; i++) cin >> A[i];
int best = 0;
for (int i=0; i<n; i++) {
int curr = 0;
for (int j=i; j<n; j++) {
if (A[j] <= A[i]) {
curr += 1;
}
}
best = max(best, curr);
}
cout << n - best << "\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<ll> A(n);
for (int i=0; i<n; i++) cin >> A[i];
map<ll,vector<ll>> adj;
for (int i=1; i<n; i++) {
ll u = A[i] + i;
ll v = u + i;
adj[u].push_back(v);
}
set<ll> vis;
function<void(ll)> dfs = [&](ll u) -> void {
if (vis.count(u)) return;
vis.insert(u);
for (ll v : adj[u]) dfs(v);
};
dfs(n);
cout << *vis.rbegin() << "\n";
}
return 0;
}
2027D1 - The Endspeaker (Easy Version)
2027D1 - The Endspeaker (Easy Version)
Let's use dynamic programming. We will have $$$\operatorname{dp}_{i,j}$$$ be the minimum cost to remove the prefix of length $$$i$$$, where the current value of $$$k$$$ is $$$j$$$. By a type $$$1$$$ operation, we can transition from $$$\operatorname{dp}_{i,j}$$$ to $$$\operatorname{dp}_{i,j+1}$$$ at no cost. Otherwise, by a type $$$2$$$ operation, we need to remove some contiguous subarray $$$a_{i+1}, a_{i+2}, \dots, a_{x}$$$ (a prefix of the current array), to transition to $$$\operatorname{dp}_{x,j}$$$ with a cost of $$$m - k$$$.
Let $$$r$$$ be the largest value of $$$x$$$ possible. Given we're spending $$$m - k$$$ whatever value of $$$x$$$ we choose, it's clear to see that we only need to transition to $$$\operatorname{dp}_{r,j}$$$. To find $$$r$$$ for each value of $$$i$$$ and $$$j$$$, we can either binary search over the prefix sums or simply maintain $$$r$$$ as we increase $$$i$$$ for a fixed value of $$$k$$$. The answer is then $$$\operatorname{dp}_{n,k}$$$. The latter method solves the problem in $$$\mathcal{O}(nm)$$$.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
void chmin(int &a, int b) {
a = min(a, b);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<int> A(n);
for (int i=0; i<n; i++) cin >> A[i];
vector<int> B(m);
for (int i=0; i<m; i++) cin >> B[i];
vector nxt(n, vector<int>(m));
for (int k=0; k<m; k++) {
int r = -1, sum = 0;
for (int i=0; i<n; i++) {
while (r < n && sum <= B[k]) sum += A[++r];
nxt[i][k] = r;
sum -= A[i];
}
}
vector dp(n+1, vector<int>(m, inf));
dp[0][0] = 0;
for (int k=0; k<m; k++) {
for (int i=0; i<n; i++) {
chmin(dp[nxt[i][k]][k], dp[i][k] + m - k - 1);
if (k < m-1)
chmin(dp[i][k+1], dp[i][k]);
}
}
int ans = inf;
for (int k=0; k<m; k++) {
chmin(ans, dp[n][k]);
}
if (ans == inf) {
cout << "-1\n";
} else {
cout << ans << "\n";
}
}
return 0;
}
2027D2 - The Endspeaker (Hard Version)
2027D2 - The Endspeaker (Hard Version)
Following on from the editorial for D1. Let's have the $$$\operatorname{dp}$$$ table store a pair of the minimum cost and the number of ways. Since we're now counting the ways, it's not enough just to consider the transition to $$$\operatorname{dp}_{r,j}$$$; we also need to transition to all $$$\operatorname{dp}_{x,j}$$$. Doing this naively is too slow, so let's instead find a way to perform range updates.
Let's say we want to range update $$$\operatorname{dp}_{l,j}, \operatorname{dp}_{l+1,j}, ..., \operatorname{dp}_{r,j}$$$. We'll store some updates in another table at either end of the range. Then, for a fixed value of $$$k$$$ as we iterate through increasing $$$i$$$-values, let's maintain a map of cost to ways. Whenever the number of ways falls to zero, we can remove it from the map. On each iteration, we can set $$$\operatorname{dp}_{i,j}$$$ to the smallest entry in the map, and then perform the transitions. This works in $$$\mathcal{O}(nm \log n)$$$.
Bonus: It's also possible to solve without the $$$\log n$$$ factor. We can use the fact that $$$\operatorname{dp}_{i,k}$$$ is non-increasing for a fixed value of $$$k$$$ to make the range updates non-intersecting by updating a range strictly after the previous iteration. Then we can just update a prefix sum array, instead of using a map.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int MOD = 1000000007;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<int> A(n);
for (int i=0; i<n; i++) cin >> A[i];
vector<int> B(m);
for (int i=0; i<m; i++) cin >> B[i];
vector nxt(n, vector<int>(m));
for (int k=0; k<m; k++) {
int r = -1, sum = 0;
for (int i=0; i<n; i++) {
while (r < n && sum <= B[k]) sum += A[++r];
nxt[i][k] = r;
sum -= A[i];
}
}
vector dp(n+1, vector<array<int,2>>(m, {inf, 0}));
vector upd(n+1, vector(m, vector<array<int,3>>()));
upd[0][0].push_back({0, 0, 1});
upd[1][0].push_back({1, 0, 1});
for (int k=0; k<m; k++) {
map<int,array<int,2>> mp;
for (int i=0; i<=n; i++) {
for (auto [t, move, count] : upd[i][k]) {
if (t == 0) {
auto &[a, b] = mp[move];
a += 1;
(b += count) %= MOD;
} else {
auto &[a, b] = mp[move];
a -= 1;
(b += MOD - count) %= MOD;
if (a == 0) mp.erase(move);
}
}
if (mp.empty()) continue;
auto &[move, info] = *mp.begin();
dp[i][k] = {move, info[1]};
if (i == n) continue;
if (k < m-1) {
upd[i][k+1].push_back({0, move, info[1]});
upd[i+1][k+1].push_back({1, move, info[1]});
}
if (nxt[i][k] > i) {
upd[i+1][k].push_back({0, move + (m - k - 1), info[1]});
if (nxt[i][k] < n) {
upd[nxt[i][k]+1][k].push_back({1, move + (m - k - 1), info[1]});
}
}
}
}
map<int,int> mp;
for (int k=0; k<m; k++) {
auto &[move, count] = dp[n][k];
(mp[move] += count) %= MOD;
}
auto &[move, count] = *mp.begin();
if (move == inf) {
cout << "-1\n";
} else {
cout << move << " " << count << "\n";
}
}
return 0;
}
There exists an alternative solution for D1 & D2, using segment tree. We can actually consider the process in reverse; let's reformulate $$$\operatorname{dp}_{i,j}$$$ to represent the minimum score required to remove all elements after the $$$i$$$-th element, given that the current value of $$$k$$$ is $$$j$$$.
Instead of using a dp table, we maintain $$$m$$$ segment trees, each of length $$$n$$$. The $$$i$$$-th segment tree will represent the $$$i$$$-th column of the dp table.
We precalculate for each $$$i$$$ and $$$j$$$ the furthest position we can remove starting from $$$i$$$ — specifically, the maximum subarray starting from $$$i$$$ with a sum less than $$$b_j$$$. We store this in $$$\operatorname{nxt}_{i,j}$$$. This calculation can be done in $$$\mathcal{O}(nm)$$$ time using a sliding window.
To transition in the dp, we have:
This transition can be computed in $$$\mathcal{O}(\log n)$$$ time thanks to range querying on the segment tree, so our total complexity is $$$\mathcal{O}(nm \log n)$$$. For D2, we can store the count of minimums within each segment, and simply sum these counts to get the total number of ways.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int modN = 1e9 + 7;
int mod(int n) {
return (n + modN) % modN;
}
struct SegmentTree {
struct Node {
int val = 1e18;
int cnt = 1;
};
vector<Node> st;
int n;
SegmentTree(int n): n(n) {
st.resize(4 * n + 1, Node());
}
SegmentTree(vector<int> a): n(a.size()) {
st.resize(4 * n + 1, Node());
build(a, 1, 0, n - 1);
}
void merge(Node& a, Node& b, Node& c) {
a.val = min(b.val, c.val);
if (b.val == c.val)
a.cnt = mod(b.cnt + c.cnt);
else if (b.val < c.val)
a.cnt = b.cnt;
else if (b.val > c.val)
a.cnt = c.cnt;
}
void build(vector<int>& a, int id, int l, int r) {
if (l == r) {
st[id].val = a[l];
return;
}
int mid = (l + r) / 2;
build(a, id * 2, l, mid);
build(a, id * 2 + 1, mid + 1, r);
merge(st[id], st[id * 2], st[id * 2 + 1]);
}
void update(int id, int l, int r, int u, int val, int cnt) {
if (l == r) {
st[id].val = val; // or st[id].sum += val
st[id].cnt = cnt;
return;
}
int mid = (l + r) / 2;
if (u <= mid) update(id * 2, l, mid, u, val, cnt);
else update(id * 2 + 1, mid + 1, r, u, val, cnt);
merge(st[id], st[id * 2], st[id * 2 + 1]);
}
void update(int idx, int val, int cnt) { //wrapper
update(1, 0, n - 1, idx, val, cnt);
}
Node query(int id, int l, int r, int u, int v) { //give 0, n - 1 as l and r and 1 as id
if (v < l || r < u) return Node();
if (u <= l && r <= v) {
return st[id];
}
int mid = (l + r) / 2;
auto a = query(id * 2, l, mid, u, v);
auto b = query(id * 2 + 1, mid + 1, r, u, v);
Node res;
merge(res, a, b);
return res;
}
Node query(int l, int r) { //wrapper
return query(1, 0, n - 1, l, r);
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int &A : a) cin >> A;
for (int &B : b) cin >> B;
if (*max_element(a.begin(), a.end()) > b[0]) {
cout << -1 << '\n';
return;
}
vector<vector<int>> nxt(m, vector<int>(n));
for (int i = 0; i < m; i++) {
int curr = 0, r = -1;
for (int j = 0; j < n; j++) {
while (r + 1 < n && curr + a[r + 1] <= b[i])
curr += a[r + 1], r += 1;
nxt[i][j] = r + 1;
if (j <= r) curr -= a[j];
r = max(r, j);
}
}
vector<SegmentTree> dp(m, SegmentTree(vector<int>(n + 1, 1e18)));
for (int i = 0; i < m; i++)
dp[i].update(n, 0, 1);
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
auto q1 = dp[j].query(i + 1, nxt[j][i]);
int v1 = q1.val + m - (j + 1), ps1 = q1.cnt;
if (i + 1 <= nxt[j][i]) dp[j].update(i, v1, ps1);
if (j != m - 1) {
auto q2 = dp[j + 1].query(i, i);
int v2 = q2.val, ps2 = q2.cnt;
auto q3 = dp[j].query(i, i);
if (v2 < q3.val)
dp[j].update(i, v2, ps2);
else if (v2 == q3.val)
dp[j].update(i, v2, mod(ps2 + q3.cnt));
}
}
}
cout << dp[0].query(0, 0).val << ' ' << dp[0].query(0, 0).cnt << '\n';
}
signed main() {
cin.tie(0) -> sync_with_stdio(false);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
2027E1 - Bit Game (Easy Version)
#include <bits/stdc++.h>
using namespace std;
int nimber(int x, int a) {
int aprime = 0;
bool goodbit = false;
for (int bit=30; bit>=0; bit--) {
if (x & (1 << bit)) {
aprime *= 2;
if (goodbit || (a & (1 << bit))) {
aprime += 1;
}
} else if (a & (1 << bit)) {
goodbit = true;
}
}
// g(2^k - 2) = 0, for all k >= 1.
for (int k=1; k<=30; k++) {
if (aprime == (1 << k) - 2) {
return 0;
}
}
// g(2^k - 1) = k, for all k >= 1.
for (int k=1; k<=30; k++) {
if (aprime == (1 << k) - 1) {
return k;
}
}
// g(2^k) = k + (-1)^k, for all k >= 0.
for (int k=1; k<=30; k++) {
if (aprime == (1 << k)) {
if (k % 2) return k - 1;
else return k + 1;
}
}
// g(2^k+1) = g(2^k+2) = ... = g(2^{k+1} - 3) = k + 1, for all k >= 2.
for (int k=2; k<=30; k++) {
if ((1 << k) < aprime && aprime <= (2 << k) - 3) {
return k + 1;
}
}
// should never get to this point
assert(false);
return -1;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> A(n);
for (int i=0; i<n; i++) cin >> A[i];
vector<int> X(n);
for (int i=0; i<n; i++) cin >> X[i];
int curr = 0;
for (int i=0; i<n; i++) curr ^= nimber(X[i], A[i]);
cout << (curr ? "Alice" : "Bob") << "\n";
}
return 0;
}
2027E2 - Bit Game (Hard Version)
#include <bits/stdc++.h>
using namespace std;
int dp[32][32][6][2][2];
const int mod = 1000000007;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> A(n);
for (int i=0; i<n; i++) cin >> A[i];
vector<int> B(n);
for (int i=0; i<n; i++) cin >> B[i];
vector<int> curr(32);
curr[0] = 1; // identity
for (int i=0; i<n; i++) {
memset(dp, 0, sizeof dp);
dp[0][0][0][0][0] = 1;
for (int j=0; j<=29; j++) {
int p = 29 - j; // place we are going to add a bit in
for (int k=0; k<=29; k++) { // position of most significant one in a'
for (int type=0; type<6; type++) { // 0, 1, 11111, 11110, 10000, else
for (int good=0; good<2; good++) { // good=1 iff good bit has occured
for (int low=0; low<2; low++) { // low=1 iff prefix below b
for (int bit=0; bit<2; bit++) { // bit in x
if (dp[j][k][type][good][low] == 0)
continue; // no point in transition since count is 0
if (!low && (B[i] & (1 << p)) == 0 && bit == 1)
continue; // x can't go higher than B[i]
if (bit == 0) {
int good2 = good || (A[i] & (1 << p)) != 0; // check good bit
int low2 = low || (B[i] & (1 << p)) != 0; // check if low
// nothing added to a' so nothing else changes
(dp[j+1][k][type][good2][low2] += dp[j][k][type][good][low]) %= mod;
} else {
int bita = good || (A[i] & (1 << p)) != 0; // bit in a'
int k2 = type == 0 ? 0 : k + 1; // increase if MSOne exists
int type2 = bita ?
(
type == 0 ? 1 : // add first one
(type == 1 || type == 2) ? 2 : // 11111
5 // can't add 1 after a 0
) : (
(type == 0) ? 0 : // 0
(type == 1 || type == 4) ? 4 : // 10000
(type == 2) ? 3 : // 11110
5 // can't have a zero in any other case
);
(dp[j+1][k2][type2][good][low] += dp[j][k][type][good][low]) %= mod;
}
}
}
}
}
}
}
vector<int> count(32); // number of x-values for each nimber
for (int k=0; k<=29; k++) { // position of MSOne
for (int good=0; good<2; good++) { // doesn't matter
for (int low=0; low<2; low++) { // doesn't matter
(count[0] += dp[30][k][0][good][low]) %= mod; // 0
(count[1] += dp[30][k][1][good][low]) %= mod; // 1
(count[k+1] += dp[30][k][2][good][low]) %= mod; // 11111
(count[0] += dp[30][k][3][good][low]) %= mod; // 11110
(count[k+(k%2?-1:1)] += dp[30][k][4][good][low]) %= mod; // 10000
(count[k+1] += dp[30][k][5][good][low]) %= mod; // else
}
}
}
count[0] -= 1; // remove when x=0
vector<int> next(32); // knapsack after adding this pile
for (int j=0; j<32; j++)
for (int k=0; k<32; k++)
(next[j ^ k] += 1LL * curr[j] * count[k] % mod) %= mod;
swap(curr, next);
}
cout << curr[0] << "\n";
}
return 0;
}
D1 is the worst problem i've seen in recent times
Problem B is very tricky.
Good to know my first approach to 2027B was nlog(n). I couldnt think of O(n^2) solution for some reason.
B and C were pretty good problems...D1 felt like a common DP problem
Can anyone explain why changing map to unordered_map in 2027C - Add Zeros causes a TL?
I even took the solution from the editorial and ended up with a TL.
Editorial solution with unordered_map 288191624 (TL 16)
Worst case access for unordered_map is O(n), whereas worst case for ordered_map is O(log n). In unordered map, the values are stored in buckets modulo a big number. If the input is constructed in such a way that all elements get stored in the same bucket, the worst case time complexity to access a single element becomes O(n). Hence, causing the TLE
test cases are made in such a way that they cause collisions , as the worst time complexity is O(n) so it can't pass. If you still want to use hashmap you would have to make your own hash function. https://codeforces.net/contest/2027/submission/288190713
One way to bypass this issue is to declare a custom_hash. The worst case time complexity for this still remains O(n), but you could atleast pass the current input values since you can use a random number generator to hash the values. Add the following piece of code and let me know if it passes or not.
Thank you for your replies!
I also found this amazing post explaining that.
Blowing up unordered_map, and how to stop getting hacked on it
Yeah, that's a great post. In the last contest, my submission to D was hacked for the very same reason..so this time, I made a custom hash function to minimize the risk of collisions for my solution to C
problem B
4
1 1 3 2
if we apply stalin then 2 will be automatically deleted and now we just have to remove 3 , then the resultant array will be 1 1 . The answer should be 1 .
You have to remove some/none of the elements then apply operations on resulting array.
Thanks for fast editorial
B was really difficult to analyze (for me); Only able to solve A ,hoping to perform better in upcoming ones.
If anyone could explain D2 to me in detailed manner would be really helpful, thanks in advance..
can anyone please outline the two pointer approach for D1?
Can we solve B using Monotoic Stack to find the maximum sub array that have the first element is largest? Time complexity will be reduce to O(n)?
Having an answer be 0 mod 1e9+7 for D2 is kind of crazy
Why my solution for Question C getting TLE
My solution 288152538
try refering this. This might help.
Problem c have also another solution