By awoo, history, 2 years 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

| Write comment?
»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

exited

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone.

»
2 years 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.

»
2 years 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.

»
2 years 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.

  • »
    »
    2 years 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".

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

gl to everyone

»
2 years 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.

»
2 years 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

  • »
    »
    2 years 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

  • »
    »
    2 years 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

    • »
      »
      »
      2 years 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

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

interesting round. B is brilliant problem

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

Greedyforces

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

I LOVEEEEEE SEGMENT TREES

»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I hate this round.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B — cringe C — cringe D — cringe

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

    Don't forget A — cringe ;)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 years 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

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          what was your greedy?

          • »
            »
            »
            »
            »
            »
            2 years 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

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

          implementation doesnt need to be long: Code

          • »
            »
            »
            »
            »
            »
            2 years 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

      • »
        »
        »
        »
        2 years 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.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        same lol.

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

    and cringe E (indeed)

»
2 years 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.

  • »
    »
    2 years 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 :(.

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had much trouble fitting this solution in constraints

    • »
      »
      »
      2 years 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?

      • »
        »
        »
        »
        2 years 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.

      • »
        »
        »
        »
        2 years 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.

»
2 years 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

  • »
    »
    2 years 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

    • »
      »
      »
      2 years 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.

      • »
        »
        »
        »
        2 years 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

        • »
          »
          »
          »
          »
          2 years 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

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      same

    • »
      »
      »
      2 years 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. :)

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the clear explanation.

      • »
        »
        »
        »
        2 years 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.

»
2 years 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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years 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?

  • »
    »
    2 years 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

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

B took away all the time

»
2 years 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

»
2 years 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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone use ternary search for C?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is logic behind B?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just a bfs problem using reverse edges

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      -

    • »
      »
      »
      2 years 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)$$$

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Is BFS really overkill? your solution requires an extra observation

      • »
        »
        »
        »
        2 years 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}$$$.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        why can't i use dp here?

        • »
          »
          »
          »
          »
          2 years 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]

          • »
            »
            »
            »
            »
            »
            2 years 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

            • »
              »
              »
              »
              »
              »
              »
              2 years 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

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years 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

    • »
      »
      »
      2 years 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

      • »
        »
        »
        »
        2 years 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

    • »
      »
      »
      2 years 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?

    • »
      »
      »
      2 years 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

      • »
        »
        »
        »
        2 years 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)$$$

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Hints :

    • 32768 is 2^15

    • Max Probable Operation : 15

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Max Probable Operation : 15

      why?

      • »
        »
        »
        »
        2 years 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

        • »
          »
          »
          »
          »
          2 years 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;

          • »
            »
            »
            »
            »
            »
            2 years 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.

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

            Do you notice something here?

            1000000000000000 32768
  • »
    »
    2 years 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)$$$.

»
2 years 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 :(

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

    Try to make the height of all trees be 3

  • »
    »
    2 years 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.

  • »
    »
    2 years 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]

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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
      • »
        »
        »
        »
        2 years 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

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

    Thank you for your replies Bungmint, robostac, helios_

  • »
    »
    2 years 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.

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
2 years 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

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

E is quite similar to 811E...

»
2 years 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).

  • »
    »
    2 years 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

    • »
      »
      »
      2 years 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.

»
2 years 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....

»
2 years 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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have linear solution

    • »
      »
      »
      2 years 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

      • »
        »
        »
        »
        2 years 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

        • »
          »
          »
          »
          »
          2 years 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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    great solution :3

»
2 years 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.

  • »
    »
    2 years 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)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Any hint regarding how to distribute them

      • »
        »
        »
        »
        2 years 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.

»
2 years 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?

  • »
    »
    2 years 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.

»
2 years 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!

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it
»
2 years 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...

»
2 years 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?

  • »
    »
    2 years 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.

»
2 years 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.

»
2 years 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

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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

»
2 years 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?

  • »
    »
    2 years 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

»
2 years 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)?

  • »
    »
    2 years 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.

»
2 years 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?

»
2 years 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?

»
2 years 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?

  • »
    »
    2 years 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.

  • »
    »
    2 years 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

»
2 years 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!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

proof to greedy approach for problem B??

»
2 years 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

»
2 years 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).