| Trophy Presentations — Asuka Ota, Ryo Nagamatsu, Mario Kart Wii |
UPD 1: added hints, problem credits, more specific acknowledgements and some remarks. Implementations are on the way, sorry for making y'all wait!
UPD 2: Implementations are finally here.
Author: awang11
Preparers: awang11, IceSerpent
Analysis: awang11
If there are two consecutive zeroes, can you ever change either of them?
t = int(input())
for _ in range(t):
n = int(input())
s = list(input())
for i in range(1,n-1):
if (s[i-1] == '1' and s[i+1] == '1'):
s[i] = '1'
ans1 = 0
for i in range(n):
if s[i] == '1':
ans1 += 1
for i in range(1,n-1):
if (s[i-1] == '1' and s[i+1] == '1'):
s[i] = '0'
for i in range(1,n-1):
if (s[i-1] == '1' and s[i+1] == '1'):
s[i] = '0'
ans = 0
for i in range(n):
if s[i] == '1':
ans += 1
print(ans, ans1)
Author: awang11
Preparers: awang11, IceSerpent
(Cool) analysis: awesomeguy856
Which animatronic should you choose with your flashlight?
How many animatronics are worth incrementing when there are $$$k$$$ flashes remaining?
Write an expression for the ending danger level in terms of the night length and the danger levels of the animatronics that get flashed.
t = int(input())
while (t > 0):
t -= 1
n, m, l = map(int, input().split())
a = list(map(int, input().split()))
lvls = [0] * m
curr = n
for i in range(l):
lvls[min(m,curr+1)-1] += 1
lvls.sort()
lvls = lvls[::-1]
if (curr > 0 and a[n-curr]-1 == i):
lvls[0] = 0
lvls.sort()
lvls = lvls[::-1]
curr -= 1
print(lvls[0])
Author: awang11
Preparer: IceSerpent
Analysis: IceSerpent
Solve the case of one drain first! You should aim for $$$O(n)$$$.
If you pick two drains, what's the shape of their overlap?
Brute force.
Implementation by misteg168.
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, h; cin >> n >> h;
vector<int> v(n);
for (auto &x : v) cin >> x;
vector<int> cnt(n);
for (int i = 0; i < n; i++) {
int curr = v[i];
cnt[i] = h - curr;
for (int j = i+1; j < n; j++)
curr = max(curr, v[j]), cnt[i] += h - curr;
curr = v[i];
for (int j = i-1; j >= 0; j--)
curr = max(curr, v[j]), cnt[i] += h - curr;
}
//~ for (int i = 0; i < n; i++)
//~ cout << v[i] << "\n";
int best = 0;
for (int i = 0; i < n; i++) {
int mx = v[i], arg = i;
for (int j = i; j < n; j++) {
if (v[j] > mx) {
mx = v[j];
arg = j;
}
best = max(cnt[i] + cnt[j] - cnt[arg], best);
}
}
cout << best << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) solve();
}
There are tons of ways to do this problem, and chances are you found a different one than most other contestants! This problem is solvable in subquadratic time however, can you do it?
Also, the diagrams in the problem, as well as the ones in all editorials and other problems, are completely drawn natively in tikzpictures. Did you know you can cram 3-D plots onto 2-D to make textured filling?
Author: awang11
Preparers: awang11, IceSerpent
Analysis: awang11
Let's first think about path graphs. For some $$$k$$$, what are the $$$n$$$ for which an $$$n$$$-path wins for Cyndaquil?
Between every pair of Cyndaquil-winning nodes a distance of $$$k$$$ apart, all the nodes on the path between them also win. How can we find these efficiently?
Why did we ask for only vertex $$$v$$$, and not for all nodes?
Tree DP.
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
typedef pair<int,int> pii;
#define INF 1e9
vector<vector<int>> adj;
int N, K, V;
int dfs(int v, int p = -1) {
int l1 = INF;
int l2 = INF;
for (int u : adj[v]) {
if (u != p) {
int guy = dfs(u, v);
if (guy < l2) swap(l2, guy);
if (l2 < l1) swap(l1, l2);
}
}
if (l1 == INF) {
return 0;
} else if (l2 == INF) {
return 1 + l1;
} else {
int s = 1 + l1;
if (l1 + l2 < K) s = 0;
return s;
}
// what
return -1;
}
int main() {
bool debug = 0;
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
while (T--) {
cin >> N >> K >> V;
adj = vector<vector<int>>(N+1);
for (int i = 1; i < N; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
cout << (dfs(V) ? "NO" : "YES") << endl;
}
return 0;
}
2207E1 - N-MEX (Constructive Version)
Author: awang11
Preparers: awang11, IceSerpent
Analysis: awang11
Write some bounds for the $$$a_i$$$. What's the biggest/smallest each one can be?
Try to pick only numbers that aren't in the $$$a_i$$$, and $$$+\infty$$$.
INF = 10**9
T = int(input())
for _ in range(T):
N = int(input())
A = list(map(int, input().split()))
taken = [False] * (N + 1)
ok = True
for i in range(N):
if not (N - i - 1 <= A[i] <= N):
ok = False
if i > 0 and A[i] > A[i - 1]:
ok = False
if not ok:
break
taken[A[i]] = True
if ok:
print("YES")
ptr = N
prev = N
for i in range(N):
if prev > A[i]:
print(INF, end=" ")
else:
ptr -= 1
while taken[ptr]:
ptr -= 1
print(ptr, end=" ")
prev = A[i]
print()
else:
print("NO")
2207E2 - N-MEX (Counting Version)
Same credits as E1.
Read E1's hints first.
There are actually a very well-constrained set of working solutions. How many times do we pick each number not present in the $$$a_i$$$?
Implementation by awesomeguy856.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define mod MOD
#define pii pair<int,int>
#define piii pair<pii,pii>
#define fi first
#define se second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// b banned, j used
// condition is that at 0, j+b = v[0]?
// b increases every index, j decreases when v[i]=v[i+1]
const int mod = 1e9+7;
void solve() {
int n; cin >> n;
vector<int> v(n);
for (int &r:v) cin >> r;
for (int i = 0; i < n; i++) {
if (v[i]<n-i-1||v[i]>n||i&&v[i]>v[i-1]) {
cout << "0\n"; return;
}
}
int ans=1;
for (int i = 0; i < n; i++) {
if (i&&v[i]==v[i-1]) ans=(ans*(v[i]-(n-i-1)))%mod;
else ans=(ans*(i+1))%mod;
}
cout << ans << "\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t=1; cin >> t;
while (t--) solve();
}
Author: IceSerpent
Preparers: awang11, IceSerpent
Analysis: awang11, IceSerpent
Think about how you'd play in the case of only one color. Once you have that, how would you do two colors?
Each color has some sequence of clues that will get them to be played correctly. How do we coalesce them into one string of clues?
Some rank clues must be given for all cards to be played. If two consecutive forced rank clues are for ranks $$$a, b$$$, is it ever optimal to only rank clue some of the ones between $$$a, b$$$?
There is an $$$O(n^2)$$$ dp. How can we speed it up?
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define f first
// #define s second
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll, ll>
struct Tree {
typedef ll T;
static constexpr T unit = 1e9;
T f(T a, T b) { return min(a,b); }
vector<T> s; ll n;
Tree(ll n = 0, T def = unit) : s(2*n, def), n(n) {}
void update(ll pos, T val) {
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(ll b, ll e) {
ll ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
T val (ll x) {
return query(x, x+1);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t; cin >> t;
while (t--) {
// inpute processing
ll n, m; cin >> n >> m;
ll nm = n * m;
ll cards [nm][2];
vector<int> order [m+1];
for (int i = 0; i < nm; i++) cin >> cards[i][1];
for (int i = 0; i < nm; i++) cin >> cards[i][0];
for (int i = 0; i < nm; i++) {
order[cards[i][0]].pb(cards[i][1]);
}
// compute fix clues
set<int> fixes [m+1];
for (int i = 1; i <= m; i++) {
int curr = 1;
for (int j = 0; j < n; j++) {
while (order[i][j] > curr) {
fixes[i].insert(curr);
curr++;
}
if (order[i][j] == curr) curr++;
}
fixes[i].insert(0);
fixes[i].insert(n+1);
}
set<int> global_fixes;
for (int i = 1; i <= m; i++) for (ll x : fixes[i]) global_fixes.insert(x);
// segtree dp
ll dp [n+1][2];
dp[0][0] = 0; dp[0][1] = 0;
// cout << dp[0][0] << " " << dp[0][1] << endl;
Tree dpc (n+1); dpc.update(0, n);
for (int i = 1; i <= n; i++) {
dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + 1;
dp[i][1] = 1e9;
if (global_fixes.count(i)) {
// cout << dp[i][0] << " " << dp[i][1] << endl;
continue;
}
int colors = m;
vector<int> bounds;
for (int j = 1; j <= m; j++) {
auto it = fixes[j].upper_bound(i); it--;
bounds.pb(*it);
}
bounds.pb(-1);
sort(bounds.begin(), bounds.end());
for (int j = m; j >= 0; j--) {
// cout << "B " << j << " " << bounds[j] << " " << dpc.query(bounds[j], i) << endl;
dp[i][1] = min(dp[i][1], dpc.query(bounds[j]+1, i) - (n-i+1) + m - j);
}
dpc.update(i, dp[i][1] + (n-i));
// cout << dp[i][0] << " " << dp[i][1] << endl;
}
cout << min(dp[n][0], dp[n][1]) - 1 << endl;
}
}
As suggested by the editorial, this problem was originally about Squid Game! Until we made the round about the 2010s, that is.
There's actually a way to do this in $$$O(nm \sqrt{nm})$$$ or faster with flows! Can you represent the problem as a flow or matching instance?
Author: awang11
Preparer: awang11
Analysis: awang11
Use Pigeonhole to first solve for the case of no needy cells.
How can you adjust your solution when there are needy cells?
The graph is planar. Recall the Euler characteristic formula.
Implementation by Hori.
#include <bits/stdc++.h>
using namespace std;
#ifdef HORI
#include "../lib/hori.h"
#else
#define debug(...)
#endif
using vi = vector<int>;
using pi = array<int, 2>;
using vpi = vector<pi>;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define nl '\n'
auto vec(auto&& v, int n) {return vector(n, v);}
auto vec(auto&& v, int n, auto... m) {return vector(n, vec(v, m...));}
template <class T> concept C = !is_same<T, string>::value && !is_same_v<std::remove_all_extents_t<T>, char> && ranges::range<T>;
template <C T> ostream& operator<<(ostream &os, const T &v) {for (auto x : v) os << x << ' '; return os << nl;}
template <C T> istream &operator>>(istream &in, T &v) {for (auto& x : v) in >> x; return in;}
#define L(x, ...) ([&] (auto&& x) -> decltype(auto) {return __VA_ARGS__;})
template <class... T> void re(T &...a) {(cin >> ... >> a);}
template <class... T> void pr(T... a) {((cout << ' ' << a), ...);}
#define def(t, a...) t a; re(a);
vi dx = {-1, 0, 1, 0};
vi dy = {0, -1, 0, 1};
void solve() {
def(int, n, m, a, b);
vector<string> g(n); re(g);
auto get = [&] (int x) {
auto v = vec(0ll, n, m);
FOR(i, 0, n) FOR(j, 0, m) v[i][j] = (i + j) % 3 != x or g[i][j] == '#';
FOR(i, 0, n) FOR(j, 0, m) if ((i + j) % 3 == x) {
while (true) {
auto prv = vec(pi{-1, -1}, n, m);
auto dfs = [&] (this auto dfs, int r, int c) -> void {
FOR(k, 0, 4) {
int nr = r + dx[k], nc = c + dy[k];
if (nr < 0 or nr >= n or nc < 0 or nc >= m) continue;
if (pi{nr, nc} == prv[r][c] or prv[nr][nc] != pi{-1, -1}) continue;
if (!v[nr][nc]) continue;
prv[nr][nc] = {r, c};
dfs(nr, nc);
}
};
dfs(i, j);
if (prv[i][j] == pi{-1, -1}) break;
int r = i, c = j;
while (g[r][c] != '.') {
auto [nr, nc] = prv[r][c];
r = nr, c = nc;
}
v[r][c] = 0;
}
}
int val = 0;
FOR(i, 0, n) FOR(j, 0, m) if (v[i][j]) val += (g[i][j] == 'x' ? b : a);
return pair{val, v};
};
auto [val, ret] = max({get(0), get(1), get(2)});
debug(val);
debug(grid_mode, ret);
auto vis = vec(0ll, n, m);
vpi v;
auto dfs = [&] (this auto dfs, int r, int c) -> void {
v.push_back({r + 1, c + 1});
vis[r][c] = 1;
FOR(k, 0, 4) {
int nr = r + dx[k], nc = c + dy[k];
if (nr < 0 or nr >= n or nc < 0 or nc >= m) continue;
if (vis[nr][nc] or !ret[nr][nc]) continue;
dfs(nr, nc);
}
};
FOR(i, 0, n) FOR(j, 0, m) if (ret[i][j] and !vis[i][j]) dfs(i, j);
pr(sz(v), nl, v);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
def(int, t); while (t--) solve();
}
It is open to us whether the following cheese is actually provably correct:
First attempt to fill in the cells (blind to whether they are special or not) in reading order, adding if it doesn't form a cycle.
Second attempt to fill in the cells, but with special cells first, in reading order, adding if it doesn't form a cycle.
We conjecture that one of the two always passes.
2207H1 - Bowser's Castle (Easy Version)
Author: awang11
Preparer: awang11, IceSerpent
Analysis: awang11, IceSerpent
Use 0-1 sorting to make the structure a little simpler. What's a concise way to visualize a min max function?
The min max function is a tree that alternates min/max across depths. Can you determine the type of the top operation?
You will need to try a good number of schemes, but try to find a point where you can split $$$f = \min(g, h)$$$ or similar. Then, divide and conquer will win.
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define INF 1e9
int get_int() {
int x; cin >> x;
if (x == -1) {
cout << "Wrong answer" << endl;
exit(0);
}
return x;
}
int ask(vector<int> Q) {
cout << "? ";
int clip = 100000;
for (int i = 1; i < Q.size(); i++) cout << max(-clip, min(clip, Q[i])) + clip + 1 << " ";
cout << endl; cout.flush();
return get_int() - clip - 1;
}
struct MMT {
int L, R; // range of variables acted on
vector<MMT*> subdivisions; // subfamilies
bool up, leaf; // type
int evals;
MMT(int L, int R, vector<MMT*> subdivisions, bool up) {
this->L = L;
this->R = R;
this->subdivisions = subdivisions;
this->up = up;
this->evals = 0;
this->leaf = (L == R);
}
MMT(int L, int R, bool up, float p = 0.5) {
this->L = L;
this->R = R;
this->up = up;
this->evals = 0;
this->leaf = (L == R);
if (leaf) return;
subdivisions = vector<MMT*>();
int prev = L-1;
for (int i = L; i < R; i++) {
if (rand() < RAND_MAX * p) {
subdivisions.push_back(new MMT(prev+1, i, !up, p));
prev = i;
}
}
if (prev == L-1) {
for (int i = L; i <= R; i++) {
subdivisions.push_back(new MMT(prev+1, i, !up, p));
prev = i;
}
} else if (prev != R) {
subdivisions.push_back(new MMT(prev+1, R, !up, p));
}
}
string vis() {
if (leaf) return "x"+to_string(L);
else {
string ret;
if (up) ret += "max";
else ret += "min";
ret += "(";
for (int i = 0; i < subdivisions.size(); i++) {
ret += subdivisions[i]->vis();
if (i != subdivisions.size() - 1) ret += ", ";
}
ret += ")";
return ret;
}
return "error";
}
int eval(const vector<int>& x) {
++evals;
if (leaf) return x[L];
int ret;
if (up) ret = -INF;
else ret = INF;
for (auto f : subdivisions) {
if (up) ret = max(ret, f->eval(x));
else ret = min(ret, f->eval(x));
}
return ret;
}
void flatten() {
if (leaf) return;
vector<MMT*> new_subdivisions;
for (auto f : subdivisions) {
f->flatten();
if (f->up == up && !f->leaf) {
for (auto x : f->subdivisions) {
new_subdivisions.push_back(x);
}
} else {
new_subdivisions.push_back(f);
}
}
subdivisions = new_subdivisions;
}
void prune_right() {
--R;
if (leaf) return;
else if ((*--subdivisions.end())->L == (*--subdivisions.end())->R) {
subdivisions.erase(--subdivisions.end());
}
else {
(*--subdivisions.end())->prune_right();
}
}
void prune_left() {
++L;
if (leaf) return;
else if ((*subdivisions.begin())->L == (*subdivisions.begin())->R) {
subdivisions.erase(subdivisions.begin());
}
else {
(*subdivisions.begin())->prune_left();
}
}
};
int bs_fwd(int L, int R, bool up, vector<int> defaults) {
vector<int> Q1;
int L1 = L;
int L2 = R;
while (L1 < L2) {
int M = (L1 + L2) / 2;
Q1 = defaults;
for (int i = L; i <= M; i++) {
Q1[i] = up;
}
for (int i = M+1; i <= R; i++) {
Q1[i] = !up;
}
if (ask(Q1) == up) L2 = M;
else L1 = M+1;
}
return L1;
}
int bs_rev(int L, int R, bool up, vector<int> defaults) {
vector<int> Q1;
int L1 = L;
int L2 = R;
while (L1 < L2) {
int M = (L1 + L2 + 1) / 2;
Q1 = defaults;
for (int i = L; i <= M-1; i++) {
Q1[i] = !up;
}
for (int i = M; i <= R; i++) {
Q1[i] = up;
}
if (ask(Q1) == up) L1 = M;
else L2 = M-1;
}
return L1;
}
MMT* mimic_full(int L, int R, vector<int> defaults) {
// if only one index remains there is nothing to do
if (L == R) return new MMT(L, R, vector<MMT*>(), 0);
int s = bs_fwd(L, R, 1, defaults);
int t = bs_rev(L, R, 1, defaults);
bool up = s < t;
vector<int> upd_defaults = defaults;
for (int i = L; i <= R; i++) upd_defaults[i] = !up;
int m_fwd = bs_fwd(L, R, up, upd_defaults);
int k_fwd = bs_fwd(m_fwd+1, R, up, upd_defaults);
int m_rev = bs_rev(L, R, up, upd_defaults);
int k_rev = bs_rev(L, m_rev-1, up, upd_defaults);
vector<int> g_fwd = upd_defaults;
vector<int> g_rev = upd_defaults;
for (int i = L; i < k_fwd; i++) g_fwd[i] = up;
for (int i = R; i > k_rev; i--) g_rev[i] = up;
int fwd_take = -1, rev_take = -1, cut = -1;
for (int i = 0; i < INF; i++) {
g_fwd[L+i] = !up;
if (ask(g_fwd) != up) {
g_fwd[L+i] = up;
fwd_take = L+i;
}
vector<int> check_fwd = g_fwd;
for (int j = L+i+1; j <= R; j++) {
check_fwd[j] = !up;
}
if (ask(check_fwd) == up) {
cut = fwd_take;
break;
}
g_rev[R-i] = !up;
if (ask(g_rev) != up) {
g_rev[R-i] = up;
rev_take = R-i;
}
vector<int> check_rev = g_rev;
for (int j = L; j <= R-i-1; j++) {
check_rev[j] = !up;
}
if (ask(check_rev) == up) {
cut = rev_take - 1;
break;
}
}
vector<int> left_defaults = upd_defaults;
for (int i = cut+1; i <= R; i++) left_defaults[i] = !up;
vector<int> right_defaults = upd_defaults;
for (int i = L; i <= cut; i++) right_defaults[i] = !up;
vector<MMT*> subdivisions;
subdivisions.push_back(mimic_full(L, cut, left_defaults));
subdivisions.push_back(mimic_full(cut+1, R, right_defaults));
return new MMT(L, R, subdivisions, up);
}
MMT* recover(int N) {
return mimic_full(1, N, vector<int>(N+1, 0));
}
int main() {
bool debug = 0;
// ios::sync_with_stdio(0);
// cin.tie(0);
int T = get_int();
while (T--) {
int N = get_int();
MMT* M = recover(N);
cout << "!" << endl; cout.flush();
while (1) {
vector<int> Q(1, 0);
for (int i = 0; i < N; i++) {
int x = get_int();
if (x == 0) break;
Q.push_back(x);
}
if (Q.size() > 1) {
cout << M->eval(Q) << endl; cout.flush();
} else break;
}
}
return 0;
}
2207H2 - Bowser's Castle (Medium Version)
Same credits as H1, main solution due to 244mhq.
Read the H1 hints.
Go for $$$O(n \log n)$$$; how can we optimize the previous approach?
Determine the top node in $$$O(\log n)$$$ time.
Scan for your split point from both ends simultaneously.
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define INF 1e9
int get_int() {
int x; cin >> x;
if (x == -1) {
cout << "Wrong answer" << endl;
exit(0);
}
return x;
}
int ask(vector<int> Q) {
cout << "? ";
int clip = 100000;
for (int i = 1; i < Q.size(); i++) cout << max(-clip, min(clip, Q[i])) + clip + 1 << " ";
cout << endl; cout.flush();
return get_int() - clip - 1;
}
struct MMT {
int L, R; // range of variables acted on
vector<MMT*> subdivisions; // subfamilies
bool up, leaf; // type
int evals;
MMT(int L, int R, vector<MMT*> subdivisions, bool up) {
this->L = L;
this->R = R;
this->subdivisions = subdivisions;
this->up = up;
this->evals = 0;
this->leaf = (L == R);
}
MMT(int L, int R, bool up, float p = 0.5) {
this->L = L;
this->R = R;
this->up = up;
this->evals = 0;
this->leaf = (L == R);
if (leaf) return;
subdivisions = vector<MMT*>();
int prev = L-1;
for (int i = L; i < R; i++) {
if (rand() < RAND_MAX * p) {
subdivisions.push_back(new MMT(prev+1, i, !up, p));
prev = i;
}
}
if (prev == L-1) {
for (int i = L; i <= R; i++) {
subdivisions.push_back(new MMT(prev+1, i, !up, p));
prev = i;
}
} else if (prev != R) {
subdivisions.push_back(new MMT(prev+1, R, !up, p));
}
}
string vis() {
if (leaf) return "x"+to_string(L);
else {
string ret;
if (up) ret += "max";
else ret += "min";
ret += "(";
for (int i = 0; i < subdivisions.size(); i++) {
ret += subdivisions[i]->vis();
if (i != subdivisions.size() - 1) ret += ", ";
}
ret += ")";
return ret;
}
return "error";
}
int eval(const vector<int>& x) {
++evals;
if (leaf) return x[L];
int ret;
if (up) ret = -INF;
else ret = INF;
for (auto f : subdivisions) {
if (up) ret = max(ret, f->eval(x));
else ret = min(ret, f->eval(x));
}
return ret;
}
void flatten() {
if (leaf) return;
vector<MMT*> new_subdivisions;
for (auto f : subdivisions) {
f->flatten();
if (f->up == up && !f->leaf) {
for (auto x : f->subdivisions) {
new_subdivisions.push_back(x);
}
} else {
new_subdivisions.push_back(f);
}
}
subdivisions = new_subdivisions;
}
void prune_right() {
--R;
if (leaf) return;
else if ((*--subdivisions.end())->L == (*--subdivisions.end())->R) {
subdivisions.erase(--subdivisions.end());
}
else {
(*--subdivisions.end())->prune_right();
}
}
void prune_left() {
++L;
if (leaf) return;
else if ((*subdivisions.begin())->L == (*subdivisions.begin())->R) {
subdivisions.erase(subdivisions.begin());
}
else {
(*subdivisions.begin())->prune_left();
}
}
};
int bs_fwd(int L, int R, bool up, vector<int> defaults) {
vector<int> Q1;
int L1 = L;
int L2 = R;
while (L1 < L2) {
int M = (L1 + L2) / 2;
Q1 = defaults;
for (int i = L; i <= M; i++) {
Q1[i] = up;
}
for (int i = M+1; i <= R; i++) {
Q1[i] = !up;
}
if (ask(Q1) == up) L2 = M;
else L1 = M+1;
}
return L1;
}
int bs_rev(int L, int R, bool up, vector<int> defaults) {
vector<int> Q1;
int L1 = L;
int L2 = R;
while (L1 < L2) {
int M = (L1 + L2 + 1) / 2;
Q1 = defaults;
for (int i = L; i <= M-1; i++) {
Q1[i] = !up;
}
for (int i = M; i <= R; i++) {
Q1[i] = up;
}
if (ask(Q1) == up) L1 = M;
else L2 = M-1;
}
return L1;
}
MMT* mimic_full(int L, int R, vector<int> defaults) {
// if only one index remains there is nothing to do
if (L == R) return new MMT(L, R, vector<MMT*>(), 0);
int s = bs_fwd(L, R, 1, defaults);
int t = bs_rev(L, R, 1, defaults);
bool up = s < t;
vector<int> upd_defaults = defaults;
for (int i = L; i <= R; i++) upd_defaults[i] = !up;
int m_fwd = bs_fwd(L, R, up, upd_defaults);
int k_fwd = bs_fwd(m_fwd+1, R, up, upd_defaults);
int m_rev = bs_rev(L, R, up, upd_defaults);
int k_rev = bs_rev(L, m_rev-1, up, upd_defaults);
vector<int> g_fwd = upd_defaults;
vector<int> g_rev = upd_defaults;
for (int i = L; i < k_fwd; i++) g_fwd[i] = up;
for (int i = R; i > k_rev; i--) g_rev[i] = up;
int fwd_take = -1, rev_take = -1, cut = -1;
for (int i = 0; i < INF; i++) {
g_fwd[L+i] = !up;
if (ask(g_fwd) != up) {
g_fwd[L+i] = up;
fwd_take = L+i;
}
vector<int> check_fwd = g_fwd;
for (int j = L+i+1; j <= R; j++) {
check_fwd[j] = !up;
}
if (ask(check_fwd) == up) {
cut = fwd_take;
break;
}
g_rev[R-i] = !up;
if (ask(g_rev) != up) {
g_rev[R-i] = up;
rev_take = R-i;
}
vector<int> check_rev = g_rev;
for (int j = L; j <= R-i-1; j++) {
check_rev[j] = !up;
}
if (ask(check_rev) == up) {
cut = rev_take - 1;
break;
}
}
vector<int> left_defaults = upd_defaults;
for (int i = cut+1; i <= R; i++) left_defaults[i] = !up;
vector<int> right_defaults = upd_defaults;
for (int i = L; i <= cut; i++) right_defaults[i] = !up;
vector<MMT*> subdivisions;
subdivisions.push_back(mimic_full(L, cut, left_defaults));
subdivisions.push_back(mimic_full(cut+1, R, right_defaults));
return new MMT(L, R, subdivisions, up);
}
MMT* recover(int N) {
return mimic_full(1, N, vector<int>(N+1, 0));
}
int main() {
bool debug = 0;
// ios::sync_with_stdio(0);
// cin.tie(0);
int T = get_int();
while (T--) {
int N = get_int();
MMT* M = recover(N);
cout << "!" << endl; cout.flush();
while (1) {
vector<int> Q(1, 0);
for (int i = 0; i < N; i++) {
int x = get_int();
if (x == 0) break;
Q.push_back(x);
}
if (Q.size() > 1) {
cout << M->eval(Q) << endl; cout.flush();
} else break;
}
}
return 0;
}
The music choice across H1, H2, H3 actually follows the level of the final castle in World 8 of New Super Mario Bros Wii.
2207H3 - Bowser's Castle (Hard Version)
Same credits as H1, main solution inspired by IceSerpent and awesomeguy856.
Read H1 and H2 first.
What is $$$f(1, \dots, n)$$$?
If $$$t = f(1, \dots, n)$$$, then $$$x_t$$$ is the leaf at an alternating path from root (max goes right, min goes left.)
What is $$$f(x_1, \dots, x_t, +\infty, \dots, +\infty)$$$? How does it relate to the tree structure of $$$f(x_1, \dots, x_n)$$$?
You know the number of variables in each child of $$$f(x_1, \dots, x_t, +\infty, \dots, +\infty)$$$ and $$$f(-\infty, \dots, -\infty, x_t, \dots, x_n)$$$. Can you use these children to assemble $$$f(x_1, \dots, x_n)$$$?
Work from the inside (two nearest pieces to $$$x_t$$$) to the outside with two pointers. How many queries do we use? The recurrence may look quite terrifying, but...
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
typedef pair<int,int> pii;
#define INF 1e9
int get_int() {
int x; cin >> x;
if (x == -1) {
cout << "Wrong answer" << endl;
exit(0);
}
return x;
}
int ask(vector<int> Q) {
cout << "? ";
int clip = 100000;
for (int i = 1; i < Q.size(); i++) cout << max(-clip, min(clip, Q[i])) + clip + 1 << " ";
cout << endl; cout.flush();
return get_int() - clip - 1;
}
struct MMT {
int L, R; // range of variables acted on
vector<MMT*> subdivisions; // subfamilies
bool up, leaf; // type
int evals;
MMT(int L, int R, vector<MMT*> subdivisions, bool up) {
this->L = L;
this->R = R;
this->subdivisions = subdivisions;
this->up = up;
this->evals = 0;
this->leaf = (L == R);
}
string vis() {
if (leaf) return "x"+to_string(L);
else {
string ret;
if (up) ret += "max";
else ret += "min";
ret += "(";
for (int i = 0; i < subdivisions.size(); i++) {
ret += subdivisions[i]->vis();
if (i != subdivisions.size() - 1) ret += ", ";
}
ret += ")";
return ret;
}
return "error";
}
int eval(const vector<int>& x) {
++evals;
if (leaf) return x[L];
int ret;
if (up) ret = -INF;
else ret = INF;
for (auto f : subdivisions) {
if (up) ret = max(ret, f->eval(x));
else ret = min(ret, f->eval(x));
}
return ret;
}
void flatten() {
if (leaf) return;
vector<MMT*> new_subdivisions;
for (auto f : subdivisions) {
f->flatten();
if (f->up == up && !f->leaf) {
for (auto x : f->subdivisions) {
new_subdivisions.push_back(x);
}
} else {
new_subdivisions.push_back(f);
}
}
subdivisions = new_subdivisions;
}
};
MMT* mimic_smart(int L, int R, vector<int> defaults) {
/**
Returns nullptr if invalid
Otherwise returns an MMT reconstruction defined on indices L..R
**/
/// Step 1: find the thing
// if only one index remains there is nothing to do
if (L == R) return new MMT(L, R, vector<MMT*>(), 0);
// get representative
vector<int> Q(defaults.begin(), defaults.end());
for (int i = L; i <= R; i++) Q[i] = i;
int cut = ask(Q);
if (cut == R) {
vector<int> new_defaults = defaults;
new_defaults = -INF;
MMT* rest = mimic_smart(L, R-1, new_defaults);
vector<MMT*> subs = {rest, new MMT(R, R, vector<MMT*>(), 0)};
return new MMT(L, R, subs, 1); // MAX
} else if (cut == L) {
vector<int> new_defaults = defaults;
new_defaults[cut] = INF;
MMT* rest = mimic_smart(L+1, R, new_defaults);
vector<MMT*> subs = {new MMT(L, L, vector<MMT*>(), 0), rest};
return new MMT(L, R, subs, 0); // MIN
}
/// Step 2: recurse
// make new defaults
vector<int> defaults_left = defaults;
for (int i = cut + 1; i <= R; i++) defaults_left[i] = INF;
vector<int> defaults_right = defaults;
for (int i = L; i < cut; i++) defaults_right[i] = -INF;
// subdivisions
vector<MMT*> left_subs, right_subs;
// left side
MMT* left = mimic_smart(L, cut, defaults_left);
left->flatten();
left_subs = left->subdivisions;
left_subs.pop_back();
// right side
MMT* right = mimic_smart(cut, R, defaults_right);
right->flatten();
right_subs = right->subdivisions;
reverse(right_subs.begin(), right_subs.end());
right_subs.pop_back();
/// Step 3: merge
// merge loop
MMT* ret = new MMT(cut, cut, vector<MMT*>(), 0);
while (left_subs.size() > 0 && right_subs.size() > 0) {
auto left_candidate = left_subs.back();
auto right_candidate = right_subs.back();
vector<int> query = defaults;
for (int i = L; i < left_candidate->L; i++) query[i] = 0;
for (int i = left_candidate->L; i <= left_candidate->R; i++) query[i] = 3;
for (int i = left_candidate->R + 1; i < right_candidate->L; i++) query[i] = 2;
for (int i = right_candidate->L; i <= right_candidate->R; i++) query[i] = 1;
for (int i = right_candidate->R + 1; i <= R; i++) query[i] = 4;
int u = ask(query);
if (u == 3) { // MAX is outside
ret = new MMT(ret->L, right_candidate->R, {ret, right_candidate}, 0); // MIN
ret->flatten();
right_subs.pop_back();
} else if (u == 1) { // MIN is outside
ret = new MMT(left_candidate->L, ret->R, {left_candidate, ret}, 1); // MAX
ret->flatten();
left_subs.pop_back();
} else {
// something went really wrong
cout << "uh oh, merge died" << endl;
exit(67);
}
}
while (left_subs.size()) {
auto left_candidate = left_subs.back();
ret = new MMT(left_candidate->L, ret->R, {left_candidate, ret}, 1); // MAX
ret->flatten();
left_subs.pop_back();
}
while (right_subs.size()) {
auto right_candidate = right_subs.back();
ret = new MMT(ret->L, right_candidate->R, {ret, right_candidate}, 0); // MIN
ret->flatten();
right_subs.pop_back();
}
return ret;
}
MMT* recover(int N) {
MMT* M = mimic_smart(1, N, vector<int>(N+1, 0));
return M;
}
int main() {
bool debug = 0;
// ios::sync_with_stdio(0);
// cin.tie(0);
int T; cin >> T;
while (T--) {
int N; cin >> N;
MMT* M = recover(N);
cout << "!" << endl; cout.flush();
while (1) {
vector<int> Q(1, 0);
for (int i = 0; i < N; i++) {
int x = get_int();
if (x == 0) break;
Q.push_back(x);
}
if (Q.size() > 1) {
cout << M->eval(Q) << endl; cout.flush();
} else break;
}
}
return 0;
}
The solution due to awesomeguy856 and incidentally the one in contest found by ecnerwala actually uses only $$$2n$$$ queries!
A naive entropy bound gives a lower bound of $$$n / \log n$$$ queries; can we push this to linear so our upper bound of $$$O(n)$$$ queries becomes asymptotically tight?
We apologize for the unexpectedly difficult B, but we hope you enjoyed thinking about the problems regardless!
Special thanks to Hori, nik_exists, awesomeguy856, shcal for their assistance with problems F through H3. We also acknowledge Amazed, chromate00, defnotmee, Noobish_Monk, awoo, misteg168, cduckling for sticking with us in copy-editing and improving statements up until the contest. Once again, a huge thanks to flummoxedfeline for making our round look beautiful. Without them this round wouldn't be complete.
Implementations will be added soon.
Auto comment: topic has been updated by awang11 (previous revision, new revision, compare).
i got goombah stompped
WORLD 9
Should have swapped B and C for the welfare of the barbarians :(
Problem b strapped my soul from my body
I got stuck on it for two hours. I got the idea and the solution in my head, but the implementation... THE IMPLEMENTATION...
Maybe you can try
std::multiset, it's easy to use. I used only 459B to get AC.Thanks, JR_Oler. But how would multiset be used in this problem?
My blog for multiset solution
The key is observation of m*l ≤ 2e5. Specifically, is m,l ≤ 2e5.
set & multiset has a function: if you traverse it using an iterator, you'll traverse the elements in increasing order.
So just use multiset to maintain the $$$min(n,m-1)$$$ animatronics which have the largest $$$d_i$$$ s and other things are the same as the editoral.
Apologize for my poor English.
It was..... traumatizing
I know there were some of you multitasking Codeforces and watching India win the world cup, I was doing the same :D
The exam is more confusing than my life, and my mind is emptier than my wallet.
Completely messed up this contest.
Just want to forget that I gave this contest lol.
Also I just can't get it why for Problem C https://mirror.codeforces.com/contest/2207/submission/365898415 fails on test case3. Wasted 2 hr on this. Can anyone explain why is it wrong?
I can't say why it's wrong, but if you start cleaning your code there's a big chance you find the problem.
That way I debugged my code and now I have AC on problem C. If you want I can share it, but there isn't anything equal in our codes.
Input:
Output: 17
Expected: 18
Debug your code via this TC
Thanks I got the issue.
in 3 hour i managed to solve first 2 question. contest was hard but i got best rank so far.
Codeforces comments aren’t LinkedIn posts bro
Did you know that C can be solved in O(n*log(n)) time using range max query? I suspect there also O(n) solution but can't figure it out yet x)
RMQ is replaceable by DSU here, so in $$$O(n \alpha)$$$ actually.
Oh yeah, you're right, DSU is indeed and better than RMQ, thanks for the info :)
Still wondering if O(n) solution exist, using sliding window or shuffling the queries, or maybe it's impossible and DSU is the best(?)
I think we can do C in $$$O(n)$$$ with dynamic programming on cartesian trees without any observations. Split each node of the cartesian tree using the maximum value.
$$$dp_{u,k}$$$ represents the maximum answer if we place $$$1 \leq k \leq 2$$$ drains in the range corresponding to node $$$u$$$ on the cartesian tree.
The transitions are easy and doable in $$$O(1)$$$ because as long as $$$k \geq 1$$$, water corresponding to rows $$$\max(a_l, \ldots, a_r) + 1$$$ to $$$h$$$ will all be drained. Excluding those rows, the drains belonging to the left child's range won't affect the amount of water drained by drains in the right child's range (and vice versa), so the contribution from each child is independent. We can just sum up $$$dp$$$ values for the left and right children.
Thank you very much! :) This is the answer that I wanted <3 Take my upvote ^^
Meanwhile me, who did in n^2 logn using RMQ
can you please explain the logic behind the nlogn solution or the DSU solution
you mean D
Exactly !
I wish I read E1 before D, wasted too much time there, was very close to solving E1 but the time ran out :(
in F editorial i think u guys forgot to change the names to iroh and zuko
Oh, true lol
Problem D was really very beautiful :D Thanks for the contest! Though B wasn't a B problem :(
it was... traumatizing(2)
Thank god I didn't get many WA on test 2 this contest...
In editorial of E1 i think you meant "Vacuously take a0=n". Cause "Vacuously take b0=n" does not make any sense.
am i the only person who found D easy (even though i spent embarrassingly long on the implementation)
me too but i didn't struggle with the implementation that much
https://mirror.codeforces.com/contest/2207/submission/367952752
Thanks for the competition! It was interesting. This is my first competition where I solved problem C in div 2. But I couldn't solve problem B. It felt like an animatronic had eaten my brains after C and now I couldn't solve it. It's interesting how I solved C: For each height a[i], I built a height map as follows: I went left and right, taking the maximum level from the current and the past. This is because we can't go down, but we can go up. Then I sorted by the total points, and took the first one (that is, the best outcome). Next, I made the following observation: It will be effective to add new places if we expand the maximum depth of the pits. For this reason, I went through all the arrays except the best one and built a new height map as the minimum height value from two pits. Then I just output the maximum value.
By the way, I made it to the competition after my newborn sister was discharged!
that was... idk, the problem B...
Hey people, I dont seem to understand that why does this logic fail in B. Please help :'(
Consider this testcase:
1
2 3 30
29 30
Your code will output 1. However correct output is 10.
As much as i enjoyed solving B on paper, it took each and every brain cell to code it out
as O(xlogx) also would pass where x=m*l and this is much small and simple code
damn, why didn't i think of this, thanks for the solution, got surface level idea, will implement
i did same as you .
We can solve problem C in O(n log n) using divide and conquer. The top water (h — max(a)) will always be taken. Recursively solve left and right of the max position to find best first and second drains using the same idea.... left.first/right.first = max water by placing first drain in left/right segment. left.second/right.second = max water by placing second drain in left/right segment. At current position: ans.first = max(left.first, right.first). ans.second = if(left.first>right.first) max(right.first, left.second) else max(left.first, right.second).
unfortunately couldn't write the code in time xd
Code — 365906211
idk why ure getting downvoted but i had the same exact thought. although i was tripping up when there are multiple equal maxxes, but i guess that doesnt matter?
maybe for bad explanation xd no problem... and no same maxes wont matter... supposedly you entered the right. its max will be same as the parent. therefor the top_drain will be 0... as u wont take any water from the top part which is what should happend..
Why is nm <= 2*10^3 in the G problem when it's easy to achieve O(n*m*a(nm)) asymptotics using dsu? This is very confusing.
I think they maybe want to mislead into thinking about more complicated stuff (for example the problem from first glance looks like it could involve some flows, and you cannot immediately disregard that because the constraints are low enough).
The editorial solution iterates O(nm) times to cut a cycle each time, so this step was allowed to be O((nm)^2).
I think the easiest way to implement that part is actually to add cells one by one in a specific order (first #, then x, then .), and loop over its neighbours to see if two of them are in the same component. This can be implemented with DSU.
B as in "Brutal"
Hello , can anyone please help me find what the error is in my code for B ? I am pretty sure it matches with the editorial solution , but getting WA at testcase 6.
365901772
I feel like problems A, B, C in this round are all about implementing the process rather than ad-hoc solutions, and they’re slightly harder to implement than in other rounds.
I just have to say
orz we12223 for going to blue:)
messed up this round B was traumatizing :(
My rating was falling consistently until this contest, but then the miracle happened: my rating went up, and what is
I got 67th place.
bro , can u guide me .
Why did this code for C got accepted . It is O(N) , cannot prove it , I just precomputed every sinks drain coverage then I sorted , i chose leftmost point with maximal drain coverage then fixing that point as Ci (refer editorial) I calculated Cj-Ck by taking max across each element wrt that fixed Ci ,i can't prove it why choosing leftmost maximal sink was optimal.
365915250
You are sorting the value, so your solution is actually O(N*log(N)), but thank you for the idea! I could write strictly linear O(N) solution without any sorting: 365932645
Proof:
See again my implementation: 365932645
Auto comment: topic has been updated by awang11 (previous revision, new revision, compare).
Double ping!
My solution to F was pretty different from what the editorial did.
First, every card must be placed as a result of a color clue or a rank clue. Rank clues can pick up all cards of that rank, but color clues can only include intervals of ranks [l...r] such that the [l... r] is a subsequence of the ranks of that color, l is a prefix maximum, and there are no larger cards of the same color between the l and the r. So now I construct a bipartite graph where one partition are the "rank clues", and the other partition consists of the maximal intervals of ranks [l,r] for each color that can be gotten with a color clue. Then we add edges between any two vertices which have a card in common. Now the requirement is that for each card, you must take either the color clue or the rank clue corresponding to that card (we drop the requirement that l is a prefix maximum when l=r, for convenience), which is equivalent to finding a min vertex cover. With hopcroft karp this is O((mn)^3/2).
Implementation is quite short: 365890006
(Edit: the authors mention this in remark 2, oops)
https://mirror.codeforces.com/gym/104945/problem/B uses similar idea and my submission: 365945580
im dead
So consistently when there is no grey/green testers B turns out like this, no hate (i didn't even participate), just happen to notice this
you can create a blog. And in the blog so that there is a suspicious decision, otherwise some people make it out of AI
Div 1 + Div 2 vs Div 1
what?
B isn't B
Can anyone help me- on which test case my code is failing for in B
365958320
wasnt it a dijkstra for third problem?
I’m a beginner and I tried solving the problems during the contest, but I was only able to solve the first one. I got stuck on the second problem and eventually had to give up. After the contest, I tried to understand it by asking GPT/Claude, but even they couldn’t provide the correct solution.
Now I’ve looked at the tutorial, but it mainly explains the observations and intuition rather than the actual implementation. As someone who is still learning, it’s difficult for me to convert those observations into code.
Could someone please help by sharing the implementation or guiding how to translate the editorial’s idea into code? It would really help beginners like me understand the solution better. Thank you!
Could someone please provide the answers to the hints for Problem D?
Problem D
"Why did we ask for only vertex v, and not for all nodes?"
-Is it because if you asked for all nodes, contestants would easily guess the Tree DP approach? Or is there another reason?
The tree DP no longer works if you ask for all nodes, actually! It’s quite important that you get no updates from “above you” in the tree. When you ask for a single node, you don’t worry about paths passing through v, because if you find one, you’re done anyway!
Got it, Thank you very much.
is this possible with accurate hitboxes?
can any one help me about problem b { in my local system test cases answer is right but in same test cases codeforces compiler is givung wrong answer }
Auto comment: topic has been updated by awang11 (previous revision, new revision, compare).
In D, I am not able to understand why
1 5 2 3 5 4 4 3 3 2 2 1
gives "NO" as the answer, Can somebody please help me out?
snlx will not act on first move, cyndl goes to 2, snlx then go to edge(2-1) amd stop cyndil om vertex 2 , now u can figure it out, basically , snlx will wait until cyndl is about to make a move that will make it win or reach a winning node, through this strategy, snlx will make sure cyndl will waste its move so that snlx can get charged.
in the above TC, after reaching 2, if cydil tries to go to 5, it will again get stopped, and same again from there.
Thanks!! Got it now
The given solution for C is superb, observing that the drain at the max height between i,j would drain all the intersecting water is awesome. I could figure out that we need to do sum-intersection but I did not observe the intersection part. Nice one!!
can anyone explain why my code is giving wa on test-case 4 for problem -C :
https://mirror.codeforces.com/contest/2207/submission/366018299
it'll be a huge help
Your divide and conquer approach is wrong. Consider this testcase:
1
14 10
6 10 6 10 6 10 6 6 10 10 10 5 10 5
Your code will output 10, However optimal answer is 13.
awang11 i think there is some repetition of loop which is unnecessary in A.
for i in range(1,n-1): if (s[i-1] == '1' and s[i+1] == '1'): s[i] = '0'
for i in range(1,n-1): if (s[i-1] == '1' and s[i+1] == '1'): s[i] = '0'
same loop twice
Can anyone please explain the solution of E1 , mainly the construction idea.
In problem E1 the input
1
7
7 5 4 3 2 1 1
can be 6 7 5 4 3 2 0 a solution? maybe I am missreading something or doing something bad, but I think that is possible
Yep I was wrong.
awang11
2207C/Solution
Shouldn't it be $$$m \lt y$$$ instead of $$$m \leq y$$$. I looked at the implementation to double check. Or else the implementation would've been
+= h - cur + 1(?)In question B,How to distribute the danger levels till there are n — m — 1 flashes remaining
Why is upper bound in H3 equal to 3N-2? I have no idea how to find or proove that value
My approach to 2207E2 - N-MEX (Counting Version) (can be similar to editorial solution):
Firstly check, if there is any construction possible using $$$n - i$$$ <= $$$a_i$$$ <= n and $$$a_i$$$ <= $$$a_{i - 1}$$$.
If construction possible,
Array a looks like [x, x, x, ..., y, y, y..., z, z, ...] (x > y > z > ...).
When filling $$$b_i$$$s, when $$$a_i$$$ = x, all numbers (> y && < x) must appear. Also, there can be some numbers less than y (due to too long x block).
Now, we get to first index, where x -> y, i.e., we are standing at first index, idx, where, a[idx] = y. Let's say, there were (k1 + 1) cells where a[i] = x. From these k1 cells, we have to allocate some (x — y — 1) cells to numbers (y + 1, y + 2, ..., x — 1) in any order.
No. of ways for that: nCr(k1, x — y — 1) * (x — y — 1) ! .
Now, we have k1 — (x — y — 1) cells left for future (can be used for placing numbers less than y). I have used $$$gps$$$ variable for counting such cells. Thus, gps = $$$k1 - (x - y - 1)$$$ for now.
Now, we are at index idx, and let's calculate ways to fill $$$b_{idx}$$$. We can put any number that we have already placed in b, and numbers greater than y. Thus, (n — y) + k1 — (x — y — 1) ways to fill $$$b_{idx}$$$. {(n — y) = numbers above y, and (k1 — (x — y — 1)) = number less than y already placed due to long blocks).
Similarly, processing, we will get to first index, idx1, where a[idx1] = z. Now, new gps = (gps + idx1 — idx — 1). We have to allocate (y — z — 1) cells to numbers (z + 1, z + 2, ..., y — 1) in any order. Ways: nCr(gps, y — z — 1) * (y — z — 1) ! . gps will decrease by (y — z — 1) now.
You can process the whole array like this. If you have any confusion in the explanation or want any proofs, please ask.
Accepted submission: 366190115
in problem B how to get 19 in this testcase?
lets say from 0 — 13 seconds the danger levels are like this (can add 13 danger levels)
7 6 0obviously i will reset 7
0 6 0from 13 — 37 seconds (can add 24 danger levels)
15 15 0i reset 15
0 15 037 — 40 seconds (can add 3 danger levels)
0 18 0how to get 19?? or am i understanding the question wrongly?
lets say from 0 — 13 seconds the danger levels are like this (can add 13 danger levels)
5 4 4obviously i will reset 5
0 4 4from 13 — 37 seconds (can add 24 danger levels)
0 16 16i reset 16
0 16 037 — 40 seconds (can add 3 danger levels)
0 19 0oh wait is it cause we can do
0 — 13 seconds
6 6 1reset 6
0 6 113 — 37 seconds
15 15 1reset 15
0 15 137 — 40 seconds
0 18 1overall danger = 19
Wrong, Problem description said:
So overall danger for
0 18 1is 18 because $$$\max(0,18,1) = 18$$$..
Is there a typo in C:
"Then, a water tile at location $$$(x, y)$$$ is drained if $$$m_{min(x, i),max(x, i)} \lt y$$$" (instead of $$$\leq$$$ in editorial)? Otherwise, water tile is at same level as dirt and can't be drained.
Yea it seems like it, although I hid it behind a spoiler https://mirror.codeforces.com/blog/entry/151886?#comment-1352718
For problem c , i was able to AC a greedy solution such that one of the drains must be the single best drain, and then finding the second drain in this topology by subtracting the water sucked by the first drain. my code Been trying to get a proof for this but cant satisfy myself, anyone ?
Problem F can be solved by flow.
code
In B cant we always increase to only 2 enemies and at any checkpoint flash at max one(this way we will have maximum at end)?
I couldn't understand part of the solution of E2: "Call an index $$$i$$$ good if $$$a_i=a_i−1$$$ and bad otherwise. By definition, $$$|S_n|=n− \text{# of good steps}$$$." Consider this input $$$n=6$$$ and $$$a =$$$ {$$$6, 6, 6, 4, 3, 3$$$}, and this solution {$$$5, 2, 1, 5, 4, 0$$$}. Firstly, I ran this solution through the E1 judge & checked it's valid (& hand checked it too); and, we can see if $$$a_0=n=6$$$, there are 4 good steps according to definition $$$(i=1,2,3,6)$$$, so $$$|S_n|$$$ should have $$$6-4=2$$$ elements; but according to definition, $$$S_n =$$$ {$$$3$$$} since $$$3$$$ is the only value in $$$[0,6)$$$ excluding the values present in $$$b_1...b_6$$$: $$$(5,4,2,1,0)$$$. So $$$|S_n|=1$$$ in this example, which should break the formula. Please help me out! Thank you.
UPD: I figured out how the solution works.
well done
I don't really understand why would you not construct b in the implementation of E1. you are make a tutorial and then doing it the most unclear way possible. Maybe you are saving memory, but in this case you are using a lot of prints, which is even worse, and slower. What's the point?
why they always make long story statements