By awoo, history, 2 months ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

• +241

 » 2 months ago, # |   -41 As a specialist give me positive contribution pls
•  » » 2 months ago, # ^ |   +16 Positive contribution unlocks from...
•  » » » 2 months ago, # ^ |   0 ...
 » 2 months ago, # |   +19 Contest rain,,,, Contest week....
 » 2 months ago, # |   -12 hopefully will be as hard as the div 4
 » 2 months ago, # | ← Rev. 2 →   +25 Coders after attempting div 4 round: Coding is not too tough ;-;
 » 2 months ago, # |   0 That's great! So many rounds :) Good luck everyone on the round!
 » 2 months ago, # | ← Rev. 2 →   0 It's raining, contest hopefully, I end up with a positive rating change after this week.
 » 2 months ago, # |   +47 Wow, Educational Codeforces Round 0x7f! Wish to have fun and high rating!
•  » » 2 months ago, # ^ |   +22 It's impossible to have fun writing educational...
•  » » » 2 months ago, # ^ |   +22 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!
•  » » » » 2 months ago, # ^ |   +5 Thank you! Good luck to you too!
 » 2 months ago, # |   0 Hope I turn pupil this round.
•  » » 2 months ago, # ^ |   +2 good luck
 » 2 months ago, # |   0 Excited.
•  » » 2 months ago, # ^ |   0 Dont get too excited cuz today is Physics monthly Test and you know what happens next. Last time I got 26/100 :D.
 » 2 months ago, # |   0 waiting for it
 » 2 months ago, # |   0 So Many contests back to back . I like it picasso
 » 2 months ago, # |   +4 contest sleep again contest and again sleep....
 » 2 months ago, # |   0 It always astonishes me that someone can AK edu faster than I AK div4...Holy....
 » 2 months ago, # |   +25 Happy to say that this is my first unrated edu round :yaaay:
 » 2 months ago, # |   -21 Don't you think we need more Div.3 ??
 » 2 months ago, # |   +5 ContestForces
 » 2 months ago, # |   0 good luck everyone
 » 2 months ago, # |   0 back to back contests and that too on codeforces is just amazing!
 » 2 months ago, # |   0 I hope to turn pupil this round
•  » » 2 months ago, # ^ |   0 I hope too
 » 2 months ago, # | ← Rev. 2 →   0 I hope I can solve two problems lol
 » 2 months ago, # |   0 I hope I can solve one problem
 » 2 months ago, # |   +4 After div 4 I guess the first problem today in Edu is harder than the latest problem in div 4 yesterday :)
 » 2 months ago, # |   +6 This will be the first edu round I join!
•  » » 2 months ago, # ^ |   +6
 » 2 months ago, # |   -9 From question's perspective, is there any difference between normal and edu rounds?
 » 2 months ago, # |   0 What should we do when we feel very demotivated after wrong answer on Test 2?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Try to find corner case like me, if you r confident that your approach is correct, otherwise try to change the idea.. :|
 » 2 months ago, # |   +5 Thank you for the round! Will reach master finally (If I don’t get hacked)
 » 2 months ago, # |   +3 Enjoyed the contest, interesting problems and ideas, especially F.
 » 2 months ago, # | ← Rev. 3 →   +1 -I gonna participate in edu today! Thats my first time !-Are you sure you wanna give up programming today?-Umm what?-Never mind, my child, never mind
 » 2 months ago, # | ← Rev. 2 →   +11 Something was changed in the way the authentication (or something else?) works. I cannot use CF tool, login fails.Any workarround available?
•  » » 2 months ago, # ^ |   +3 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.
•  » » 2 months ago, # ^ |   +3 It is because cf api wasn’t working during contest
•  » » » 2 months ago, # ^ |   0 I can confirm that it works again now.
 » 2 months ago, # |   +4 How to Solve D?
•  » » 2 months ago, # ^ | ← Rev. 3 →   +12 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,...,xThe 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.
•  » » » 2 months ago, # ^ |   0 So then we just look over all possible locations of smaller and greater ones, right?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » » » » 2 months ago, # ^ |   0 Thank you!
•  » » » » » 2 months ago, # ^ |   0 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.
•  » » » » » » 2 months ago, # ^ |   +4 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$.
•  » » 2 months ago, # ^ |   0 notice that you need to find only min max from given arraythen you need to handle ranges 1..(min-1) and (max+1)..xso 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
 » 2 months ago, # |   0 Why is this solution giving WA on B??
•  » » 2 months ago, # ^ |   0 3 1 3 5 ` Your code gives NO, answer is yes. If we think about extremes, max-> max-1 & min -> min + 1. Let t1 = max-1, t2 = min + 1, number elements between t1 & t2 = (t1 — t2 + 1) The solution will always exist if max-1 -(min+1) + 1 == n Else no solution
 » 2 months ago, # |   -27 Solved 5 DIV2 tasks for the first timelow asymptotics tasks be like
•  » » 2 months ago, # ^ |   -22 lgbt person detected
•  » » » 2 months ago, # ^ |   +4 r-e-t-a-r-d person detected
 » 2 months ago, # | ← Rev. 2 →   +11 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.
•  » » 2 months ago, # ^ |   0 My solution is clean :D
•  » » » 2 months ago, # ^ |   0 You are doing great :D
•  » » 2 months ago, # ^ |   0 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)]).
 » 2 months ago, # |   +4 Idea for D ?
•  » » 2 months ago, # ^ |   +9 Hint – you can just add 1 and x to the given array, not all of the numbers
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +11 Basically you have 3 options:1) Add 1 after minimum element2) Add 1 before first element3) Add 1 after last elementOther options can't be optimalSame for the x and maximum
•  » » » » 2 months ago, # ^ |   0 For condition 1, if l > 1 you initialized cur = 2 * (l — 1). Shouldn't this be the case only when x is at-least mn?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 .
•  » » 2 months ago, # ^ |   +2 My approachObservation Define initial score is the score you get for not putting any number For any 2 adjacent elements, putting any numbers that lies between them won't affect the initial score Based on 1., we can put as many number as possible that we haven't put that still within the range between two elements 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
 » 2 months ago, # |   0 Who can really prove the greedy solution for D ?
•  » » 2 months ago, # ^ |   +1 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).
 » 2 months ago, # |   -16 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
•  » » 2 months ago, # ^ |   0 no more than once:I thought it was clear? Idk
•  » » » 2 months ago, # ^ |   -9 huh understand I read what either x-1 either x+1 then I thought I have to change LOL
•  » » 2 months ago, # ^ |   +10 Its clearly written in the second paragraph bro : " For the i-th point, it can be either xi−1, xi or xi+1"
 » 2 months ago, # |   +4 In problem E, why the output in the first example is 16?
 » 2 months ago, # | ← Rev. 2 →   0 In problem ECan someone explain me what is the different between two codes? 154575910 and 154578191Why one of them accept and the other not.
•  » » 2 months ago, # ^ |   0 You are not swapping the subtrees in the first one.
•  » » » 2 months ago, # ^ |   0 I am getting the largest possible lexicography string in every subtree by using solve
•  » » » » 2 months ago, # ^ |   0 If I am not mistaken it seems like you are just swapping the characters of the children, and not the entire subtrees.
•  » » » » » 2 months ago, # ^ |   0 Yeah but I cant find the case that will make this fail.
•  » » » » » » 2 months ago, # ^ |   0 Here's the smallest counter example: Ticket 5584
 » 2 months ago, # |   0 How to solve C?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 2 months ago, # ^ |   0 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$
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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
 » 2 months ago, # |   +13 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.
 » 2 months ago, # |   +17 This contest be like:
 » 2 months ago, # | ← Rev. 2 →   +4 such a fun contest. really enjoyed C and D
 » 2 months ago, # |   +3 C is good.
 » 2 months ago, # |   0 GREAT CONTEST..I REALLY ENJOY ..PROBLEM C IS NICE
 » 2 months ago, # |   0 How to do E?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +26 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 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$
•  » » 2 months ago, # ^ |   +18 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.
•  » » » 2 months ago, # ^ |   0 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!
•  » » » 2 months ago, # ^ |   0 can you explain how it is working
 » 2 months ago, # |   +4 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).
 » 2 months ago, # | ← Rev. 2 →   -6 weird ""mathy"" problemset but ok I'll take it (upd: i dont)
 » 2 months ago, # |   0 HI everyone~ I have given two contest but can not solve a single questions. Is CP is not for me?
•  » » 2 months ago, # ^ |   0 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...
•  » » » 2 months ago, # ^ |   0 NO, I do not have experience in math contest, thank you for your reply.
•  » » » » 2 months ago, # ^ |   0 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.
•  » » » » » 2 months ago, # ^ |   0 okay, I will look for it.
•  » » » » » » 2 months ago, # ^ |   0 You can try to go at the problems of the recent Div4 contest :)
•  » » » » » » » 2 months ago, # ^ |   0 okay, thank you.
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   -9 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
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 Video Solutions : A-D
 » 2 months ago, # | ← Rev. 2 →   -8 -
 » 2 months ago, # |   0 In problem E, I misunderstood the problem and think the input string is "preorder string" then get WA...
 » 2 months ago, # |   0 why I haven't got my point?
 » 2 months ago, # |   0 why no tutorial
 » 2 months ago, # |   0 System testing when?
 » 2 months ago, # |   0 how to do c?
 » 2 months ago, # |   0 why I have not gotten my point？
•  » » 2 months ago, # ^ |   0 System testing has not even started yet!
 » 2 months ago, # |   0 really smart C，good question
 » 2 months ago, # |   0 Any ideas and hints to solve Problem C?I tried to brute-force it but got a TLE on tc 3.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 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
 » 2 months ago, # |   +3 When will the rating be changed? The next contest will start. :[
•  » » 2 months ago, # ^ |   0 Literally don't see any local minima in your graph..How do you improve so soon? Tips please
 » 2 months ago, # | ← Rev. 2 →   0 why this sub for c gives TLE 154641815 ? bug or bad idea
•  » » 2 months ago, # ^ |   0 This runs in O(dlogn) and d could be up to x — min(a) which can be 10^9.
•  » » 2 months ago, # ^ |   +3 "STEV" in your code is so cool, how can you make it?
•  » » » 2 months ago, # ^ |   0 Search for " Ascii art generator "
 » 2 months ago, # | ← Rev. 2 →   0 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.
 » 2 months ago, # |   0 Is the staff sleeping? The results have not been released for so long。。。。。。。
 » 2 months ago, # |   0 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?
•  » » 2 months ago, # ^ |   0 You are using Array.sort, in Java it runs on Quick Sort whose worst case Time Complexity is O(n2)
•  » » » 2 months ago, # ^ |   +1 Thank you for the reply. Can’t believe made same mistake again. (Have had a similar situation few contests back):(
 » 2 months ago, # |   +3 When will the editorials be uploaded?
 » 2 months ago, # |   +1 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.
 » 2 months ago, # |   0 Hello, I got a message today that my submission https://codeforces.com/contest/1671/submission/154561381 for the problem 1671B significantly coincides with the solution of Era/154518343 during the Educational codeforces round 127 and I haven't got ratings for this contest. It was merely a coincidence as the problem was solved by me on my own. Please look into the matter.
 » 2 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).