By awoo, history, 3 months ago, translation,

Hello Codeforces!

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

• +145

 » 3 months ago, # |   +33 exited
 » 3 months ago, # |   -23 Thanks A lot
 » 3 months ago, # |   +4 Finally a contest on the weekend that I can participate. GL everyone.
•  » » 3 months ago, # ^ |   0 GL bro
 » 3 months ago, # |   0 Good luck everyone
 » 3 months ago, # |   0 Good luck everyone.
 » 3 months ago, # |   0 I've been constantly going up and down between blue and purple these days.Good luck to all the contestants.
 » 3 months ago, # |   0 Good Luck Everyone :)
 » 3 months ago, # |   +4 I love to see the increased participation on the weekends. Good luck everyone.
 » 3 months ago, # |   0 So why is this round postponed to today? I remember that it was supposed to be held on April 6.
•  » » 3 months ago, # ^ |   +1 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".
•  » » » 3 months ago, # ^ |   0 Oh, I see. Thanks for answering!
 » 3 months ago, # |   0 Vladimir vovuh Petrov makes the best questions...excited!!gl to everyone
•  » » 3 months ago, # ^ |   0 problems*
•  » » » 3 months ago, # ^ |   0 bugaboos*
•  » » 3 months ago, # ^ |   0 So, this was said sarcastically?
 » 3 months ago, # |   0 ooo educational awesome thanks.All good luck today contest.contirubation !!!
 » 3 months ago, # |   +5 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.
•  » » 3 months ago, # ^ |   0 I'm not sure but I think also down/up voting others blogs also plays a part of contributions.
•  » » 3 months ago, # ^ |   0 You got downvotes for your previous comments
 » 3 months ago, # |   +1 D = Cses Polynomial Queries
•  » » 3 months ago, # ^ | ← Rev. 2 →   +38 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
•  » » » 3 months ago, # ^ |   0 Wow, that's neat
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 3 months ago, # ^ |   0 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
 » 3 months ago, # |   +3 interesting round. B is brilliant problem
 » 3 months ago, # |   +3 Greedyforces
 » 3 months ago, # |   +3 I LOVEEEEEE SEGMENT TREES
 » 3 months ago, # |   -6 I hate this round.
•  » » 3 months ago, # ^ |   0 Why ??
 » 3 months ago, # |   0 B — cringe C — cringe D — cringe
•  » » 3 months ago, # ^ |   +4 Don't forget A — cringe ;)
•  » » » 3 months ago, # ^ |   0 I dp-ed A b/c I'm stupid
•  » » » » 3 months ago, # ^ |   +3 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
•  » » » » » 3 months ago, # ^ |   0 what was your greedy?
•  » » » » » » 3 months ago, # ^ |   0 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
•  » » » » » 3 months ago, # ^ |   +3 implementation doesnt need to be long: Code
•  » » » » » » 3 months ago, # ^ |   0 Hm, makes sense. Actually was doing exactly same thing, just it code turned out a bit longer, right
•  » » » » 3 months ago, # ^ |   -28 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.
•  » » » » » 3 months ago, # ^ |   +1 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
•  » » » » 3 months ago, # ^ |   0 same lol.
•  » » 3 months ago, # ^ |   +18 and cringe E (indeed)
 » 3 months ago, # |   0 how do i see the solution..?
•  » » 3 months ago, # ^ |   0 Just go to standing and see .
 » 3 months ago, # | ← Rev. 2 →   0 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.
•  » » 3 months ago, # ^ |   0 I thought it was a segment tree problem, but my implementation was too buggy to finish it in contest time :(.
•  » » 3 months ago, # ^ |   +35 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.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Oh, that seems super obvious now that you mention it... Thanks for the help.
•  » » » 3 months ago, # ^ |   0 I had much trouble fitting this solution in constraints
•  » » » 3 months ago, # ^ |   0 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?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +1 I had the same problem as you. I've managed to overcome it: https://codeforces.com/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.
•  » » » » 3 months ago, # ^ |   +1 Example: 1 - 7 1 - x 1 - 8 Here, we want to map 7 -> 1, 8 -> 1, because it will merge them. 1 - 7 x - x 2 - 8 Here, we can either map 1 -> 7, 2 -> 8 or 7 -> 1, 8 -> 2, it doesn't matter.
•  » » » » » 3 months ago, # ^ |   0 That's clever. Thanks for explanation!
 » 3 months ago, # |   +1 C is indeed a good greedy problem and I got AC after six WAs, LMAO
•  » » 3 months ago, # ^ |   0 What's the solution? i tried using binary search initially to find minimum required days
•  » » » 3 months ago, # ^ |   +6 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.
•  » » » » 3 months ago, # ^ |   0 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.com/contest/1661/submission/153212636
•  » » » » » 3 months ago, # ^ |   0 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
•  » » » 3 months ago, # ^ |   0 same
•  » » » 3 months ago, # ^ |   +12 My solution is to count how many 1s and 2s you need: ll need1=0,need2=0; for(int i=1;i<=n;i++){ need1+=(maxv-heit[i])%2; need2+=(maxv-heit[i])/2; } When need2>=need1, it's obvious that you can take one 2 as two 1s and get the best solution: ll tmp=(need2-need1)/3; need2-=tmp; need1+=tmp*2; cout<need2){ ll ans=daysneed(need1,need2),tmp1=n-need1,tmp2=need1+need2; need1=tmp1; need2=tmp2;//this is how need1 and need2 behave after increasing the maximal height by 1 ll tmp=(need2-need1)/3; need2-=tmp; need1+=tmp*2; ans=min(ans,min(daysneed(need1,need2),daysneed(need1+2,need2-1))); cout<
•  » » » » 3 months ago, # ^ |   0 Thanks for the clear explanation.
•  » » » » 3 months ago, # ^ |   +8 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.
 » 3 months ago, # |   0 Nice.
 » 3 months ago, # |   0 Every time i'm promising myself to never ever participate into a edu round, but every time I return back hoping on nice problems
 » 3 months ago, # |   0 Any hints for D would be appreciated, no idea completely..
•  » » 3 months ago, # ^ |   +8 You can do the operations greedily from right to left.
•  » » » 3 months ago, # ^ |   0 thx..！got it
•  » » 3 months ago, # ^ |   0 Create a from the end.
•  » » » 3 months ago, # ^ |   +3 thx..! I overestimate it..
 » 3 months ago, # |   +4 Any proof of A why taking smaller element in one array in an index and the bigger for the other array works?
•  » » 3 months ago, # ^ |   0 collecting smaller elements in one array, and bigger elements in another array, because |ai — aj| must be minimum
•  » » » 3 months ago, # ^ |   +1 what's the name of the character in your pfp?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Todo Shotoroki
 » 3 months ago, # | ← Rev. 4 →   +7 B took away all the time
•  » » 3 months ago, # ^ |   0 me too
 » 3 months ago, # |   0 WA problem C because I use int instead of long long int. God I feel so titled right now
 » 3 months ago, # |   +17 I was literally one second late for submitting E, otherwise I would become master today (I'm crying
 » 3 months ago, # |   0 Did anyone use ternary search for C?
•  » » 3 months ago, # ^ |   0 Yeah i saw my friend doing it that way !
 » 3 months ago, # |   0 What is logic behind B?
•  » » 3 months ago, # ^ |   0 Just a bfs problem using reverse edges
•  » » » 3 months ago, # ^ |   +5 @Bungmint u have yt channel??
•  » » » 3 months ago, # ^ |   +25 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)$
•  » » » » 3 months ago, # ^ |   +11 Is BFS really overkill? your solution requires an extra observation
•  » » » » » 3 months ago, # ^ |   0 overkill in terms of implementation
•  » » » » 3 months ago, # ^ |   0 can we multiple with 2 until it becomes nearest to one of the powers of 2 and then add ones to it so that it becomes power of 2 and then try to make it 2 ^ 15??
•  » » » » » 3 months ago, # ^ |   0 that won't give you optimal result every time
•  » » » » » 3 months ago, # ^ |   0 Consider a number , increment it by 1 and multiply it by 2 p times u get(x + 1) . 2 ^ p = x * 2 ^ p + 2 ^ p The operations required = p + 1 say if we multiplied x first by 2 p times we would have got x = x * 2 ^ p now to get the same previous number we need 2 ^ p more additions which will require in total p + 2 ^ p operations. You can get an idea why incrementing first and then multiplying by 2 helps us.
•  » » » » 3 months ago, # ^ |   0 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}$.
•  » » » » 3 months ago, # ^ |   0 why can't i use dp here?
•  » » » » » 3 months ago, # ^ |   0 you can use dp actually with O(nlogn) : dp[count_operation][current_number]
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » » 3 months ago, # ^ |   0 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
•  » » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 i don't think it will work because no order exists... i tried it and got wrong ans
•  » » » 3 months ago, # ^ |   +5 bfs???Seriously??That's not intended solution for sure, there are better solutions
•  » » » » 3 months ago, # ^ |   +3 Actually this is definitely one of the intended solutions, look at the constraints
•  » » » 3 months ago, # ^ |   0 I did not get the part when you reversed the edges. Can you please elaborate a bit?
•  » » » 3 months ago, # ^ |   0 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
•  » » » » 3 months ago, # ^ |   0 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)$
•  » » » » » 3 months ago, # ^ |   0 okay thanks
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 Hints : 32768 is 2^15 Max Probable Operation : 15
•  » » » 3 months ago, # ^ |   0 Max Probable Operation : 15why?
•  » » » » 3 months ago, # ^ |   0 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
•  » » » » » 3 months ago, # ^ |   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 etcI don't believe that there will be a factor 2^15;
•  » » » » » » 3 months ago, # ^ |   +4 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.
•  » » » » » » 3 months ago, # ^ |   +3 Do you notice something here? 1000000000000000 32768 1000000000000000 32768 0100001001101000 17000 0000010011010000 1232 0000100110100000 2464 0001001101000000 4928 0010011010000000 9856 0100110100000000 19712 0001101000000000 6656 0011010000000000 13312 0110100000000000 26624 0101000000000000 20480 0010000000000000 8192 0100000000000000 16384 
•  » » » » » » » 3 months ago, # ^ |   0 Wow, great explanation thanks
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 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)$.
 » 3 months ago, # |   +6 For Problem C, can someone help me understand how the below test case answer is 9 days ? 7 1 1 1 1 1 1 2 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 :(
•  » » 3 months ago, # ^ |   +8 Try to make the height of all trees be 3
•  » » 3 months ago, # ^ |   +5 Water the tree with height 2 on day 1 so you can do something on the even days.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +13 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]
•  » » 3 months ago, # ^ |   0 Someone please say how to solve 3rd case in 1st test case in 16 days as well.
•  » » » 3 months ago, # ^ |   +4 dvaravind 3rd case in 1st test case: 7 2 5 4 8 3 7 4 Same thing in sorted 2 3 4 4 5 7 8Days: 2 3 4 4 5 7 8 — Day 0 2 3 4 4 5 8 8 — Day 1 2 3 4 4 7 8 8 — Day 2 2 3 4 4 8 8 8 — Day 3 2 3 4 6 8 8 8 — Day 4 2 4 4 6 8 8 8 — Day 5 2 6 4 6 8 8 8 — Day 6 2 7 4 6 8 8 8 — Day 7 4 7 4 6 8 8 8 — Day 8 4 8 4 6 8 8 8 — Day 9 6 8 4 6 8 8 8 — Day 10 7 8 4 6 8 8 8 — Day 11 7 8 6 6 8 8 8 — Day 12 8 8 6 6 8 8 8 — Day 13 8 8 8 6 8 8 8 — Day 14 8 8 8 6 8 8 8 — Day 15 (Skip) 8 8 8 8 8 8 8 — Day 16
•  » » » » 3 months ago, # ^ |   +3 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
•  » » 3 months ago, # ^ |   +1 Thank you for your replies Bungmint, robostac, yagami__
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 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.
 » 3 months ago, # |   +5 Problem F is an easier version of Doubletrouble from JBOI 2018.
 » 3 months ago, # |   +5 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
•  » » 3 months ago, # ^ |   0 memset is o(n) and you do it t times
•  » » » 3 months ago, # ^ |   0 OHHHH!! Thanks a lot, I did not see it.Man!! :(
 » 3 months ago, # |   +8 E is quite similar to 811E...
•  » » 3 months ago, # ^ |   0 It is easier than it
 » 3 months ago, # |   +13 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).
•  » » 3 months ago, # ^ |   0 I did not find a counterexample for my submission. My submission id 153253105 ticket 4346
•  » » » 3 months ago, # ^ |   0 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.
•  » » » » 3 months ago, # ^ |   0 thanks
 » 3 months ago, # |   +5 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....
 » 3 months ago, # |   +36 I have a solution for E that works in $\mathcal{O}(n \cdot \alpha (n) + q)$. SolutionSo 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
•  » » 3 months ago, # ^ |   0 I have linear solution
•  » » » 3 months ago, # ^ |   +9 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
•  » » » » 3 months ago, # ^ |   +3 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
•  » » » » » 3 months ago, # ^ |   0 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
•  » » 3 months ago, # ^ |   0 great solution :3
 » 3 months ago, # |   0 Any hint for C , I was able to thought that we will make max or max+1 height. but what after.
•  » » 3 months ago, # ^ |   0 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)
•  » » » 3 months ago, # ^ |   0 Any hint regarding how to distribute them
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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.
 » 3 months ago, # |   0 I just realized my algorithm for B isn't correct, how did you all solve B?
•  » » 3 months ago, # ^ |   +1 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.
 » 3 months ago, # |   0 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!
 » 3 months ago, # |   +4
•  » » 3 months ago, # ^ |   +5 Nice!
 » 3 months ago, # |   +5 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...
•  » » 3 months ago, # ^ |   0 What was about this contest that it was hard to even make sense of A? I have solved harder problems than this.
 » 3 months ago, # |   0 Is there any mathematical proof for C that only max(h), max(h)+1 are the possible candidates?
•  » » 3 months ago, # ^ |   +12 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.
 » 3 months ago, # |   +2 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.
 » 3 months ago, # |   0 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.com/contest/1661/submission/153237229
•  » » 3 months ago, # ^ |   0 If value of a1 is equal to 0 your while loop will enter into an infinite loop.
•  » » » 3 months ago, # ^ |   0 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
 » 3 months ago, # |   0 how to solve problem c ? can any one explain its solution in details?
•  » » 3 months ago, # ^ |   +4 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 heightfor now, we will assume that we will do all the rest of the height +2, we will write the number of such operations in cnt2that 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 doif 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 1let 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 * 2If the remainder of the division = 1, then 1 2 1 2 1 is the sum // 3 * 2 + 1if 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
•  » » » 3 months ago, # ^ |   0 thank you for your great explanation
 » 3 months ago, # |   0 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)?
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 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 and sum and only consider the case i >= k - 1 at first.
 » 3 months ago, # |   0 i don't know why my solution was hacked problem B 153191941 after the contest i submitted the same solution and i got accepted . 153232889 can someone help me understand why
•  » » 3 months ago, # ^ |   0 cuz hacking is still no end,after hacking will end,every solution will retest
•  » » » 3 months ago, # ^ |   0 okay thanks
 » 3 months ago, # | ← Rev. 2 →   0 The test cases for problem D is weak. I hacked 18 submissions with the same hack case 300000 150000 1e12 1e12 1e12 ..... Does the setter intentionally not providing this kind of corner case?
 » 3 months ago, # | ← Rev. 3 →   +5 I was looking at submissions for problem C to see if my solution could be hacked, and I found these two solutions: https://codeforces.com/contest/1661/submission/153183418https://codeforces.com/contest/1661/submission/153182822They 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?
 » 3 months ago, # | ← Rev. 2 →   0 Can you help me with why this TLEs for problem B, I'd appreciate your help, thanks in advance. #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; auto&& solve = [=](int64_t X) -> int64_t { std::queue> q; // pair of (number, how many operations done to reach it). q.push({X, 0}); std::vector done(32768 + 1, false); while (!q.empty()) { std::pair u = q.front(); q.pop(); done[u.first] = true; if (u.first == 0) // if the number (u.first) is congruent to 0 (mod 32768). return u.second; // return the number of operations done to reach it. for (auto nxt : {(u.first + 1) % 32768, (u.first * 2) % 32768}) if (!done[nxt]) q.push({nxt, u.second + 1}); } return -1; // shouldn't reach here. }; while (N--) { int X; cin >> X; cout << solve(X) << ' '; } } 
 » 3 months ago, # | ← Rev. 2 →   0 I think 153213622 is for a total complexity of at most $O(\sum a)$, so it should be hacked by 32768 32767 32767 32767 ..... however, it only takes 951ms to get the answer. why?
•  » » 3 months ago, # ^ |   0 the submission you mentioned looks like mine (i submitted it after the contest), and mine only passes if I use the "Ofast" optimization option.1) don't know why the submission you mentioned is faster than mine.2) don't know why both submissions pass.this is my code: https://codeforces.com/contest/1661/submission/153254977probably mine is hackable.
•  » » 3 months ago, # ^ |   0 It returned early: if(now==0) return dist[now]; So to hack it we should find the last number that is reachable.
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 4037 is the best to hack, but still fail. Because of early return, the most iteration cnts will be 4146
 » 3 months ago, # |   +53 To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!