Sorry for underestimating the difficulties of the problems, especially B2 and D. We tried to serve as many cool problems as we could. And apparently, this led to some difficult ones.
Thank you for participating in the round. We all hope you enjoyed all of our problems.
2258A - Odd Eraser Idea: ItsNotMeItsYou, mychecksdead
Think of the case $$$n=3$$$. Can you remove the first or the last number in any way?
We cannot obtain a number larger than $$$\gcd(a_1,a_n)$$$ because the first and last numbers in the array can't be removed. We can remove all other elements by choosing $$$[1, i, n]$$$, so the answer is $$$\gcd(a_1, a_n)$$$.
2258B1 - Carrot Chopdown (Easy Version) Idea: mychecksdead
What is the answer for a fixed $$$x$$$?
Iterating over the values $$$x=1...m$$$, we can find the answer for each possible $$$x$$$.
For any $$$x$$$, the answer is the number of carrots of length greater than or equal to $$$x$$$, plus the number of carrots of length $$$2x$$$.
2258B2 - Carrot Chopdown (Hard Version) Idea: mychecksdead (This problem was originally designed with only $$$k=2$$$; thanks to ItsNotMeItsYou for expanding on the idea.)
Consider solving the problem for a fixed $$$x$$$.
Consider solving the problem for $$$k=2$$$.
What happens if $$$k$$$ is bigger than $$$18$$$?
What are the optimal $$$x$$$ values for cutting?
For target value $$$x$$$, it is optimal to use cuts in the following order: $$$x \cdot 2^{k-1}, x \cdot 2^{k-2}, \ldots, x \cdot 1$$$.
For each $$$i$$$, $$$a_i=2^k \cdot x$$$ adds $$$2^k$$$ to the answer. Otherwise, the contribution is $$$\min(\frac{a_i}{x}, 2^k-1)$$$.
The optimal $$$x$$$ is less than or equal to $$$\frac{m}{2^k}$$$ (if less than $$$1$$$, it equals $$$1$$$, and the answer is basically the sum of all carrot lengths). Moreover, no $$$i$$$ can contribute more than $$$2^k$$$ to any $$$x$$$. Using prefix sum, determine the number of values contributing $$$y$$$ to the answer for each possible $$$x$$$. This solution runs in $$$\mathcal{O}(n + m \log m)$$$.
2258C - Far Cities Idea: Seferoglu (This problem was originally designed simply to find the furthest node from the root; thanks to cadmiumky for expanding on the idea. Thanks to robert9524 for providing stronger tests on cutting random solutions without an adaptive grader.)
How to find a diameter?
Consider the simplest algorithm.
For each node, first determine whether it is closer to the first vertex than the longest distance seen so far. If not, just skip the node. This uses $$$n-1$$$ queries. Otherwise, while the query returns true, increase the queried distance by one. This can happen up to $$$n-1$$$ times. We can find one end of the diameter by running $$$2n - 2$$$ queries in total. Then repeat the process to find the other end of the diameter. This yields a total of $$$4n-4$$$ queries. But, as previously written, distance can increase at most $$$n-1$$$ times. So this yields a total of $$$3n-3$$$ queries.
2258D - Magic Tiles Idea: ItsNotMeItsYou
What happens when a range includes another?
A range that is included by another range is useless. What happens when we remove all such useless ranges?
We only need to solve the problem for chains of ranges. How?
In this editorial we will use BigIntegers, which are simple vectors, and addition and comparison is $$$\mathcal{O}(n)$$$. It can be proven that if one range includes another, we can remove the other. Also, it can be proven that only start and endpoints of the intervals are important, and let them be $$$pts$$$. Well-known $$$\mathcal{O}(n^3)$$$ dp exists; $$$dp_i$$$ means the maximum score if we fill all of the rows through $$$pts_i$$$; $$$dp_i=\max dp_j + 100^{100^{i-j}}$$$ if there is an interval that covers interval $$$[j, i)$$$. Because there are only $$$2$$$ columns, it can be proven that this solution works in $$$\mathcal{O}(n^2)$$$. From another perspective, you can imagine you have chains.
Can you solve for bigger constraints, such as $$$n,m \le 2 \cdot 10^5$$$? Thanks to dinohaur for the code: 388911329
2258E - DivMEX Idea: ItsNotMeItsYou, carcinisation (This problem was actually designed differently. Thanks to anpaio for this version.)
What kind of integers can exist as an $$$f(l,r)=x$$$ value?
How to check a value $$$x$$$ exists as a $$$f(l,r)$$$?
It can be seen that each value of $$$f$$$ must satisfy $$$f(l,r) \leq \text{smallest prime power bigger than n}$$$; for each $$$x$$$ that satisfies this constraint, we will try to check whether this value can be obtained or not.
A range that satisfies $$$f(l,r)=x$$$ can't contain a multiple of $$$x$$$; otherwise, the set of divisors would have $$$x$$$ in it. When considering multiples of $$$x$$$ as obstacles, we realize that it is optimal to greedily select between two consecutive obstacles. Hence, at each obstacle, we check whether every number $$$y$$$ that satisfies $$$1 \leq y \le x$$$ appears as a factor of any integer between this and the previous obstacle. This solution works in $$$\mathcal{O}(( \sum_{i=1}^n |S_i|) \cdot n$$$. Where $$$S_x$$$ represents the prime powers of $$$x$$$.
To optimize this solution, we iterate over all $$$a_i$$$ and check every factor of $$$a_i$$$, considering the index $$$i$$$ as an obstacle. In order to verify that every element smaller than $$$x$$$ is present between this and the previous obstacle, use a minimum segment tree. This solution works in $$$\mathcal{O}(( \sum_{i=1}^n |S_i|) \log n) \le \mathcal{O}(n \log^2 n)$$$.
2258F - Plus Minus Tree Idea: ItsNotMeItsYou
Consider $$$\mathcal{O}(n^2)$$$ $$$dp[v][\text{#1's count in subtree of v}]$$$ using the merging subtrees technique. The dp is convex because we are adding only two convex functions, resulting in a convex function. Then, using small to large, you can achieve $$$\mathcal{O}(n \log^2 n)$$$ complexity.
To elaborate:
For $$$\mathcal{O}(n^2)$$$, you can keep dp as pairs for simplicity: $$$(\text{score of v}, \text{minimum score})$$$.
As can be seen in the vector, scores are increasing by $$$2$$$. So you can keep dp with the vector's first element and then with the differences. When you merge two children's subtrees, you are basically doing a Minkowski sum, which is just updating the first element as $$$\text{(lhs[0].first + rhs[0].first, lhs[0].second + rhs[0].second})$$$, and merging the differences.
Then, for each point added to $$$|x|$$$, you must add $$$+2$$$ or $$$-2$$$ ($$$2$$$ due to parity) for all differences split by $$$0$$$ (be careful not to add any difference to $$$[-1, +1]$$$).
You can maintain two sets for each vertex, resulting in $$$\mathcal{O}(n \log^2 n)$$$ complexity from small to large.
First, identify all nodes in the tree with an initial value of zero, set them to one, and store them in a candidate list. Then, until the list is completely empty, select the most advantageous node at each step. For each node, we trace the path up to the root, counting how many nodes along that path have a subtree sum greater than one ($$$\text{pos}$$$) and how many have a subtree sum less than one ($$$\text{neg}$$$), thereby calculating a score based on the difference $$$\text{pos} - \text{neg}$$$.
After finding the node with the highest score among the list, select it, change its value to minus one, and decrease the subtree sums of all ancestors along the path from the chosen node to the root by two. We repeat this process until all special nodes are processed and the list is empty. And you can fasten this algorithm by HLD.
$$$\mathcal{O}(n^3)$$$ code by anpaio: 388911953 $$$\mathcal{O}(n \log^2 n)$$$ code by anpaio: 388911806
On clist.by we can check the hardest div2D since 2026:
wonderful 2500 difficulty!
.
I enjoyed the contest! (despite being one of the goobers who killed all their time on B2 :P)
me too...
so do I
editorial: "Thanks to robert9524 for providing stronger tests on cutting random solutions without an adaptive grader"
me: AC'd with a randomised solution and feels like the 0.01% of bacteria that don't get killed by soap
what was your randomized appraoch?
basically because so many interactive problems have binary search, my brain went straight to binary searching for the exact distance when you find a new farthest node, instead of realising that you can just increment it by one and that will happen at most $$$n - 1$$$ times.
here's what i ended up doing:
same general idea of the two DFS passes
in each pass, keep track of furthest node $$$u$$$ and its distance $$$d$$$
maintain a variable $$$h$$$ as the maximum length a path in this graph can have (initially $$$n - 1$$$)
when considering a new node, first check if it beats the distance by at least 1. if not, stop and go to the next node. otherwise, binary search between $$$[d + 1, h]$$$ to find distance of this node. then update $$$h$$$ to be $$$MIN(h, \text{new distance + number of nodes left})$$$.
the randomised part of the solution is that instead of starting at vertex $$$1$$$, and then querying $$$2, 3, 4, ... n$$$ in order, I shuffle the vertices so that I should only need to do $$$O(log(n))$$$ binary searches, so on average, I should have $$$2 n - 2 + O(log^2(n))$$$ queries. The worst case is still just $$$n log(n)$$$.
intuitively, the worst case for such a solution should just be a path, so i wrote a program locally to simulate the process on a bunch of randomised paths, and it never exceeded $$$3n$$$ queries there.
submission: 388829880
I wouldnt call that a "0.01% bacteria that survives" solution, the approach is also good even if it can exceed 3n bound in principle, also I admire anyone solving problems in Rust, I wouldnt be able to lol
Thanks lol. Maybe the type of randomised solution they're talking about cutting is actually something different (tho I can't really think of what it would be).
cool man, apart from randomized u had some nice cost cutting also
the check +1 possible, if not skip and the upper limit for d
An amazing solution
kawasaki, Synd209, elotelo, Anfeco tested the contest.
Can someone tell me how many problems they solved?
In D, why do you use biginteger when one can compare vectors lexicographically?
No, as we said they are just simple vectors. But we believe that writing struct is much easier.
I keep facing either TLE or MLE while trying to compare vectors lexicographically. Can you take a look at my code or tell me the idea of this approach? Here is one of my submissions: 389170837
It seems that your solution is $$$O((n+m)^3)$$$. Correct me if I'm wrong but you probably have $O(n+m)^2) transitions
Oh yeah, I also tried to manually code out a function to compare 2 vectors and pointer arrays to prevent MLE possibilities. And I also tried to optimize the inner loops to jump straight to the maximum possible segment length instead of testing every single midpoint. 389176247
I really don't understand the solution to B2 in the editorial. Can someone who solved it please explain.
388828299
Instead of the editorial's approach, you can solve this very cleanly using a Harmonic Series and counting thresholds.
To find how many pieces of target size i we get, we usually calculate a / i for each carrot.
But instead of dividing, we can just count how many carrots are >=i, plus how many are >=2i, plus >=3i, and so on.
A carrot of size 3i will naturally be counted exactly 3 times.
my logic :
Outer loop: Target piece size i (from 1 to m).
Inner loop: Multiples j (1, 2, 3... up to m/i).
Add the number of carrots >= i*j to a running
count.The Cap: The problem states k cuts can only extract a maximum of 2^k — 1 pieces from an oversized carrot. So, the exact moment j hits 2^k — 1, our running count perfectly represents the capped answer for k cuts,
The Bonus: We just add the frequency of exact matches freq[i * 2^k] to the count, because perfectly sized carrots yield exactly 2^k pieces, not 2^k — 1.Because the inner loop only runs m/i times, the total iterations are m/1 + m/2 + m/3..., which is O(m log m).
My total solution is O(nlogn + mlogmlogn)
Thanks!
Why B2 feels harder than C
See the score distribution: B2 is $$$1750$$$, C is $$$1250$$$
(((( i didn't notice that, but still nice contest amazing C, E and F
yo dude i get everyone is slandering B2 but personally i enjoyed it
Nice then )
Let,
$$$f_l$$$ = cnt of $$$a_i$$$ such that $$$(a_i = l)$$$ and,
$$$S_l$$$ = cnt of $$$a_i$$$ such that $$$(a_i \ge l) = f_l + f_{l+1} + \dots + f_m$$$
For $$$k = 1$$$:
For a specific target length $$$i$$$ and $$$k$$$ operations, the count of pieces of size $$$i$$$ = ( pieces from carrots $$$\ge i\ $$$) + ( pieces from carrots $$$\ge 2i\ $$$) + ... + ( bonus pieces from carrots exactly $$$2^k \cdot i\ $$$)
or,
(The summation from $$$j = 1$$$ to $$$2^k - 1$$$ counts all the guaranteed pieces we get from large carrots)
For general $$$k \le m$$$:
(Prefix max bcuz if we can get $$$X$$$ pieces with $$$k-1$$$ ops, we can get at least $$$X$$$ pieces with $$$k$$$ ops)
code (c++)
upd: fixed url
Thank you so much, appreciate it mate (code url is not working)
Don't know why unable to add this spoiler above ...
isn t editorial for E false? for example take a=[1,2,3,4,5] f(1,5)=7>max(a)+1=6
Yes, it should be the smallest prime power greater than $$$MAX(a)$$$
Thanks, fixed :)
Interactive problems look easier (they’re less algorithmic).
Could you please include proofs for the lemmas used in the B2 editorial as well? The main point of the problem seems to rely on these lemmas, but they are stated without any proof or justification.
nice round write more plz
Nice problems. Humbled the shit out of me :(. Too weak.
Overall, not a bad contest, I just kind of sold on B1, because I thought there was some smart solution rather than the brute force (with prefix sums).
code of F is not viewable, can you check it pls
Hi, I'm unable to view the code solution of the problem. Anyone has any idea why this is happening?
Oh, sorry we will fix.
Hey, just reminding in case you missed it. The solutions are still not viewable.
Anyways thanks for the contest! Questions were nice!
Then repeat the process to find the other end of the diameter. This yields a total of 4n−4 queries. But, as previously written, distance can increase at most n−1 times. So this yields a total of 3n−3 queries.
can someone explain how 3n-3 queries instead of 4n-4?
because you dont restart the process when you find the first end, you keep the same d, if you reset it, then you have 4n — 4 queries.
if my choosen node is center of the diameter then max dist i can get n/2 dist(worst case). then from n/2 dist max query can (n-1)/2 + (n-1).. so total query 3n — 3 + (n-1) / 2 ... can you explain more ?? (a bamboo tree)
B2 editorial use k + 1 cuts?
For problem C the editorial should say "For each node, first determine whether it is farther to the first vertex than the longest distance seen so far." Otherwise the solution logic doesn't make any sense.
Hello! I am trying to view the code solutions for the problems but clicking the submission link just redirects me to the editorial with a notification saying "You are not allowed to view the requested page."
Can anyone help me on why this is happening?
contest was great b2 got time from me but thumbs up for u guys nice round <3
why no nlog²m allowed for B2
Are we really voting Terrible on B2 because it's hard? I didn't solve it in contest but it's my fault for overcomplicating it. The difficulty distribution isn't good, but the problem is nice on its own.
whats wrong with this randomised approach 388836021
I thought that the probability of randomly picking a node with average distance(in between the max and min) would be high , so if that node's distance is $$$\ge \text{CURR_MAX} + 1$$$ , I apply binary search from $$$\text{CURR_MAX} + 2$$$ to $$$\text{n}-1$$$ ,otherwise I just pop it. Doing the same for the 2nd loop too, but like I cant figure out why this random approach is wrong? Please point out the total max queries with this approach.
I am not sure if my reasoning is right but I made an attempt to show that your code may fail with a good probability. Firstly, your code always asks at least 2n — 2 queries
Take example of this graph, here the distances from node 1 will be of the form [1,1,1,1,2,2,2,3,3,3], in the absolute worst scenario, you will ask queries in order of distances 1 -> 2 -> 3, this will contribute an additional $$$\log_2 (n - 2)$$$ + $$$\log_2 (n - 3)$$$ + $$$\log_2 (n - 4)$$$ to the queries. Now after you have chosen the first end of the diameter, say, node 7. You will have distances in the order, [1, 2, 3, 4, 4, 4, 5, 5, 6, 6] and again for the worst case scenario you will select in order of distances as 4 -> 5 -> 6 which will contribute $$$\log_2 (n - 5)$$$ + $$$\log_2 (n - 6)$$$ + $$$\log_2 (n - 7)$$$ to the queries. In our case, for n = 11, this will surpass the 33 queries limit with $$$\approx$$$ 35 queries. The probability of this happening in a single test case is actually the the chances of selecting 1 -> 2 -> 3 and then 4 -> 5 -> 6 and it comes to around 0.083% however the probability of exceeding 3n will be slightly more because here we chose the absolute worst case so to make thing easier let's say it is 0.1%. For t = 500, the probability of passing every test case is around $$$(0.999)^{500}$$$ $$$\approx$$$ 60%. A 40% probability of failing is actually pretty high in my opinion.
makes sense tysm, I guess it couldve worked if the query limit was not too tight for example for 4n queries, Should've just dumped the randomised approach during the contest! Although the actual solution is just too adhoc to think that it would work..
B2 and D are just incredibly difficult, first time seeing <300 ppl solve a D in div 2(correct me if im wrong). B2 was nice tho but i cant found a way to do D :Sob:
"You are not allowed to view the requested page" Anyone facing this problem to see code
By clicking on the code. It's showing "You are not allowed to visit the requested page". Authors ItsNotMeItsYou please have a look.
Why i can't look at the code ? It is saying you are not allowed to look .
Gave a contest after a very long time and somehow ended up going from Specialist to Pupil
But I enjoyed every bit of it. What a wonderful contest. Brainstormed B2 for quite a while but couldn’t get it through.
Will upsolve it today.
Thanks to the contest writers!
The editorial about B2 states that the optimal order is $$$x \cdot 2^k, x \cdot 2^{k-1}, \dots, x \cdot 1$$$.However, this sequence actually contains $$$k+1$$$ operations instead of $$$k$$$. Furthermore, if we start with $$$x \cdot 2^k$$$, a carrot of exact size $$$a_i = 2^k \cdot x$$$ would remain unaffected during the first cut (since $$$l \le x \cdot 2^k$$$), which wastes an operation and prevents it from reaching the maximum $$$2^k$$$ pieces.The correct sequence of exactly $$$k$$$ operations should start from $$$x \cdot 2^{k-1}$$$, i.e., $$$x \cdot 2^{k-1}, x \cdot 2^{k-2}, \dots, x \cdot 1$$$.Just wanted to point this out! Thanks again for the nice problem.
Oh no. B2 was harder than C. Could not solve it, should have gone for C
I don't think B2 is that easy. It could even be around Div. 2 D difficulty, though it's also possible that this problem just happens to be outside my strengths.
I had an alternative implementation for B2.
Once you grasp the solution, the challenge becomes efficiently computing the following:
for a fixed $$$k$$$ and target height $$$x$$$ find $$$\sum\limits_{i = 1}^{n}{\min(\frac{a_i}{x}, 2^k)}$$$
Note that for $$$a_i \gt 2^k * x$$$ we should subtract $$$1$$$ as these carrots will leave an unwanted long piece.
The above expression can be computed efficiently computed by using the identity
$$$\left\lfloor \frac{a}{x} \right\rfloor =
\sum_{j=1}^{\infty} [a \ge jx]$$$
Thus over a series of numbers we want to calculate
$$$\sum_{i=1}^{n}\left\lfloor \frac{a_i}{x}\right\rfloor =
\sum_{i=1}^{n}\sum_{j=1}^{\infty}[a_i \ge jx] =
\sum_{j=1}^{\infty}\sum_{i=1}^{n}[a_i \ge jx]$$$
For each target $$$x$$$, we first use a suffix count array to get the number of carrots with length at least each multiple $$$jx$$$, then build prefix sums over those counts. This lets us evaluate $$$\sum_{i = 1}^{n} \lfloor a_i/x\rfloor$$$ in $$$O(1)$$$ for any fixed $$$k$$$.
Building these prefix sums costs $$$O(m/x)$$$ for target $$$x$$$, so over all targets the total is $$$\sum_{x=1}^{m} O(m/x)=O(m\log m)$$$ via the standard harmonic series argument. We also check $$$O(\log m)$$$ values of $$$k$$$ for each of the $$$m$$$ targets, adding another $$$O(m\log m)$$$, so the total runtime is $$$O(n+m\log m)$$$.
For D, My approach is, select the longest contiguous segment and update the remaining segments by adjusting their start and end pos, but this fails can anyone spot what goes wrong here?
The code link isn't working. "You are not allowed to view the requested page"
I had a different implementation for D without BigInteger.
After coordinate compression, let
For every (j), let (st_j) be the smallest index such that some black interval contains
Then the DP is
The main difference is how I compare DP states.
I store the multiset of chosen segment lengths in a persistent segment tree. To compare two states, I find the largest length where their frequencies differ.
Each node stores two 64-bit additive hashes. So I can check subtree equality in (O(1)), go to the right child first, and find the first differing length in (O(\log 10^{18})).
The hashing makes it probabilistic, but I use two independent 64-bit hashes.
it took me much longer than i'd like to admit to figure out that the author's username is not ItsNotMeltsYou instead of ItsNotMeItsYou
Me too, I thought the author's username is ItsNotMeltsYou but it's ItsNotMeItsYou.
i'm not the only one???
Here's where I realized that I'm wrong
Hi everyone,
In problem C, the editorial uses the standard tree diameter trick: start a DFS/BFS from any vertex s, take the farthest vertex u, then DFS/BFS again from u and the farthest vertex v gives the diameter.
I understand the algorithm, but I can't convince myself of the key claim: why is u (the farthest vertex from an arbitrary s) guaranteed to be an endpoint of some diameter?
I tried to break it with this tree: s — p, p — u, p — q, q — a, q — b, where a and b are the deepest leaves of two subtrees under q. I wanted a-b to be the diameter with u being farthest from s, but it seems u being farthest from s forces d(p,u) >= 1 + d(q,a), which makes u-a longer than a-b, so it always works out. But I don't see the general reason.
Is there a short proof or intuition for why the farthest vertex from any s is always a diameter endpoint? A case analysis (path s-u intersects diameter / doesn't intersect diameter) or a "center of the tree" argument would be great.
Thanks!
https://codeforces.me/blog/entry/101271
This blog helped me.
How to prove the correctness of the alternative solution of 2258F?my idea is similar: using a regret greedy approach.Of course, Without the help of kinetic to lower the time complexity of a segmentree, the idea is proved to be TLE.Does anyone know how to prove the correctness of the greedy algorithm?that would be very helpful,thx.
I'm also curious about this.However,i dont understand why this solution can be fasten by only HLD.i mean that how to lower the time complexity of a segamentree is easy,but how to lower the time complexity of the process of change every node's score and compare them once again?
What's the rating for B2 then?