Thank you everyone for participating in the round! We hope you enjoyed the problems :)
2028A - Alice's Adventures in ''Chess''
Hint
How many times do you have to repeat the string until you know for certain whether Alice will ever reach the Red Queen?
Solution
Tutorial is loading...
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
Do casework on whether $$$b = 0$$$ or not.
Solution
Tutorial is loading...
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
How can you quickly determine if Alice can ever receive the piece $$$a[i:j] = [a_i, a_{i+1}, \ldots, a_{j-1}]$$$?
Hint 2
For a given $$$i$$$, how can you quickly check the maximum $$$j$$$ such that Alice can receive the piece $$$a[i:j]$$$?
Solution
Tutorial is loading...
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
This is not a graph problem. Try to think about for each card $$$i$$$ whether Alice can ever trade up from $$$i$$$ to $$$n$$$.
Solution
Tutorial is loading...
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
Solve the same problem, but now with the additional requirement that the solution must use the minimum number of trades (same constraints).
2028E - Alice's Adventures in the Rabbit Hole
Hint 1
What are Alice's and the Red Queen's optimal moves at a given position?
Hint 2
Solve the problem for a path (bamboo) of length $$$n$$$ first.
Hint 3
Solve Hint 2 first. Now, generalize the solution to an arbitrary tree.
Solution
Tutorial is loading...
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
Come up with a DP algorithm running in time $$$O(n^2 m)$$$.
Hint 2
Try optimizing the Hint 1 DP to run in time $$$O(nm \log m)$$$ when $$$a_i \ge 2$$$ for all $$$i$$$.
Hint 3
Do some casework to extend Hint 2 to $$$a_i \ge 0$$$.
Hint 4
Solution
Tutorial is loading...
Code
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
LOG = 14
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
a = list(map(int, input().split()))
prev, pfx, zero = 1, 1, 0
mk = (1 << (m + 1)) - 1
q = deque()
for x in a:
curr = zero
if x == 0:
curr |= pfx
zero = curr
q.appendleft((0, prev))
elif x == 1:
curr |= (prev | (prev << 1)) & mk
else:
prod = 1
ptr = 0
q.appendleft((x, prev))
while ptr < len(q) and prod > 0 and prod * q[ptr][0] <= m:
prod *= q[ptr][0]
curr |= (q[ptr][1] << prod) & mk
ptr += 1
pfx |= curr
prev = curr
if len(q) > LOG:
q.pop()
print("YES" if (prev & (1 << m)) else "NO")
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?)
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.
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.
Thank you for such a cool Problem F, I hope in the future I will learn to solve this)
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.
that's why it's problem F
A good problem F shouldn't be difficult on optimisation unrelated to the main idea
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.
best contest ever,
I liked problem B so much.
Every problem should be like this in every contest.
Thanks, upvote who agrees.
are you serious right now bra
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...".
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.
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
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.
I still think B is cool. But yeah its hard to find the logic behind it.
Thanks for fast editorial! orz applepi216
Thanks for a very first tutorial
I still don't understand why my ceil division didn't work like this:
This formula only works when c <= n.
Try this testcase:
1 3 1 5I have specific part to handle other cases:
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.
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.
you did not take n-2 for consideration
else if(c==n-1 || c==n-2) { ans=n-1;}
Problem B
1
100000000000000 1 1
test not working when use while, but there are accept solution with while.
A. OK. nice. AC
B---lew me away.
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.
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
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. :(
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?
d should just be d(v).
thanks, updated editorial mildly to make it $$$d(v)$$$.
New lesson learned — use fenwick tree whenever possible to prevent MLE, missed D by 1 second!
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
Who wrote the problem B? "I just wanna talk to him"
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
For problem A, why it is not enough to run the pattern for 10 times ?
Consider
SNNEand $$$(10,9)$$$.thanks
Why exactly less than 100 is sufficient and not less than 50 or 90 and more than 110 or 150 or 200 ??
i did 20 and got AC
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 wasSand will now be repeating the sequence of movesENESWS(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.
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.
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).
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)
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
Problem B: binary search solution:
https://codeforces.net/contest/2028/submission/290960549
Thnx!. Couldn't thought of a o(1) solution. I completely forgot that 128 bit intengers exist
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
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?
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.
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.
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.
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 :(
This part (inside handling b==0):
is wrong when $$$c\geq n$$$ (the answer should be $$$n$$$ in that case).
Wow thank you so much that solved the problem. Have a nice day!
can anyone tell why my approach fails 290961099 ? can we solve it by binary search ?
problem c.
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:
and
(which is in a sense symmetric)
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
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
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.
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?
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.
https://codeforces.net/contest/2028/submission/290993428
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.
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.
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.
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
You probably misunderstood the meaning of preference values. The Jack values 4 over 3 because $$$p_4 > p_3$$$ ($$$3 > 2$$$).
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.
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.
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)
i figured this out but i would love if you dropped a little proof
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
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.
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:
The solution is YES but my code prints NO. Any div 1 user, please feel free to uphack :)
I realize why I got WA now. Thanks a lot.
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
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?
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.
Please, say me what equations we need to write
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.
Ive never felt more satisfaction getting AC on a D2B
D is a cute problem. Thanks.
I use Pypy in problem A with an almost same code, but it's time exceeded.
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
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).
Editorial's hint for D :
Tags 😁 :
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.
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:
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.
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
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.
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.
I think that my two pointers solution for problem C is simple and elegant.
Let $$$f(x)$$$ = max number of monsters we can satisfy using the first x pieces for all x in [0,n].
Let $$$g(x)$$$ = same as $$$f(x)$$$ but using the last x pieces.
We create a function that takes a vector and V ( min value to deem partition good), and it return f(x).
To compute g(x), we just need to make a copy of $$$a$$$, reverse it and use the same function.
if f(n) < m then we cannot feed all monsters even with all the pieces and ans = -1.
Now that we have $$$f(x)$$$ and $$$g(x)$$$, it's a very straight forward two pointers algorithm.
We consider a segment $$$a[l:r]$$$ good, if after giving it to Alice, the rest suffices to feed all of m monsters.
It's easy to notice that if some segment is good, then any segment inside it is also good. And if a segment is bad, then any segment that contains it is also bad.
This is a very strong indication that the two pointers methods may be used here.
I learned this for the course in Codeforces under Edu section. Check it out. It's good.
Now for each r in [0,n) we find the longest good segment that ends at r, and among all of there, we pick the best of course..
For this problem specifically, it was helpful to deem a segment to be good if it's empty to avoid some troubling bugs.
How to check whether a segment[l, r] is good?
we use all pieces in a[0:l), (l pieces) to feed monsters and max num of monsters we can feed with first l pieces is f(l),
and pieces in [r+1,n) are also available, their count is $$$n-r-1$$$, and clearly we can now an extra $$$g(n-r-1)$$$, if the sum >= m, segment is good
so segment is good <=> segment is empty or $$$f(l)+g(n-r-1) >= m$$$
N.B. an empty segment is indeed good because we have already checked that $$$f(n) >= m$$$. But if use $$$f(l)+g(n-r-1) >= m$$$ to check if an empty segment is good, I think we can get in trouble, so it's better to use a different condition, simple $$$r-l+1 == 0 => good$$$ Here is the code
291149416
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
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
5and Queen intends to move5 -> 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).
Another direct proof for $$$t[i] = 1 - (i - 1) d^{-1}$$$ in the Problem E. The comment proves that the following equation
with the boundary conditions
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
which is equivalent to
To solve Eq. (3) we construct the characteristic polynomial:
Hence $$$\lambda=1$$$ (it is the root of multiplicity 2). So
where $$$C_1$$$ and $$$C_1$$$ are constants, which can be founded from the boundary conditions. Let us substitute (4) into (2) and obtain
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,
The statement is proved.
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.
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:
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.
How to be able to solve problems like E, I feel that however i spend time i can never solve it.