Author: FairyWinx
Preparation: FairyWinx
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
if (s == "^") {
cout << 1 << '\n';
continue;
}
int ans = 0;
if (s[0] == '_')
++ans;
if (s.back() == '_')
++ans;
for (int i = 0; i < (int) s.size() - 1; ++i) {
if (s[i] == '_' && s[i + 1] == '_')
++ans;
}
cout << ans << '\n';
}
}
1820B - JoJo's Incredible Adventures
Author: golikovnik
Preparation: teraqqq
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
string s; cin >> s; s += s;
int k = 0, z = 0;
for (char c : s) {
z = c == '1' ? z+1 : 0;
k = max(k, z);
}
const int n = s.size() / 2;
if (k > n) {
cout << (ll)n*n << '\n';
} else {
const ll side_a = (k+1)/2;
const ll side_b = (k+2)/2;
cout << side_a * side_b << '\n';
}
}
}
Author: TeaTime
Preparation: golikovnik
Editorial
Tutorial is loading...
Solution
// Nikita Golikov, 2023
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#ifdef GOLIKOV
#define debug(x) cerr << (#x) << ":\t" << (x) << endl
#else
#define debug(x) 238;
#endif
template <class A, class B>
bool smin(A& x, B&& y) {
if (y < x) {
x = y;
return true;
}
return false;
}
template <class A, class B>
bool smax(A& x, B&& y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <class T>
int calcMex(vector<T> v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int n = int(v.size());
for (int i = 0; i < n; ++i) if (v[i] != i) return i;
return n;
}
bool solveTest() {
int n; cin >> n;
vector<int> a(n);
map<int, int> leftOcc, rightOcc;
for (int i = 0; i < n; ++i) {
cin >> a[i];
rightOcc[a[i]] = i;
if (!leftOcc.count(a[i])) leftOcc[a[i]] = i;
}
int mex = calcMex(a);
if (leftOcc.count(mex + 1)) {
int L = leftOcc[mex + 1], R = rightOcc[mex + 1];
for (int i = L; i <= R; ++i) {
a[i] = mex;
}
int mx = calcMex(a);
assert(mx <= mex + 1);
return mx == mex + 1;
}
for (int i = 0; i < n; ++i) {
assert(a[i] != mex);
if (a[i] > mex || (leftOcc[a[i]] != rightOcc[a[i]])) {
return true;
}
}
return false;
}
int main() {
#ifdef GOLIKOV
assert(freopen("in", "rt", stdin));
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
cout << (solveTest() ? "Yes" : "No") << '\n';
}
#ifdef GOLIKOV
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Author: Tikhon228
Preparation: Kon567889
Editorial
Tutorial is loading...
Solution
//#pragma GCC target("trapv")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <iostream>
#include <list>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
const ll INF = 1e9 * 1e9 + 100, SZ = 1100;
ll n;
vector<pair<ll, ll>> vec;
map<ll, pair<ll, ll>> blocks;
pair<ll, ll> solve() {
set<pair<ll, ll>> widest, longest;
for (size_t i = 0; i < vec.size(); i++) {
widest.insert({ vec[i].first, i });
longest.insert({ vec[i].second, i });
blocks[i] = vec[i];
}
pair<ll, ll> ans = { -1, -1 };
bool mode = 0;
ll prevw = INF, prevh = INF, prv = -1;
bool cringe = 0;
while (widest.size() != 0) {
if (mode == 0) {
ll cur = (*widest.rbegin()).first, sum = 0;
if (ans.second == -1) ans.second = cur;
prv = blocks[(*widest.rbegin()).second].second;
while (widest.size() > 0 && (*widest.rbegin()).first == cur) {
auto it = (--widest.end());
longest.erase({blocks[it->second].second, it->second });
sum += blocks[it->second].second;
widest.erase(it);
}
if (!cringe) ans.first = sum;
prv = sum;
if (prevw == INF) {
prevh = cur;
} else {
prevw -= sum;
if (prevh != cur) return { -1, -1 };
}
} else {
ll cur = (*longest.rbegin()).first, sum = 0;
if (!cringe) {
ans.first = cur + prv;
cringe = 1;
}
while (longest.size() > 0 && (*longest.rbegin()).first == cur) {
auto it = (--longest.end());
widest.erase({ blocks[it->second].first, it->second });
sum += blocks[it->second].first;
longest.erase(it);
}
if (prevw == INF) {
prevw = cur;
prevh -= sum;
if (prevw != cur) return { -1, -1 };
} else {
prevh -= sum;
if (prevw != cur) return { -1, -1 };
}
}
mode ^= 1;
}
if (prevh == 0 || prevw == 0 || prevh == INF || prevw == INF) {
return ans;
} else {
return { -1, -1 };
}
}
signed main() {
fastInp;
ll t;
cin >> t;
while (t--) {
vec.clear();
blocks.clear();
cin >> n;
vec.resize(n);
for (auto& c : vec) cin >> c.first >> c.second;
vector<pair<ll, ll>> ans;
ans.push_back(solve());
swap(ans.back().first, ans.back().second);
if (ans.back().first == -1) ans.pop_back();
for (auto& c : vec) swap(c.first, c.second);
ans.push_back(solve());
if (ans.back().first == -1) ans.pop_back();
if (ans.size() == 2 && ans[0] == ans[1]) {
ans.pop_back();
}
cout << ans.size() << "\n";
for (auto c : ans) cout << c.first << " " << c.second << "\n";
}
return 0;
}
1819C - The Fox and the Complete Tree Traversal
Author: golikovnik
Preparation: DishonoredRighteous
Editorial
Tutorial is loading...
Solution
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <stdio.h>
#include <bits/stdc++.h>
#ifdef PERVEEVM_LOCAL
#define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
#define debug(x) 238
#endif
#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"
using ll = long long;
using ld = long double;
#ifdef PERVEEVM_LOCAL
std::mt19937 rnd(238);
#else
std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
template<typename T>
bool smin(T& a, const T& b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool smax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 200100;
std::vector<int> g[N];
int d[N], par[N];
bool onDiameter[N];
void dfs(int v, int p, int depth) {
d[v] = depth;
par[v] = p;
for (auto to : g[v]) {
if (to != p) {
dfs(to, v, depth + 1);
}
}
}
void run() {
int n;
scanf("%d", &n);
for (int i = 0; i < n - 1; ++i) {
int from, to;
scanf("%d%d", &from, &to);
g[from - 1].push_back(to - 1);
g[to - 1].push_back(from - 1);
}
dfs(0, 0, 0);
int v1 = 0;
for (int i = 0; i < n; ++i) {
if (d[i] > d[v1]) {
v1 = i;
}
}
dfs(v1, v1, 0);
int v2 = v1;
for (int i = 0; i < n; ++i) {
if (d[i] > d[v2]) {
v2 = i;
}
}
std::vector<int> diameter;
for (int v = v2; v != v1; v = par[v]) {
onDiameter[v] = true;
diameter.push_back(v);
}
onDiameter[v1] = true;
diameter.push_back(v1);
std::reverse(diameter.begin(), diameter.end());
for (int i = 0; i < n; ++i) {
if (onDiameter[i]) {
continue;
}
if (!onDiameter[par[i]]) {
printf("No\n");
return;
}
}
printf("Yes\n");
std::vector<int> ans;
for (int i = 0; i < (int)diameter.size(); i += 2) {
ans.push_back(diameter[i]);
if (i + 1 != (int)diameter.size()) {
for (auto to : g[diameter[i + 1]]) {
if (!onDiameter[to]) {
ans.push_back(to);
}
}
}
}
if (diameter.size() % 2 == 0) {
for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {
ans.push_back(diameter[i]);
if (i - 1 >= 0) {
for (auto to : g[diameter[i - 1]]) {
if (!onDiameter[to]) {
ans.push_back(to);
}
}
}
}
} else {
for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {
ans.push_back(diameter[i - 1]);
if (i - 2 >= 0) {
for (auto to : g[diameter[i - 2]]) {
if (!onDiameter[to]) {
ans.push_back(to);
}
}
}
}
}
assert((int)ans.size() == n);
for (auto i : ans) {
printf("%d ", i + 1);
}
printf("\n");
}
int main(void) {
// freopen(NAME".in", "r", stdin);
// freopen(NAME".out", "w", stdout);
#ifdef PERVEEVM_LOCAL
auto start = std::chrono::high_resolution_clock::now();
#endif
run();
#ifdef PERVEEVM_LOCAL
auto end = std::chrono::high_resolution_clock::now();
std::cerr << "Execution time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms" << std::endl;
#endif
return 0;
}
Author: Um_nik
Preparation: dshindov
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#include <exception>
using namespace std;
using ll = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> apples(n);
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
for (int j = 0; j < k; ++j) {
int x;
cin >> x;
apples[i].push_back(x);
}
}
// vector<int> last(m + 1, -1);
unordered_map<int, int> last;
auto get_last = [&](int i) {
if (!last.count(i)) {
return -1;
} else {
return last[i];
}
};
vector<char> can_zero(n + 1, false);
vector<int> prev(n + 1, 0);
can_zero[0] = true;
int oops = -1;
for (int i = 0; i < n; ++i) {
if (apples[i].empty()) {
can_zero[i + 1] = true;
last[0] = i;
} else {
int nearest_pair = get_last(0);
int new_oops = oops;
for (int x : apples[i]) {
nearest_pair = max(nearest_pair, get_last(x));
new_oops = max(new_oops, get_last(x));
last[x] = i;
}
if (nearest_pair != -1) {
int nearest_zero = prev[nearest_pair];
if (oops < nearest_zero) {
can_zero[i + 1] = true;
}
}
oops = new_oops;
}
if (can_zero[i + 1]) {
prev[i + 1] = i + 1;
} else {
prev[i + 1] = prev[i];
}
}
// vector<char> used(m + 1, false);
unordered_set<int> used;
vector<int> max_cnt(n + 1, 0);
int current_cnt = 0;
for (int i = n - 1; i >= 0; --i) {
bool fail = false;
if (apples[i].empty()) {
used.insert(0);
}
for (int x : apples[i]) {
if (used.count(x)) {
fail = true;
break;
}
used.insert(x);
++current_cnt;
}
if (fail) {
break;
}
if (used.count(0)) {
max_cnt[i] = m;
} else {
max_cnt[i] = current_cnt;
}
}
int ans = 0;
for (int i = 0; i <= n; ++i) {
if (can_zero[i]) {
ans = max(ans, max_cnt[i]);
}
}
cout << ans << '\n';
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--) solve();
}
Author: Tikhon228
Preparation: grphil
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
mt19937 rnd;
struct solve {
vector<pair<int, int>> r;
vector<vector<pair<int, int>>> s;
vector<int> ans;
int n, m;
static constexpr int rep = 45;
int dfs(int a, int p, int b) {
for (auto i : s[a]) {
if (i.x == b) {
return i.y;
}
if (i.x == p) {
continue;
}
int x = dfs(i.x, a, b);
if (x != -1) {
return x;
}
}
return -1;
}
solve() {
cin >> n >> m;
r.resize(m);
for (int i = 0; i < m; i++) {
cin >> r[i].x >> r[i].y;
r[i].x--;
r[i].y--;
}
s.resize(n);
ans.resize(m, -1);
int cnt = 0;
for (int i = 0; i < m; i++) {
rem(i);
for (int j = 0; j < rep; j++) {
if (!ask_end(i)) {
ans[i] = 1;
break;
}
}
if (ans[i] == 1) {
add(i);
cnt++;
s[r[i].x].emplace_back(r[i].y, i);
s[r[i].y].emplace_back(r[i].x, i);
}
}
assert(cnt == n - 1);
for (int i = 0; i < m; i++) {
if (ans[i] != -1) continue;
ans[i] = 1;
int c = dfs(r[i].x, -1, r[i].y);
rem(c);
add(i);
for (int j = 0; j < rep; j++) {
if (!ask_end(i)) {
ans[i] = 0;
break;
}
}
rem(i);
add(c);
}
cout << "!";
for (int i = 0; i < m; i++) {
cout << ' ' << ans[i];
}
cout << endl;
int x;
cin >> x;
if (x != 1) {
exit(1);
}
}
void rem(int x) {
cout << "- " << x + 1 << endl;
}
void add(int x) {
cout << "+ " << x + 1 << endl;
}
bool ask(int a) {
cout << "? " << a + 1 << endl;
// cerr << "? " << a + 1 << endl;
int x;
cin >> x;
return x == 1;
}
bool ask_end(int i) {
// cerr << "ask_end " << i << endl;
int a = r[i].x;
if (rnd() % 2) {
a = r[i].y;
}
return ask(a);
}
};
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
solve();
}
}
1819F - Willy-nilly, Crack, Into Release!
Author: teraqqq
Preparation: teraqqq
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using ll = long long;
const int Q = 1e5;
const int N = 20;
const int V = N*Q;
const ll LINF = 1e18;
struct MinMaxValue {
ll min_value;
ll max_value;
MinMaxValue operator * (const MinMaxValue& x) const {
if (x.max_value < 0 || max_value < 0) {
return MinMaxValue { 0, -1 };
}
return MinMaxValue {
.min_value = x.min_value + min_value,
.max_value = x.max_value + max_value
};
}
MinMaxValue operator + (const MinMaxValue& x) const {
if (x.max_value == -1) return *this;
if (max_value == -1) return x;
return MinMaxValue {
.min_value = min(x.min_value, min_value),
.max_value = max(x.max_value, max_value)
};
}
MinMaxValue& operator += (const MinMaxValue& x) {
return *this = *this + x;
}
void Reset() {
min_value = 0;
max_value = -1;
}
};
struct {
MinMaxValue dig, ver, hor;
int cnt;
int go[4];
} nd[V];
int vc = 0;
MinMaxValue dig[N+1], ver[N+1], hor[N+1];
std::set<ll> words;
int NewVertex(int h) {
int* go = nd[vc].go;
go[0] = go[1] = go[2] = go[3] = -1;
nd[vc].dig = dig[h];
nd[vc].hor = hor[h];
nd[vc].ver = ver[h];
nd[vc].cnt = 0;
return vc++;
}
tuple<const MinMaxValue&, const MinMaxValue&, const MinMaxValue&, int> GetState(int v, int h) {
return v == -1 ? make_tuple(cref(dig[h]), cref(ver[h]), cref(hor[h]), 0)
: make_tuple(cref(nd[v].dig), cref(nd[v].ver), cref(nd[v].hor), nd[v].cnt);
}
void Calculate(int v, int h, int corner) {
auto [dig0, ver0, hor0, cnt0] = GetState(nd[v].go[corner^0], h-1);
auto [dig1, ver1, hor1, cnt1] = GetState(nd[v].go[corner^1], h-1);
auto [dig2, ver2, hor2, cnt2] = GetState(nd[v].go[corner^2], h-1);
auto [dig3, ver3, hor3, cnt3] = GetState(nd[v].go[corner^3], h-1);
nd[v].cnt = cnt0 + cnt1 + cnt2 + cnt3;
nd[v].dig.Reset();
if (cnt0 == 0) nd[v].dig += hor2 * dig3 * ver1;
if (cnt3 == 0) nd[v].dig += ver2 * dig0 * hor1;
nd[v].hor = ver0 * dig2 * dig3 * ver1;
if (cnt2 + cnt3 == 0) nd[v].hor += hor0 * hor1;
nd[v].ver = hor0 * dig1 * dig3 * hor2;
if (cnt1 + cnt3 == 0) nd[v].ver += ver0 * ver2;
}
void UpdateCount(int v, int h, int corner, ll msk, ll msk_save) {
if (h == 0) {
if (nd[v].cnt == 0) {
words.insert(msk_save);
} else {
words.erase(msk_save);
}
nd[v].cnt ^= 1;
} else {
UpdateCount(nd[v].go[msk & 3], h-1, msk & 3, msk >> 2, msk_save);
Calculate(v, h, corner);
}
}
bool near_symbols[256][256];
MinMaxValue GetAnswer(int h) {
int v = 0;
if (nd[v].cnt == 0) {
return MinMaxValue { .min_value = 2, .max_value = 4 * dig[h-1].max_value };
}
MinMaxValue res; res.Reset();
bool cycle_len2 = false;
if (nd[v].cnt <= 1) cycle_len2 = true;
if (nd[v].cnt == 2) {
string s, t;
for (ll msk = *words.begin(); s.size() < h; msk >>= 2) s.push_back("abdc"[msk & 3]);
for (ll msk = *next(words.begin()); t.size() < h; msk >>= 2) t.push_back("abdc"[msk & 3]);
auto flag = near_symbols[s.back()][t.back()];
if (s.substr(0, h-1) == t.substr(0, h-1) && flag) {
cycle_len2 = true;
}
int s_suf = 0, t_suf = 0;
while (s_suf < h && s[h - s_suf - 1] == s.back()) ++s_suf;
while (t_suf < h && t[h - t_suf - 1] == t.back()) ++t_suf;
if (s_suf == t_suf && s_suf < h && flag && s.substr(0, h-s_suf-1) == t.substr(0, h-t_suf-1)
&& s.back() == t[h - s_suf - 1]
&& t.back() == s[h - t_suf - 1]) cycle_len2 = true;
}
if (cycle_len2) {
res.min_value = 2;
res.max_value = 2;
}
while (h != 0) {
const int v0 = nd[v].go[0], v1 = nd[v].go[1], v2 = nd[v].go[2], v3 = nd[v].go[3];
const auto& dig0 = get<0>(GetState(v0, h-1));
const auto& dig1 = get<0>(GetState(v1, h-1));
const auto& dig2 = get<0>(GetState(v2, h-1));
const auto& dig3 = get<0>(GetState(v3, h-1));
if(dig0.max_value > 0 && dig1.max_value > 0 && dig2.max_value > 0 && dig3.max_value > 0) {
res += dig0 * dig1 * dig2 * dig3;
}
--h;
if (v0 != -1 && nd[v0].cnt == nd[v].cnt) { v = v0; continue; }
if (v1 != -1 && nd[v1].cnt == nd[v].cnt) { v = v1; continue; }
if (v2 != -1 && nd[v2].cnt == nd[v].cnt) { v = v2; continue; }
if (v3 != -1 && nd[v3].cnt == nd[v].cnt) { v = v3; continue; }
break;
}
return res;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
vector<ll> v(q);
for (int i = 0; i < 4; ++i) {
int j = (i + 1) % 4;
near_symbols['a' + i]['a' + j] = true;
near_symbols['a' + j]['a' + i] = true;
}
dig[0] = ver[0] = hor[0] = { 1, 1 };
for (int i = 1; i <= n; ++i) {
dig[i] = hor[i-1] * dig[i-1] * ver[i-1];
hor[i] = ver[i] = hor[i-1] * hor[i-1] + ver[i-1] * ver[i-1] * dig[i-1] * dig[i-1];
}
int m_root = NewVertex(n); // make_root
assert(m_root == 0);
for (int i = 0; i < q; ++i) {
string s; cin >> s;
for (int j = 0; j < n; ++j) {
v[i] += (s[j] == 'b' || s[j] == 'c' ? 1ll : 0) << (2*j);
v[i] += (s[j] == 'c' || s[j] == 'd' ? 2ll : 0) << (2*j);
}
int w = 0;
for (int j = 0; j < n; ++j) {
int& next = nd[w].go[(v[i] >> (2*j)) & 3];
if (next == -1) next = NewVertex(n-j-1);
w = next;
}
}
for (ll msk : v) {
UpdateCount(0, n, 0, msk, msk);
auto [a, b] = GetAnswer(n);
if (a > b) {
cout << -1 << '\n';
} else {
cout << a << " " << b << '\n';
}
}
}
Thanks for the editorial.
The idea in 1819C is so clever. How come I am so stupid in it, sticking in a implementation on it.
My stupid idea is that every subtree (apart from original) will expose exactly two routes to the rest of the tree, hence it could be implemented in a way of discussing the case of exposing exactly one current subtree root (if this subtree has no other nodes), the case of exposing one subtree root together with one its direct son, and the case of exposing two of its direct sons.
Removed it from my ugly implementation problem collection.
A different solution for D1D, runs in O(NlogN) and is slightly more horrible in implementation, but (imho) easier to understand. First, if there are two shops that both sell nothing and are located next to each other, we can delete the prefix before those two shops — it won't matter anyway. If there is a shop at the end — the answer is simply M, we can always choose the remaining apples.
Now let's divide the remaining shops into contiguous blocks which are separated by a shop which we can choose. Let's calculate for each shop the next shop at which it will intersect and delete all apples, if there is no such shop, we put it equal to N — we call it go. Then, the claim is such — if i and go[i] lie in the same block, we add an edge from i to go[i] + 1. Otherwise, find the first position of a shop that sells nothing — call it pos. We need to add an edge to all positions from pos + 1 to go[i] + 1. We can do it with a segment tree-like construction. Then, we simply run a DFS from vertex 0 and look at the optimal position we can reach.
Working code: https://codeforces.me/contest/1819/submission/202346479
The segment tree on nodes is a neat technique, but you don't actually need to build the graph in this problem. Since you're just interested in which nodes you can reach, and not the path you take to get there, and since all edges go from left to right, you can just iterate through the nodes from left to right. For each node $$$i$$$, if you can reach $$$i$$$, then add $$$1$$$ to the values of all nodes in the range it can reach. Then you can check if a node is reachable by checking if it's value is positive.
And you do not need data structures to add $$$1$$$ over a range. You can add $$$1$$$ to the first node in the range, subtract $$$1$$$ from the one after the last one and build prefix sums as you go.
Code
Wow, that's really neat. And you don't have any of my segment tree horridness, and it works in $$$O(N)$$$. That's cool.
my merge sort tree ghastliness
The Python solution of 1819B gets TL in the system tests (or maybe you have to be extra careful with the constant). Is that what it was supposed to be?
Code: https://codeforces.me/contest/1820/submission/202227398
I submitted your code but with fast I/O. AC submission: https://codeforces.me/contest/1820/submission/202402504
Sounds surprisingly simple, thanks!
In 1819A/1820C
It's easy to see that in the resulting array, there should exist some element equal to {m+1}.I believe, that is should be {$$$m$$$}, and not {$$$m+1$$$}, since existence of {$$$m+1$$$} would not allow for $$$MEX$$$ = {$$$m+1$$$}.
Also, with regard to the time complexity, I believe, that $$$O(n)$$$ should work. I used a bitset to achieve the same (an array works as well).
Submission: 202202551
Here, I map all large/inconsequential elements to {$$$a.length+9$$$} (just for convenience)
Edit 1: Corrected typo
Edit 2: Added problem ID
CHEESY $$$O(N.(\log{N})^{2})$$$ implementation for div-1 D using segment tree: Link. (It can be optimized to $$$O(N.\log{N})$$$ using fractional cascading but im too lazy lol)
As for the solution to problem D, "Then we check that there will be no disappearances on the segment [s+1,j−1]". There might be a typo, we should check [s+1,i-1] instead because the disappearances on [j,i-1] can also affect the presence of apples.
The idea for D1C is clever, however, it requires some observation. I have come up with a solution with dp, I think it's harder to implement, but we don't need to say "If there is no subgraph then we win". Let's say there are two boolean arrays $$$from$$$ and $$$to$$$.
$$$from[v] = 1$$$ if we can travel all vertices in subtree of $$$v$$$ starting at $$$v$$$ and end in its child $$$u$$$, else $$$from[v] = 0$$$.
$$$to[v] = 1$$$ if we can travel all vertices in subtree of $$$v$$$ starting in some child $$$u$$$ of $$$v$$$ and end in $$$v$$$.
If $$$v$$$ is a leaf, we say that $$$from[v] = to[v] = 1$$$, however is isn't very important.
This might seem a little strange, but if you try to draw a path, these arrays will come naturally (at least I was able to think of this during the contest).
Both of these can be counted using dp. For example, for $$$to[v] = 1$$$ we need to travel through all children and their subtrees. If at least two children are not leafs, then we can already say that $$$to[v] = 0$$$, because if you go down from $$$u$$$, you can only go back in $$$v$$$, but then it will be final move in subtree, meaning there can only be at most non-leaf child. If all children are leafs, $$$to[v] = 1$$$. Else, let's say the remaining child is $$$u$$$. We need to travel through all vertices in subtree and then go back to $$$v$$$, meaning we need to end in a child, which is the exact definition of $$$from[u]$$$. So $$$to[v] = 1$$$ if all children are leafs, or there is one non-leaf child $$$u$$$ and $$$to[u] = 1$$$. $$$from[v]$$$ is counted using similar ideas.
Let's say we root the tree to a non-leaf vertex $$$root$$$ (if $$$n > 2$$$ then there is at least one). Let's remember all children of $$$root$$$ and erase them. If there are at least 3 vertices left, the answer is No. Else if there are 0, the answer is obviosly Yes, if there is 1 $$$u$$$, either $$$from[u]$$$ or $$$to[u]$$$ must be true, if there are 2 $$$s$$$ and $$$t$$$, $$$to[s] = 1$$$ and $$$from[t] = 1$$$, so that we can create the path.
The path will look like $$$root\space ->\space ...\space ->\space s\space ->\space all \space leafs\space -> f \space-> ... ->\space root$$$. First $$$...$$$ is a path that starts in a child of $$$s$$$ and ends in $$$s$$$. Second $$$...$$$ is a path that starts in $$$f$$$ and ends in its child. These sound familiar. We can recover those using recursive functions that call each other.
Actually I figured out, that we don't need to count dp, but instead do a little bruteforce. Since there can be at most 2 non-leaf children of $$$root$$$, we can just try every combination of $$$s$$$ and $$$f$$$, since finding the answer doesn't need $$$from$$$ and $$$to$$$!
Правда что задача D1B Мясник была названа так, чтобы отдать дань уважения nn русскому репу, а именно в честь трека Мясник который вышел за день до раунда(https://music.yandex.ru/album/25431536)
Конечно, весь состав жюри олимпиады уважает российскую аграрную промышленность и считает русские репы самыми лучшими.
Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
Div1C is a weaker version of this problem.
div1 ABCD video solution for Chinese ：
BiliBili
My solution of question The Butcher is giving Run time error on tc 4. I have debugged it for hours and couldnt able to spot any potential error.
Any help is apppreciated. Thank you
202609494
C. Конструктивная задача
Нам же не надо учитывать существование чисел больших(и равных) n. Следовательно можно обойтись левыми и правыми границами только для чисел строго меньших n.
И проверять можно только индексы до первого пустого значения(наше искомое число). Получится асимптотика без сортировок и махинаций с векторами. Разве это не линейная сложность за O(n)?
submission/202646652
Div 1 B:
But why?
UPDATE:
It's now obvious to me after re-reading the statement. We cut and then put one of the part in a box and don't cut it again.
Can someone explain me this part of the solution to Jojo's adventures?
If the longest chain of $$$1$$$'s in the double string (considered for including cycles) turns out to be greater than the length the string. The only case where it happens is if there are NO ZEROES. i.e. the entire square is filled with $$$1$$$'s (then the value of
k == s.size()). The answer is the area of the entire square!I've just realized that my solution to 1819D - Misha and Apples is somewhat different from the official solution.
Let $$$s_i$$$ be the set of all $$$k$$$ such that it's possible to visit $$$[1, i]$$$ with last reset (= the apples disappear) in $$$k$$$.
$$$s_i$$$ is a subset of $$$s_{i-1} \cup \{i\}$$$. How to find $$$s_i$$$? Let's define $$$j < i$$$ like in the editorial.
So, in the set $$$s$$$ you have to support "insert $$$i$$$" (which will become the largest element of $$$s$$$) and "remove elements from the beginning". So, you can just maintain $$$s$$$ using a queue. Then, you can calculate the final answer like in the editorial.
AC submission: 202229089 (it's $$$O(n (\log n + \log m))$$$, can be optimized to $$$O(n)$$$ like above, supposing $$$\sum k_i = O(n)$$$)
Alternate easy dp solution for D1-C which also runs in $$$O(n)$$$:
Let us root the tree at some node $$$r$$$.
The only observation required: If some valid cyclic path exists, then there will exist atleast one valid cyclic path which obeys the following rule: Whenever we enter subtree of some node $$$u$$$ while going along the path, then we exit it only after visiting all the nodes in subtree of $$$u$$$.
Consider a node $$$v$$$ and it's two children $$$c_1$$$ and $$$c_2$$$.
Let us assume that the claim is false, this would mean that it could be possible for our path to go from some node in $$$c_1$$$'s subtree to some node in $$$c_2$$$'s subtree, and back to some node in $$$c_1$$$'s subtree.
It is extremely easy to prove that this is not possible, and is left as practice for the reader. (Divide the scenario into a couple of cases based on relative order of first visiting $$$v$$$, node in $$$c_1$$$'s subtree and node in $$$c_2$$$'s subtree.)
Ok, so now that we can divide the paths into subpaths which are disjoint and completely contained within different subtrees, it's natural to think of subtree dp.
The states only need to hold boolean values, and they will be:
Now technically speaking there could have existed another slightly tricker to handle dp state, but we can completely neglect it by simply rooting the tree at a node with $$$> 1$$$ degree, so do it.
Ok, so what will the transitions be like? They're pretty trivial but here goes:
Finally, we have to handle transitions for the root node, $$$r$$$ seperately. The final answer will exist only if the children of $$$r$$$ can be rearranged such that:
And that's it, you can rebuild the required path from this dp with some simple implementation.
Implementation: link (my implementation is $$$O(n \log{n})$$$ which can be easily optimized to $$$O(n)$$$)
https://codeforces.me/contest/1819/submission/290286624 A- constructive problem why wrong answer on test 10 .