Educational Codeforces Round 126 [Rated for Div. 2]

Hello Codeforces!

On Saturday, April 9, 2022 at 14:35UTC 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!

• 15 hours ago, # ^ |

  GL bro

• 18 hours ago, # ^ |

  You did not specify positive or negative contribution. XD

  • 18 hours ago, # ^ |

    As a blue, give me positive contribution.

    • 16 hours ago, # ^ |

      Positive contribution unlocks from purple

      • 14 hours ago, # ^ |

        ← Rev. 4 →  

        +21

        As a purple, give me positive contribution. Please

        • 13 hours ago, # ^ |

          we ain't givin contribution to those who beg for it, work hard for contribution

          contribution ain't free bro

      • 13 hours ago, # ^ |

        then you too fall in the negative contribution zone :)

    • 14 hours ago, # ^ |

      da ba dee da ba di

• 21 hour(s) ago, # ^ |

  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".

  • 21 hour(s) ago, # ^ |

    Oh, I see. Thanks for answering!

• 16 hours ago, # ^ |

  problems*

  • 13 hours ago, # ^ |

    bugaboos*

• 10 hours ago, # ^ |

  So, this was said sarcastically?

• 11 hours ago, # ^ |

  I'm not sure but I think also down/up voting others blogs also plays a part of contributions.

• 11 hours ago, # ^ |

  You got downvotes for your previous comments

• 11 hours ago, # ^ |

  ← Rev. 2 →  

  +22

  Problem D is actually even easier, you don't need any range data structures.

  If you have kk open APs which together add a sum ss to some position ii, when moving to i−1i−1, it will add a sum s−(k−starti)s−(k−starti) where startistarti is the number of APs which start at ii.

  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

  • 10 hours ago, # ^ |

    Wow, that's neat

• 11 hours ago, # ^ |

  Don't forget A — cringe ;)

  • 11 hours ago, # ^ |

    I dp-ed A b/c I'm stupid

    • 10 hours ago, # ^ |

      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

      • 10 hours ago, # ^ |

        what was your greedy?

        • 9 hours ago, # ^ |

          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

      • 10 hours ago, # ^ |

        implementation doesnt need to be long: Code

        • 9 hours ago, # ^ |

          Hm, makes sense. Actually was doing exactly same thing, just it code turned out a bit longer, right

    • 10 hours ago, # ^ |

      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.

      • 10 hours ago, # ^ |

        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

• 11 hours ago, # ^ |

  and cringe E (indeed)

• 10 hours ago, # ^ |

  Just go to standing and see .

• 11 hours ago, # ^ |

  I thought it was a segment tree problem, but my implementation was too buggy to finish it in contest time :(.

• 11 hours ago, # ^ |

  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.

  • 10 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Oh, that seems super obvious now that you mention it... Thanks for the help.

  • 10 hours ago, # ^ |

    I had much trouble fitting this solution in constraints

  • 10 hours ago, # ^ |

    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?

    • 9 hours ago, # ^ |

      ← Rev. 2 →  

      0

      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.

    • 9 hours ago, # ^ |

      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.

• 11 hours ago, # ^ |

  What's the solution? i tried using binary search initially to find minimum required days

  • 11 hours ago, # ^ |

    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.

    • 11 hours ago, # ^ |

      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

      • 11 hours ago, # ^ |

        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

  • 11 hours ago, # ^ |

  • 11 hours ago, # ^ |

    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<<min(daysneed(need1,need2),daysneed(need1+2,need2-1))<<endl;

    When need2<need1, you need to consider the possibility that the maximal height may increase by 1:

    if(need1>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<<ans<<endl;
    }

    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. :)

    • 10 hours ago, # ^ |

      Thanks for the clear explanation.

• 11 hours ago, # ^ |

  You can do the operations greedily from right to left.

  • 10 hours ago, # ^ |

    thx..！got it

• 11 hours ago, # ^ |

  Create a from the end.

  • 10 hours ago, # ^ |

    thx..! I overestimate it..

• 10 hours ago, # ^ |

  collecting smaller elements in one array, and bigger elements in another array, because |ai — aj| must be minimum

  • 10 hours ago, # ^ |

    what's the name of the character in your pfp?

    • 10 hours ago, # ^ |

      ← Rev. 2 →  

      0

      Todo Shotoroki

• 10 hours ago, # ^ |

  Just a bfs problem using reverse edges

  • 10 hours ago, # ^ |

    @Bungmint u have yt channel??

  • 10 hours ago, # ^ |

    I thought along these lines for a few mins before realizing it is super overkill.

    If we multiply by 22, it will be divisible by 215=32768215=32768 in at most 1515 steps.

    Also clearly we're trying to clear the lower bits, so adding more 11s in-between doesn't exactly make much sense. So we perform some i≤15i≤15 additions at the start and just find the minimum number of multiplications required to make it ≡0mod32768≡0mod32768 for a total complexity of at most O(nlog2n)O(nlog2⁡n)

    • 10 hours ago, # ^ |

      Is BFS really overkill? your solution requires an extra observation

      • 10 hours ago, # ^ |

        overkill in terms of implementation

    • 10 hours ago, # ^ |

      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??

      • 10 hours ago, # ^ |

        that won't give you optimal result every time

      • 10 hours ago, # ^ |

        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.

    • 9 hours ago, # ^ |

      It can be improved to O(nlogn)O(nlog⁡n) by using a recurrence like ra=min(cnta,1+ra+1)ra=min(cnta,1+ra+1) where cntacnta is minimum number of multiplications to make a≡0(mod32768)a≡0(mod32768).

  • 10 hours ago, # ^ |

    bfs???Seriously??That's not intended solution for sure, there are better solutions

    • 5 hours ago, # ^ |

      Actually this is definitely one of the intended solutions, look at the constraints

  • 8 hours ago, # ^ |

    I did not get the part when you reversed the edges. Can you please elaborate a bit?

  • 5 hours ago, # ^ |

    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

    • 5 hours ago, # ^ |

      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(230)O(32768∗32768)=O(230). 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)O(32768)

      • 5 hours ago, # ^ |

        okay thanks

• 10 hours ago, # ^ |

  ← Rev. 2 →  

  +8

  Hints :

  • 32768 is 2^15

  • Max Probable Operation : 15

  • 9 hours ago, # ^ |

    Max Probable Operation : 15

    • 9 hours ago, # ^ |

      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

      • 8 hours ago, # ^ |

        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;

        • 8 hours ago, # ^ |

          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.

        • 8 hours ago, # ^ |

          Do you notice something here?

          1000000000000000 32768

          • 8 hours ago, # ^ |

            Wow, great explanation thanks

• 10 hours ago, # ^ |

  We can put the number of operations needed to make each number ,i, 1 ... 32768 to 32768 by using the second operation, (2*i)mod 32768, in an array(ans). Then calculate if there is any number j such that j-i + ans[j] < ans[i].if there is then print MIN(j-i + ans[j],32768-i) otherwise MIN(ans[i],32768-i).

7
1 1 1 1 1 1 2

• 10 hours ago, # ^ |

  Try to make the height of all trees be 3

• 10 hours ago, # ^ |

  Water the tree with height 2 on day 1 so you can do something on the even days.

• 10 hours 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]

• 10 hours ago, # ^ |

  Someone please say how to solve 3rd case in 1st test case in 16 days as well.

  • 10 hours ago, # ^ |

    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 8

    Days:

    • 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

    • 9 hours ago, # ^ |

      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

• 4 hours ago, # ^ |

  memset is o(n) and you do it t times

• 9 hours ago, # ^ |

  It is easier than it

• 9 minutes ago, # ^ |

  I did not find a counterexample for my submission. My submission id 153253105 ticket 4346

• 10 hours ago, # ^ |

  I have linear solution

  • 8 hours ago, # ^ |

    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

• 9 hours ago, # ^ |

  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)

  • 9 hours ago, # ^ |

    Any hint regarding how to distribute them

    • 9 hours 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.

• 7 hours ago, # ^ |

  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.

• 8 hours ago, # ^ |

  What was about this contest that it was hard to even make sense of A? I have solved harder problems than this.

• 8 hours ago, # ^ |

  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.

• 7 hours ago, # ^ |

  If value of a1 is equal to 0 your while loop will enter into an infinite loop.

  • 7 hours ago, # ^ |

    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

• 6 hours ago, # ^ |

  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

  • 5 hours ago, # ^ |

    thank you for your great explanation

• 6 hours ago, # ^ |

  ← Rev. 3 →  

  0

  You don't need a segment tree. Your idea will be O(n2)O(n2) if you apply your additions to all kk values at once. Don't do this, this can be done more efficient! Remember how often you applied the addition at positions i+1i+1, i+2i+2, ... i+k−1i+k−1. Let this be mm additions and their total sum at the moment for position ii is SS. When you go from ii to i−1i−1, SS will decrease by mm.

  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.

• 5 hours ago, # ^ |

  cuz hacking is still no end,after hacking will end,every solution will retest

  • 5 hours ago, # ^ |

    okay thanks