Codeforces Round 986 (Div. 2) Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Thank you everyone for participating in the round! We hope you enjoyed the problems :)

2028A - Alice's Adventures in ''Chess''

Hint

Solution

Code

def solve():
    [n, a, b] = list(map(int, input().split()))
    s = str(input())
    x, y = 0, 0
    for __ in range(100):
        for c in s:
            if c == 'N':
                y += 1
            elif c == 'E':
                x += 1
            elif c == 'S':
                y -= 1
            else:
                x -= 1
            if x == a and y == b:
                print("YES")
                return
    print("NO")
 
t = int(input())
 
for _ in range(t):
    solve()

2028B - Alice's Adventures in Permuting

Hint

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define pb push_back
#define endl '\n'
 
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
 
mt19937 rng(time(0));
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	while (t--) {
		ll n, b, c; cin >> n >> b >> c;
		if (b == 0) {
			if (c >= n) {
				cout << n << "\n";
			} else if (c >= n - 2) {
				cout << n - 1 << "\n";
			} else {
				cout << -1 << "\n";
			}
		} else {
		    if (c >= n) cout << n << "\n";
			else cout << n - max(0ll, 1 + (n - c - 1) / b) << "\n";
		}
	}
}

2028C - Alice's Adventures in Cutting Cake

Hint 1

Hint 2

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define pb push_back
#define endl '\n'
 
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
 
mt19937 rng(time(0));
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	while (t--) {
		int n, m; cin >> n >> m;
		ll v; cin >> v;
		vector<ll> a(n);
		rep(i,0,n) cin >> a[i];
 
		vector<ll> sums(n + 1);
		rep(i,0,n) sums[i + 1] = sums[i] + a[i];
 
		auto query = [&](int i, int j) { // [i, j)
			return sums[j] - sums[i];
		};
 
		auto compute_pfx = [&]() -> vector<int> {
			vector<int> pfx(n + 1, 0);
			int end = 0, val = 0;
			ll sum = 0;
			for (int start = 0; start < n; start++) {
				while (end < n && sum < v) {
					sum += a[end];
					++end;
					pfx[end] = max(pfx[end], pfx[end - 1]);
				}
				if (sum >= v) {
					pfx[end] = 1 + pfx[start];
				}
				sum -= a[start];
			}
			rep(i,1,n+1) {
				pfx[i] = max(pfx[i], pfx[i - 1]);
			}
			return pfx;
		};
 
		auto pfx = compute_pfx();
		reverse(all(a));
		auto sfx = compute_pfx();
		reverse(all(a));
		reverse(all(sfx));
 
		if (pfx[n] < m) {
			cout << "-1\n";
			continue;
		}
 
		int end = 0;
		ll ans = 0;
		for (int start = 0; start < n; start++) {
			while (end < n && pfx[start] + sfx[end + 1] >= m) ++end;
			if (pfx[start] + sfx[end] >= m)
				ans = max(ans, query(start, end));
		}
		cout << ans << "\n";
	}
}

2028D - Alice's Adventures in Cards

Hint

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define pb push_back
#define endl '\n'
 
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
 
mt19937 rng(time(0));
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	std::string s = "qkj";
	while (t--) {
		int n; cin >> n;
		vector p(3, vector<int>(n + 1));
		rep(i,0,3) rep(j,1,n + 1) cin >> p[i][j];
		vector<pair<char, int>> sol(n + 1, {'\0', -1});
		array<int, 3> mins = {n, n, n}; // minimizing index
		for (int i = n - 1; i >= 1; i--) {
			int win = -1;
			rep(j,0,3) if (p[j][i] > p[j][mins[j]]) win = j;
			if (win == -1) continue;
			sol[i] = {s[win], mins[win]};
			rep(j,0,3) if (p[j][i] < p[j][mins[j]]) mins[j] = i;
		}
		if (sol[1].second == -1) {
			cout << "NO\n";
			continue;
		}
		cout << "YES\n";
		vector<pair<char, int>> ans = {sol[1]};
		while (ans.back().second >= 0) {
			ans.push_back(sol[ans.back().second]);
		}
		ans.pop_back();
		cout << sz(ans) << "\n";
		for (auto && [c, i] : ans) {
			cout << c << " " << i << "\n";
		}
	}
}

Bonus

2028E - Alice's Adventures in the Rabbit Hole

Hint 1

Hint 2

Hint 3

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define pb push_back
#define endl '\n'
 
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
 
// mt19937 rng(time(0));
 
ll euclid(ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, a;
	ll d = euclid(b, a % b, y, x);
	return y -= a/b * x, d;
}
 
const ll mod = 998244353;
struct mint {
	ll x;
	mint(ll xx) : x(xx) {}
	mint operator+(mint b) { return mint((x + b.x) % mod); }
	mint operator-(mint b) { return mint((x - b.x + mod) % mod); }
	mint operator*(mint b) { return mint((x * b.x) % mod); }
	mint operator/(mint b) { return *this * invert(b); }
	mint invert(mint a) {
		ll x, y, g = euclid(a.x, mod, x, y);
		assert(g == 1); return mint((x + mod) % mod);
	}
	mint operator^(ll e) {
		if (!e) return mint(1);
		mint r = *this ^ (e / 2); r = r * r;
		return e&1 ? *this * r : r;
	}
};
 
void solve() {
	int n; cin >> n;
	vector<vector<int>> t(n);
	rep(i,0,n-1) {
		int x, y; cin >> x >> y; --x, --y;
		t[x].push_back(y);
		t[y].push_back(x);
	}
 
	vector<int> d(n, n + 1);
	function<int(int, int)> depths = [&](int curr, int par) {
		for (auto v : t[curr]) {
			if (v == par) continue;
			d[curr] = min(d[curr], 1 + depths(v, curr));
		}
		if (d[curr] > n) d[curr] = 0;
		return d[curr];
	};
 
	depths(0, -1);
 
	vector<mint> ans(n, 0);
	function<void(int, int, mint)> dfs = [&](int curr, int par, mint val) {
		ans[curr] = val;
		for (auto v : t[curr]) {
			if (v == par) continue;
			dfs(v, curr, val * d[v] / (d[v] + 1));
		}
	};
 
	dfs(0, -1, mint(1));
	for (auto x : ans) {
		cout << x.x << " ";
	}
	cout << "\n";
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	while (t--) solve();
}

2028F - Alice's Adventures in Addition

Hint 1

Hint 2

Hint 3

Hint 4

Solution

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define pb push_back
#define endl '\n'

const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;

mt19937 rng(time(0));

const int LOG = 14;
const int MAX = 10000 + 1;

int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    int t; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        bitset<MAX> prev(1), pfx(1), zero(0);
        list<pair<int, bitset<MAX>>> q;
        rep(i,0,n) {
            int x; cin >> x;
            bitset<MAX> curr = zero;

            if (x == 0) {
                curr |= pfx;
                zero = curr;
                q.push_front({0, prev});
            } else if (x == 1) {
                curr |= prev | (prev << 1);
            } else {
                int prod = 1;
                q.push_front({x, prev});
                for (auto const& val : q) {
                    if (prod == 0 || prod * val.first > m) break;
                    prod *= val.first;
                    curr |= val.second << prod;
                }
            }
            pfx |= curr;
            prev = curr;
            if (sz(q) > LOG) q.pop_back();
        }

        cout << (prev[m] ? "YES" : "NO") << "\n";
    }
}

while (T-- > 0) { int64_t n, b, c; cin >> n >> b >> c; int64_t ans = -1; if (b == 0) { if (n == 1) { ans = (c == 0 ? 0 : 1); } else if (n == 2) { ans = min(int64_t{2}, max(int64_t{1}, c)); } else if (n >= 3) { if (c == 0) ans = -1; else { if (c >= n) { ans = n; } else { ans = n - 1; } } } } else { if (c >= n) { ans = n; } else if (c == n - 1) { ans = n - 1; } else { ans = n - (n - c + b - 1) / b; } } println("{}", ans); }

else { if (b==0) { if (c<=n-1) cout<<n-1<<nl; else cout<<n<<nl; } else { float k = (float)(n-1-c)/(float)b; if (k < 0) cout<<n<<nl; else cout<<(n-1-(int)k)<<nl; } }

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--){ ll n, b, c; cin >> n >> b >> c; if(b == 0){ if(c == 0){ if(n == 1){ cout << 0 << endl; } else if(n == 2){ cout << 1 << endl; } else{ cout << -1 << endl; } } else{ if(n == 1){ cout << 1 << endl; } else{ if(n - c > 2){ cout << -1 << endl; } else{ cout << n - 1 << endl; } } } } else{ if(n - 1 < c){ cout << n << endl; } else{ if(n - 1 == c){ cout << n - 1 << endl; } else{ ll temp = (n - 1 - c) / b; cout << n - 1 - temp << endl; } } } } }

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--){ ll n, b, c; cin >> n >> b >> c; if(b == 0){ if(c == 0){ if(n == 1){ cout << 0 << endl; } else if(n == 2){ cout << 1 << endl; } else{ cout << -1 << endl; } } else{ if(n == 1) { cout << 1 << endl; } else{ if(c > (n - 1)){ cout << n << endl; } else{ cout << (n - 1) << endl; } } } } else{ if(c > (n - 1)){ cout << n << endl; } else{ ll temp = (n - 1 - c) / b; if(temp < 0) temp = 0; else if(temp + 1 > n) temp = n; ll m = temp + 1; if(m > n) m = n; ll k = n - m; cout << k << endl; } } } }

Problem E, My Solution (In detail) Let i be the node on which alice is currently. The optimal moves will be => Alice will always try going to the parent of the current node => Other person will always pull Alice to a child node of the current node via which some leaf node is closest. Let, dp[i] be the probability of alice escaping, ch[i] be the optimal child node of i for the second person and p[i] be the parent node of i. dp[i] = (1 / 2) * dp[p[i]] + (1 / 2) * dp[ch[i]] -> (1) dp[1] = 1 (Alice can always escape) For All leafs dp[leaf] = 0 (Alice can never escape) Let, i -> ch[0] (ch[0] is nothing but ch[i] in equation 1) ch[0] -> ch[1] ch[1] -> ch[2] ch[x-1] -> ch[x] (ch[x] is a leaf) be the optimal child nodes for the other player. Now, dp[ch[0]] = dp[i] * (1/2) + dp[ch[1]] * (1/2) dp[ch[1]] = dp[ch[0]] * (1/2) + dp[ch[2]] * (1/2) -------- dp[ch[x-1]] = dp[ch[x-2]] * (1/2) + dp[ch[x]] * (1/2) dp[ch[x]] = 0 Simplify dp[ch[x-1]] , dp[ch[x-2]] , dp[ch[x-3]]. dp[ch[x-1]] = dp[ch[x-2]] * (1/2) dp[ch[x-2]] = dp[ch[x-3]] * (1/2) + dp[ch[x-1]] * (1/2) dp[ch[x-2]] = dp[ch[x-3]] * (1/2) + dp[ch[x-2]] * (1/4) dp[ch[x-2]] * (1 - (1/4)) = dp[ch[x-3]] * (1/2) dp[ch[x-2]] = dp[ch[x-3]] * (2/3) dp[ch[x-3]] = dp[ch[x-4]] * (1/2) + dp[ch[x-2]] * (1/2) dp[ch[x-3]] = dp[ch[x-4]] * (1/2) + dp[ch[x-3]] * (1/3) dp[ch[x-3]] * (1 - (1/3)) = dp[ch[x-4]] * (1/2) dp[ch[x-3]] = dp[ch[x-4]] * (3/4) By mathematical Induction we can say dp[ch[0]] = dp[i] * (x / (x + 1)) -> (2) Now, Let d[i] be the minimum depth from node i to any leaf in the subtree of i Then, dp[ch[i]] = ((d[i] - 1) / d[i]) * dp[i] (From equation 2) Substitute this in equation (1) dp[i] = dp[p[i]] * (1 / 2) + dp[i] * ((d[i] - 1) / d[i]) * (1 / 2) dp[i] * (2 - ((d[i] - 1) / d[i])) = dp[p[i]] dp[i] * ((d[i] + 1) / d[i]) = dp[p[i]] dp[i] = dp[p[i]] * (d[i] / (d[i] + 1)) So, dp[1] = 1 dp[leaf] = 0 (all leafs) dp[i] = dp[p[i]] * (d[i] / (d[i] + 1)) (For all other nodes appart from 1 and leafs) Precompute d[i] for every node and compute dp[i] with above transitions :) .

// this is code #include<bits/stdc++.h> using namespace std; void solve(){ long long n,b,c; cin>>n>>b>>c; long long l = 0; long long r = n-1; long long m = (l+r)/2; // if(b==0 && c== 0){ cout<<n-1<<endl; return;} if( b== 1 && c==0){ cout<<0<<endl; return;} if(b==0 && c < n-2){ cout<<-1<<endl; return;} if(b==0 && c < n){ cout<<n-1<<endl; return;} if(b==0 && c >= n){ cout<<n<<endl; return;} long long ans = -1; while(l <= r){ // long long val = ; if( (double)b < ((double)n-c)/m){ ans = m; l = m+1; } else{ r = m-1; } m = (l+r)/2; } cout<<n-ans-1<<endl; return; } int main(){ int t; cin>>t; while(t--){ solve(); } return 0; }

#include <bits/stdc++.h> using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int tt = 1; cin >> tt; while (tt--) { int n, m, v; cin >> n >> m >> v; vector<int> a(n); long long S = 0, SS = 0; for (int i = 0; i < n; i++) { cin >> a[i]; S += a[i]; } int L = 0, R = 0; int i = 0, j = n - 1; int ip = 0, jp = n - 1; while (i <= j && m > 0) { if (i == j) { if (a[i] >= v) { SS += a[i]; m--; } break; } while (i <= jp && L < v) { L += a[i]; i++; } while (j >= ip && R < v) { R += a[j]; j--; } if (L >= v && R >= v) { if (L < R) { SS += L; L = 0, R = 0; j = jp; ip = i; } else { SS += R; L = 0, R = 0; i = ip; jp = j; } } else if (L >= v) { SS += L; j = jp; ip = i; } else if (R >= v) { SS += R; i = ip; jp = j; } else { m = 1; break; } L = 0, R = 0; m--; } cout << (m != 0 ? -1 : S - SS) << '\n'; } return 0; }

Comments (154)

Write comment?

SkyWave2024

6 weeks ago, # |

← Rev. 2 →

-31

I dont understand what the meaning of 32MB in F. I don't like problems with too many meaningless details (I believe the main idea of F is not the memory optimisation, or maybe this retarded problem does not have main idea at all?)

→ Reply

papa-ka-para

6 weeks ago, # ^ |

← Rev. 3 →

same goes for problem B. why put 10^18, simply 10 ^ 9 was sufficient. But no, the author has to make us deal with overflows.

applepi216

+38

I'd call F a "DP Optimization" problem. There's a fairly short $$$O(n^2 m)$$$ solution, and then the question becomes how to optimize it. Memory optimization is a real thing that people care about a lot, and here I think it's pretty cool how it naturally falls out of the analysis.

amirhanordobaev

Thank you for such a cool Problem F, I hope in the future I will learn to solve this)

-38

I'm trying to understand what you are talking about. I think the only main idea should be, the number of $$$\times$$$ operation will not exceed $$$\log_2 m$$$, and other parts are just trivial knapsack DP (including bitset optimisation)

So why not just set $$$n,m \le 5000$$$ with 512MB ML to let the $$$\mathcal O(nm \log m)$$$ solution pass? In this case I will call this a cute problem (but still not that good).

The bitset optimisation is ok, but the memory optimisation is really bad. If one knows the $$$\mathcal O(\dfrac{nm \log m}{w})$$$ solution, he must know how to optimize the memory, in this case the tight ML just increases the difficulty of implementation, which is really annoying.

awesomeguy856

+70

that's why it's problem F

-24

A good problem F shouldn't be difficult on optimisation unrelated to the main idea

oldcumcrispy

-6

Actually, I don't think the memory optimization is an issue. It is pretty easy to see that you can only keep the last log bitsets if you realise the rest of the solution. Anyway the solution is ok, but it's pretty easy itself, I think too easy for a problem F.

StellarSpecter

-125

best contest ever,

I liked problem B so much.

Every problem should be like this in every contest.

Thanks, upvote who agrees.

Xbalanque

are you serious right now bra

RedQuality

+23

He's kidding obviously. B is the shittiest problem ever. Thats the worst nightmare of "hmm, should i use k-1 or k in this 108th case...".

noheart_inside

ya man constructive problems are the worst we can expect in a contest

But I should say that the solution for B is elegant. IMHO, the editorial doesn't clearify all the details of the solution but once you understand it, you don't feel like this problem is that tricky anymore.

djm03178

+10

The trickiness of this kind of problems is hugely determined by the strength of the examples, and this one kinda well-hided the edge cases. If the examples were even weaker, I'd say it could be at least as hard as a regular D2C.

ya i find it difficult to check all the edge cases during the contest but nice contest i hope it will increase my ability to think more next time

LANSGANBS

I got the answer to Question B of this Wrong Answer three times, but I got all four questions in ACDE AC once. This question I thought was cleverly designed to avoid certain special cases in the sample, which is something to watch out for in reality, and the ICPC tends to test a player's sensitivity to such Cases.

CodeBugs

I still think B is cool. But yeah its hard to find the logic behind it.

sososonoob

Thanks for fast editorial! orz applepi216

CatchMe_

Thanks for a very first tutorial

notarmen

I still don't understand why my ceil division didn't work like this:

ans = n - (n - c + b - 1) / b

D4nnyLee

This formula only works when c <= n.

Try this testcase: 1 3 1 5

I have specific part to handle other cases:

      if (c >= n) {
        ans = n;
      } else if (c == n - 1) {
        ans = n - 1;
      } else {
        ans = n - (n - c + b - 1) / b;
      }

How about b = 0

Here goes the whole solution

I think the formula is not the reason you got WA, b == 0 && c == 0 is not the only case that answer = -1.

AaravSin

say b is 0, now all the n values will be c, now if n!=c+2 we wont be getting a permutation. if b is non zero we will always get a solution which will be number of number greater than n-1 in our vector.

bluishhhxd

you did not take n-2 for consideration

else if(c==n-1 || c==n-2) { ans=n-1;}

Forestmy17

Problem B

100000000000000 1 1

test not working when use while, but there are accept solution with while.

adiroy2

A. OK. nice. AC

B---lew me away.

Yugandhar_Master

Tree solution to $$$D$$$ :

Lett root of the tree be $$$n$$$, now add the edge between $$$i$$$ and $$$j$$$ such that $$$i$$$ is more valuable than $$$j$$$ in atleast one of the $$$3$$$ permutations and $$$i > j$$$, answer is the decreasing path from $$$n$$$ to $$$1$$$, it's easy to construct solution from the path.

Sovi_11

Wouldn't the number of edges be $$$O(n^2)$$$ in this solution ?

How can tree have $$$n^2$$$ edges, tree have $$$n-1$$$ edges hence we are considering every element only once

chenwenmo

May I ask if you could simply explain the code implementation? I don't quite understand how to create the graph. I wrote about a similar method in the contest, but I didn't complete. :(

UP84

The formula for t(v) doesn't make any sense in problem E, you define d(v) and then wrote d/d+1 .What is that?

shsh

+11

d should just be d(v).

thanks, updated editorial mildly to make it $$$d(v)$$$.

pikachu1010

New lesson learned — use fenwick tree whenever possible to prevent MLE, missed D by 1 second!

Tsar1453

Man, if these kind of problem were being asked in div 2 B, then I might not reach pupil in this life. But I would say problem A was good though. Haven't solved it in contest, but it gave new perspective to solve Brute force type problems

verdantgmd

+15

Who wrote the problem B? "I just wanna talk to him"

HarshitKumarGupta

The entire contest was authored by a single author, it's clear from that.

I have found out max 14 iterations can be taken. Edge case:- n=9 a=10 b=1 WWWNSEEEE

|_,_,_,_ s e

If we go for 13 iterations then 'e' will be at 13,0 which gives highest point at (9,1). But if we go for 14 iterations then 'e' will be at 14,0 which gives highest point at (10,1).

Here is my submission

Hamza_28

For problem A, why it is not enough to run the pattern for 10 times ?

zrnstnsr

Consider SNNE and $$$(10,9)$$$.

thanks

SOMANSH24

Why exactly less than 100 is sufficient and not less than 50 or 90 and more than 110 or 150 or 200 ??

BeanBurrito

i did 20 and got AC

MasFlam

It is definitely sufficient to repeat the move sequence exactly 100 times.

First just look at where Alice lands after a full sequence. You can think of that as a translation in 2D space, a vector. Repeating the full sequence will just result in multiplying that vector by an integer. Clearly, it will never take more than 10 applications of an integer vector to reach the target which coordinates are $$$\le 10$$$.

Now let's think of what happens when Alice performs just the first move. After that, she will more or less start repeating the same sequence again. More precisely, for example if her sequence was SENESW, then her first move was S and will now be repeating the sequence of moves ENESWS (except for her very last move). That new sequence has the same length. So to reach the target after her first move, 10 repetitions of the sequence are enough again.

The same reasoning can be applied when you think about what if she has done her first two moves, first three moves, etc. But her sequence is only 10 moves long, so in total she will never need more than $$$10 \times 10$$$ moves.

Not saying it can't be capped at a lower number as others have written, but this was enough to get AC.

misaki646

consider at each time you repeat a sequence, your position improved 1 distance to the target.

Mahattan distance from (0,0) to nmax (10, 10) is 20. So worst case it can do is 20 loops.

But my instinct tell me to do something around 100 (nmax*nmax, and in my sub I do 110 because I'm very lazy to think about edge cases in A/B problem). Kinda doing it with what the guts tell though.

Later, the problem B hurt me so much I don't have enough time for C. Just barely 5 minute I'll AC problem C but just can't.

https://codeforces.net/contest/2028/submission/290973014

Having spent basically half the contest thinking about E, I am somewhat underwhelmed by the lack of proof of the formula for $$$t(v)$$$. The editorial just drops it on you saying it matches up with the bamboo case (fair enough) but gives no intuition on why it works :(

Hm, I think the main point I'm trying to make is that we can reduce the problem to solving it on paths. In other words, we can somewhat simulate "removing" the edges of the shortest path from root to leaf, which decomposes the tree into a forest. For each root of that forest, we now know the probability of Alice escaping from that root, and so the same inductive logic applies (cut away a shortest root-to-leaf path, repeat). So, the proof for the bamboo case must apply to the whole tree.

Okay I took some more time to parse the last paragraph and your reply and I see it now, the $$$t(v)$$$ formula in the second paragraph clearly follows from that reasoning, thanks!

I think a good way convince oneself that the game takes place at one (subtree)root-leaf path at a time is to say that: Alice is trying to advance to the root asap; Bob is trying to get to any leaf asap; the most probable path to any vertex is the shortest one, so it is optimal for Bob to alway target the closest leaf at any given time. (So long as it doesn't involve going upwards, as that move is always optimal for Alice, and we're playing a zero sum game)

mixeil_sarkisiani

I liked it very much, even though I don't know enough to solve harder problems :D I'll make sure to write them (with help of editorial)

For E, one can enumerate leaves from low depth to high depth, and fill the link between the leaf and the first ancestor that is filled with an A. P. Code: 290943603

EmotionlessTragic9yoGirl

Problem B: binary search solution:

https://codeforces.net/contest/2028/submission/290960549

saelcc03

Thnx!. Couldn't thought of a o(1) solution. I completely forgot that 128 bit intengers exist

yuxuan013

Can someone help me understand what is wrong with my code for B?https://codeforces.net/contest/2028/submission/290960656

in your if statement where b==0 there are 3 cases

if(c>=n) ans=n;
else if(c>=(n-2)) ans=n-1;
else ans=-1;

Andimeo

From problem C, I found one segment from the start and one segment from the end, use whichever is smaller. max(the remaining part, maximum of the m parts if the sum of the remaining part is over v) is for alice. Why is this approach incorrect?

And what is the 222nd test case for pretest case 2?

NexTopper

10 4 1 4 4 4 4 4 4 1 1 1 10

Thank you, got it.

Initially, I tried that as well but it doesn't work. Try these cases:

n = 9 m = 4 v = 10: 13 1 12 9 1 11 8 3 1

n = 9 m = 4 v = 10: 13 1 12 9 1 13 8 3 1

They should both be 14.

Thank you! But what are n, m, v then?

edited

basically it seems like with this approach you can't know which side to take from unless you check the entire middle (which takes O(n) time per creature), so O(mn) time overall.

Thanks, got it.

Skal1337

Does anyone have proof for A?

I don't have the proof for the tight bound, but it's easy to see that repeating it large enough times is sufficient.

Consider a case when you completed the move sequence once, and now you're at $$$(x,y)$$$. If $$$x=0$$$ and $$$y=0$$$, repeating the same sequence will never let you get anywhere new. Otherwise, each time you perform the move sequence, your position will change by $$$(x,y)$$$ again, which will eventually "surpass" $$$(a,b)$$$, either in positive or negative direction. Since each sequence has limited number of moves, you can't reach more than the length of the sequence away from your current position within a single move sequence. Therefore, after enough iterations, $$$(x,y)$$$ will become far from $$$(a,b)$$$ that you cannot reach there within another move sequence, and the distance will become even greater after each move sequence.

Schmoov

Let r be the max(x, y) after doing the pattern once. if r = 0, 1 simulation is enough else after 20 simulations we have to start from a point that is a least 20 away from the beginning and cannot reach a coordinate in the square 10,10 since the pattern is 10 long.

I've added a proof to the editorial.

lequoctran181

I spent almost 2 hours to debug problem B with no success, with every solution "Wrong Answer on test 2". When the contest was over, I checked the verdict and realized the verdict's comment: Wrong answer 6077th number differs. Please can anyone tell me what's wrong with my code, thanks for your time. After I read the editorial, I still didn't understand why my solution is wrong.

This is my code:

consider 4 0 7

Edited: Realized the whole point where I'm wrong and I've gotten AC. Thank you so much for your help. I am missing if c >= n when b = 0 (should print "n" instead of "n — 1"). Please ignore my comment :)

Oh wow thanks, I realized the problem. With this below code, it seems to run out properly (4 0 7) outputted 4, but I still get Wrong answer 6077th number differs. Can you come up with another test case that could work? Thanks so much! I've never gotten desperate to a Div2 B problem like today :(

MathGuy1729

This part (inside handling b==0):

if(n - c > 2){
    cout << -1 << endl;
} else{
    cout << n - 1 << endl;
}

is wrong when $$$c\geq n$$$ (the answer should be $$$n$$$ in that case).

+12

Wow thank you so much that solved the problem. Have a nice day!

s_tapan005

can anyone tell why my approach fails 290961099 ? can we solve it by binary search ?

problem c.

Aswineeey

best C ever

Does anyone know the tight bound of the number of repeats for A, and how to make the worst case?

Here are the two worst cases, taking 14 repeats:

9 10 1
WWWNSEEEE

and

9 1 10
SSSEWNNNN

(which is in a sense symmetric)

At7777

Can someone help me with problem D .I am just not able to find the error. My code is failing on input 230 of tc 3. ;)

https://codeforces.net/contest/2028/submission/290954199

roronoa_2z

I was writing O(n) solution for A but it's too much case work for checking this

start.x + gap.x * k(iteration ) = x start.y + gap.y *k(iteration) = y

Kanishk_0012

I also wrote an AC O(N) solution, but true, it was too much of a case work :(

I would like to share my key-learnings from today's contest in this blog post. Since I have negative contributions, My post is not visible due to Negative contributions.

34z12000

Actually your post is visible, or at least I can see it

Can anyone explain below expression: 1 + (n — c — 1) / b

Instead of this why can't we take 1 + (n-c)/b?

zittear

I think that is because we need to fill 0~n-1 not 1~n

https://codeforces.net/contest/2028/submission/290975793

Does anyone have simpler O(n) solution of A than this .

It's simply two much case work.

0x81

https://codeforces.net/contest/2028/submission/290993428

yellow_13

Bonus for D would be using segment tree right? Instead of maintaining the minimum $$$x$$$ as mentioned in editorial, we'll have to maintain 3 arrays which will store the DP values according to the order of $$$p_i$$$ for each player. Then when we want to find answer for $$$a$$$, we'll do an RMQ to find the $$$b$$$ with minimum $$$dp_b$$$ with $$$p_b<p_a$$$ across all 3. After this we will update the DP value for $$$p_a$$$ using point update.

I think, you just have to maintain the distance. No need to segment tree.

My intended solution for this version is indeed a segtree -- can you elaborate by what you mean for "maintain the distance"?

Hi applepi216, before I explain my thought process, I would like to confirm what I am thinking is right or not.

https://codeforces.net/contest/2028/submission/290968924

Can you please run/test output of your code, with segment tree, and see, if number of required trades are equal.

If they are equal, then I will try to elaborate my idea.

ryucc

I think it can be done without segtree too,

I want to sort the cards by the permutation. for example

the permutation, 2 3 1 4

pair with index (2,1), (3,2), (1,3), (4,4)

Then sort (1,3), (2,1), (3,2), (4,4)

Then I can Dijkstra over this representation. Every node can reach any other node to its left. So every time I pop a node from the priority queue, I check every unexplored node to its left.

If the card number is larger, I add it it to the priority queue, if the card number is smaller, I can safely ignore(within king, queen, jack), since it does not explore any extra nodes than the current, so I don't have to add it later even if it is reachable.

Using a monotonic increasing pointer to keep track of the last unchecked edge, I can check each edge at most once.

9mar3

My submission of A: flex is only O(n) The movement have permutation nature, i mean "NE" is equal to "EN". so if the sequence is "NESWSWNSWES", and the the way to reach the queen is NESWSWNSWES + NESW, it's equal to NESW + NESWSWNSWES. i call (i,j) is the result of NESWSWNSWES, so the road should be (i,j)*x times+ subset of NESWSWNSWES. so we just start from this subset result, and try to determine whether it can reach the queen. notice negative road (instead of +(i,j), it will — (i,j) ) My English s*ck

290935227

Problem D:

In the second example, why can’t Alice trade with the Queen to get card 3, and then trade with the Jack to get card 4?

The queen values 1 over 3, so Alice can trade 1 for 3. The jack values 3 over 4, so Alice can trade 3 for 4.

Clearly, I’m missing something obvious but can’t see it after re-reading the problem.

Sinphnice

Had you found out why? I am also unable to understand this case. And I tried the code given in the tutorial, which is also confusing: input: 1 4 3 1 2 4 1 2 3 4 1 4 3 2

output: YES 2 q 2 j 4

_Kee

You probably misunderstood the meaning of preference values. The Jack values 4 over 3 because $$$p_4 > p_3$$$ ($$$3 > 2$$$).

sudhanshunain21

For C: We can maintain a count and keep accumulate the sum from the right side, whenever our sum is >=v, we store this index as check[count] = i, count++, since this index is enough to feed count number of people.

Now we iterate from left side, whenever we feed c people, we find j=check[m-c] index which is the farthest index from i such that m-c people can be feed. so for each such i, ans = max(ans, sum a[i+1,j-1]). Finally, ans variable stores the largest segment which Alice can have.

Submission : 290978919 runs in O(n) with just 2 iterations in 77ms.

Do let me know if you have something to ask about this.

4svOff

Can someone explain, what system of linear equations is mentioned in problem E editorial? Or just explain in other way, why $$$1 − \frac{(i−1)}{d}$$$ is a solution for a bamboo.

Suppose we have a bamboo on nodes $$$0, 1, \ldots, d$$$. Let $$$p_i$$$ be the probability of Alice escaping from node $$$i$$$ (let $$$0$$$ be the root, so $$$p_0 = 1$$$ and $$$p_d = 0$$$). Then, $$$p_i = \frac 12 p_{i+1} + \frac 12 p_{i-1}$$$ for all $$$1\le i \le d - 1$$$.

From this system of equations, you can prove by substitution & induction or other means (for example, martingales or some discrete harmonic function facts) that $$$p_i = 1 - \frac id$$$. In fact, if you guess that this is the solution it is not too hard to verify that it works by plugging it in.

MMihalev

Why does pd equals zero?

By definition, Alice loses if she reaches any leaf (here I'm just shifting so that $$$0$$$ is the root and $$$d$$$ is the leaf)

Negationist

i figured this out but i would love if you dropped a little proof

sidlad

p(i) = (p(i+1) + p(i-1))/2

p(i) − p(i-1) = p(i+1) − p(i)

It is easy to see that the change in probability between the adjacent nodes on the branch being referred to by applepi216 will become a constant from the leaf upto parent of the ith node

yeah, arithmetic relation, cool

You can simply see that p(i) − p(i-1) = p(i+1) − p(i) holds from the above equation, with p(d) = 0 and p(0) = 1

It is easy to see that the change in probability of these adjacent nodes is constant, from which you can get that going from p(d) to p(0), p(i) = 1 − i/d

junhan_sg

Is there a way to see or download the full testcases? I do not understand why my answer is wrong.

There isn't. You can refer to this submission.

https://codeforces.net/contest/2028/submission/290971915

Look at the small hack I use in the getInput() function. May be u can use the same.

Lolboyyyy

I wrote a BFS solution for D which got accepted. But I now realize after reading the editorial that the solution is incorrect.

In fact, it fails on this particular test case:

1
6
1 2 4 5 3 6
3 2 5 1 6 4
1 2 3 4 5 6

The solution is YES but my code prints NO. Any div 1 user, please feel free to uphack :)

YipChip

I realize why I got WA now. Thanks a lot.

moradiya84

Hey!!

applepi216 in bonus of problem D Bonus can we claim that if answer exist than minimum length of it would be either 1,2,3(number of trade)? I can't really put argument since i couldn't come up with any proof.

Try this

1
8
1 3 2 5 4 7 6 8
2 1 4 3 6 5 8 7
1 2 3 4 5 6 7 8

I think the minimum steps is 7.

Queen only trades 2->3, 4->5, 6->7

King only trades 1->2, 3->4, 5->6

Jack does not trade at all.

oh I see.you are right.

In problem B,I found that c+(b-1)*((n-c-1)/b)+(n-c-1)%b can also be used instead of n-max(0ll,1+(n-c-1)/b) by math,can anybody prove it that they are actually the same?

Si_jo

What felt natural to me in E: //1. write the equations and observe each node depends on its parent and node leading to the nearest leaf. //2. to determine the order in which values have to be found draw the directed graph and decompose into SCCs, then //topsort, in that order. pretty common stuff. //3. for each SCC, observe it is a path from v to some ancestor. p(i)=1/2(p(i-1)+p(i+1)) roots of its char eqn is 1,1 //so p(i)=a+bi if outgoing edge of v leads to a node with prob x and similarly ancestor leads to y then, //a=x and b=(y-x)/(sz(SCC)+1). //okay, a pretty obvious thing was that witch will pull it down, even if nearest leaf can be obtained by going up.

poituk

Please, say me what equations we need to write

Surajshivam919810

In testcase case no. 2 of problem c answer would be 20 instead of 12 because she can divide the cake into (1+1),(1+1) and remaining would be (10+10)=20

Subarrays mean that they have to be contiguous, so you can't give both $$$[10]$$$ and $$$[10]$$$ to Alice.

_Terra_Incognita

Ive never felt more satisfaction getting AC on a D2B

Flaming_Blade

D is a cute problem. Thanks.

James_Zhang

I use Pypy in problem A with an almost same code, but it's time exceeded.

joj00

is binary search possible on problem b , given constraints are very large

It worked for me. As I wasn't able to deduce the direct formula used for the else part in the suggested editorial solution for case when $$$b != 0$$$, I had realized using Binary Search for the problem B.

If it works in PyPy3 (Python implementation of Python 3), it should work on most of the languages. Check out my Binary Search inclusive solution to Problem B here: https://codeforces.net/contest/2028/submission/290951271

PUSSY_LICKING_LOLI_69

-21

I still dont get problem E, isnt it possible that alice will move back and forth indefinitely if the coin keeps alternating between heads and tails?

As the number of flips goes to infinity, the probability that Alice still hasn't reached the root or a leaf goes to zero, meaning that Alice will almost surely end up either at the root or a leaf with infinite amount of tries.

im not big brain enough for this @_@

bruh change your name

To see why this isn't the case in another way, consider the event that the coin flips heads $$$n$$$ times in a row (we will keep flipping the coin even after Alice either escapes or gets trapped). Certainly, if it's heads $$$n$$$ times in a row then the process stops. But, this event happens with probability $$$1$$$ (in other words, as djm03178 put it, it will almost surely occur) so we can "condition" on this event. Thus, eventually someone will win with probability 1.

For anyone that doesn't understand the last paragraph of E, including me here is a slightly better explanation. Let the node we want to escape from be v, the parent is p, the chance of escape from the parent is p(v) and distance to closest leaf node is d we can say that until we reach the parent v, the game will only be played on the bamboo going from p, into v, and to the closest leaf. Thus the chance of getting to the parent p is the chance of getting from the node second from the top to the top in a bamboo. This turns out to be d/(d+1)(or to say it out loud, # of nodes below this one over the total number of nodes not including this one) which just comes from the bamboo equations. So we can derive that the overall chance is p(v)*d/(d+1).

sushmanth.dampur8780

← Rev. 5 →

+14

the_last_smilodon

← Rev. 4 →

Editorial's hint for D :

This is not a graph problem.

Tags 😁 :

AdityaRathore

Can someone please explain me A in a simpler way? I am not getting it.

i didn't read the editorial but just simulate once, check to see if you reach. If not, you know the total delta distance per cycle so run it a few times and have a set to check to see if you brought a and b in range, refer to my submission.

shubhamjr1729

After the first run of the movement pattern, Alice will either move towards -x, +x, -y, +y, or remain at the same position. This depends on which direction has the highest count among N, E, S, and W. If all directions (N, E, S, and W) have the same count, she will remain at the same position.

In the worst case, you could have a pattern like NNNNNNSSSS. In this case, Alice will move down by up to 4 levels and then move back up. After 10 iterations, Alice will reach a position that is 10 units away, but since there are four additional S moves, she will come down again, within a 10x10 grid. After 4 more iterations, Alice will reach the border of a 14x14 grid. If the pattern continues, the farthest she can reach is the edge of a 10x10 grid.

Thus, in the worst case, you need 15 loops to be safe:

10 iterations to reach the 10x10 grid border.
5 more iterations to ensure Alice does not re-enter the 10x10 grid while following the movement pattern.

huo_hua_ya

The problen D is pretty good.It made me realize my shortage in dp.Though,i failed to solve it in time,it actually made me stronger.

eternal_happiness

Why is it not possible to multi-source bfs from all the non-root leaves to all the other edges to find the shortest path to the next non-root leaf? I tried this and it failed

Noluck_167

C is really a nice question ,i missed on really simple observation that what can be the maximum piece from i Alice can take and tried to binary search on segments or binary search on answer.

Husanboy

+21

In Problem E, the derivation of the formula $$$t[i] = 1 - \frac{i - 1}{d}$$$:

We have the base cases $$$t[1] = 1$$$ and $$$t[d+1] = 0$$$.

As there are two moves with equal probability (moving $$$i - 1$$$ or moving $$$i + 1$$$) for all other $$$i$$$, the equation $$$t[i] = \frac{t[i - 1]}{2} + \frac{t[i + 1]}{2}$$$ holds.

We can rewrite the equation as $$$t[i] = \frac{t[i - 1] + t[i + 1]}{2}$$$. So we need to find a sequence of length $$$d+1$$$ whose first term is equal to $$$1$$$ and the last term is $$$0$$$ and the other terms must be arithmetic mean of the two neighbouring terms. Does that remind you of something?

Yes, it does. All the conditions hold, if and only if the sequence is arithmetic. Let's change the question: You are given first and the last terms of an arithmetic sequence of length $$$d + 1$$$, and asked to find the sequence itself. You can find the difference, $$$dif$$$, between two consecutive terms by the formula $$$dif = \frac{term_{d+1} - term_1}{d}$$$. Just substitute last term with $$$0$$$ and first term with $$$1$$$, then you will get $$$dif = \frac{-1}{d}$$$. Then, the formula for the $$$i_{th}$$$ term will be $$$t[i] = t[1] + (i - 1) \times dif$$$. Again, substitute everything to get the final formula:

$$$t[i] = 1 + (i - 1) \times (\frac{-1}{d})$$$ $$$\rightarrow$$$ $$$t[i] = 1 - \frac{i - 1}{d}$$$.

The problem just requires some thinking and knowledge from 4th grader. Amazing.

Thank you, applepi216, for such an interesting problem.

phatdapchai

5 weeks ago, # ^ |

Orz, thanks for enlightening me.

IF-THEN

I think that my two pointers solution for problem C is simple and elegant.

harshit_chauhan

In B , even binary search gives TLE. According to the tutorial, it can be done in O(1) , but BS should also not give TLE. I think

Xiao_2710

Can somebody please explain why this fails in C? I used a 2 pointer based greedy,where i create segment from start(sum>=v): say from 0 to i and same segment from the back(say from j to n-1), now I choose the segment with the lower sum(but still >=v), and decrease count and move pointers accordingly.

PROBLEM E: Why optimal move of the Queen is downward? Considering the following case:

What if Alice starts at 5 and Queen intends to move 5 -> 3 -> 4. Will the probability be greater or lesser than the moving downward way?

Think about it this way: the Queen has more winning possibilities by moving downward than moving upward. In other words, the probability of Alice losing increases as we go down the tree (since it must decrease as we go up the tree).

Cuellius

Another direct proof for $$$t[i] = 1 - (i - 1) d^{-1}$$$ in the Problem E. The comment proves that the following equation

$$$ t[i] = 2^{-1} (t[i - 1] + t[i + 1]), \tag{1} $$$

with the boundary conditions

$$$ t[1] = 1,\quad t[d+1] = 0, \tag{2} $$$

holds.

Further, various authors suggest noticing something to solve Eq. (1). However, there is no need to notice anything. We need only to apply the standard technique. Denote $$$ j = i + 1 $$$, then we have

$$$ t[j - 1] = 2^{-1} (t[j - 2] + t[j]), $$$

which is equivalent to

$$$ t[j] - 2 t[j - 1] + t[j - 2] = 0, \tag{3} $$$

To solve Eq. (3) we construct the characteristic polynomial:

$$$ \lambda^2 - 2 \lambda + 1 = 0. $$$

Hence $$$\lambda=1$$$ (it is the root of multiplicity 2). So

$$$ t[j] = C_1 1^j + C_2 j 1^j = C_1 + C_2 j, \tag{4} $$$

where $$$C_1$$$ and $$$C_1$$$ are constants, which can be founded from the boundary conditions. Let us substitute (4) into (2) and obtain

$$$ t[1] = C_1 + C_2 = 1,\quad t[d+1] = C_1 + C_2 (d+1) = 0. \tag{5} $$$

The solution of the system (5) has the form: $$$C_1 = \dfrac{d+1}{d} = 1 + \dfrac{1}{d}$$$ and $$$C_2 = -\dfrac{1}{d}$$$ (it is so obvious that I don't see the point in describing it in detail). Thus,

$$$ t[i] = C_1 + C_2 i = 1 + \dfrac{1}{d} - \dfrac{i}{d} = 1 + \dfrac{1 - i}{d}. $$$

The statement is proved.

yyashm1491625

Im trying to use 2 pointers here by calculating the minimum sum subarray such that sum >= v by traversing from start as well as the end. If the sum from left was smaller and lets say now left pointer is at L than in next iteration pointer from right end lets say R should end at L, ip and jp are current left and right ends.

AlexTheFirelord

5 weeks ago, # |

I found an interesting way to solve E by constructing a different system of linear equations and solving it using a variation of Tridiagonal Matrix Algorithm: https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm.

Let $$$p_v$$$ be the answer for vertex $$$v$$$, $$$p(v)$$$ be the parent of $$$v$$$ and $$$s^*(v)$$$ be the child of $$$v$$$ which lies on the shortest path from $$$v$$$ to leaf in subtree of $$$v$$$. Then we have:

$$$p_v = \begin{cases} 1, & \text{if $$$v$$$ is a root,} \\ 0, & \text{if $$$v$$$ is a leaf,} \\ \frac{1}{2}\left(p_{p(v)} + p_{s^*(v)}\right), & \text{if $$$v$$$ is neither a root nor leaf.} \end{cases} $$$

This system is quite difficult to solve in a straightforward way by Gaussian elimination since it requires $$$O(n^3)$$$ time in general, but we can use the approach similar to Tridiagonal Matrix Algorithm in $$$O(n)$$$ time. We express $$$p_{p(v)}$$$ as $$$\alpha_v p_v + \beta_v$$$, substitute this in an equation for $$$p_v$$$ and find coefficients $$$\alpha_{s^*(v)}$$$ and $$$\beta_{s^*(v)}$$$ in terms of $$$\alpha_v$$$ and $$$\beta_v$$$, solve for $$$p_{s^*(v)}$$$ recursively and then solve for $$$p_v$$$.

Then we can implement DFS-like solver which starts from $$$v = 1$$$ with $$$\alpha_1 = 0$$$ and $$$\beta_1 = 1$$$ (since $$$p_1 = 1$$$), propagates $$$\alpha_v$$$ and $$$\beta_v$$$ into $$$s^*(v)$$$, then solves for $$$p_v$$$ and goes into another children. The only problem left is the proper way to "go into another children". Since we've already found $$$p_{p(v)}$$$, from the expression for $$$p_v$$$ we conclude that it's enough to pass $$$\alpha = \frac{1}{2}$$$ and $$$\beta = \frac{1}{2}p_{p(v)}$$$ into DFS call for every child.

Shoeib

How to be able to solve problems like E, I feel that however i spend time i can never solve it.

SkibidiPilav

i just solved D, and its a beautiful problem, thank you.

c is cool too, kinda sad that this contest happened while i was on a break, but very happy to solve the problems regardeless :D

Yoralen

For F's code showed in the editorial,this case would be "NO",but it responds "YES" 1 1 0 1

OmarAboutaleb77

4 weeks ago, # |

There is another way to solve Problem D by treating it as a graph problem. First, I will describe the straightforward $$$O(n^2 \log(n))$$$ solution, and then I will optimize it to $$$O(n \log(n))$$$.

Graph Representation

Consider each card from $$$1$$$ to $$$n$$$ as a node. An edge from node $$$i$$$ to node $$$j$$$ exists if there is a valid trade involving one of the three other players (Queen, King, or Jack of Hearts), allowing Alice to trade card $$$i$$$ for card $$$j$$$.

For a trade to be valid, it must satisfy two conditions:

$$$j > i$$$
$$$p[i] > p[j]$$$ for at least one of the three other players.

Naive $$$O(n^2 \log(n))$$$ Solution

Iterate over nodes from $$$N$$$ down to $$$1$$$.
For each node $$$i$$$:
Use a map to find all nodes $$$x$$$ where $$$p[x] > p[i]$$$.
Add edges from all such $$$x$$$ to $$$i$$$.
After constructing the graph, run a BFS starting from node $$$1$$$ to reconstruct the solution.

This solution works but is too slow due to the $$$O(n^2 \log(n))$$$ complexity.

Optimized $$$O(n \log(n))$$$ Solution

We can optimize the solution by avoiding redundant edge additions and unnecessary checks.

Use a Set for Efficient Tracking:
Maintain a set of unvisited nodes, initially containing all nodes from $$$1$$$ to $$$n$$$
Iterate over nodes $$$i$$$ from $$$N$$$ down to $$$1$$$.
Use the set to find all nodes $$$x$$$ where $$$p[x] > p[i]$$$. These are the nodes that can have edges directed to $$$i$$$.
Add edges from all such nodes $$$x$$$ to $$$i$$$.
Remove these nodes $$$x$$$ from the set, as they are fully processed and no longer need to be considered.
Once the graph is constructed, run a BFS from node $$$1$$$ to reconstruct the solution.

This solution is $$$O(nlog(n))$$$. The reason why this works is that every node that is removed from the set is already part of a path to node n, so there is no reason to add another edge to it. We only consider visited nodes as unvisited nodes don't belong to any path to node n.

If you have any questions feel free to ask.

gabrielfaure

7 days ago, # ^ |

I've come up with a O(n) graph solution. I don't have a proof of it, but it got accepted and it shouldn't be too hard to prove its correctness, albeit perhaps tedious.

Find the inverse permutations of q, k, and j. This gives an ordering from least preferred card to most preferred card for each of the Queen, King, and Jack.
For each of these inverse permutations, calculate the next lesser element and the previous greater element for each element (assuming they exist). This can be done using a monotonic stack.
Create a digraph with nodes 1...n, and arcs pointing from each element to its previous greater element, and also arcs pointing to each element from its next lesser element, for each inverse permutation.
DFS/BFS from 1 to n.

Algo_Ace

3 weeks ago, # |

Does anybody have other solution of first question ?

applepi216's blog

2028A - Alice's Adventures in ''Chess''

2028B - Alice's Adventures in Permuting

2028C - Alice's Adventures in Cutting Cake

2028D - Alice's Adventures in Cards

2028E - Alice's Adventures in the Rabbit Hole

2028F - Alice's Adventures in Addition