### tourist's blog

By tourist, history, 15 months ago, Enjoy!

A. Balanced Rating Changes
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int flag = 1;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x % 2 == 0) {
cout << x / 2 << '\n';
} else {
cout << (x + flag) / 2 << '\n';
flag *= -1;
}
}
return 0;
}

B. Balanced Tunnel
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
--b[i];
}
vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[b[i]] = i;
}
vector<int> c(n);
for (int i = 0; i < n; i++) {
c[i] = pos[a[i]];
}
int mx = -1, ans = 0;
for (int i = 0; i < n; i++) {
if (c[i] > mx) {
mx = c[i];
} else {
++ans;
}
}
cout << ans << '\n';
return 0;
}

C1. Balanced Removals (Easier)
Solution by arsijo
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<pair<int, int>, pair<int, int> > ii;

int main(){
int n;
cin >> n;

vector<ii> v(n);
for (int i = 0; i < n; i++){
cin >> v[i].first.first >> v[i].first.second >> v[i].second.first;
v[i].second.second = i + 1;
}

while(!v.empty()){
sort(v.begin(), v.end());
int x = v.back().first.first;
int y = v.back().first.second;
int z = v.back().second.first;
int pos = v.back().second.second;
v.pop_back();
int ind = 0;
ll d = 1e10;
for (int i = 0; i < (int) v.size(); i++){
ll dist = abs(v[i].first.first - x);
dist += abs(v[i].first.second - y);
dist += abs(v[i].second.first - z);
if (dist < d){
d = dist;
ind = i;
}
}
cout << pos << " " << v[ind].second.second << endl;
v.erase(v.begin() + ind);
}
}

C2. Balanced Removals (Harder)
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

const int D = 3;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<int>> p(n, vector<int>(D));
for (int i = 0; i < n; i++) {
for (int j = 0; j < D; j++) {
cin >> p[i][j];
}
}
auto Solve = [&](auto& Self, vector<int> ids, int k) {
if (k == D) {
return ids;
}
map<int, vector<int>> mp;
for (int x : ids) {
mp[p[x][k]].push_back(x);
}
vector<int> a;
for (auto& q : mp) {
int cur = Self(Self, q.second, k + 1);
if (cur != -1) {
a.push_back(cur);
}
}
for (int i = 0; i + 1 < (int) a.size(); i += 2) {
cout << a[i] + 1 << " " << a[i + 1] + 1 << '\n';
}
return (a.size() % 2 == 1 ? a.back() : -1);
};
vector<int> t(n);
iota(t.begin(), t.end(), 0);
Solve(Solve, t, 0);
return 0;
}

D. Balanced Playlist
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(3 * n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i + n] = a[i + 2 * n] = a[i];
}
vector<int> ans(3 * n);
vector<int> st_max;
vector<int> st_min;
for (int i = 3 * n - 1; i >= 0; i--) {
while (!st_max.empty() && a[st_max.back()] < a[i]) {
st_max.pop_back();
}
while (!st_min.empty() && a[st_min.back()] > a[i]) {
st_min.pop_back();
}
int low = 0, high = (int) st_min.size();
while (low < high) {
int mid = (low + high) >> 1;
if (a[st_min[mid]] * 2 < a[i]) {
low = mid + 1;
} else {
high = mid;
}
}
int nxt = 3 * n;
if (low > 0) {
nxt = min(nxt, st_min[low - 1]);
}
if (!st_max.empty()) {
nxt = min(nxt, st_max.back());
}
if (nxt < 3 * n && a[nxt] >= a[i]) {
ans[i] = ans[nxt];
} else {
ans[i] = nxt;
}
st_min.push_back(i);
st_max.push_back(i);
}
for (int i = 0; i < n; i++) {
if (i > 0) {
cout << " ";
}
cout << (ans[i] == 3 * n ? -1 : ans[i] - i);
}
cout << '\n';
return 0;
}

E. Balanced Binary Search Trees
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int x = 1;
while (x <= n) {
if (n == x || n == x + 1) {
cout << 1 << '\n';
return 0;
}
if (x % 2 == 0) {
x = x + 1 + x;
} else {
x = (x + 1) + 1 + x;
}
}
cout << 0 << '\n';
return 0;
}

F. Balanced Domino Placements
Solution by arsijo
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 998244353;
const int MAX = 3610;
ll dp1[MAX][MAX], dp2[MAX][MAX];
int has1[MAX], has2[MAX];
ll fac[MAX], c[MAX][MAX];
int n, m, k;

void make(int n){
dp1 = 1;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= m; j++){
dp1[i][j] = dp1[i - 1][j];
if (j && i >= 2 && has1[i] == 0 && has1[i - 1] == 0){
dp1[i][j] += dp1[i - 2][j - 1];
}
dp1[i][j] %= MOD;
}
}
}

int main(){
cin >> n >> m >> k;
int t = max(n, m) + 1;
vector<ll> f(t);
for (int i = 1; i <= k; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
if (has1[a] || has1[c] || has2[b] || has2[d]){
cout << 0 << endl;
return 0;
}
has1[a] = has1[c] = has2[b] = has2[d] = 1;
}
int N = n, M = m;
for (int i = 1; i <= n; i++){
N -= has1[i];
}
for (int i = 1; i <= m; i++){
M -= has2[i];
}
make(n);
swap(dp1, dp2);
swap(has1, has2);
make(m);
swap(dp1, dp2);
swap(has1, has2);
c = 1;
f = 1;
for (int i = 1; i < t; i++){
f[i] = (f[i - 1] * i) % MOD;
c[i] = c[i][i] = 1;
for (int j = 1; j < i; j++){
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
if (c[i][j] >= MOD){
c[i][j] -= MOD;
}
}
}
ll ans = 0;
for (int i = 0; (i << 1) <= N; i++){
for (int j = 0; (j << 1) <= M; j++){
int have1 = N - 2 * i;
int have2 = M - 2 * j;
ll res = dp1[n][i] * dp2[m][j];
res %= MOD;
res *= c[have1][j];
res %= MOD;
res *= c[have2][i];
res %= MOD;
res *= f[i];
res %= MOD;
res *= f[j];
res %= MOD;
ans += res;
}
}
ans %= MOD;
cout << ans << endl;
}

G. Balanced Distribution
Solution by KAN
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 200005;
const int maxk = 19;
const int inf = 1e9;

ll a[2 * maxn];
ll psum[2 * maxn];
pair2<int> go[maxk][2 * maxn];
map<ll, int> lst[maxn];
int id[2 * maxn];
int n, k;
ll need;

void perform(int l)
{
int fn = min(l + k, n);
assert(psum[fn] >= 0);
ll wassum = psum[fn];
vector<ll> exchange = vector<ll>(k, need);
int start = min(n - k, l);
for (int i = start; i < l; i++) exchange[i - start] = need + a[i];
exchange[l - start] += -psum[l];
exchange.back() += psum[fn];
for (int i = l; i < fn; i++) a[i] = 0;
a[l] += -psum[l];
a[fn - 1] += psum[fn];
for (int i = start; i < start + k; i++) psum[i + 1] = psum[i] + a[i];
assert(wassum == psum[fn]);
}

void restore(int l)
{
if (l >= n) return;
if (a[l] == 0 && psum[l] == 0)
{
restore(l + 1);
return;
}
int fn = min(l + k, n);
if (psum[fn] >= 0)
{
perform(l);
restore(l + k - (psum[fn] > 0));
return;
} else
{
restore(l + k - 1);
assert(psum[fn] == 0);
perform(l);
}
}

int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
need = accumulate(a, a + n, 0LL);
assert(need % n == 0);
need /= n;
for (int i = 0; i < n; i++) a[i] -= need;
for (int i = 0; i < n; i++) a[i + n] = a[i];
partial_sum(a, a + 2 * n, psum + 1);
pair2<int> ans = {inf, -1};
for (int j = 0; j < maxk; j++) go[j][2 * n] = {2 * n, 0};
for (int i = 2 * n - 1; i >= 0; i--)
{
int curid = id[i + 1];
if (lst[curid].count(psum[i]))
{
int to = lst[curid][psum[i]];
go[i] = {to, (to - i - 1) / (k - 1)};
} else
{
int to = 2 * n;
go[i] = {to, (to - i + k - 2) / (k - 1)};
}
for (int j = 1; j < maxk; j++) go[j][i] = {go[j - 1][go[j - 1][i].fi].fi, go[j - 1][i].se + go[j - 1][go[j - 1][i].fi].se};

if (i < n)
{
int to = n + i;
int cur = i;
int curans = 0;
for (int j = maxk - 1; j >= 0; j--) if (go[j][cur].fi <= to)
{
curans += go[j][cur].se;
cur = go[j][cur].fi;
}
if (cur < to) curans += (to - cur - 1 + k - 2) / (k - 1);
ans = min(ans, {curans, i});
}

id[i] = (2 * n - i) % (k - 1);
lst[id[i]][psum[i]] = i;
}

rotate(a, a + ans.se, a + n);
partial_sum(a, a + n, psum + 1);
restore(0);

{
printf("%d", (t.fi + ans.se) % n);
for (auto tt : t.se) printf(" %lld", tt);
printf("\n");
}
return 0;
}

H. Balanced Reversals
Solution by KAN
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 4005;

vector<int> ss, tt;
char s[maxn], t[maxn];
int n;
int cnt;

vector<int> prepare(char *s)
{
vector<int> ans;
for (int i = 0; i < 2 * n; i += 2) ans.pb((s[i] - '0') * 2 + (s[i + 1] - '0'));
return ans;
}

{
if (x <= 0) return;
}

void doreverse(vector<int> &v, int l)
{
reverse(v.begin(), v.begin() + l);
for (int j = 0; j < l; j++) if (v[j] >= 1 && v[j] <= 2)
{
v[j] = 3 - v[j];
}
}

int main()
{
int NT;
scanf("%d", &NT);
for (int T = 0; T < NT; T++)
{
scanf("%s%s", s, t);
n = strlen(s) / 2;
ss = prepare(s);
tt = prepare(t);
for (auto &t : tt) if (t == 1 || t == 2) t = 3 - t;
cnt = cnt = cnt = cnt = 0;
for (auto t : ss) cnt[t]++;
for (auto t : tt) cnt[t]--;
if (cnt != 0 || cnt != 0)
{
printf("-1\n");
continue;
}
bool found = cnt == 0;
int before = -1;
int after = -1;
for (int i = 1; i <= n && !found; i++)
{
cnt[ss[i - 1]]--;
cnt[3 - ss[i - 1]]++;
if (cnt == 0)
{
before = 2 * i;
doreverse(ss, i);
found = true;
}
}
if (!found)
{
for (int i = 1; i <= n; i++)
{
cnt[ss[i - 1]]++;
cnt[3 - ss[i - 1]]--;
}
}
for (int i = 1; i <= n && !found; i++)
{
cnt[tt[i - 1]]++;
cnt[3 - tt[i - 1]]--;
if (cnt == 0)
{
after = 2 * i;
doreverse(tt, i);
found = true;
}
}
assert(found);

for (int i = n - 1; i >= 0; i--)
{
int wh = -1;
for (int j = n - 1 - i; j < n; j++) if (ss[j] == tt[i]) wh = j;
doreverse(ss, wh);
doreverse(ss, wh + 1);
}

for (auto t : answer) reverse(s, s + t);
assert(strcmp(s, t) == 0);

for (auto t : answer) printf("%d ", t);
printf("\n");
}
return 0;
} Tutorial of Codeforces Global Round 5 Comments (167)
 » 15 months ago, # | ← Rev. 3 →   tourist Just curious to know, What is the Checker code logic for C?
•  » » If you mean arsijo's code for C1, it picks point $j$ as the closest point to $i$ using Manhattan metric.
•  » » » cool. in future we may see problem A using FFT.
•  » » » » Manhattan distance just means $|\Delta x| + |\Delta y|$.
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   manish_joshi i see :) hehehe
•  » » » tourist No. I mean. There are multiple solutions possible for C. So How are you testing whether the solution is correct or wrong?
•  » » » » I guess it's KD-Tree or bitset. :D
•  » » » » » I feel coding is very hard.
•  » » » » Ah, you mean checker. It can probably be implemented in $O(n \log^3 n)$ and even $O(n \log^2 n)$, but I did a straighforward $O(n^2)$, a bit optimized to make it work in about 2 seconds.
•  » » » » » tourist can you please explain the Solve function you used on your solution to c2?
•  » » » » » » Solve(ids, k) stands for "please match points with indices in ids, given that their coordinates in the first k dimensions are exactly the same, and return the id of the only unmatched point, or -1 if ids was of even length".
•  » » » » » » » Thanks!
•  » » » » » » » » editorials code was hard for me to understand . but this codeis very easy to understand according to editorial
•  » » » » » » » » » 15 months ago, # ^ | ← Rev. 2 →   better solution
•  » » » » » » » » » 15 months ago, # ^ | ← Rev. 3 →   scorpionn code referred by you is easy to understand but that has dimension limitations whereas editorials code can be expanded to any dimensions.
•  » » » » » » How do you solve such difficult problems tourist?
•  » » » » » » » plz work hard my friend
•  » » » » » » » It takes time to be better at programming. For instance, tourist is practising for last 10 years and he has solved around 1500 problems on codeforces, now take example of yours, how many you solved compared to 1500, when you solve 1500 then come here and ask. I think you got my point.
•  » » » » » » » » where do I see the number of problems solved by me ? Pleas help.
•  » » » » » » » » » problemset > standings
•  » » » » » » » » » thanks a lot @helth
•  » » » » » » » » »
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   please ignore
 » 15 months ago, # | ← Rev. 2 →   Test Cases are still not visible.UPD: It is visible now.
 » 15 months ago, # | ← Rev. 2 →   Here's my solution for E with proof:Perfectly balanced tree must have the condition that every level, except possibly the last, must be completely filled.What's the condition for striped BSTs? Let's find the condition for each child to match condition of its parent. So, if it's a left child, it should have key parity different than the parent and if it's a right child, it should have key parity different than the parent. Now, observe that for a left child $u$, $\text{key of parent} = u + \text{size of right subtree of } u + 1$This tells us that every node which is a left child of its parent must have even number of nodes in its right subtree. Similary for every right child $u$, $\text{key of parent} + \text{size of left subtree of } u + 1 = u$This tells us that every node which is a right child of its parent must have odd number of children in its left subtree. With these two observations, we can find number of possible subtrees of height $h$ like this,For height $1$, there is only one tree, one node with no children. For height $2$, there is only one tree, one node with one child on its left and no child on its right.For each height $h$, let's store all the possible trees as a pair $(a,b)$ where $a$ is the number of nodes in the left subtree of the root and $b$ is the number of children in the right subtree of the root. Now, we observe the following simple pattern:For height $1$ possible trees: $(0,0)$, possible sizes: $1$For height $2$: $(1,0)$, possible sizes: $2$For height $3$: $(1, 2)$, $(2,2)$, possible sizes: $4$, $5$For height $4$: $(4, 4)$, $(5,4)$, possible sizes: $9$, $10$For height $5$: $(9,10)$, $(10,10)$, possible sizes: $20$, $21$Can you spot the pattern and prove it? For every height $\geq 3$, there are exactly two trees possible.Proof: If for height $i$ we have possible trees $(a,x)$ and $(b,x)$ where $x$ is even, $a$ is even and $b$ is odd, then for height $i+1$, we can have the right child only as $(b,x)$ as only then then number of nodes in its left subtree will be even. But the left child can have any of the two values as both satisfy the condition of right subtree having even size. Thus, the new trees are $(a+x+1,b+x+1)$ and $(b+x+1,b+x+1)$, which can then be replaced with new $A$, $B$ and $X$ having $A = b + x + 1$, $B = a + x + 1$ and $X = b + x + 1$. Thus, we can say that the pattern holds by induction.Base case has $i = 3$, which is satisfied as $a = 2$, $b=1$ and $x=2$.So, find all possible trees till height $\log(\text{max value of n})$ and output $1$ if $n$ is one of those values and output $0$ if it isn't.AC Code: 62737057
•  » » IMO the easiest way to solve this is to come up with the brute force DP: $dp(n, p) = \sum_{root, parity(root)=p} dp(root - 1, 1 - parity(root)) \cdot dp(n - root, 0)$But notice that the sizes of the left and right subtrees can only be floor and ceil (n-1)/2 to be perfectly balanced, so the summation really only has one or zero terms.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   Consider a tree with 11 nodes:  1 / \ 2 3 / \ / \ 4 5 6 7 / \ / \ 8 9 10 11 This is perfectly balanced. It has 7 in the left part and 3 in the right. Am I missing something?
•  » » » » It's not a BST.
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   I did not intend for it to be a BST. Replace the numbers with arbitrary numbers, I just wanted to exhibit a structure of a perfectly balanced binary tree that does not satisfy the floor/ceil condition as mentioned in the parent comment. The point was that, if the parity conditions were absent, the dp does not have a single term.
•  » » » » It's not even BST and even more, it doesn't satisfy parity conditions xD.
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   So, if a BST is perfectly balanced, then its subtrees can only be floor and ceil (n-1)/2, or it must also satisfy parity condition ? Can you please explain a little bit, I can not get the concept behind though ><
•  » » » » » » According to the definition, it should have minimum sum of depths. BST with minimum sum of depths should have all leaves on the last level or the last but one level. Now we can deduce that a perfect BST of height $h$ has two perfectly balanced subtrees of height $h-1$.Then apply the parity condition to inductively find all striped perfect BST.
•  » » » » Wow, yeah I have no idea how I thought this was correct. Seems I got lucky that the trees asked about in the question actually do satisfy this
•  » » » » » LOL, is that the legendary intuition ?
•  » » “Perfectly balanced tree must have the condition that every level, except possibly the last, must be completely filled.“Can you prove this? This statement seems incorrect.
 » 15 months ago, # | ← Rev. 3 →   I’m facing a special problem that actually I want to turn off the cf code editor and I don’t know how to do that. Can anybody help me please?
 » Am I only one,who solved B with BIT in O(nlogn)?
•  » » I just solved B with ordered set. I feel really stupid now.https://codeforces.com/contest/1237/submission/62739056
•  » » what is bit can you please explain
•  » » » It's Binary Indexed Tree aka Fenwick tree.
•  » » You're not alone :)62707885
•  » » » You are not alone too :')https://codeforces.com/contest/1237/submission/62752373
•  » » » Can you briefly explain how to do that with BIT tree?
•  » » » » When a car is exitting, if the number of cars in front of it is less than the number when it's entering, that means it overtook some cars.
•  » » » » » But, there can be the case that there are same no. of cars in front of it even after exiting even though it has overtaken some cars.
•  » » » » » » Only consider cars which enter earlier than that car.
•  » » » » here's a similar problem from spoj https://www.spoj.com/problems/INVCNT/
•  » » 15 months ago, # ^ | ← Rev. 2 →   If you use lower_bound to find the minimum , it just can be slove be in O(nlogn) xd
 » Problem C is great. I just loved it.
 » In problem C2, I just wonder is Solve is a recursive function ?it is my first time to see a thing like this
•  » » It's a lambda expression.
 » The intended solution of H is very nice!Do you know who did this during the contest? It seems the submissions are still invisible.
•  » » Thanks! Unfortunately, it seems that everyone who solved the problem during the contest used some kind of randomization.Submissions must be visible now.
•  » » » Sorry to say that, but it seems you did not follow the rule "if you can't create good tests then don't use this problem". It was kind of obvious to me that some randomized solutions could be created here, but I thought this would be too naive to code it since they seemed pretty simple. As a contestant I did not think carefully how I would exactly design one and how I would ensure this doesn't pass if I were a problemsetter (I decided it's a better decision for me to fight my today's archenemy — problem C xD), but it's always really sad to see hard problem with no legit solutions accepted where many heuristics passed. At least the problem itself is nice :)
•  » » » » Hi, how can randomization be used to solve this problem? I'm just curious, as it wasn't obvious to me.
•  » » I was almost there (62731786), but couldn't quite figure out in time how to make the initial situation 'handy' (fixed after contest: 62742219). Fortunately the fifteenth place was (barely) enough for me to reach nutella :).
•  » » 15 months ago, # ^ | ← Rev. 2 →   I tried to do something similar to this during the contest but my last submission for it was missing 2 characters :(
 » 15 months ago, # | ← Rev. 2 →   In problem E, I used DP: $dp[i][par_{root}][par_{size}]$ means the polynomial where the coefficient of $x^j$ is the number of ways to build a tree such that the depth is $i$ and the parity of root value is $par_{root}$, and the parity of the size value is $par_{size}$. The answer we want is the sum of the $n$-th term in $dp[d][0/1][n\text{ mod }2]$.Then we have $dp[i][r][s] = multpoly(dp[i][\neg r][\neg r], dp[i][s \oplus r])$. Then I used NTT to do the multiplication and solved it barely fitting in the TL.Now I realize the base cases are all polynomials with only 0/1 term! Which means we can just store an number for each polynomial, and do the multiplication just by adding those numbers! This will run in $O(\log n)$, and this offers an different way to prove the model solution of this problem.
 » Another solution of B could be like this: Let A = ingoing car array and B = outgoing car array. Consider indices i and j running over A and B respectively. If Ai == Bj, the current car is in right order. So we insert Ai to a hash_set and we increment i and j such that Ai and Bj aren't in the hash_set. If Ai != Bj, Bj should be fined. We increase fined_car_counter by one and insert Bj to the hash_set. Then we increase j such that Bj is again not in the hash_set. The loop stops if either of i and j hits the end. Works in O(n) time.
•  » » if both the arrays are equal will the solution work??
•  » » » Yes, that'd mean no one overtook. You never hit the 2nd case. Answer is 0. This is my solution: https://codeforces.com/contest/1237/submission/62717631
 » Please make video solution for problem D,E,F
 » tourist Wow, solution to H is actually easier to understand than E and F to me (both needing induction/maths of some kind). Thank you for the great contest! Though your coordinators still have not been announced :O
 » I overkilled D. I used merge sort tree+ segment tree to solve D. It took me almost 2 hours to implement.
 » 15 months ago, # | ← Rev. 2 →   Question C1 : O(n^2) solution was not getting accepted using Python 3 even after using fast input and output.
 » For Problem D, we can find the monotonicity of the position to stop. That is, let $s_i$ be the position to stop if song $i$ is the first played song. Then for $i = 2, ..., n$, it holds $s_i \geq s_{i-1}$. Here we assume the list is cyclic.So we can use two pointers to loop over the stopping songs for each starting song. To determine if a song can be added into the current playlist, we need to keep the maximum element of the sliding window. Using STL set can achieve $O(nlogn)$ time and we can further apply monotonic queue to achieve $O(n)$ time.My submission: 62706780. I used STL set in contest, for simplicity of code.
•  » » I had the same idea as you as well! Looking at your code, one thing that you might not know is that you don't actually need a multiset of pairs to delete one instance of a number; if you do s.erase(s.find(x)) it will only erase one instance (I believe the first) of x in the multiset.My code: 62729086Note: I used %N to eliminate the need for explicitly extending the input array.Cheers!
•  » » » 15 months ago, # ^ | ← Rev. 2 →   I had realized it after the contest XDIn contest I wanted to implement monotonic queue at first, so the pair existed, but later I changed my mind to use STL set. I wrote another simpler version after contest.EDIT: If anyone interested with the simplified version, here it is: 62751793
 » In Problem A in C++ i'm getting WA for cout<
•  » » it returns -0 for few cases so u need to remove '-'
•  » » You may want to try the result of following code: cout << ceil(-0.5); 
•  » » » Thanks a lot
 » 1237B — Balanced Tunnel"Specifically, can $a_i$ must be fined if $c_i$ is bigger than $max(c_1,c_2,…,c_{i−1})$"I think, it should be "smaller" — not "bigger". And there is a typo — "can" was meant to be "car".
•  » » You're right, thanks.
 » Another solution for D: split the array into sqrt-size blocks and preprocesses whether the first track of each block can go to all tracks in the block, and preprocess the minimum and maximum of each block. Then iterate over every i from 0 to n-1, and for each i go skipping every block that you can hear all the tracks (keeping the current maximum and checking the minimum of the block).
•  » » 15 months ago, # ^ | ← Rev. 2 →   You can hear the whole block if the first track of the block can hear all the block and (current_maximum + 1) / 2 <= min_block
•  » » Is this called Square Root Decomposition?
•  » » » Yes.
 » 15 months ago, # | ← Rev. 2 →   tourist For problem C, what I did was to first use a stable sort on x of all points, then on y and then on z. Now taking central pairs from this sorted array was supposed to give me the solution but it failed on a test case. Do you think the order of coordinates in the stable sort matters? I mean should I do it like first on z, then on y and then on x?
•  » » The order of coordinates definitely doesn't matter. Consider a simpler test case: 4 0 1 0 1 1 0 2 0 0 2 1 0 Your solution removes points 2 and 3 first, but they can't be removed due to point 4.
•  » » » Now I see. Got your point. Thanks.
 » 15 months ago, # | ← Rev. 2 →   The cycle formation part in D is not clear.Isn't it enough to repeat the sequence 2 times ? Please help !
 » 15 months ago, # | ← Rev. 2 →   Somewhat funny, slightly different solution for H.Probably it's more tempting to try to match the last two characters of $a$ and the last two characters of $b$. By doing operations like abcdefxyghij -> yxfedcbaghij -> jihgabcdefxy on either $a$ or $b$, we can usually achieve this. The only undesirable situation is when $a$ ends with $01$, $b$ ends with $10$, $a$ contains no $10$, and $b$ contains no $01$ (or vice versa).However, this is rather a handy situation in the intended solution! So, if we switch to the intended solution at this point, everyone will be happy. We can even save one more operation.
 » please can someone provide a simple solution for C2 ,..... I got the approach for it as in editorial but coudn't understand the implementation... please
 » Spent 2 hours finding tricky cases for A and it happened to be -0 problem because of double. Don't wanna live anymore)
 » tourist participated in 153 cf rounds and came first in 77 (=ceil(153/2)).perfectly balanced
•  » » It doesn't sum to zero????? Disappointing
•  » » 15 months ago, # ^ | ← Rev. 2 →   did you count one by one in his rank list? BTW nice observation.
 » 15 months ago, # | ← Rev. 3 →   Bonus for D: Use a queue/ Double-ended queue:For i = 1 to 2*n (you can cycle as many as you want, but I think 2 times is enough): While a[Q.back()] < a[i]: Q.pop_back() and Unify (Q.back(), i). Here means if you start playing from track Q.back(), you can play track i which has greater coolness, so the result of Q.back() should be the same with the result of i. Push track i to the back of the Deque Because tracks in the Deque are sorted non-increasingly, so if you push track i to the back of the Deque then you should pop out track from the front of the queue. Suppose j = Q.front() then j is popped out from the front if and only if a[j] > 2*a[i]. Which means if you play from track Q.front() then you must stop at track i. After the loop, any tracks left in the Queue is UNSTOPPABLE. By using Disjoint Set Union, every track in the same connected component has the same result. To maximize, we take the result of the coolest track in that connected component.Finally, calculate the answer. The overall complexity is O(n) (Or close enough, since I use DSU)Submission 62720568
•  » » yes you should cycle atmost 2 times in the worst case in the first cycle you will go through maximum number in the array and in second cycle you should find its answer if you can't find answer then answer is infinity.
•  » » Why so many downvotes hmm?
•  » » This solution looks awesome,can you please explain the logic eloborately?
 » How to prove this code?
•  » » This $O(1)$ code is amazing...
•  » » WHAT THE CODE !!!
 » Is there anyone who wrote FFT in E?
•  » » 15 months ago, # ^ | ← Rev. 3 →   let $f(i,j,op)$ be the quantity of $2^i-1+j$-nodes perfectly balanced striped binary search trees, the parity of the key of the root is $op$. $0\le j<2^i$.a perfectly balanced striped binary search tree rooted at $u$ should satisfy:(1) the subtree size of $lc[u]$ and the key of $lc[u]$ have the same parities.(2) in the subtree of $rc[u]$, rank of $rc[u]$ is even.Consider array $a$ and $b$:if $j$ is odd, $a_j=0$, $b_j=f(i-1,j,0)$ ;if $j$ is even, $a_j=f(i-1,j,1)$, $b_j=0$ .Then we can get:$f(i,j,0)=\sum_{x+y=j}a_xf(i-1,y,0)$$f(i,j,1)=\sum_{x+y=j}b_xf(i-1,y,0)$Noticed $0\le j<2^i$, use NTT, it can be solved in $O(i\times 2^i)$.if we let $k$ be the maxium value that $2^k-1\le n$, then the answer is $f(k,n-2^k+1,0)+f(k,n-2^k+1,1)$.the complexity is $\sum_{i\le\log n}i\times2^i=O(n\log n)$.
 » Any simple implementation for C2 with same logic?
•  » » I tried 3D solution with 3 dimensional ArrayList. Here's my JAVA code: 62776171
•  » » » can you explain your code ,how it is working?
 » I think a better way of solving B would be using queue,as it follows First-in First-out and then all we need to do is to check if the element of b is equal to front element of queue and mark it as visited and pop.If it is not equal then counter++.Also while front element of queue is marked visited,pop it.Here is my solution.
•  » » I also solved B using queue. Also used HashSet for tracking already gone cars. Kept popping queue while it is already in the gone set. Just whenever next going car isn't in hashset and isn't equal to queue front then increased the answer. Here is my JAVA code : 62716214
•  » » 15 months ago, # ^ | ← Rev. 2 →   I did B using Binary search https://codeforces.com/contest/1237/submission/62707665
•  » » » Just overkill !!
•  » » Why is it "better"?
•  » » » As there is no need to create an an array c and also this is exactly what the problem says...No extra thinking or logic required.
•  » » » » So you create the "visited" array instead.This is subjective — the validity of your approach is not so obvious that it does not require justification.
•  » » » » » You can consider queue as a tunnel,push as an entry,pop as an exit and the if-else part(in my code) as a guard who takes fine.
•  » » » » » » Can't consider queue as the tunnel — cars exit not in the same order as they enter.
•  » » » » » » » Typo- Pop as Expected exit.
•  » » » » » » » » 15 months ago, # ^ | ← Rev. 8 →   What is "expected exit"?Your queue is not really a queue, because you effectively delete (mark for deletion) items in the middle. You pop items marked for deletion when they reach the front of the queue.Implementation using std::list is shorter and cleaner (and faster):https://codeforces.com/contest/1237/submission/62834786And it is all starting to make sense now.Start with sequence $a$ of cars entering tunnel. Then the first car exiting is fined iff it is not the first in $a$. Remove this car from $a$ and repeat the same with the next car exiting.
 » 15 months ago, # | ← Rev. 3 →   I solved D in $O(n^{1.5})$. Precompute min coolness and max coolness of $\sqrt{n}$ intervals. Start from the largest coolness music to the smallest coolness music. Find some specific target values in each iteration. Check my code for details. https://codeforces.com/contest/1237/submission/62726962
 » 15 months ago, # | ← Rev. 6 →   Here is an alternate solution to E that does not require the solver to initially conjecture that the answer is either $0$ or $1$:Suppose we fix the parity of the root (it will be the parity of $n$). A perfectly balanced tree is a complete binary tree of depth $d - 1 +$ some leaves at depth $d$. So we can find the parities of all the nodes in the complete binary tree (i.e. for all nodes with depth $\leq d - 1$). Write them down in a sequence, like, for $n = 10$, the following will be the sequence: $0, 1, 1, 0, 1, 0, 0$ (we can compute this sequence using a recursion). Now, since the final inorder traversal will have parities like $1, 0, 1, 0, 1, 0 \ldots$ (because the inorder will be $1, 2, 3, 4 \ldots$), we must insert a $0$ whenever there are two consecutive $1$s and a $1$ whenever there are two consecutive $0$s. Also note that if $j$ corresponds to a leaf, $A_j \neq A_{j + 1}$ (proof follows because the next node in the inorder is just the first right turn while moving up from the leaf, and a right turn means a different parity), and if $j$ is a non-leaf, then $j - 1$ corresponds to a leaf (because of complete binary tree-ness) and $A_{j - 1} \neq A_j$ (similar proof). So we have: If $A_1 = 0$, insert a leaf before (in the left) because the first node has to be 1. If $A_j = A_{j - 1}$, insert a leaf here (in the left). Otherwise, don't (can't) insert a leaf here. All this is compulsory for a perfectly balanced striped tree. So the answer exists only if the number of leaves to be inserted is $n - 2^{d - 1} + 1$ (i.e., the number of leaves you have).P.S.: Note that proving $A_j \neq A_{j + 1}$ for leaves etc. was not compulsory. We could just not think about them during the contest, and set answer = 0 if $A_j = A_{j + 1}$, because if it occurs, you cannot insert anything to fix it (because, same parity on the right). Also if for non-leaves $A_j = A_{j - 1}$, then that case would be handled by the leaf at position $j - 1$ (who would give an answer of 0 as just mentioned). But still, the answer will remain $0$ or $1$, without deciphering the structure of the sequence. That part could be left to be handled by the code itself.P.P.S: If I'm not wrong, this also proves that all leaves in the last level should be left children.Submission: 62757866
 » For problem C2 I implemented the 3D solution. Here is the java code : 62760448 I sorted the points using Comparator.
 » Can there be a greedy solution for C2 involving sorting using Manhatten or Eucledian Distance and removing in pairs ?
 » In tutorial of F" It follows that $R=f(h,dv)∗\binom{h−2dv}{dh}$ "Shouldn't we only choose from rows marked 0 instead of all the h rows? I think it should be" $R=f(h,dv)∗\binom{h- (no of filled rows) − 2dv}{dh}$"
 » 15 months ago, # | ← Rev. 2 →   Here is an alternate solution for D: lets say we want to find the answer for track x : find the first track after x that has a coolness greater than x (lets call it y) also find the first track after x that has a coolness less than x/2 (lets call it z). if z lies between x and y then the answer for track x will be the number of tracks between x and z. otherwise the answer for track x would be number of track between x and y plus the answer for track y (we can calculate the answers recursively).
•  » » Yeah, but how are you finding which one among z and y is closer to x and also how are you finding the position of z or y after knowing that?
 » I have a question of problem E. If n=5, the tree can be like this: 3 / \ 2 5 / \ 1 4 Also, it can be like this: 3 / \ 2 5 / / 1 4 Which tree dose not meet the conditions? I would appriciate it if you could answer my question!
 » I have a question of problem E.If n=5, the tree can be like this: 3 / \ 2 5 / \1 4Also, it can be like this: 3 / \ 2 5 / /1 4Which tree dose not meet the conditions?I would appriciate it if you could answer my question!
•  » » 15 months ago, # ^ | ← Rev. 2 →   Your 1st Tree is not BST
•  » » » OK，I see! Thanks a lot！
•  » » Your first tree is not a BST. $4$ cannot be in the left subtree of $3$.
•  » » » OK，I see! Thanks a lot！
 » 15 months ago, # | ← Rev. 2 →   I got WA on Pretest 5 in A and the checker says wrong output format Expected integer, but "-0" found. What does this mean?Casting the output to int gives AC. If the error was in output format, why did the first 4 pretests pass?Link to code
•  » » 15 months ago, # ^ | ← Rev. 2 →   https://en.cppreference.com/w/cpp/numeric/math/floorThis function doesn't return an integer. Your code passed the first 4 pretests by chance.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   Yes, the floor and ceil functions will return double datatype. But still it doesn't make sense.What does the checker output mean? I mean what is "-0" and why is it not an integer?Also, as 1.0 is printed as 1. How does printing double values instead of int make any difference in the output text file? How can the first 4 pretests pass by chance?Thanks for replying kabuszki.
•  » » » » -0 or -0.00...0 is a valid representation of a floating point number. It's very small but negative; it would have non-zero digits, but they're rounded off on the output. When you multiply it by a very large positive float, you can get a reasonably large negative float, so it has a purpose.In integers, minus zero is zero, so -0 isn't a valid representation of an integer. There's no way to obtain the output -0 by printing an integer.
 » One of the best D !
 » In problem D, how can one do binary search over a segment tree?
•  » » Could Someone Please Help?How to solve D using binary search on segment tree? Xellos
 » In problem D, what is the reason why repeat the numbers 3 times is enough?
 » In 1237F, I am facing difficulty in understanding the equation of number of ways to place exactly dh horizontal domino and dv vertical Domino. Can someone explain how we arrived at this equation: R⋅C⋅dh!⋅dv!.
•  » » 15 months ago, # ^ | ← Rev. 2 →   This took me a while to figure out too.To getting a perfectly balanced placement, we need to choose which rows contain vertical dominos and which rows contain horizontal dominos (R ways) choose which columns contain vertical dominos and which columns contain horizontal dominos (C ways) choose how to place the horizontal dominos in the selected rows and columns (dh! ways) choose how to place the vertical dominos in the selected rows and columns (dv! ways)
 » Author’s solutions are good, but I know more interesting way to make this world better — checking M3139 homework ^_^
 » tourist Wonderful round, as always, but something about it clearly require further consideration. Maybe it’s homework of group m3139...
 » Very wonderful and complicated problems. But I know some more. For example, the problem of checking M3139 homework.
 » Amazing balanced problems. I think it's time to check M3139 homework 4more balance :3
 » 15 months ago, # | ← Rev. 3 →   Thanks a lot to MikeMirzayanov for Codeforces and Polygon, and also thanks to tourist for checking M3139 homework
 » An alternative approach for problem H: (a bit not elegant, but able to solve the problem in n operations)First, check the number of 00s, 11s and 01/10s. Then, judge the situation where there're no 01/10s, which can be solved easily in n operations.Consider we can do operations on both binary strings, as doing a sequence of operations on B is equivalent to doing the reverse of the sequence on A. And think about each time we make the last 2 characters of A and B equal and do the process on the prefix of length n — 2 of A and B.Then, assume that at least one of the strings begins with 01 or 10.Then, discuss about these cases: 1) One of the strings begins and ends with 00 or 11 while the other doesn't begin or end with 00 or 11. In this case, we can modify the other string such that the end of the other string before the operation becomes the beginning of it. It begins with 01 or 10. 2) At least one of the strings ends with 00 or 11, except for case 1: In this case, there's at least one string which begins with 01 or 10 and ends with 00 or 11. Modify the other string. 3) Neither of the strings ends with 00 or 11. Consider string A neither begins with 00 nor 11. It's definitely possible to do operations on A such that its end equals to that of B. After the operation, A's end becomes A's beginning, which is 01 or 10. Note that at first we need to modify the string so that at least one of A and B doesn't begin with 00 or 11. This takes 1 operation. But we can find that when the length of A and B both becomes 2, we'll need only 1 operation at most. So the total number of operations is n. Is there any solution with a smaller number of operations? I wonder ... 
 » in B.)"Recall that car ai must be fined if there exists a car that entered the tunnel earlier and exited the tunnel later." tourist's words i think it's the opposite of what's true.a car should be fined if it enters tunnel later and exits earlier. please explain if i'm wrong
 » can anyone explain the logic of j and k in question D?
•  » » For each $i$, let $j$ be the closest position after $i$ such that $a_j > a_i$, also let $k$ be the closest position after $i$ such that $a_k < a_i/2$. There are 2 cases:When $k$ is closer than $j$, it means that for sure we know that we will play $k - i$ tracks, so $answer_i = k - i$.When $j$ is closer than $k$, it means that if we start playing at $i$, for sure we will not stop until we reach $j$ (because we would have to stop at most at position $k$, and $k$ is after $j$). Since $a_j > a_i$, the answer for position $i$ is the distance to position $j$ plus the answer for position $j$. $answer_i = j - i + answer_j$
•  » » » And how do we find the answer for j? I didn't understand how to use binary seach on segment trees. Can you explain the idea?
•  » » » » There are a couple of ways to find $j$ and $k$. I used coordinate compression (there will be at most $2n$ different values), and a segment tree that for each value kept its minimum position so far. So I went from $i=n$ to $i=1$ and for each position did 2 queries, and then updated the segment tree for the element at that position.This is a step up from the most basic usages of segment trees, so if you're not familiar with them you should try solving easier problems.
•  » » » » » Did you use coordinate compression on the entire input array or what?I didn't get your atmost 2n different values statement. Well, I know about Segment trees but unable to understand its usage in the given problem. I mean, what to store in each node of the segment trees and why and how is it helping me here. This usage of Segment trees is somewhat new to me.Your explanation will help me understand a newer application of them. So, Kindly help.
•  » » » » » » What am I compressing? Notice that for the problem, for each $i$, we are concerned with at most 2 values: $a_i$ and $\lfloor a_i/2 \rfloor$ (if $a_i$ is even, the second value is actually $\lfloor a_i/2 \rfloor - 1$, we need this for the segment tree queries later). So, at most $2n$ values will be needed for the segment tree. This is how many leaves it should have.The segment tree stores, if we go from the last to the first element, the minimum position so far of a certain value we've passed.Here is my submission with comments: https://codeforces.com/contest/1237/submission/63557702
•  » » » » » » » 15 months ago, # ^ | ← Rev. 2 →   // take the array a. now take a copy of it and put it at the end // of the first array. you have 2n elements. // initialize the segment tree with the positions // of the elements in the second half for (int i = n; i >= 1; --i) { int x = newvalmp[a[i]]; update(1, 0, m-1, x, i+n); } You built your tree with inf and now updating the compressed value of the a[i] with i+n.What's the logic in updating with i+n?
•  » » » » » » » » You're right, I guess there's no need to build it with inf and then do those updates. When I was trying to solve the problem, I tried to be as fast as possible, so redundancies like that happen.
 » 15 months ago, # | ← Rev. 3 →   can anybody tell me whats wrong with below code for A? #include using namespace std; int main(){ int n; cin>>n; int flag=0; for(int i=0;i>a; if(a%2==0) cout<
 » can anybody explain ques B approach please
•  » » 15 months ago, # ^ | ← Rev. 3 →   I can tell you my solution (which I personally find more intuitive). I push all cars from the first array in order into a queue. I also have a "visited" array which keeps track of all cars that we have already processed. This gives us that for any 2 cars a and b such that a is in front of b in the queue, a entered the tunnel before b.Now, we process, the second array in order. For every iteration of i we do the following: While the car at the front of the queue has already been processed (check this using visited array), pop it from the front of the queue. If car at index i (of the second array) does not equal the front of the queue, this means car i should be fined. We know this because the q.front() is guaranteed to have entered the tunnel before car i, and i is leaving the tunnel before q.front(). Thus, we add one to a running count, and mark car i as visited. if the car at index i does equal the front of the queue, pop the element at the front of the queue. Output the counter at the end.My code: 62699992
•  » » » 15 months ago, # ^ | ← Rev. 2 →   Another same idea lolMine: 62694197
•  » » » » o_o lol
 » I was 100% sure that in D we need to use the fact that end of path is x/2. But this solution is general, the problem could be given as x-c, and path stops when you reach x-c. But I am glad I still got solution even though I was skeptical that I didnt use the fact x/2 at any point except that x/2 < x.
 » 15 months ago, # | ← Rev. 2 →   Hi,please down vote me
 » Can you make this solution to E any shorter? Maybe by using some other programming language?
•  » » Hi, Can you explain your solution?
•  » » » So by brute forcing/looking at the cases where the answer is 1, and their bit representation, you can notice that they all look like 10101010.. and a few random bits at the end. Now when you multiply that by 3, it will look like 111111... and a few random bits at the end.So you need to check if 3*n is of form 2^k-1,2^k-2,2^k-3,2^k-4 or 2^k-5, where k is some number.Now to check this we can do if n^(n+5)>n.
 » 15 months ago, # | ← Rev. 3 →   tourist In editorial of problem C2 why is 'n' not necessarily even when in the question it clearly states that 'n' is even?
•  » » The 'n' for the 3 dimensions is even. but for 2 or 1 it's not necessary to be even (at last in every dimension is only one point alone and we know that the number(not coordinates) of these alone points is even so we match them two by two and then we're ok
 » tourist in your solution of prob D, by taking st_min and st_max, we are looking back i.e. already processed tracks(left direction of current track). But we to check right side of current track, isn't it?
 » tourist In problem D, can u plz elaborate little more why 3times repetition necessary to pretend cyclic list linear, to me it seems that 2times repetition is sufficient
»

# ЛУЧШИЙ

 » O(n * log^2(n)) solution with Binary Search and Segment Tree is giving TLE. Can anyone help ? Submission: 83481373
•  » » It shouldn't give TLE, right. The TL are too tight. BTW, you can get it accepted by using G++17 (64 bit)
 » 2 months ago, # | ← Rev. 5 →   what wrong in this code for question Bsubmission: 97906554