Hello Codeforces!
The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos.
On Apr/29/2024 17:35 (Moscow time) Educational Codeforces Round 165 (Rated for Div. 2) will start.
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, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov 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
Waiting for a good contest!
Make this comment most disliked comment in CF
I guess this is one of the most downvoted comments. I wanted someone to nominate me tho :(
I hope there will be an interactive problem soon
Usually, I do not find interactive problems in an educational contest. Have you such an example where it happened recently?
yes in edu round 155.
If the contest has an interactive problem they should say in the announcement.
I would like to give you a downvote but because we are in the same community take an upvote.
Edu time I hope A-E is data structures problems , or 2 of them at least
All the best guys :) ;
The penalty for each incorrect submission until the submission with a full solution is 10 minutes. what this line means, how penalties are given in this case. I know only -50 for wrong submission is a type of penalty.
in Edu rounds the leaderboard is sorted Depending on how many problems you solve there is no score
but what if there is 2 people have the same number of problems solve they will sum the times of them and sort it by the person who have less time
Hope able to solve ABC
I hope I don't get negative delta...
I wish high rating to participants
1800 plz!
Doma Umaru?!
:)
Best of luck everyone.
Very long time no see, Educational Codeforces. I wish this contest teach me a lot.
pls no guessforces
My first Educational round. Hop to get positive delta for everybody.
"I wonder how you folks (BledDest, adedalic, Neon, Roms, awoo) come up with so many tasks. It's like you've been holding Educational Rounds since the invention of sliced bread=)
Will the 12-hour hacking part give any additional score? Will it be possible to hack the solutions of your room during the contest?
Hope everyone will not get stuck in A, B and C.
It was kinda shitty contest tbh
because you couldn't solve C?
C>>>D. 10 minutes for D and 1hr+(multiple WA) for C.
Isn't C just a standard dp?
ah yes because 2D is standard DP. Someone who actually solved C & D
what logic you apply while solve d ?
I can not solve c and d !!
C : 2D DP with n and k. Where DP[i][j] is maximum subtracted from sum in first i elements with j operations. DP[i][j] = max ( DP [i-q-1][j-q] for all q between 0 and j).
D: Sort all for minimizing Alice's cost. Then, look at all items where Alice pays less than what Bob could pay. Store all of Bob's costs in a min heap priority queue. Bob gets k minimal costs for free. answer = max(sum(Bob) excluding top k elements — sum(Alice)).
How could you solve greedy problem more easily than the DP problem ?
D <<< C
If you don't mind me asking, what was the solution for D?
Well, firstly sort things by Bobs cost, if equal sort it in decreasing order by Alice cost. Let's say we want to buy first $$$t$$$ things. For all of them we will get max(0, $$$b_i-a_i$$$), if we will additionally buy any $$$k$$$ things (so Bob will choose them). We just need to maintain sum of $$$k$$$ smallest numbers of $$$a_i$$$ to the right of $$$t$$$ and brute-force $$$t$$$ from left to right.
Maybe it's a little bit messy, but this is what i have...
thanks brosef I understand now
C was easy DP, maybe a little tricky to implement.
DP itself was not intuitive for me, as we are able to replace $$$a_i$$$ not only with $$$a_{i-1}$$$, but also with $$$a_{i+1}$$$.
Maybe it's easier if you think about the operation as "choose a subarray [l,r] and replace all elements with the subarray minimum".
Then dp[i][j] = minimum sum of subarray [0,j] after applying i operations, and you can iterate over the size of the subarray including the element j (can be 1, 2... k).
yeah, that is the observation I needed to solve this.
It's a dime in dozen occasion, lol. I usually manage to solve more complicated problems, rather than easier ones. IDK why rly...
orz
My solution discussion stream
why my solution is failing for C ?
It's hard to use greedy for C, or even impossible (I actually think about a lot of ways to use greedy but I found lots of counter examples either, so just use DP is a better approach).
Hello DuongNeverAlone sensei, how are you? and plz Can you tell me what is the best way to start DP, so that i can cover all the standard problems of it? and from where? Answer my question Greedily sensei ;)
Just do it LOL. I have no idea what is the best way to start. Until now there are much topics in DP I haven't covered yet (some DP optimization techniques for example). Heading to codeforces, leetcode, cses, spoj, ... or any other online judges you know and sort to do DP.
Good contest, I liked the problems.
Idea for D?
Hint: Think in reverse operation order. Suppose you include N elements and want to remove one, what's the optimal strategy for Alice?
The model approach is the following one:
Sort the items according to their price for Bob. Then, whenever Alice chooses a subset of items, $$$k$$$ last items from the subset will be taken for free, and the remaining items will be bought by Bob.
Let's bruteforce the "border" — an index $$$i$$$ such that the items after $$$i$$$ will be taken for free, and the items before $$$i$$$ (including it) will be bought. Then, Alice has to take $$$k$$$ items from the right part. Since they will be taken by Bob for free, she should choose $$$k$$$ minimum-priced items for herself from the right part — so, we need to calculate the sum of minimum $$$k$$$ values of $$$a_j$$$ after the border. This sum of $$$k$$$ minimums can be maintained as follows: iterate on $$$i$$$ from right to left and store $$$k$$$ minimums in a data structure that allows inserting an element and removing the largest element (this is priority queue, but you can also use multiset).
What about the items to the left of the "border"? Every item will add $$$b_j - a_j$$$ to the profit, so we need to calculate the sum of $$$\max(0, b_j - a_j)$$$ to the left of the border (and this is just prefix sums).
ah nice explanation, thanks broski
Why Bob will take for free most expensive for him, if his goal is to minimize Alice profit? I sorted by $$$b_i-a_i$$$ and got different answer on pretests.
Upd: Think I got it, Alice already paid for entire subset, so it makes sense to sort by $$$b_i$$$
Thank you for explanation
I sorted the lists based on the decreasing differences in values and it WA on test 3. Basically sorted a list of pairs $$$(b[i]-a[i], i)$$$. Why does this idea fail?
I believe I have a more "elegant" greedy solution which utilizes different observations so I'd like to share it.
First observe that if Alice selects fixed $$$M$$$ elements, Bob will take the $$$K$$$ with the largest sum of $$$b_i$$$.
Next, observe that Alice never wants to take an element if $$$a_i \gt b_i$$$. Just consider both cases (Bob takes this element and Bob does not take it) and the answer never becomes worse if Alice excludes it.
Now that we know this, suppose that Alice chooses all elements such that $$$a_i \lt =b_i$$$, let the count of such elements be $$$l$$$. Let's denote the elements selected by Bob by $$$(a_1,b_1),(a_2,b_2),...,(a_k,b_k)$$$ and the remaining ones by $$$(a_{k+1},b_{k+1}),(a_{k+2},b_{k+2}),...,(a_l,b_l)$$$. We know the total sum for this choice, because Bob chooses greedily the $$$K$$$ largest $$$b_i$$$'s.
Now what happens if Alice wants to choose $$$l-1$$$ elements?
We never want to remove an element that is not already chosen by Bob, because it will just reduce the total sum. If we remove an element $$$(a_p,b_p)$$$ that is chosen by Bob, the total sum increases by $$$a_p$$$ and it can trivially be proved that we can never add $$$b_p$$$ to our total sum in the future by performing removals. So it's always optimal to remove the element with the largest $$$a_p$$$ and instead of it insert the one with the largest $$$b_q$$$ such that $$$(a_q,b_q)$$$ is not present in Bob's set.
We can easily simulate this process using two multisets.
I didn't write the proof in a formal way here, because it would be lengthy, but one can derive it if they want.
Here's my submission 258749293
If Alice chooses some subset of elements, then Bob will pick the $$$K$$$ elements with the highest values of $$$B_i$$$. If we sort the items by $$$B_i$$$, then this just means Bob will always pick the rightmost $$$K$$$ elements in any subset. Therefore, our array will become split into 2 partitions: the left partition's elements go to Alice, and $$$K$$$ of the elements in the right partition go to Bob (we can choose the ones with lowest $$$B_i$$$).
We can do the following: Iterate over the size of the right partition from size $$$K$$$ to size $$$N$$$, and maintain the sum of the smallest $$$K$$$ values of $$$B_i$$$ using a multiset. We then calculate Alice's profit as $$$\max(0, B_i-A_i)$$$ for all elements $$$i$$$ in the left partition, which we maintain with a prefix sum array.
I skip the problem because I thoug the profit can be negative and that's why I never understood the 3 example, that should be specified in the statement. Upd: now i see you can buy an empty set :(.
Was buying empty set not mentioned during contest?
Best contest ever!!! I very much enjoyed it :)
I bruteforced sorting criteria for D and resulted in a +7 AC... what a way to live... XD
Anyway, anyone can prove the validity of D? My (greedy) approach is to sort everything, first on Alice's buying cost in increasing order, then Alice's theoretical profit (assuming Bob doesn't take anything for free) in decreasing order.
Let's think of a strategy for Bob. If I take s elements (s>k) then he will choose s-k elements with the minimum b. That's obviously true because sum of a is fixed and to minimize the profit Bob will choose the smallest bs. Now, I'm Alice and I know that. Then I wiill check each b. If I fix some b[i], then for all b[j] such that j>i I will choose minimum k as from them. I know that since they are k and Bob will choose minimum bs, he will not choose from them. So now remains the elements in the prefix of i. Any element I will choose in this prefix, Bob will choose it too. So I want all positive profits in this prefix. I'm not sure if this is kind of a proof, but this was my though process.
can someone please tell why is this giving WA on 3 is there any logic error or bug
I also had WA on 3, does someone have a counter example which I may have overlooked?
"wrong answer 14th numbers differ — expected: '14', found: '13'"
did you find counter case? ( I am getting wrong answer on same tc) My Code
nope, but I will write here if I manage to find.
try for this test case:
4 1
1 1 3 9
3 4 5 15
here you will get 0 but answer is 2
TFW you get a WA a couple minutes before the contest ends and out of supreme luck, you unknowingly click "Mobile Version" on Codeforces and instead of debugging your code, you end up debugging what just happened 🙃
Tip (to self, others):
Whenever changing limits like this for debugging purposes — it's probably best to add print statements alongside (so that you remember to fix this as well)
Alternatively, in languages where there is support for compiler-warnings, add those :)
i needed this tip too!
I got AC on problem E one minute after the contest ended. The problems were really nice, thanks
Sigma
https://mirror.codeforces.com/contest/1969/submission/258748770 How to memoize this recursive approach to C ? Or any other recursive solution ?
simple recursive 258735237
what's the idea for c? I couldn't debug my dp solution in time, with mp[j][val] standing for j operations used and the last value being val. since val could be huge, i used unordered_map to store the status. and to avoid space overflow, status with the values that aren't possible to be at the end for current moment need to be erased. or is there a much easier solution?
k is less than 10 so you can solve with 2D DP.
bruh I thought $$$k \leq n$$$ and couldn't come up with anything. can't believe I have misread that
It seems like the time limit of E is too tight. Submission https://mirror.codeforces.com/contest/1969/submission/258765134 got TLE on test 25 by using
BTreeSet, however, submission https://mirror.codeforces.com/contest/1969/submission/258766945 got AC by usingHashSet(it was simply replacedBTreeSetasHashSet)E can solve by Monotonic Stack in O(n),so the timelimit is enough. Code
Can anyone please explain me the DP approach to solve problem c?
$$$dp[i][j]$$$ = the minimum sum when we only consider the first $$$i$$$ elements, and perform $$$j$$$ operations. We can do $$$dp[i][j] = dp[i-1][j] + A_i$$$ to do nothing. Suppose we perform $$$x$$$ moves: we convert elements $$$A_{i-x}, ..., A_{i}$$$ to the minimum element in this range (call it $$$min$$$), and the new sum of this range is $$$(x+1)*min$$$. The minimum sum for the remaining elements can be obtained with $$$dp[i-1-x][y]$$$, where $$$y$$$ is the # of moves performed beforehand. Therefore, we do $$$dp[i][x+y] = (x+1)*min + dp[i-1-x][y]$$$ for all pairs $$$(x,y)$$$ where $$$x+y \le K$$$.
thanx for explaining the states and transitions
If I define dp[i][j], the maximum sum of elements I am able to delete, if I am at index i and perform j operations. Then I subtract the maximum value of dp[i][j] from the total original sum of the array, why am I getting wrong answer ?
Edit — Resolved. Should have used long long.
My second educational round, and again not solve C. So educational round means high difficulty??? Both two my edu round solve only AB and rank 3600+ (:_;)
I'm going to be specialist and hope to get my rate back in div3 round a few days later X(
C is not too hard, but not too easy in this round. If you take a look at previous Edu round, it is something really different, so it doesn't mean high difficulty
Maybe I just to weak in 2D or 3D dp (:_;).
And I determined to try to come up with a greedy solution, till the end of round. Although I've imagined this is probably a dp, I refused to go ahead because I thought I have little chance to solve a 2D dp problem (x_x;)
Or you could do tmrw's Div. 2 and somehow solve A-D :)
why u lying?? ur 1. edu u solved ABC
Oops, it was two rounds that were really close and I mistakenly remember this, sorry. It was actually the round right after that edu round:(
Fantastic Edu round as always. Thanks a lot BledDest awoo adedalic Neon Roms and all testers!
I posted my code of problem D in the last 10 seconds, but the evaluator didn't receive it.
After the contest finished, I reposted my code, and then it was accepted.
Now I wanna die right now.
sorry man
C was bit hard for its position.
I believe it's my skill issue:) it was a good problem actually
hard to implement. Not hard to solve.
Any counter Test for this https://mirror.codeforces.com/contest/1969/submission/258771109
C was obvious dp don't why some people found D easier than C is it because there is some standard idea / technique if so please tell me. Thanks!
I'd say both are pretty obvious. Personally, I just found them hard to implement
can you please tell me what's wrong with this
can't say, sorry
Many solutions to problem A, including mine, are hacked, because of set.
How is it possible? The time complexity is $$$O(t∗n∗(n−1)/2∗4∗log(4))=O(5∗10^7)$$$ which should not work longer, than 2 seconds.
I have solved ABCDE, and would become a master, if my solution to A wasn't hacked :(
We'll stay forever this way You are safe in my heart And my heart will go on and on
Pardon me if I'm mistaken, The time complexity of your code is O(t∗n∗n∗O(n)) = O(6∗109). As inner clr(set) takes O(n) in every iteration.
He always just pushes 4 elements to the set and clears it, so clearing the set doesn't take o(n). It takes o(4).
o(4)std::sethas a lot of overhead as it uses a tree structure, so you end up using a lot of time allocating and deallocating memory, rebalancing the tree, etc.My solution is the same, but the only difference is that you clear the set, I define a new one each time. I think this is the reason why you take more time on the original tests and got hacked.
i'm surprised that your solution din't get hacked. this one did get hacked tho. He also created a new set.
maybe because he's declaring vectors and calling a solve function? I think the smallest differences can make my 1968ms get tle
i found the place or the hole in the code which gives allows the hack to give TLE. Its the fact that the code does n^2 iteration, still no proof how tho. you code does $$$ \frac{n(n-1)}{2} $$$ iterations. I think that can make a proof. I tried both. Your approach just passes with 1999ms. The others don't. and that too if we don't use function call and stuff. A normal
while(t--)loop passes barely but doing anything other that will not work. even if you do $$$ j = i+1$$$ it still gives TLE on test 4. creating a vector also doesn't make any different if we do $$$\frac{n(n-1)}{2}$$$ iterations.I tried finding the issue but I couldn't and this is the information i was able to discover. any details would be really appreciated by some experienced coder.
I think it is because of the chosen compiler. I was reading this blog and I think the reason is that GNU C++17(64) and GNU C++20(64) is better than GNU C++17
i use c++ 20. you can refer to my submissions.
Don't use
endlFor problem E 258747661 should be hackable. I have no proof on the bound of the no of iterations.
Can anyone explain what does it mean "Generator is not determinate [the verification run produces different output, cmd =7 4956565656565656564512121], [1100006 bytes, '1000 300 6 151 55 114 76 65 24 12 86 135 38 98 2...290 266 282 34 73 297 245 5 118 261 79 200 35 ', sha1=f0a1c17d87899a11c1db8f805df18da45b1251d5] vs. [1100006 bytes, '1000 300 2 151 55 114 76 65 24 12 86 135 38 98 2...290 266 282 34 73 297 245 5 118 261 79 200 35 ', sha1=a2117fdfb95eb249f578f57f01f328e2a91fc766]."
A generator must be deterministic, that is, it must produce the same output every time it's run. If you use RNG, you must set a random seed.
I really liked problems D and E!
can anyone provide counter example? I don't see any reason why this not working.
You are applying a greedy algorithm, i.e. merging the immediate best, rather than doing a deeper search.
For example,
1 5 2 20 10 19 28
Your algorithm will see the largest difference (20-10) and merge them, and then merge 19 together, totaling 10+10+10+28 = 58. but the optimal solution would be 20+10+10+10 = 50
I just spent quite a while debugging my solution to C, which I was confident was correct but failed on test 5 due to a runtime error. It turns out that it was a stack overflow error, and after I increased the stack size, my solution passed (original, with increased stack size). I feel that I should have gotten credit for my original solution during the contest since it would have passed within the given time and memory constraints and only failed due to a restriction in the judging environment.
reject memoization, embrace tabulation
I have solve the problem E by Monotonic Stack in O(n).
The submission
It's a stack.
How to solve E?
let st[i] be the largest j so that j < i and the subarray [j, i] is not unique (if j doesnt exist, st[i] = inf).
Now, if st[i] < i (for i = 1 -> n), we have a segment [st[i], i], now the problem becomes: calculate the minimum number of black points so that each segment contains at least 1 black point. It's easy to solve using deque and dp.
Could someone explain why this solution was hacked in problem A? Here's the link to the submission: link. It's supposed to be ( n^2 ) and should pass. Can someone verify if the test validator is working correctly?
awoo adedalic BledDest Neon Roms
made a mistake, but set has a high overhead for each operation.
Good edu round :)
Could someone please tell me why this contest didn't count towards my rating? I did the registration as usual
We just need to wait for the update of the ratings. It usually takes a few hours after the contest end.
is the system testing over?
In the standings title it is said they are final. Except, probably, for the cheaters.
where's the contest?
Until the editorial gets published, can anyone provide some help regarding problem F? I've been thinking of some DP, where $$$dp_i$$$ = number of coins you can get if you start with a full unique deck and have the last $$$i$$$ cards in the stack. I tried to come up with the transitions but I am missing something. Thank you in advance!
Assuming “full unique deck” means one card of each number, you’re on the right track. In terms of transitions, here are some questions to think about:
Thank you very much, the confirmation that I am on the right track motivated me to keep going. I just got AC on it
Congrats to OliviaRodrigo who did very well on the contest! Big fan of your songs here!!
Can't Catch Me Now
For problem B pre-test did'nt include overflow cases. :cry
Will the rating changes before 942??
Could someone explain me why this https://mirror.codeforces.com/contest/1969/submission/258724763 code for B got AC on pretests and now is getting WA on test 1? I understand why it fails but why didnt it got WA on the same test during the contest?
It's probably cause by ub(undefined behavior). You tried to get the front of an empty deque in
int first=v.front();. And maybe in the pretest, this behavior somehow get a value that can pass test 1.How does undefined behavior work? Because it had to give a correct answer for every case formed only by '0's, and if it was so, why not after pretest?
As it's name, it's undefined and we can't predict how it works. It's up to the compiler. Maybe you have extreme luck in pretest and passed temporarily, and your luck disappeared in main test.
I had understood it works like that but seems I just had incredibly bad luck. Thanks for replying and have a good day
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).