Hello Codeforces!
On Apr/09/2022 17:35 (Moscow time) Educational Codeforces Round 126 (Rated for Div. 2) will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Good luck to all the participants!
UPD: Editorial is out
exited
Finally a contest on the weekend that I can participate. GL everyone.
Good luck everyone.
I've been constantly going up and down between blue and purple these days.Good luck to all the contestants.
I love to see the increased participation on the weekends. Good luck everyone.
So why is this round postponed to today? I remember that it was supposed to be held on April 6.
I believe it was because there was a codechef starters at the same time. I also remember the cc admin saying "we are discussing the clashing of the dates with codeforces".
Vladimir vovuh Petrov makes the best questions...excited!!
gl to everyone
problems*
bugaboos*
So, this was said sarcastically?
I have a question,that it doesn't have to do with the contest but i think is not that important to write a blog about it. What i want to ask is how can somebody get negative contribution without commenting or posting a blog? My contribution decreased by 1 point compared to the one i had yesterday but without me doing anything. If anyone knows why this happened,please let me know. Thank you.
You got downvotes for your previous comments
D = Cses Polynomial Queries
"Template": https://codeforces.me/blog/entry/78923?#comment-644972
Problem D is actually even easier, you don't need any range data structures.
If you have $$$k$$$ open APs which together add a sum $$$s$$$ to some position $$$i$$$, when moving to $$$i - 1$$$, it will add a sum $$$s - (k - start_{i})$$$ where $$$start_{i}$$$ is the number of APs which start at $$$i$$$.
So by just storing the number of APs starting from a point (which can be trivially set when we add a new A), we have all the information we need to just simply solve it with a single iteration.
Submission — 153184495
Wow, that's neat
How can you solve D with this technique from Polynomial Queries? I have an AC on CSES and honestly, I don't know how to use it here
once you modify your code to add 1*x, 2*x, 3*x... k*x to a range instead of (1,2,3..k) where x is a constant, then you should be able to solve the problem greedily from right to left
interesting round. B is brilliant problem
Greedyforces
I LOVEEEEEE SEGMENT TREES
I hate this round.
Why ??
B — cringe C — cringe D — cringe
Don't forget A — cringe ;)
I dp-ed A b/c I'm stupid
Just usual A is something simple in few lines, didn't expect it to be a greedy with quite long implementation as for problem A
what was your greedy?
Choosing min (abs(a[i]-a[i-1])+abs(b[i]-b[i-1]), abs(a[i]-b[i-1])+abs(b[i]-a[i-1])), basically what bottom comment does
implementation doesnt need to be long: Code
Hm, makes sense. Actually was doing exactly same thing, just it code turned out a bit longer, right
Actually, comparing to last 2 months rounds A should have been B, B should have been C, C shouldn't have been in this contest B/
My friend solved D and E, couldn't solve C — that tells everything about this contest.
I thought that A was harder than usual, but a simple dp will solve it. C was okay for its place, but B had an interesting observation. I tried to bash it with a solution similar to my solution for this problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=1182
same lol.
and cringe E (indeed)
Is this approach roughly correct for E or am I way off and / or overkilling it?
Lets call components that contain both $$$(1, i)$$$ and $$$(3, i)$$$ but not $$$(2, i)$$$ for some i to be "partitionable".
These partitionable components must be connected by vertical lines spanning all $$$3$$$ rows in some columns, lets call them "partitioning lines".
Suppose a component has multiple "partitioning lines", lets call the rectangle formed by each adjacent pairs of "partitioning lines" of the same component a "partitioning rectangle".
After counting the partition lines and partitioning rectangles, lets go ahead and remove $$$(2, i)$$$ for each partitioning line. Now each partionable component has been partitioned.
Then the answer for a range is (the number of components that are partially or fully covered) — (the number of partitioning lines covered) + (the number of partitioning rectangles that are fully covered).
This can then be calculated using Mo's with a per-operation time of O(1) using a few supplementary arrays to represent the corresponding ranges.
I thought it was a segment tree problem, but my implementation was too buggy to finish it in contest time :(.
It can be done with a segment tree. For a range you should store the number of components in it and the connectivity information among its six vertical border cells. These are enough to merge two adjacent ranges.
Oh, that seems super obvious now that you mention it... Thanks for the help.
I had much trouble fitting this solution in constraints
How do you merge two ranges? I had the same approach but got TLE. My implementation now is to build a new graph with 12 vertices (6 from the left range and 6 from the right) and do BFS on it, which seems to be too slow. Is there a better way to combine ranges?
I had the same problem as you. I've managed to overcome it: https://codeforces.me/contest/1661/submission/153229389 (look at the method "combine").
Basically, the idea is that we can just map either the left-side components to their right-side counterparts or vice versa. If on one side we have only one component, then it is always good to map something to it, since it can potentially merge some components from the other side. If on both sides there are two components, then the mapping direction doesn't matter, because disjointed components on each side will stay disjointed.
Alternatively (that's what I did in the code), you can map from the side with two components. The idea is the same, the direction only matters when there is 1 component on one side and 2 on the other.
Sorry for a messy explanation, it's kinda hard to put it into words. :D If you have any questions, feel free to ask, I'll try to clarify.
Example:
Here, we want to map 7 -> 1, 8 -> 1, because it will merge them.
Here, we can either map 1 -> 7, 2 -> 8 or 7 -> 1, 8 -> 2, it doesn't matter.
C is indeed a good greedy problem and I got AC after six WAs, LMAO
What's the solution? i tried using binary search initially to find minimum required days
I used binary search on the number of days. Note that you first have to make all the elements of the array have the same parity.
i did the same except the part of similar parity. What's the intuition behind it?
you can check my submission sorry for the spaghetti code https://codeforces.me/contest/1661/submission/153212636
Well, noticing that the operation on even days, which is adding two to a height of a tree, does not change the parity, so you must use the odd day operations to equalize the parities
same
My solution is to count how many 1s and 2s you need:
When need2>=need1, it's obvious that you can take one 2 as two 1s and get the best solution:
When need2<need1, you need to consider the possibility that the maximal height may increase by 1:
This is not obvious and you can find this possibility by analysing this case:
10 1 1 1 1 1 1 1 1 1 2
Hope I could help you. Excuse me for my bad English. :)
Thanks for the clear explanation.
I also thought of this initially, that you can calculate how many days you will need because, roughly speaking, after handling parities, 1/3 of your growth requirement will be handled by odd days and 2/3 by even days so we can solve for the final day. But this is a bit annoying at the edge, it needs some precise handling, so I just binary searched instead of explicitly solving these computations.
Many BS problems have direct formulae, but you will find that doing the BS saves a lot of implementation and headache at the cost of a log factor.
Every time i'm promising myself to never ever participate into a edu round, but every time I return back hoping on nice problems
Any hints for D would be appreciated, no idea completely..
You can do the operations greedily from right to left.
thx..!got it
Create a from the end.
thx..! I overestimate it..
Any proof of A why taking smaller element in one array in an index and the bigger for the other array works?
collecting smaller elements in one array, and bigger elements in another array, because |ai — aj| must be minimum
what's the name of the character in your pfp?
B took away all the time
WA problem C because I use int instead of long long int. God I feel so titled right now
I was literally one second late for submitting E, otherwise I would become master today (I'm crying
Did anyone use ternary search for C?
Yeah i saw my friend doing it that way !
What is logic behind B?
Just a bfs problem using reverse edges
-
I thought along these lines for a few mins before realizing it is super overkill.
If we multiply by $$$2$$$, it will be divisible by $$$2^{15} = 32768$$$ in at most $$$15$$$ steps.
Also clearly we're trying to clear the lower bits, so adding more $$$1$$$s in-between doesn't exactly make much sense. So we perform some $$$i \leq 15$$$ additions at the start and just find the minimum number of multiplications required to make it $$$\equiv 0 \mod 32768$$$ for a total complexity of at most $$$O(n \log^2 n)$$$
Is BFS really overkill? your solution requires an extra observation
overkill in terms of implementation
It can be improved to $$$\mathcal{O}(n\log{n})$$$ by using a recurrence like $$$r_a=\min{(cnt_a,1+r_{a+1})}$$$ where $$$cnt_a$$$ is minimum number of multiplications to make $$$a \equiv 0 \pmod{32768}$$$.
why can't i use dp here?
you can use dp actually with O(nlogn) : dp[count_operation][current_number]
in what order will u compute?
dp(i, j) -> dp((i + 1) % 2^15, j + 1)
dp(i, j) -> dp((2 * i) % 2^15, j + 1)
the next state of i can either be greater than current i or less than current i
why does it matter when you do recursive dp? It's hard to find the order when you do iterative dp but in case of recursive dp it doesn't matter
i don't think it will work because no order exists... i tried it and got wrong ans
bfs???Seriously??That's not intended solution for sure, there are better solutions
Actually this is definitely one of the intended solutions, look at the constraints
I did not get the part when you reversed the edges. Can you please elaborate a bit?
i did use bfs and my solution was hacked could you please explain what went wrong ? 153191941 . after the contest i submitted the same solution and i got accepted 153232889
Just a heads up, the hacking phase is still ongoing, so the current test does not include the hack that hacked your solution, so your "accepted" solution is still going to fail. Your solution does not work because you are repeatedly bfs-ing for each number in the array, which would result in $$$O(32768 * 32768) = O(2 ^ {30})$$$. Instead you should bfs once, just starting from 0 and using the "reverse edges" ((j + 1) % 32768 to j and (2 * j) % 32768 to j), which would ensure an asymptotic behavior of $$$O(32768)$$$
Hints :
32768 is 2^15
Max Probable Operation : 15
Max Probable Operation : 15
why?
because you always can multiply a number : X by 2 — 15 times which is X * 2^15 and X * 2^15 mod 32768(2^15) is obviously 0
I'm not a big number theory guy, could you please show more straightforward proof; I can see that it gets rounded back when we multiply by 2 x = 17000 1232 = (17000*2)%32768 2464 = (1232*2)%32768 etc
I don't believe that there will be a factor 2^15;
You can represent any number as sum of power of 2: Let's take 2^14 + 2^12 + 2^1 And when we do second operation: (2*(2^14 + 2^12 + 2^1)) % 2^15 = ((2^15 + 2^13 + 2^2))%2^15 = ((2^13 + 2^2))%2^15 And this way we can get 0 after at most 15 operations, because the minimum element can be 2^0.
Do you notice something here?
Wow, great explanation thanks
We can put the number of operations needed to make each number $$$i$$$, $$$1\text{ to }32768$$$ by using the second operation, $$$(2\times i)\text{ mod }32768$$$, in an array, $$$ans[\text{ }]$$$ . Then calculate if there is any number $$$j$$$ such that $$$j-i$$$ $$$+ans[j] $$$ $$$<$$$ $$$ans[i]$$$.If there is then print $$$\text{MIN}(j-i + ans[j],\text{ 32768}-i)$$$ otherwise $$$\text{MIN}(ans[i],\text{ 32768}-i)$$$.
For
Problem C
, can someone help me understand how the below test case answer is9 days
?I am getting
11
, as all the trees with height 1 can be watered on every odd day(Days: 1,3,5,7,9,11)
.Not sure what I am missing :(
Try to make the height of all trees be 3
Water the tree with height 2 on day 1 so you can do something on the even days.
On day 1 , water the tree of height 2 , so new array becomes => [ 1 , 1 , 1 , 1 , 1 , 1 , 3] ,On day 2 , water the tree of height 1 , so new array becomes => [ 3 , 1 , 1 , 1 , 1 , 1 , 3] ,On day 3 , water the tree of height 1 , so new array becomes => [ 3 , 2 , 1 , 1 , 1 , 1 , 3] ,On day 4 , water the tree of height 1 , so new array becomes => [ 3 , 2 , 3 , 1 , 1 , 1 , 3] ,On day 5 , water the tree of height 2 , so new array becomes => [ 3 , 3 , 3 , 1 , 1 , 1 , 3] ,On day 6 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 1 , 1 , 3] ,On day 7 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 2 , 1 , 3] ,On day 8 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 2 , 3 , 3] ,On day 9 , water the tree of height 2 , so new array becomes => [ 3 , 3 , 3 , 3 , 3 , 3 , 3]
Someone please say how to solve 3rd case in 1st test case in 16 days as well.
dvaravind 3rd case in 1st test case:
Same thing in sorted
2 3 4 4 5 7 8
Days:
Thank you! I was wondering I skipped only one day and made all 8. But I skipped even day and you skipped odd day. This is where I went wrong
Thank you for your replies Bungmint, robostac, helios_
They didn't say we always have to make everything equal to max element of array. Just extra check for max_element + 1 would have passed all testcase . I got this intution by this example which i created during contest Hope it help you.
Testcase Example — 1 1 1 1 1 1 1 1 1 2 (Instead making everything 2 make everything 3) Making everything 2 will cost 17 days while making 3 will cost 13 days . I was so happy when i found it during contest and got Ac.
Problem F is an easier version of Doubletrouble from JBOI 2018.
I don’t know why I’m getting a TLE. I asked me friends and they have kind of a similar implementation and theirs has passed. Could someone please check my solution. Thank you. 153209572
memset is o(n) and you do it t times
OHHHH!! Thanks a lot, I did not see it.
Man!! :(
E is quite similar to 811E...
It is easier than it
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
I've also added 2 new features: Near real-time log streaming and Compressed Parameter editing without using tables.
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
I did not find a counterexample for my submission. My submission id
153253105
ticket4346
Failing Testcase: Ticket 4370
If you fail to find a counter example, set $$$t\_low = t\_high = \infty$$$ so that your code is evaluated on larger number of testcases per input.
thanks
WOW, WHAT A CONTEST, every problem almost destroyed my sanity in a different manner, but I managed to solve them all (ABCD), but to get Expert performance again....
I have a solution for E that works in $$$\mathcal{O}(n \cdot \alpha (n) + q)$$$.
So the idea is this: We will find the number of connected components considering columns upto column $$$i$$$ and store this as $$$p_i$$$. Then the answer to the query is $$$p_r-p_{l-1}+C$$$, where $$$C$$$ is the correction to the count. It will be small, $$$\leq 2$$$, actually. Now let's look at the columns $$$l-1$$$ and $$$l$$$. Count the number of rows where both cells in the columns are free, let it be $$$cnt$$$.
If $$$cnt$$$ is $$$0$$$, $$$C=0$$$ (we didn't undercount).
If $$$cnt$$$ is $$$1$$$ or $$$3$$$, $$$C=1$$$ (we undercounted $$$1$$$ connected component).
If $$$cnt$$$ is $$$2$$$, let's check if the $$$2$$$ rows are adjacent. If yes, then $$$C=1$$$, same reason as before.
If not, then we have to check if we are undercounting by $$$1$$$ or $$$2$$$. The two rows are top and bottom. Now, notice that if they form a single connected component somewhere, there must be a middle row cell that's free inside the intersection of the ranges the top free component and bottom free components cover. Checking if they are a single connected component in a subrange is now the same as checking if there is a free middle row cell in that subrange. Now, I will claim that we are always undercounting by $$$2$$$, unless they form a connected component both in $$$[0,l)$$$ and in $$$[l,r]$$$, in which case we are undercounting by $$$1$$$. Proof left as an exercise to the reader because I'm exhausted.
We can achieve all this in linear time with prefix sums and similar. Implementation (somewhat commented) given below.
Implementation: 153223011
I have linear solution
it seems to me that you have lower_bound in your code. Time complexity of std::lower_bound() is O(log(SIZE)). So your solution isn't linear
Yeah that part can be changed to be linear, it just looks to closest 101 to the left and to the right, which can be looked in o(1) with preprocessing
I also precount components, and represent them as intervals with leftmost and rightmost cells.
Then during query i give answer of these interval counts. But understand that some component can fall apart (1 or 2 of them at the borders). It happens when 101 is at the border and these ones are connected using outer cells from outside (l, r). I consider these cases with some hard coded logic, that looks into leftmost and rightmost 101s
great solution :3
Any hint for C , I was able to thought that we will make max or max+1 height. but what after.
Just that will suffice. The rest is figuring out the best way to water the plants (how to properly distribute the 1's and 2's)
Any hint regarding how to distribute them
If you have too many 2's, then you can split them up into two 1's, however, the opposite isn't true, as when you first count how many 1's are needed, they indicate the parity of the numbers (i.e. how many odds there are, and you can't distribute the addition of 2 to two separate numbers).
How to count the 1's and 2's: if the number is odd, then you can increment the amount of 1's by one, then you increment the amount of 2's by (number / 2). Then you need to find the best result using what was said in the previous paragraph.
I just realized my algorithm for B isn't correct, how did you all solve B?
I upsolved it in the following way. There will be a max of 15 operations because applying the second operation 15 times will make the given number a multiple of 2 ^ 15. Also, all the manageable addition operations should be done initially. The second operation will shift the bitmask of the given number and doing the first operation on the shifted bitmask will take more cost than it is taking while doing those operations initially. Brute force over the initial addition operations up to 15 and then brute force over the second type of operations 15 times and then add whatever is needed to reach the end i.e 2 ^ 15.
Can someone try hacking my submission? It seems like a buggy implementation of what I was attempting, which was this. (Negative numbers show up when there aren't parity differences, but they somehow cancel out) Thanks!
Screencast + explanations :))
Nice!
Couldn't solve the A problem on this one. felt I was getting ever closer to the solution with every submission but reached a dead-end at last. maan!! being unable to solve A, really does a lot of damage to your confidence...
Is there any mathematical proof for C that only max(h), max(h)+1 are the possible candidates?
max(h) + 2 isn't a possible candidate because if all the trees could reach that height, they would have been able to reach max(h) in less time. The mathematical proof is prolly a more general version of this idea.
153217575 Even the solution of D was leaked. This guy got a rank under 1k through cheating. Please improve plag check to detect these types of codes. top_06 is using this kind of template in all contests to avoid plag.
Could someone please explain to me why my solution to B is timing out? I've checked multiple times and it seems like it should run if at most 15*15*32768 = 7*10^6 operations.
https://codeforces.me/contest/1661/submission/153237229
If value of a1 is equal to 0 your while loop will enter into an infinite loop.
Ohhh I see, now it works if I take care of that. can't believe I spent over one hour in contest trying to debug this
how to solve problem c ? can any one explain its solution in details?
It was translated from another language, I'm sorry if something is unclear. note that we do not necessarily want to make everyone equal to the current maximum, sometimes it is a maximum of + 1. For example, 2 1 1 1 1 1 1 1 1 is faster to lead to the form 3 3 3 3 3 3 3 3 3, than to 2 2 2 2 2 2 2 2 2 also note that > max + 1 is obviously bad (instead of increasing each by 2+ from the current maximum, we could just not do it) then we will separately solve the problem for max and for max + 1 and take a smaller value as we solve: alternately, we look at the current growth of the tree and if it needs to be grown to an odd height, we add 1 to CNT 1 — the minimum of operations + 1 that we will have to perform, otherwise it will not be possible to grow the tree to an odd height
for now, we will assume that we will do all the rest of the height +2, we will write the number of such operations in cnt2
that is, the height of the tree 3 that we want to grow to 10 will add 1 to CNT 1 and 3 to cnt2 (1 + 3*2 = 7)
now if cnt1 = cnt2 — the answer is 2 * cnt1 (we do 1 2 1 2 1 2 1 2 1 2, no day is missed, so it can't be more effective)
if cnt1 > cnt2, then the answer is 2 * cnt1 — 1 In short, it will not work, cnt1 tc (we do 1 2 1 2 1 2 1 _ 1 _ 1) — cnt1 is the minimum of operations that we have to do
if cnt2 > cnt1, then the intuitive solution looks like this 1 2 1 2 _ 2 _ 2 _ 2. And we can improve this by replacing some 2 with 1 1
let the sum = cnt1 + 2 * cnt2 — how much height we have to add to the trees.
Then if the sum is divided by 3 — obviously the most effective scheme 1 2 1 2 1 2 1 2 1 2 answer = sum // 3 * 2
If the remainder of the division = 1, then 1 2 1 2 1 is the sum // 3 * 2 + 1
if the remainder of the division is 2, then 1 2 1 2 1 2 _ 2 In the latter case, it will definitely not be shorter, since without the last two we will not reach the sum of the answer sum // 3 * 2 + 2
thank you for your great explanation
I understand that in D we should increment values going from n — 1 to 0. But this simple solution gives O(n^2). Can it be implemented using a segment tree in O(n log n)?
You don't need a segment tree. Your idea will be $$$O(n^2)$$$ if you apply your additions to all $$$k$$$ values at once. Don't do this, this can be done more efficient! Remember how often you applied the addition at positions $$$i+1$$$, $$$i+2$$$, ... $$$i+k-1$$$. Let this be $$$m$$$ additions and their total sum at the moment for position $$$i$$$ is $$$S$$$. When you go from $$$i$$$ to $$$i-1$$$, $$$S$$$ will decrease by $$$m$$$.
I guess this can be quite confusing, compare 153239645 the values
q
,element
andsum
and only consider the casei >= k - 1
at first.The test cases for problem D is weak. I hacked 18 submissions with the same hack case
Does the setter intentionally not providing this kind of corner case?
I was looking at submissions for problem C to see if my solution could be hacked, and I found these two solutions: https://codeforces.me/contest/1661/submission/153183418
https://codeforces.me/contest/1661/submission/153182822
They are identical, but from different accounts; both were submitted during the contest window (clearly cheating). I was wondering if there is a way to report these accounts/submissions; will they automatically be taken care of since the submissions are identical, or is there some other procedure that should be followed?
I think 153213622 is for a total complexity of at most $$$O(\sum a)$$$, so it should be hacked by
however, it only takes 951ms to get the answer. why?
It returned early: if(now==0) return dist[now]; So to hack it we should find the last number that is reachable.
4037 is the best to hack, but still fail. Because of early return, the most iteration cnts will be 4146
To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!
proof to greedy approach for problem B??
Can anyone tell me why I am getting RE on test 7 in problem D? 153304212
check diagnostics
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).