Hello Codeforces!
On Apr/20/2023 17:35 (Moscow time) Educational Codeforces Round 147 (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, 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!
Our friends at Harbour.Space also have a message for you:
Hey Codeforces!
Are you curious about the latest AI advancements and how they impact our world? Do you want to know more about how AI-based methods, especially in Natural Language Processing, are revolutionizing the way we work and interact with technology?
Space.Talks Present: Radoslav Neychev, AI Enthusiast, Researcher, and Machine & Deep Learning Professor.
Radoslav, a top-tier data scientist with extensive experience in Deep Learning and Reinforcement learning techniques, is coming to our Harbour.Space Barcelona Campus to give a talk on this topic. If you can't make it there, you can join the conversation, as we will stream it live on our YouTube channel here.
In this Space.Talk, Radoslav will share his expertise on how AI is changing our everyday lives and why it's important for both technical and non-technical specialists to understand the basics of how AI works. Plus, he'll also answer important questions about AI research and its future implications.
Mark your calendar for Thursday, April 20th, at 12hrs CET, and join us for an engaging conversation. Whether you're an experienced tech expert or just starting to explore the world of coding, this talk is for you!
And remember that we are always looking for the best and brightest! If you want to learn from industry experts like Radoslav, check out the scholarships we are offering and build a brighter future with us!
UPD: Editorial is out
Great. Contest are rare lately. Is it because of ICPC on the platform?
Because during summer in Europe it's GMT+2 instead of GMT+1 (winter)
As a participant, I will appreciate the work of authors and testers. Thank you for the contest!
Thanks for the contest!!. That's my 2nd educational round. Let Go!!
Hope for stable servers.
And hope for correct author solutions.
And for rated contest.
Feeling like after 1 year I will participate in a CF Contest. These days contests are rare.
My first educational round since 3 months ago. Will I be able to solve 4 problems?
glhf!
You better not leave the rating like last time.
Hoping to learn new techniques and methods regardless of rating changes.
MUDA MUDA MUDA MUDA
I have 192 points to candidate master, hope to get more rating points tonight.
I hope that I can get more ratings this round.
Oh,hope fast editorial,too.
Why are you trolling newbies :(
I just need 481 points to reach Candidate Master. hoping to make the difference 500 this round.
I will pray for your 1st rank today :)
If you hack someone you will get points?
Not in educational rounds.
i didn't understand , so hack unrated?
In educational rounds if you hack someone's solution, it doesn't contribute anything to your "score" per se, although it could increase your ranking due to the submission no longer being "accepted".
Is the site getting hanged due to DDoS?
Solved A-E. Problem F has simple O(n*m) solution but I don't know how to optimize it.
A: Each '?' provides 10 options except the '?' at the beginning of the string, which provides 9 options. Also the first char of string cannot be '0'.
B: Because a!=a', we can find the minimum index L and maximum index R that a and a' differ at that position. Then the answer must contains [L, R]. To find the longest possible subarray, we need to extend [L, R] to left and right while a' is non-decreasing on this range.
C: Consider for all possible selection of remained character. Let c be the remained char, we can find all maximal blocks without c, and consider them seperately. For each block, let it's size be L, then we need 1+floor(log(L)) to remove it, and the answer depends on the maximum size of blocks.
D: Let r be the furthest cell we move to, and t be the number of segments we used, then the cost is r+2t. If we ignore a segment [l, r](and possibly make t decreased by 1), we will make r be increased by at least r-l+1, so we can assume that only segment with size 1 is ignored. Then for each possible segment which could contain the furthest cell, we calculate the number of 1-size segments before it, and the number of cells we can ignore (which is (sum of size of segments) — k), then we know there are how many segments we can ignore if we stop in this segment.
E: If we always remove the most right valid pair of brackets, we can see that the cost is the sum of depth of each pair of brackets, which means if we let '(' be 1 and ')' be -1, and s[i] be the array of prefix-sum, the cost is sum(str[i]==')')(s[i]) (the sum of prefix-sums at positions of right brackets). Therefore, we can see how to reduce the cost: If we move a right bracket from i to the right of j (j<i), we make s[i] on range [j+1, i-1] be reduced by 1, and changed s[i] to s[j]-1. If we move a left bracket from i to the right of j (j>i), we make s[i] on range [i+1, j] be reduced by 1. Also these moves must remain s[i]>=0 for all i. Therefore, we can consider for every possible i and find the optimal j by range minimum query and binary search, then we solved the problem for k=1. For k>1, I used greedy approach (which means simply solve the k=1 version for k times) and it passed the pretest (however I can't prove it).
Can this fact be used to optimize F ?
m * (k + 1) < n
I failed test 2 on B. Why is it that simply getting the longest non-descending subarray is wrong? Since isnt any non-descending subarray from a can be obtained by sorting a'?
Consider this case: 1
5
2 1 1 2 3
1 2 1 2 3
is there any better explanation of problem c? like with some example cases?
for example the string "codeforces" and we chose the letter 'c' to be the last letter remain in the string. We need to remove two substring "odefor" and "es", since these too substrings are apart from the letter 'c', so the required number of operation will be depend on the longest substrings need to be removed.
for a string with the length of L, we need floor(log2(L)) + 1 operation to remove the whole string, since each operation we can remove at most L/2 letter if L is even, (L+1)/2 if L is odd,
Great explanation. And for the less mathematically inclined (like myself), it's perfectly reasonable to calculate the number of steps needed as:
Which should be easy to understand: at every step, we can delete half the characters (rounding up, so the number of remaining characters is rounded down).
In E, in one move we should always move '(' next to its corresponding ')', now for all the brackets in middles of this pair depth decrease by one. So answer is just pick k pairs with maximum number of ')' in between them. The constraint k<=5 doesn't matter. Code : 202899903
Hi I dont understand for some test cases for example You are given a regular bracket sequence. In one move, you can remove a pair of adjacent brackets such that the left one is an opening bracket and the right one is a closing bracket. Then concatenate the resulting parts without changing the order. The cost of this move is the number of brackets to the right of the right bracket of this pair. I think for k = 0 squence = (()) we could remove the first outside () and leave inside () at cost 0 because there is no brackets for outside () , and remove the inside (). the total cost is 0 , but why it's 1 ? thanks
We can only remove adjacent brackets.
What was D ? fully ruin my contest -_-
The problem required the perfect code so that corner cases get handled coorectly, apart from that it was simple multiset implementation.
can you explain a little bit more
Maybe my submission here helps?
I tried to explain how it works in the comments. The crucial insight is that although it's mostly optimal to fill ranges from left to right, it may be better to skip ranges of size 1, and add the black cells to a later, larger range instead, to save the cost of pressing and releasing the shift keys.
Let me know if something is unclear!
It was definitely tricky, but it didn't require any complex data structure at all: just a few counters.
I failed to solve it during the contest myself (while I had no trouble with Problem E), but if you know what you're doing, it's quite simple. See: https://mirror.codeforces.com/contest/1821/submission/202905798
I solved it just after contest.....just some manipulation in my previous code which was giving wa.....i used multiset datastructure.
Very good string problem for C. I like it.
I agree, that was a fun one!
Problem E was also fun, though maybe more of a tree-problem disguised as a string-problem.
F was cool, thanks!
Maybe my solution for problem E is incorrect, but I don't understand why $$$k\leq 5$$$
Can you explain sol to F ?
https://codeforces.me/blog/entry/115221?#comment-1024143
Some brute force solutions works in $$$O(kn)$$$ :)
Using my idea, I can implement it in $$$O(n \cdot \log{n})$$$ (though I did it in $$$O(nk)$$$).
I think, if $$$k$$$ is big, there can happen some additional complex cases cases.
my DP solution works in $$$O(k^2 n \log n + n \log^2 n)$$$. Can be reduced to $$$O(k^2 n + n \log n)$$$ but I'm too lazy :) 202876787
I did the same in E. To be honest, I don't see any reason for it to be incorrect.
Misread E for about 20mins(because of my poor English carelessness,I thought I could choose "some brackets"),and tried to solve F by dp with data structures but failed.So I missed a great chance to enter the top 10 in rated contestants.Sad :(
So could someone teach me how to solve F? thx >-<
I ran into the same pitfall of some bracket. As a result, I didn't solve E in the contest XD.
For F, I manage to solve it except for this one part:
How to find the number of m-tuples that add up to n such that at least j numbers is greater than k? Find this for all j from 0 to m.
With this, you can change the question to how many different ways to place the empty space, then depending on the number of regions of empty space > k, you multiply some power of 2. (Fix the tree to always fall left if possible).
My solution for problem F:
We can say that, given $$$n$$$ positions, a subset of $$$m$$$ positions is good if it is possible to assign to each position a subsegment of length $$$k+1$$$ that either starts or ends at this position, and these segments cannot intersect.
Let $$$l_i$$$ be the number of positions between the $$$i$$$-th and $$$(i+1)$$$-th picked ones; $$$l_0$$$ being the number of positions before the first picked, and $$$l_m$$$ -- the number of positions after the $$$m$$$-th one. Each of the positions may be coded by a number from
012
by the following principle:LR
.RL
.Assume that we have the coded sequence $$$c_0\ldots c_m$$$. Then the generating function of the number of total positions occupied can be represented as
where
Let $y = x^k$. Then for each sequence of codes for the segments we have some polynomial which looks like the product of different $$$(1-y)$$$, $$$(y-y^2)$$$ and $$$y^2$$$'s, divided by $$$(1-x)^m$$$. Let's calculate the sum of these products over all valid codes.
But what is a valid code? One can see that a code is valid iff between every two 0-s there is at least one 2. Indeed, otherwise, for a sequence, say,
01110
, the trees fall likeL (0) R (1) ? (1) ? (1) L (0) R
. One can see that if we want to define the direction of falling for all trees from left to right, we inevitably end up replacing each?
withR
and contradict the last(1)
.Now we can do some dp. We can say that each time we are in one of two states; call them safe and unsafe. A state if safe if we can insert 0 right now and not lose immediately; therefore we start from the safe state.
We have some transitions:
1
when we are in an unsafe state, we proceed to an unsafe state.2
when we are in an unsafe state, we proceed to a safe state.0
when we are in an safe state, we proceed to a unsafe state.1
or2
when we are in an safe state, we proceed to a safe state.So we can express the transitions by a matrix, and in the end the polynomial is
The matrix exponent can be calculated in
It may be not very optimal, did anyone do anything easier?
Assume trees always fall to the left if possible. We look at the spaces the trees can take up after they fall, and then multiply by the number of ways they could have fallen. If a tree has $$$k$$$ spaces before where it falls, then it can only have been at the right endpoint. Therefore, if there are $$$x$$$ trees without $$$k$$$ spaces to the left, and $$$m-k$$$ trees with $$$k$$$ spaces to the left, then there were $$$2^x$$$ ways for the trees to fall. If we let $$$a[x]$$$ be the number of ways that at most $$$x$$$ trees have $$$k$$$ spaces to the left, $$$a[x] = \binom{n-2km+kx}{x,m-x}$$$. Let $$$b[x]$$$ be exactly how many ways the trees fall. We can count $$$b[x]$$$ using PIE with $$$a[x]$$$. $$$b[x] = a[x] - a[x-1]*\binom{m-x+1}{m-x} + a[x-2]*\binom{m-x+2}{m-x} - \ldots$$$. To find $$$\sum b[x]\cdot 2^x$$$, we do some math, and it nicely evaluates to $$$\sum a[x]\cdot 2^x \cdot (-1)^{m-x}$$$, which can be done in $$$O(m)$$$ time. A nicer way of finding the sum with PIE can be done by starting with all cases with $$$x=m$$$, and then subtracting and adding the inside cases until we reach $$$x=0$$$, but the expression is the same.
Because smax told me to, here's a link to the submission 202891483.
Done the same. Having struggled for a long time to solve the problem
But later on, found that it is unnecessary to solve this problem directly.
What does $$$x, m-x$$$ mean in the formula for $$$a[x]$$$?
Actually the polynomial matrix multiplication result is just simply $$$(2y - y^2)^m$$$ (according to WolframAlpha),thus the complexity would be $$$O(n)$$$.
problem E completely ruins the problemset. 400ish solves wtf.. I have never seen that much solves for E, especially in educational rounds.
Why would that be bad?
I always think it's good when the solve rate for each problem is somewhere between 1/2 and 1/3 of the previous problem. That allows sequences like 10000, 5000, 2500, 1250, 625, 312, 156, or 10000, 3333, 1111, 370, 123, 41, 13. I hate it when there is a hard cliff where for example “everyone” solves the first three problems and “nobody” solves the last three problems.
This contest was fairly well balanced. Solve ratios between adjacent problems were: 1.5, 1.4, 4.6, 2.4, 14.4. That means that problem F was arguably too hard, but problem E was pretty good.
If I pass the system tests, I will become expert today for the first time
congratulations
Thanks
Weak pretests in D
what is the anti test ?
Could someone help with my submission for D?
202882450
Screencast with commentary
Who is author of problem C and who specifically prepared the samples?
E is a nice problem: cost of the brackets can be interpreted as the area under the graph of prefix sum of the sequence :) (
1/2 (Area - n/2)
to be precise)Problem D:
Getting WA on TestCase 2
Suggest some counter Case. Unable to figure out the mistake.
the edge cases in D are when you are considering intervals of size 1
is D just greedily skipping and picking segments T-T
Yes
bruh I thought it was some variation of knapsack or bitmask dp. i came up with the greedy solution in the last 2 mins rip
Imagine performing bad twice in row just because you mistyped variable name
Imagine performing bad because you are doing
j = i
instead ofi = j
https://codeforces.me/contest/1821/submission/202880565
can any help to find my mistakes or find any anti test. (: its differ on 1215th on test-2.. -_-
Thanks.. how do you debug. can you share your process plz
I use Codepal for stress testing
Could you construct a solution with output 93?
Can anyone please give me a counter example for my submission for problem D.
UPD: Aced with Greedy. Thank you everyone for the help. (adityagamer thanks for test case).
Isn't it correct? like I would color $$$21-36$$$ then $$$59-65$$$ so total = $$${65 + 2 * 2 = 69}$$$ I would hold and release shift twice?
The ranges are inclusive — 21->36 is 16 squares so you only need to colour 59->63
Ohh Thank you I got my mistake!
You can just go to 63, and that's enough 21 colored cells. So 63 + 2 * 2 = 67.
Since k is 21, you only need to go till 63. So total = 63+2*2 = 67
What's the issue with this more general solution for D that doesn't explicitly use the special len=1 case but should still take it into account?
Take a look at Ticket 16848 from CF Stress for a counter example.
I liked D, nice problem
oh bro really?? very nice to know that tbh
Am I the only one who solved D with sqrt decomposition+ greedy :d I figured there would be an easier solution but sqrt seemed fun :d
Share your sqrt solution, I'm curious :)
Can someone give me a counter test to this submission for problem D? Thanks in advance.
I don't think that's true. this AC submission also gives 59 as an output to that test case :<.
Yes, Sorry.
UPD: This test case was invalid
Take a look at Ticket 16844 from CF Stress for a counter example.
Thank you. Amazing website, didn’t know it existed.
Can anyone share a dp solution for D?
Can anyone tell me what is wrong with my C https://codeforces.me/contest/1821/submission/202883081 am using same approach as in editorial and is running fine for every case i can think of
You checked only for characters whose count is maximum in the string while it may be possible that for some other character you get the smallest number of steps so instead of checking for those characters only check for all characters from a to z since there are only 26 of them so u shouldn't be worry about time complexity.
how to solve C?
For every letter you see the minimum operations to remain with only that letter
In problem D, can anyone please explain why the correct output of this case is 22 but not 23?
Color 4-6, 9-13, 15-16
Can someone explain why this approach fails for problem D. I am just trying to minimse the number of segments that needs to be taken by removing the segments with lowest differences. Link to submission Thank you in advance.
check this comment. i did the same mistake
Got it thanks
this is my solution for problem D. Plz somebody explain what is wrong with this approach.
Does it work for touching segments where you don’t need to click shift on the border?
by definition there are no touching segments. as they have stated that r(i) <l(i+1)-1
Damn, I was solving with assumption that there are:)
In constraints section it is specify that touching section is not allowed Given that r[i] < l[i+1]-1 for all 1 <= i <= n
Then the second question, why the upper bound from begin?
My basic approach is that:- 1. I skip coloring initial i-1 segment and start coloring from i-th segment then prefix count all colorable cells upto i-1 segment is stored in previous variable. When i was finding upto which segment i have to travel to get at least k colorable cells. I take upper bound , and i m taking it from beginning because i added previous in it.
ll idx = upper_bound(aux.begin() , aux.end() , k+previous) - aux.begin();
During contest i was thinking it will reduce some complexity.Then you should consider previous+=aux[i]; However, what if you need to skip nonconsecutive blocks?
in addition, you have no need to skip blocks of length >= 2 since you will need at least 2extra moves that is not better than 2 clicks
ohh got it , thank you.
Nice contest! You can find the video editorial for Problem A, Problem B, Problem C and Problem D here- here
Thanks for the video editorial ^ ^
Maybe this sounds like a stupid question, but why are div 1 users included in the official standings?
Both div 1 and div 2 participants are included in the official standings till the final system testing. Afterwards, you get the option to see only div1 participants, only div2 participants or everyone, in the standings.
Got it, thanks!
Can anyone please explain why this code gives RE in GNU C++20 202863602, but AC in Clang++20 202892668.
Later I changed vector<pair<int, int>> v to vector v which stores only differences and it gave AC on GNU too, but I don't see a reason why this would give RE.
Your comparator function for sort is wrong (it must return false on equal values — https://codeforces.me/blog/entry/70237).
Oh... Somehow I remembered the opposite. Thanks:)
Can someone pls explain how the expected output for this input is 11?
Also can someone pls provide a counter case for this submission: My Submission
I used a double binary search approach.
Can someone please prove or hack my solution to problem E which I did in O(n)?
Approach: Find pairing between individual brackets. For example in (()) first bracket is paired with fourth and the second with third. Find this using stack. Simply eliminate the top-k pairs of brackets where pairs are farthest apart. The answer is the cost of the resultant string.
can you explain problem E statement ?
TestCase : ((())()(()())((()))) Answer : 4
WHY ?
Honestly, authors should give at least good test case with proper explanation.
The cost for any rbs is the minimum cost to make it empty. So, the optimal way is to repeatedly remove the rightmost adjacent parentheses pair until we remove all pairs greedily since this gives the minimum cost. Now, before calculating the cost for the given string, we are allowed to perform k operations as mentioned in the problem statement. After a single operation, you can place a bracket adjacent to it's respective partner such that it can be removed easily. This is how I interpreted it
What's up with the server?
Can someone explain to me why greedy with min-priority-queue works for problem D? Having a hard time grasping it.
Can anybody tell what's wrong with my code and on which testcase it is failing. https://codeforces.me/contest/1821/submission/202836388
Try this, answer should be (1, 2) whereas yours gives (1, 3)
bro, i just forgot to break the loop in else condition : /
for problem b
14
3 4 2 1 4 5 2 1 8 7 6 5 4 3
1 2 3 4 4 5 2 1 3 4 5 6 7 8
the output is 1 14 it should be 8 14 right I am unable to understand the question can someone please help
Note the constrain:it is possible to obtain the array a′ by sorting one subarray of a.
While for this input it should sort at least 2 subarrays.
Registed 6 years ago, and become master finally. And still huge gap to grandmaster. Cheer for myself.
Can someone help me with C, I am getting TLE in test case 8. My submission
I got it accepted, just slap a main() function in and your code runs way faster: https://codeforces.me/contest/1821/submission/202933122
Do you know why it makes it faster?
Its the difference between local and global variables in python / pypy
https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function
When python compiles down to bytecode, accessing local variables are done using STORE_FAST instead of STORE_NAME, where one uses array access instead of dict (hashing) access
Thanks for this info
During the contest I got AC for this code: https://codeforces.me/contest/1821/submission/202855933
While not optimised, I believed that it was sufficient to pass the time limits (I had ~700ms runtime), so I did not optimise it further.
After the contest it got TLE due to high constant factor of using set()
I changed the code and now it works: https://codeforces.me/contest/1821/submission/202930258
It is pretty unfortunate as I really thought that my original solution was optimised enough for the testcases, how could I tell if I should always optimise my code beforehand? Should I always optimise my code even if it passes the pre-tests?
thank you
Does E problem's "extract" mean for one time I can take a pair of matching braclets "(......)" ? If take ONE braclet each time how can I pass the example?
I definitely comprehend the problem as "extract a pair of bracket each time", and it got Accepted...
can we use DP to solve D.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Why hasn't the tutorial been released yet?
Wondering solution of D by using binary search
hey in E why k is only till 5 is it too confuse us? or make implementation easier?