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
As a specialist give me positive contribution pls
Positive contribution unlocks from...
Contest rain,,,, Contest week....
hopefully will be as hard as the div 4
Coders after attempting div 4 round: Coding is not too tough ;-;
That's great! So many rounds :) Good luck everyone on the round!
It's raining, contest hopefully, I end up with a positive rating change after this week.
Wow, Educational Codeforces Round
0x7f
! Wish to have fun and high rating!It's impossible to have fun writing educational...
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!
Thank you! Good luck to you too!
Hope I turn pupil this round.
good luck
waiting for it
So Many contests back to back . I like it picasso
contest sleep again contest and again sleep....
It always astonishes me that someone can AK edu faster than I AK div4...Holy....
Happy to say that this is my first unrated edu round :yaaay:
ContestForces
I hope I can solve one problem
After div 4 I guess the first problem today in Edu is harder than the latest problem in div 4 yesterday :)
This will be the first edu round I join!
From question's perspective, is there any difference between normal and edu rounds?
What should we do when we feel very demotivated after wrong answer on Test 2?
Try to find corner case like me, if you r confident that your approach is correct, otherwise try to change the idea.. :|
Thank you for the round! Will reach master finally (If I don’t get hacked)
Enjoyed the contest, interesting problems and ideas, especially F.
-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
Something was changed in the way the authentication (or something else?) works. I cannot use CF tool, login fails.
Any workarround available?
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.
It is because cf api wasn’t working during contest
I can confirm that it works again now.
How to Solve D?
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.
So then we just look over all possible locations of smaller and greater ones, right?
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
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.
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$$$.
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
Solved 5 DIV2 tasks for the first time
low asymptotics tasks be like
lgbt person detected
r-e-t-a-r-d person detected
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.
My solution is clean :D
You are doing great :D
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)]).
Idea for D ?
Hint – you can just add 1 and x to the given array, not all of the numbers
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
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?
.
My approach
Observation 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
Who can really prove the greedy solution for D ?
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).
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
no more than once:
I thought it was clear? Idk
Its clearly written in the second paragraph bro : " For the i-th point, it can be either xi−1, xi or xi+1"
In problem E, why the output in the first example is 16?
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.
You are not swapping the subtrees in the first one.
I am getting the largest possible lexicography string in every subtree by using solve
If I am not mistaken it seems like you are just swapping the characters of the children, and not the entire subtrees.
Yeah but I cant find the case that will make this fail.
How to solve C?
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.
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$$$
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
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.
This contest be like:
such a fun contest. really enjoyed C and D
C is good.
GREAT CONTEST..I REALLY ENJOY ..PROBLEM C IS NICE
How to do E?
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.
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$$$
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.
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!
can you explain how it is working
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).
weird ""mathy"" problemset but ok I'll take it (upd: i dont)
HI everyone~ I have given two contest but can not solve a single questions. Is CP is not for me?
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...
NO, I do not have experience in math contest, thank you for your reply.
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.
okay, I will look for it.
You can try to go at the problems of the recent Div4 contest :)
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.
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
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.
Video Solutions : A-D
In problem E, I misunderstood the problem and think the input string is "preorder string" then get WA...
Any ideas and hints to solve Problem C?
I tried to brute-force it but got a TLE on tc 3.
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
When will the rating be changed? The next contest will start. :[
why this sub for c gives TLE 154641815 ? bug or bad idea
"STEV" in your code is so cool, how can you make 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.
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?
You are using Array.sort, in Java it runs on Quick Sort whose worst case Time Complexity is O(n2)
Thank you for the reply. Can’t believe made same mistake again. (Have had a similar situation few contests back)
:(
When will the editorials be uploaded?
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.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).