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

Hello Codeforces!

On Apr/22/2022 17:35 (Moscow time) Educational Codeforces Round 127 (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
  • +241
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it -41 Vote: I do not like it

As a specialist give me positive contribution pls

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

Contest rain,,,, Contest week....

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

hopefully will be as hard as the div 4

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

Coders after attempting div 4 round: Coding is not too tough ;-;

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

That's great! So many rounds :) Good luck everyone on the round!

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

It's raining, contest hopefully, I end up with a positive rating change after this week.

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

Wow, Educational Codeforces Round 0x7f! Wish to have fun and high rating!

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

    It's impossible to have fun writing educational...

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

      It doesn't matter. As for me, getting a high rating and having something new to learn are both great. Btw, be confident and back to Master! Good luck!

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

        Thank you! Good luck to you too!

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

Hope I turn pupil this round.

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

waiting for it

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

So Many contests back to back . I like it picasso

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

contest sleep again contest and again sleep....

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

It always astonishes me that someone can AK edu faster than I AK div4...Holy....

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

Happy to say that this is my first unrated edu round :yaaay:

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

ContestForces

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

I hope I can solve one problem

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

After div 4 I guess the first problem today in Edu is harder than the latest problem in div 4 yesterday :)

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

This will be the first edu round I join!

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

From question's perspective, is there any difference between normal and edu rounds?

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

What should we do when we feel very demotivated after wrong answer on Test 2?

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

    Try to find corner case like me, if you r confident that your approach is correct, otherwise try to change the idea.. :|

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

Thank you for the round! Will reach master finally (If I don’t get hacked)

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

Enjoyed the contest, interesting problems and ideas, especially F.

»
3 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

-I gonna participate in edu today! That`s my first time !

-Are you sure you wanna give up programming today?

-Umm what?

-Never mind, my child, never mind

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

Something was changed in the way the authentication (or something else?) works. I cannot use CF tool, login fails.

Any workarround available?

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

    I have my tool to download statements and test cases (no auth involved, just fetch the pages) and it started failing today too. I think it's not auth related, maybe some URLs changed.

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

    It is because cf api wasn’t working during contest

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

How to Solve D?

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

    Note that any x[i] that is between min(a[]) and max(a[]) can be placed somewhere for free, since there exist two a[i],a[i+1] where that x[i] fits in between.

    So we are left with some x[i] like 1...min(a[])-1, and max(a[])+1,...,x

    The smaller ones (if some exist) can be placed in front of the first element, after the last element, or between the two elements with value min(a[]).

    Same goes for the greater ones.

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

      So then we just look over all possible locations of smaller and greater ones, right?

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

        Well, if min(a[]>1), then we have placed the x with value equal min(a[]) next to that min a[i]. Then we can put the remaining x[] (with values 1...min(a[]-1) between those two elements with value min(a[]), for the cost of 2*(min(a[])-1).

        The same goes for the bigger elements, if x>max(a[]).

        see 154578729

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

          Hi, wouldnt this fail for x < min(a[i]) though? I did exactly this in the contest, But made an exception for this case which resulted in WA.

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

            You probably got confused because of the assumption that the minimum element always occurs at least twice.

            Think of a test like this: $$$[20, 5, 6, 20]$$$, having $$$x = 3$$$. You can see that the sum of absolute differences equals $$$30$$$ before inserting the extra values.

            Now, according to spookywooky's code, $$$min(20 - 1, 20 - 1, (5 - 1) * 2) = 8$$$ is added to the final answer, which is clearly the optimal solution.

            You can think of adding the absolute difference between $$$2$$$ integers to the solution as if you decreased the maximum of these $$$2$$$ integers to the minimum (made them both equal).

            In the previous example, $$$5$$$ is the minimum and it only occurred once. However, after adding the absolute difference between $$$5$$$ and $$$6$$$, you can now assume that there are now $$$2$$$ occurrences of the number $$$5$$$ (which is the minimum) in the array.

            The same goes for the segment from maximum $$$+$$$ $$$1$$$ to $$$x$$$.

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

    notice that you need to find only min max from given array
    then you need to handle ranges 1..(min-1) and (max+1)..x
    so you can put them in the beginning, in the end or between some a[i]-a[i] pair if a[i] lies between given 1..x range

»
3 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Solved 5 DIV2 tasks for the first time

low asymptotics tasks be like

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

For me D is painful. If you have a clean solution, then you are doing great. But I was using a complicated case solution and didn't resolve all cases correctly during the contest. I thought my case analysis was correct, but I kept getting WA on test 2.

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

    My solution is clean :D

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

    During the contest, I observed that inserting v to an array is free if min(array) <= v <= max(array), but I didn't realize that we can just consider inserting 1 and x. Instead, I considered inserting all numbers in [1, x] and ended up having so many corner cases (discussing the relation between [1, x] and [min(array), max(array)]).

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

Idea for D ?

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

    Hint – you can just add 1 and x to the given array, not all of the numbers

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

      Basically you have 3 options:

      1) Add 1 after minimum element

      2) Add 1 before first element

      3) Add 1 after last element

      Other options can't be optimal

      Same for the x and maximum

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

    My approach

    Observation Define initial score is the score you get for not putting any number

    1. For any 2 adjacent elements, putting any numbers that lies between them won't affect the initial score

    2. Based on 1., we can put as many number as possible that we haven't put that still within the range between two elements

    3. Now if we observe carefully, all numbers within the min element and max element of the array will be put accordingly. So we're only left with $$$1 .. min-1$$$ and $$$max+1 .. x$$$ (just need to take care when $$$x$$$ is smaller than $$$max$$$)

    The rest is implementation

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

Who can really prove the greedy solution for D ?

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

    When you put $$$x$$$ between $$$a$$$ and $$$b$$$ (assume $$$x>a>b$$$), the difference turns into $$$(x-a) + (x-b)$$$ where it used to be $$$a-b$$$. So the difference delta is $$$delta=(x-a)+(x-b)-(a-b)=2(x-a)$$$. Since when you put $$$x$$$ $$$(x>max)$$$ between any two elements the delta can only be greater or equal than $$$2(x-max)$$$ and you can actually achieve that equal, it is the optimal solution. Then just simply consider the case that you don't put it between any two (meaning that you put it at the beginning or at the end).

»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

What do you think? Why in B problem's description there is no such case "you don't have to change every number". Many coders thought we have to change every element and we have one unsuccessful attempt xD

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

    no more than once:

    I thought it was clear? Idk

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

    Its clearly written in the second paragraph bro : " For the i-th point, it can be either xi−1, xi or xi+1"

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

In problem E, why the output in the first example is 16?

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

In problem E

Can someone explain me what is the different between two codes? 154575910 and 154578191

Why one of them accept and the other not.

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

    You are not swapping the subtrees in the first one.

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

      I am getting the largest possible lexicography string in every subtree by using solve

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

        If I am not mistaken it seems like you are just swapping the characters of the children, and not the entire subtrees.

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

          Yeah but I cant find the case that will make this fail.

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

How to solve C?

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

    I did with some wiered two pointer like aproach.

    Note that we can never buy more sugar than on first day. So create prefix sums of the sorted prices, and binary search the number of shops we can visit on day 0.

    Then we can buy the same amount of sugar maybe for some more days. Calculate this number as $$$(x-sum)/cnt$$$

    So after that number of days, x is not enough to buy that number of sugars any more. So decrement the number of sugar until x is enough to pay that new number of sugars. Then the same repeats... until number of sugars is zero.

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

    Answer this question : At what days range we can buy $$$k$$$ number of items? (For each $$$1 \le k \le n$$$)

    To answer that question, we can use binary search. We can buy $$$k$$$ candies at day $$$d$$$ if $$$(a_1 + ... + a_k) + k \times d \le x$$$ (in other words, our money csn buy $$$k$$$ number of items)

    We can use greedy to prioritize the cheapest item first and use prefix sum to count $$$a_1 + .. + a_k$$$

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

    Sort the array from cheapest to most expensive. Go from left to right through the array to calculate a prefix sum up to this point. Also store in another array how many days you would be able to buy the with current configuration $$$(x-sum[i])/cnt[i] + 1$$$. Then go backwards through the array $$$i=n\dots 1$$$: you buy all packs you haven't already bought with the previous configuration: $$$(cnt[i+1] - cnt[i]) * i$$$

    154535703

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

Despite the slow start, I am happy that I could solve three problems for the first time in Div 3 or higher.

Not sure how I did better today than yesterday's div 4, maybe it was a good warmup.

Thanks for hosting.

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

This contest be like:

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

such a fun contest. really enjoyed C and D

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

C is good.

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

GREAT CONTEST..I REALLY ENJOY ..PROBLEM C IS NICE

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

How to do E?

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

    Answer is 2^x, where x = number of nodes such that it's left and right subtrees aren't isomorphic.

    Isomorphic means that you can get the subtrees equal by using some sequence of swaps.

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

    Sort each subtree for each node according to the preorder string, starting from the leaves. Lexicographically smaller subtree to the left, greater to the right. Then count the amount $$$K$$$ of nodes for which both subtrees form different preorder strings. Answer is $$$2^K$$$

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

    check on each node if the string of left children is same as right children. if not, multiply the result by 2. construct string of each node with s[node] + min(child string) + max(child string) to avoid duplication.

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

      Your construction not primarily avoids duplication (I mean it does, but that changes the asymptotics from $$$O(n \cdot 2^n)$$$ to $$$O(2^n)$$$ which is not so important). But more importantly, it sorts the subtrees.

      Just wanted to point that out. It is more elegant than my solution above your post though!

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

      can you explain how it is working

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

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

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.

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

weird ""mathy"" problemset but ok I'll take it (upd: i dont)

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

HI everyone~ I have given two contest but can not solve a single questions. Is CP is not for me?

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

    Do you have former experience in math contests? If not, then I think it is normal to not solve any questions for the first few times due to various reasons like competition anxiety and newness. If it happens repeatedly and you do not find joy in doing it then it's not for you. I am still finding out myself...

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

      NO, I do not have experience in math contest, thank you for your reply.

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

        Try solving 800-rating problems in the archive. I would suggest to aim to solve ~20 of them, and then you'll feel confident about solving at least one problem in the contest (easiest one is at A level). If you can't solve an archived problem in 30-min — check out tutorial for it.

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

          okay, I will look for it.

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

            You can try to go at the problems of the recent Div4 contest :)

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

    CP is hard to start with but once you will do some questions, you will learn how to think and it will be a lot more fun. Just do questions close to your difficulty level. Maybe these problems were hard for you. You can try some div3 problems.

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Felt confident thinking I could do E but then realized why the first test case was 16 and said nope! Anyone else feel the same? Haha

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

    my confident ass, trying to count the number of As and Bs to determine if the string would be unique or not only to get to know, in first test case, that it won't be enough they still can be unique.

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

Video Solutions : A-D

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

In problem E, I misunderstood the problem and think the input string is "preorder string" then get WA...

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

Any ideas and hints to solve Problem C?

I tried to brute-force it but got a TLE on tc 3.

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

    You have to sort the array, and then for each i, calculate the maximum number of days you can buy only from the first i shops in the sorted array. This can be done in this way: (x — pre[i])/i, where pre is the prefix sum till i

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

When will the rating be changed? The next contest will start. :[

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

why this sub for c gives TLE 154641815 ? bug or bad idea

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

    "STEV" in your code is so cool, how can you make it?

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

Every time I participate to such a round I always get ripped off. Gotta tip my hat to those that make these tasks for managing that.

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

Can anyone point out why I'm getting TLE on TestCase 7, in my submission 154567604 for Problem C ?

For each shop, I am doing Binary Search to find the no. of days. Isn't, O(n*logn) sufficient?

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

    You are using Array.sort, in Java it runs on Quick Sort whose worst case Time Complexity is O(n2)

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

      Thank you for the reply. Can’t believe made same mistake again. (Have had a similar situation few contests back)

      :(

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

When will the editorials be uploaded?

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

Hello I cheated from a classmate without him knowing. I want to correct my mistake and admit to what I have done wrong because I got the rating increase while the other person didn't. I hope admins could make this right.

»
3 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).