All the Polygon materials (including the official implementations of all the problems) are here.
Author: TheScrasse
Preparation: TheScrasse
Can you reach the score $$$\max(a) + \lceil n/2 \rceil$$$?
Can you reach the score $$$\max(a) + \lceil n/2 \rceil - 1$$$?
The maximum red element is $$$\leq \max(a)$$$, and the number of red elements is $$$\lceil n/2 \rceil$$$. Can you reach the score $$$\max(a) + \lceil n/2 \rceil$$$?
- If $$$n$$$ is even, you always can, by either choosing all the elements in even positions or all the elements in odd positions (at least one of these choices contains $$$\max(a)$$$).
- If $$$n$$$ is odd, you can if and only if there is one occurrence of $$$\max(a)$$$ in an odd position. Otherwise, you can choose even positions and your score is $$$\max(a) + \lceil n/2 \rceil - 1$$$.
Complexity: $$$O(n)$$$
Author: TheScrasse
Preparation: TheScrasse
Can you determine fast how many intervals contain point $$$p$$$?
The intervals that contain point $$$p$$$ are the ones with $$$l \leq p$$$ and $$$r \geq p$$$.
Determine how many intervals contain:
- point $$$x_1$$$;
- points $$$x_1 + 1, \ldots, x_2 - 1$$$;
- point $$$x_2$$$;
- $$$\ldots$$$
- point $$$x_n$$$.
First, let's focus on determining how many intervals contain some point $$$x$$$. These intervals are the ones with $$$l \leq x$$$ and $$$x \leq r$$$.
So a point $$$x_i < p < x_{i+1}$$$ satisfies $$$x_1 \leq p, \ldots, x_i \leq p$$$, and $$$p \leq x_{i+1}, \ldots, p \leq x_n$$$. It means that you have found $$$x_{i+1} - x_i - 1$$$ points contained in exactly $$$i(n-i)$$$ intervals (because there are $$$i$$$ possible left endpoints and $$$n-i$$$ possible right endpoints).
Similarly, the point $$$p = x_i$$$ is contained in $$$i(n-i+1) - 1$$$ intervals (you have to remove interval $$$[x_i, x_i]$$$, which you do not draw).
So you can use a map that stores how many points are contained in exactly $$$x$$$ intervals, and update the map in the positions $$$i(n-i)$$$ and $$$i(n-i+1) - 1$$$.
Complexity: $$$O(n \log n)$$$
Author: TheScrasse
Preparation: TheScrasse
The answer is at most $$$n$$$.
Solve the problem with $$$k = 0$$$.
When is the answer $$$n$$$?
If the answer is not $$$n$$$, how can you buy cards?
Note that there are $$$n$$$ types of cards, so the subsets have size at most $$$n$$$, and the answer is at most $$$n$$$.
If $$$k = 0$$$, you can make subsets of size $$$s$$$ if and only if the following conditions are true:
- the number of cards ($$$m$$$) is a multiple of $$$s$$$;
- the maximum number of cards of some type ($$$x$$$) is $$$\leq m/s$$$.
For a generic $$$k$$$, the answer is $$$n$$$ if you can make the number of cards of type $$$1, \ldots, n$$$ equal. Otherwise, for any choice of number of cards to buy, you can buy them without changing $$$x$$$. It means that you need $$$x \cdot s$$$ cards in total:
- if you have less than $$$x \cdot s$$$ cards, you have to check if you can reach $$$x \cdot s$$$ cards by buying at most $$$k$$$ new cards;
- if you already have $$$x \cdot s$$$ or more cards at the beginning, you have to check if you can make $$$m$$$ a multiple of $$$s$$$.
Complexity: $$$O(n)$$$
Author: TheScrasse
Preparation: TheScrasse
When is the answer $$$0$$$?
Starting from city $$$x$$$ is equivalent to setting $$$a_x = 1$$$.
At some time $$$t$$$, consider the minimal interval $$$[l, r]$$$ that contains all the cities with $$$a_i \leq t$$$ (let's call it "the minimal interval at time $$$t$$$"). If this interval has length $$$> t$$$, the answer is $$$0$$$.
Otherwise, the answer is at least $$$1$$$. A possible construction is visiting the cities in order of $$$a_i$$$ (extending the interval until you reach the city you want to visit). In this way, at time $$$t$$$ you will have conquered all the cities in the minimal interval at time $$$t$$$ (which is short enough), and possibly other cities.
Starting from city $$$x$$$ is equivalent to setting $$$a_x = 1$$$. After this operation, you have to guarantee that, for each $$$i$$$, the minimal interval at time $$$t$$$ is short enough. If this interval is $$$[l, r]$$$ before the operation, $$$x$$$ must be contained in $$$[r-t+1, l+t-1]$$$. So it's enough to calculate and intersect the intervals obtained at $$$t = 1, \ldots, n$$$, and print the length of the final interval.
Another correct solution is to intersect the intervals $$$[i-a_i+1, i+a_i-1]$$$. The proof is contained in the editorial of 2018F3 - Speedbreaker Counting (Hard Version).
Complexity: $$$O(n)$$$
Author: wksni
Preparation: TheScrasse
Solve for a fixed final depth of the leaves.
Which nodes are "alive" if all leaves are at depth $$$d$$$ at the end?
If the final depth of the leaves is $$$d$$$, it's optimal to keep in the tree all the nodes at depth $$$d$$$ and all their ancestors. These nodes are the only ones which satisfy the following two conditions:
- their depth ($$$a_i$$$) is $$$\leq d$$$;
- the maximum depth of a node in their subtree ($$$b_i$$$) is $$$\geq d$$$.
So every node is alive in the interval of depths $$$[a_i, b_i]$$$. The optimal $$$d$$$ is the one contained in the maximum number of intervals.
2018D - Max Plus Min Plus Size
Author: TheScrasse
Preparation: TheScrasse
The optimal subsequence must contain at least one occurrence of the maximum.
Iterate over the minimum, in decreasing order.
You have some "connected components". How many elements can you pick from each component? How to make sure you have picked at least one occurrence of the maximum?
The optimal subsequence must contain at least one occurrence of the maximum ($$$r$$$) (suppose it doesn't; then you can just add one occurrence, at the cost of removing at most two elements, and this does not make your score smaller).
Now you can iterate over the minimum value ($$$l$$$), in decreasing order. At any moment, you can pick elements with values $$$[l, r]$$$. Then you have to support queries "insert pick-able element" and "calculate score".
The pick-able elements make some "connected components" of size $$$s$$$, and you can pick $$$\lceil s/2 \rceil$$$ elements. You can maintain the components with a DSU.
You also want to pick an element with value $$$r$$$. For each component, check if it contains $$$r$$$ in a subsequence with maximum size. If this does not happen for any component, your score decreases by $$$1$$$. All this information can be maintained by storing, for each component, if it contains $$$r$$$ in even positions, and if it contains $$$r$$$ in odd positions.
Complexity: $$$O(n \alpha(n))$$$
2018E1 - Complex Segments (Easy Version), 2018E2 - Complex Segments (Hard Version)
Authors: lorenzoferrari, TheScrasse
Full solution: Flamire
Preparation: franv, lorenzoferrari
Solve for a fixed $$$m$$$ (size of the subsets).
$$$m = 1$$$ is easy. Can you do something similar for other $$$m$$$?
Solve for a fixed $$$k$$$ (number of subsets).
If you have a $$$O(n \log n)$$$ solution for a fixed $$$m$$$, note that there exists a faster solution!
Let's write a function max_k(m)
, which returns the maximum $$$k$$$ such that there exists a partition of $$$k$$$ valid sets containing $$$m$$$ intervals each. max_k
works in $$$O(n \log n)$$$ in the following way (using a lazy segment tree):
- (wlog) $$$r_i \leq r_{i+1}$$$;
- for each $$$i$$$ not intersecting the previous subset, add $$$1$$$ on the interval $$$[l[i], r[i]]$$$;
- as soon as a point belongs to $$$m$$$ intervals, they become a subset;
- return the number of subsets.
For a given $$$k$$$, you can binary search the maximum $$$m$$$ such that max_k(m)
$$$\geq k$$$ in $$$O(n \log^2 n)$$$.
The problem asks for the maximum $$$mk$$$. Since $$$mk \leq n$$$, for any constant $$$C$$$ either $$$m \leq C$$$ or $$$k \leq n/C$$$. For $$$C = (n \log n)^{1/2}$$$, the total complexity becomes $$$O((n \log n)^{3/2})$$$, which is enough to solve 2018E1 - Complex Segments (Easy Version). You can also find max_k(m)
for all $$$m$$$ with a divide and conquer approach, with the same time complexity and a much better constant factor.
Now let's go back to max_k(m)
. It turns out you can implement it in $$$O(n \alpha(n))$$$.
First of all, let's make all the endpoints distinct, in such a way that two intervals intersect if and only if they were intersecting before.
Let's maintain a binary string of size $$$n$$$, initially containing only ones, that can support the following queries:
- set bit in position $$$p$$$ to
0
; - find the nearest
1
to the left of position $$$p$$$.
This can be maintained with DSU, where the components are the maximal intervals containing 100...00
.
Now let's reuse the previous solution (sweeping $$$r$$$ from left to right), but instead of a segment tree we will maintain a binary string with the following information:
- the positions $$$> r$$$ store
1
; - the positions $$$\leq r$$$ store
1
if and only if the value in that position (in the previous solution) is a suffix max.
So the queries become:
- add $$$1$$$ to $$$[l, r]$$$:
-
- $$$r$$$ changes, so you have to set elements in $$$[r'+1, r-1]$$$ to $$$0$$$;
-
- the only other element that changes is the nearest
1
to the left of position $$$l$$$, which does not represent a suffix max anymore.
- the only other element that changes is the nearest
- find the maximum: it's equal to the number of suffix maximums, which depends on $$$r$$$ and on the number of components.
This solution allows us to replace a $$$O(\log n)$$$ factor with a $$$O(\alpha(n))$$$ factor.
Complexity: $$$O(n \alpha(n) \sqrt{n \log n})$$$
2018F1 - Speedbreaker Counting (Easy Version), 2018F2 - Speedbreaker Counting (Medium Version), 2018F3 - Speedbreaker Counting (Hard Version)
Author: TheScrasse
Full solution: Flamire
Preparation: TheScrasse
Suppose you are given a starting city and you want to win. Find several strategies to win (if possible) and try to work with the simplest ones.
The valid starting cities are either zero, or all the cities in $$$I := \cap_{i=1}^n [a_i - i + 1, a_i + i - 1] = [l, r]$$$.
Now you have some bounds on the $$$a_i$$$.
Fix the interval $$$I$$$ and try to find a (slow) DP.
Counting paths seems easier than counting arrays. Make sure that, for each array, you make exactly one path (or a number of paths which is easy to handle).
How many distinct states do you calculate in your DP?
Lemma 1
For a fixed starting city, if you can win, this strategy works:
- [Strategy 1] If there is a city on the right whose distance is $$$t$$$ and whose deadline is in $$$t$$$ turns, go to the right. Otherwise, go to the left.
Proof:
- All constraints on the right hold.
- This strategy minimizes the time to reach any city on the left. So, if any strategy works, this strategy works too.
Corollary
For a fixed starting city, if you can win, this strategy works:
- [Strategy 2] If there is a city whose distance is $$$t$$$ and whose deadline is in $$$t$$$ turns, go to that direction. Otherwise, go to any direction.
Lemma 2
The valid starting cities are either zero, or all the cities in $$$I := \cap_{i=1}^n [i - a_i + 1, i + a_i - 1] = [l, r]$$$.
Proof:
- The cities outside $$$I$$$ are losing, because there exists at least one unreachable city.
- Let's start from any city $$$x$$$ in $$$I$$$, and use Strategy 2.
- You want to show that, for any $$$x$$$ in $$$I$$$, Strategy 2 can visit all cities in $$$I$$$ first, then all the other cities. Then, you can conclude that either all the cities in $$$I$$$ are winning, or they are all losing.
- The interval $$$I$$$ gives bounds on the $$$a_i$$$: specifically, $$$a_i \geq \max(i-l+1, r-i+1)$$$. Then, you can verify that visiting the interval $$$I$$$ first does not violate Strategy 2.
Corollary
If you use Strategy 1, the first move on the right determines $$$l$$$.
$$$\LARGE O(n^4)$$$ DP
Let's iterate on the (non-empty) interval $$$I$$$. Let's calculate the bounds $$$a_i \geq \max(i-l+1, r-i+1)$$$. Note that Strategy 1 is deterministic (i.e., it gives exactly one visiting order for each fixed pair (starting city, $$$a$$$)). From now, you will use Strategy 1.
Now you will calculate the number of pairs ($$$a$$$, visiting order) such that the cities in $$$I$$$ are valid starting cities (and there might be other valid starting cities).
Let's define dp[i][j][k] =
number of pairs ($$$a$$$, visiting order), restricted to the interval $$$[i, j]$$$, where $$$k =$$$ "are you forced to go to the right in the next move?". Here are the main ideas to find the transitions:
- If you go from $$$[i+1, j]$$$ to $$$[i, j]$$$, you must ensure that $$$a_i \geq \max(i-l+1, r-i+1, j-i+1)$$$ (because you visit it at time $$$j-i+1$$$). Also, $$$k$$$ must be $$$0$$$.
- If you go from $$$[i, j-1]$$$ to $$$[i, j]$$$, and you want to make $$$k = 0$$$, you must make $$$a_j = j-i+1$$$. It means that $$$j$$$ was the city that was enforcing you to go to the right.
In my code, the result is stored in int_ans[i][j]
.
Now you want to calculate the number of pairs ($$$a$$$, visiting order) such that the cities in $$$I$$$ are the only valid starting cities. This is similar to 2D prefix sums, and it's enough to make int_ans[i][j] -= int_ans[i - 1][j] + int_ans[i][j + 1] - int_ans[i - 1][j + 1]
.
Since, for a fixed $$$a$$$, the visiting order only depends on the starting city, the number of $$$a$$$ for the interval $$$[i, j]$$$ is now int_ans[i][j] / (j - i + 1)
.
You have solved $$$k \geq 1$$$. The answer for $$$k = 0$$$ is just $$$n^n$$$ minus all the other answers.
$$$\LARGE O(n^3)$$$ DP
In the previous section, you are running the same DP for $$$O(n^2)$$$ different "bound arrays" on the $$$a_i$$$ (in particular, $$$O(n)$$$ arrays for each $$$k$$$). Now you want to solve a single $$$k$$$ with a single DP.
For a fixed $$$k$$$, you can notice that, if you run the DP on an array of length $$$2n$$$ instead of $$$n$$$, the bound array obtained from $$$I = [n-k+1, n]$$$ contains all the bound arrays you wanted as subarrays of length $$$n$$$. So you can run the DP and get all the results as dp[i][i + n - 1][0]
.
$$$\LARGE O(n^2)$$$ DP
You still have $$$O(n^3)$$$ distinct states in total. How to make "bound arrays" simpler?
It turns out that you can handle $$$l$$$ and $$$r$$$ differently! You can create bound arrays only based on $$$r$$$ (and get $$$O(n^2)$$$ distinct states), and find $$$l$$$ using the Corollary of Lemma 2. The transitions before finding $$$l$$$ are very simple (you always go to the left). So a possible way to get $$$O(n^2)$$$ complexity is processing Strategy 1 and the DP in reverse order (from time $$$n$$$ to time $$$1$$$).
Complexity: $$$O(n^2)$$$
1 minute late editorial?
:)))) Too fast
E was such a good problem, great problemset. im so mad i didnt get C earlier though
very interesting problems!!
The goddamn C...
so fast :O
anyway, good songs :D
Thank you so much for the great contest! I loved the problems!
Is it just me or was this Div 2, little too difficult?
i think this is one of the easier ones recently. a and b are pretty simple and c seems hard (atleast it seemed to me) but is actually fairly simple. the rest are pretty standard div2 problems imo
It's just me then I guess. Tbh, I couldn't even solve one lol. I did get the basic idea but could not solve them completely, in first and second question. Anyways thanks for the reply, mate!
i think its a bit easier than other div2 , C usually is harder i find it a bit easy i came up with the idea for it very fast but took me some time to fully solve it and b was easy but i spent a lot of time understanding what they want like it took me 40 min just to understand the problem and solve it in like 15min
To solve the third problem [2018A cards partition], can we use the binary search?
if yes then how to implement the checker function that this size of deck is possible or not
I tried but mine didn't work
i thinking no, because the checker is no montonic fuction
thinking in the primes number and k=0, the 6 can be divide, 7 no, and 8 yes. So the binary search can fail.
I think we can't do binary search on no.of decks
consider how you would make the decks, you would put all the cards with the highest frequency first, and then just greedily put all the cards on top of the lowest deck that you own currently, without making any new decks. then in the end if the last "row" you filled wasn't completely filled, you can try filling it with the k coins you have. you can do that if (sum)%x<=k , where x is the size youre checking. i didnt do it with bs, since i couldnt prove that if x doesnt work then x+1 surely wont work. also you have to check that the partition that you made actually uses all cards, you can check this by seeing if the amount of decks you would have would be atleast the frequency of the most frequent card. i hope i explained it well, if its not clear, just ask. also you can check my solution for details, but its very simple
I tried but got WA on pretest 4, I think search space is not monotonic
A binary search on all numbers from $$$1$$$ to $$$n$$$ doesn't work, because the function isn't monotonic, so if some deck size fails, it's still possible for a bigger one to succeed. Consider a case where you have $$$n=5$$$, $$$k=0$$$, and $$$1$$$ card of each type. Clearly, the only possible deck sizes are $$$1$$$ and $$$5$$$, while $$$2$$$, $$$3$$$ and $$$4$$$ fail, but $$$5>4$$$.
It might be possible to do a binary search on all numbers that divide at least one possible number of cards you can get. I'm not sure about that. In any case, as of now, I'm not aware of any reasonably fast checker function that isn't $$$O(1)$$$ (or easily possible to turn into $$$O(1)$$$ by some precomputation), so this probably isn't a great way to think about the problem.
How much practice do i need i was stuck at B completely.
its an complete observation problem.Second test case is enough to get the answer try to dry run it, you will get the answer
E1,O(n * sqrt(n) * log^2(n)) got a TLE......sad
Rename account maybe
How to implement E.
here. if you have any questions, just ask
the only thing i don't understand is how maxwin affects the answer. I was able to implement everything else.
maxwin[i] is the maximum depth you can reach if you start going down from the i-th vertex. then when checking for a certain depth x, if maxwin[i] is smaller than x, then i must be destroyed, because the i-th vertex can never become a leaf with depth x, and neither can any node in it's subtree, so the entire subtree must be destroyed, since i counted all the vertices by themselves i just remove a vertex one by one
yes yes brilliant thank you. I was trying to do something like this with prefix sums as well but failed miserably.
today's contest just ruined my day (though contest was good)... My submission on C 283251847 is the biggest blunder i had done till now... if i did not tried the binary search && just run a loop my code would be accepted && I might be Cyan today...
when i firstly start to solve this C.. i go for nlogn approach... then make the function 'f' .. but i did not notice function is literally O(1) .. so I could run a O(n) loop...
when i find this 1 minute after contest, I realize this CP is not for me...
(apologies for my poor english)..
The intervals in the editorial of F should be $$$[i - a_i + 1, i + a_i - 1]$$$?
Yes, fixed!
did you mean like that ?
or i didn't get it :(
283258453
It only works if the answer is $$$\geq 1$$$, you need to check if the answer is $$$0$$$ separately.
thank you
An alternative solution for Speedbreaker (Div2D):
There are 4 cases:
Submission: 283247155
I did binary search.
283252824
cool
Wasn't div2 E a lot easier for its position?
C was tooo gorgeous... Gave it the attempt of my life on Codeforces... Learnt a lot, it was like an adventure... Thank you contest×codeforces
literally had the same experience with C, spent like an hour on it and finally got the perfect solution.
also is your profile picture a reference to the AMV tan(x) by lolligerjor?
Ummm, No, didn't know that such thing existed, but my good name is Tanishq, it kinda sounds like TanX, maybe...Yes!
For div2 E i used ternary search on depth...and got wrong answer on test 3.i can not find any wrong case.can anyone hep me 283252293? update: may be this problem can't be solve using ternary search. i got a case
woah too fast (:
Felt like DIV2B was harder than DIV2C :)
Oh wow, my solution to F is completely different. The canonical strategy that I use for an array with a marked interval of possible starting cities is to always go to the city with the shortest deadline and break ties by going left. It seems that the resulting dp is very different (and in particular I don't need to use any division)
Obligatory "thanks mr Radewoosh" comment.
div1E is https://codeforces.net/blog/entry/61331
Why this code is a incorrect !! My intuition was first find maximum element across the array and then if n is even — n/2 and if n is odd — ((n+1)/2)?!
First of all, your n == 3 case should be reconsidered as on test cases:
Your code says
3
but the answer ismax_ele(3) + 2 = 5
As the1 2 3
you can colour 3 and 1 red having 2 red elements + max_ele(3) will give optimal answer as 5. Moreover, you have to consider the max element being in an odd place having all odd indexes counted elements, or being in an even place having all even indexes counted elements.what about this solution-
what do you think the answer should be?
It's shocking that so many people in Div1 solved problem C.
i found D1C to be the easiest div1 problem today, looking at my friendlist, most people had the same feeling. It was obvious to me what to do upon reading the problem. Same for D too, I took less time to mindsolve CD combined than either of AB
D might be *2200,but C is sure under 1900.
And C even easier than B.
so why u are chocked ?
C is easier than usual
I am interested to know your opinion on this. After reading your comment, I spent some more time on problem C, unfortunately I still can't come up with the solution. I haven't looked at the editorial but so far my idea is to consider iterating on the levels of the tree and taking the minimum and for a particular level the answer is N-number of distinct vertices on the path from the root to all the vertices on the current level(I actually figured all this in about ten minutes but I can't think of a way to calculate this in O(n), maybe LCA/inclusion exclusion to avoid double counting I don't know). What do you think one should ideally do in such case? Try for more time or just look at the editorial and be done with it?
Also, I solved DIV1 A in about 30 minutes and got the idea even fairly quick and spent time only to fix a stupid typo. However, if I didn't already know the fact that we only need to know the max element and total sum to figure out if we can arrange the cards, then I don't think I would have been able to solve the problem. So, for DIV1A I would recommend someone to look at the editorial quite early if they weren't able to solve it. So, my general question is how long do you think should one spend time trying to solve a problem before looking at editorial and what was your strategy when you were at specialist/expert level ?
can someone please tell me what's wrong with this soln for Div2-B? it gave WA on pretest 9
maybe integer overflow in the line cnt += (n-1+(i*(n-1-i))); You have taken n and i as int.
My O(n^5) solution (with small constant) passed F1. However it's hard to optimize to O(n^4) or better (Because I solved d1B by a suboptimal solution, which mislead my thinking of F1)