By awoo, history, 3 months ago, translation, In English

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

 
 
 
 
  • Vote: I like it
  • +145
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +33 Vote: I do not like it

exited

»
3 months ago, # |
  Vote: I like it -23 Vote: I do not like it

Thanks A lot

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Finally a contest on the weekend that I can participate. GL everyone.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've been constantly going up and down between blue and purple these days.Good luck to all the contestants.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck Everyone :)

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I love to see the increased participation on the weekends. Good luck everyone.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So why is this round postponed to today? I remember that it was supposed to be held on April 6.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Vladimir vovuh Petrov makes the best questions...excited!!

gl to everyone

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

ooo educational awesome thanks.All good luck today contest.contirubation !!!

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You got downvotes for your previous comments

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

D = Cses Polynomial Queries

"Template": https://codeforces.com/blog/entry/78923?#comment-644972

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +38 Vote: I do not like it

    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, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +3 Vote: I do not like it

interesting round. B is brilliant problem

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Greedyforces

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I LOVEEEEEE SEGMENT TREES

»
3 months ago, # |
  Vote: I like it -6 Vote: I do not like it

I hate this round.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B — cringe C — cringe D — cringe

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Don't forget A — cringe ;)

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          what was your greedy?

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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, # ^ |
            Vote: I like it +3 Vote: I do not like it

          implementation doesnt need to be long: Code

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it -28 Vote: I do not like it

        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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        same lol.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    and cringe E (indeed)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how do i see the solution..?

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had much trouble fitting this solution in constraints

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it +1 Vote: I do not like it

        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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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, # |
  Vote: I like it +1 Vote: I do not like it

C is indeed a good greedy problem and I got AC after six WAs, LMAO

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      same

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the clear explanation.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

Nice.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for D would be appreciated, no idea completely..

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
Rev. 4   Vote: I like it +7 Vote: I do not like it

B took away all the time

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WA problem C because I use int instead of long long int. God I feel so titled right now

»
3 months ago, # |
  Vote: I like it +17 Vote: I do not like it

I was literally one second late for submitting E, otherwise I would become master today (I'm crying

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone use ternary search for C?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is logic behind B?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just a bfs problem using reverse edges

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      @Bungmint u have yt channel??

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      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, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Is BFS really overkill? your solution requires an extra observation

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          that won't give you optimal result every time

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        why can't i use dp here?

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          you can use dp actually with O(nlogn) : dp[count_operation][current_number]

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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   Vote: I like it 0 Vote: I do not like it

                i don't think it will work because no order exists... i tried it and got wrong ans

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Hints :

    • 32768 is 2^15

    • Max Probable Operation : 15

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Max Probable Operation : 15

      why?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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;

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            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, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Do you notice something here?

            1000000000000000 32768
  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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, # |
  Vote: I like it +6 Vote: I do not like it

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, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Try to make the height of all trees be 3

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank you for your replies Bungmint, robostac, yagami__

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +5 Vote: I do not like it

Problem F is an easier version of Doubletrouble from JBOI 2018.

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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, # |
  Vote: I like it +8 Vote: I do not like it

E is quite similar to 811E...

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like 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).

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +5 Vote: I do not like it

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, # |
  Vote: I like it +36 Vote: I do not like it

I have a solution for E that works in $$$\mathcal{O}(n \cdot \alpha (n) + q)$$$.

Solution

Implementation: 153223011

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have linear solution

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    great solution :3

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint for C , I was able to thought that we will make max or max+1 height. but what after.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Any hint regarding how to distribute them

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

I just realized my algorithm for B isn't correct, how did you all solve B?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +4 Vote: I do not like it
»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Is there any mathematical proof for C that only max(h), max(h)+1 are the possible candidates?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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, # |
  Vote: I like it +2 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem c ? can any one explain its solution in details?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +5 Vote: I do not like it

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/153183418

https://codeforces.com/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?

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you help me with why this TLEs for problem B, I'd appreciate your help, thanks in advance.

#include <bits/stdc++.h>
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<pair<int, int>> q; // pair of (number, how many operations done to reach it).
        q.push({X, 0});

        std::vector<bool> done(32768 + 1, false);

        while (!q.empty()) {
            std::pair<int, int> 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   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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/153254977

    probably mine is hackable.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

    4037 is the best to hack, but still fail. Because of early return, the most iteration cnts will be 4146

»
3 months ago, # |
  Vote: I like it +53 Vote: I do not like it

To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Take a look at this submission:Link.

    This guy had already uploaded the solution on his Youtube

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

proof to greedy approach for problem B??

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why I am getting RE on test 7 in problem D? 153304212

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).