Hello Codeforces!
On Oct/09/2023 17:35 (Moscow time) Educational Codeforces Round 156 (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, Roman Roms Glazov, Alex fcspartakm Frolov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Please note that the problems of this round partially intersect with the problems of the Qualification stage of the Southern and Volga Russian Regional Contest. If you took part in the qualification, please refrain from participating in the round.
Good luck to all the participants!
Our friends at Harbour.Space also have a message for you:
Scholarships for Master's students in Computer Science and Data Science are available in Harbour.Space University Barcelona campus!
Scholarship Summary:
- Fully funded scholarship (29.900 €/year) to study a Master’s degree in Data Science or Computer Science for two years
- Successful applicants will become part of the University’s “Talent pool” and will be shown to the sponsoring companies. In case the candidate is picked for the Work&Study Program from our industry partner, the student starts an internship with a commitment to study 3 hours/day and work for 4 hour/day
Please note preselected candidates will be requested to pay a non-refundable application fee of 85€ to study at Harbour.Space University.
Candidate’s commitment:
You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.
Candidate’s requirements:
- Bachelor's degree in the field of Mathematics, Statistics, Data Science, Computer Science or similar
- English proficiency
- Advanced knowledge and experience in Python, SQL, Spark/Scala, and bash
- Experienced use of Big Data technologies: Spark, HDFS, Kafka, etc.
- Hands-on experience with Data Science techniques: feature engineering,
- Strong ML knowledge
- Strong Software Engineering Background
- Problem-solving aptitude
Note: These scholarships are only available for qualified applicants with a bachelor’s degree.
UPD: Editorial is out
already getting bad vibes
is the contest delayed? It is time but it is still saying 23 minutes left
The contest is tomorrow
whoops i see now, my bad
that's 23 hours bro
Excited
As the person who preordered this contest (i.e. took part in the qualification), the problems are actually good.
Alex fcspartakm not a writer on the contest page. I don’t know how I noticed that :)
Why do all educational contests have the same authors?
The term "Educational Contests" specifically refers to the initiative by Harbour Space University, so it's organized by the same individuals, with a few occasional variations.
Educational Rounds are usually mathforces af. Will skip this one.
I agree with you.
bro you have already skipped all the contest in the last 6 month , i don't think so you should be saying that when you are not active
I am planning to make a comeback but on a positive note. Will start with Div3. I am regular on Leetcode Contests.
Lol you were right with this one ^^
No offensive but I have a bad feeling about this round T.T
Classic huge difficulty gap between C and D.
Even C is really annoying binary search problem.
I like C actually
You can also solve it greedily using stacks
I think my implementation is quite clean.
Can you please tell how to binary search?
I haven't solved the problem. Based on the above replies I think I might have overcomplicated my approach. First I found out the indices where the string characters decrease with respect to preceding character. If the indices are say i1,i2,..,ik then s_{ik} is the suffix of s upto starting from ik. The length of s till s_{ik} is n+(n-1)+...+(n-ik+1) So like this I tried to binary search the index upto which we much consider to obtain the index pos. I faced much trouble in implementing this approach due to plenty of corner cases.
What difficulty gap are you talking about? In my opinion, D was easier than C
obviously for you, coz you are D-constructor
brickforces
For me, this is one of the toughest div2D's for sure
For me, this is one of the harders Div2Cs ever, but D seems ok if you have seen the trick.
How to solve D?
It can be noticed that the answer of a string $$$s[0..n-2]$$$ is the product of the indexes with letter '?', thus the problem can be solved easily.
Consider reversing the order, taking characters from back to front. In this case, '<' and '>' force you to choose the minimum/maximum, and '?' force you to choose value other than minimum/maximum. It can be proved that the conclusion is correct.
I still didn't quite get the intuition behind the approach. Let's use this string for example :
<>?<
The third index is
?
, so there will be three possibilities to fill the slot. What are those 3 possibilities?I use 0-indexed string, so there should be 2 possibilities.
got it. thanks
Thank you for clean explanation. The intuition is so cool, I love this question.
(and I'm simultaneously depressed for not solving it lmao)
Thankyou very much, understood it very well!
Consider the relative order of all the elements, a single "order sequence" corresponds to a permutation. We consider how many of these sequences are achievable by iterating over [1, n]. If a[i] = < or a[i] = >, then we can only place it in the front or back of the current sequence, resulting in an *1 to the answer. Otherwise, the previous i — 1 numbers have i — 2 spaces between then, we can just randomly insert a[i] into one of these, since any two ways of insertion is equivalent, this would result in an *(i — 2) to the answer.
For the operations (i, c), we notice that every single one of them only result in the change of ways to insert a[i], thus we can make our answer /(i — 2) if it is not ? before the operator and *(i — 2) if not ? after it. We can prework inv to speed the process up to O(n).
btw, note that if a[1] = ?, the answer is 0.
You can have an order from the first i chars of the string. Now if you get a '>' then a new element has to be put at the end of the order and if you get '<' then put it at the beginning. If you get a '?' then you can put a new element at any position except first and last. There are i-1 such positions. So total possibilities is the product over all (i-1) such that s[i] == '?' (one based indexing).
Thanks Here we are not concerned about which elements will come at a specific postion, rather we are concerned about how many ways are there to place the a fixed element a[i] in the ongoing set Am i correct?
Could you explain what do you mean by "order" and use some example if possible?
Nevermind. I think I've got it. Thanks for the insight. Let me share an example to help other readers.
Say our final permutation will named $$$p_i$$$
Assume we have another sequence of order named $$$ord$$$ where $$$ord_i$$$ is the relative order of $$$p_i$$$
for example, an order sequence $$$[2, 3, 1, 5, 4]$$$ means $$$p_2 < p_3 < p_1 < p_5 < p_4$$$
Then from string $$$s$$$, we can "build" the order sequence one by one
For example let's use $$$s = $$$
<?>?
and process each character one by one<
then $$$p_2 < p_1$$$?
then $$$p_3$$$ can only be put between $$$p_2$$$ and $$$p_1$$$ so $$$p_2 < p_3 < p_1$$$>
then $$$p_4$$$ can only be put in the end so $$$p_2 < p_3 < p_1 < p_4$$$?
then $$$p_5$$$ can be put at $$$3$$$ different position that is between $$$p_2$$$ and $$$p_3$$$; $$$p_3$$$ and $$$p_1$$$; or $$$p_1$$$ and $$$p_4$$$ (it cannot be placed on either left/right end because otherwise will make the $$$s_3$$$ not equals to?
Therefore because there's $$$i$$$ possibilities to place $$$p_i$$$ on the order sequence, we multiply the result by $$$i$$$
Why is it that the problems I don't solve always have the most elegant and easy solutions...
loved B. (definitely didn't waste 2 hours on it dealing with precision errors)
Can someone offer me the test case 2 of C? I think my code is true but WA in the case 2
The case that broke my attempt was:
Output should be
o
I can pass this test case. But I still don't know why I can't pass the 2nd case
I found a problematic test-case:
The output should be
n
, but your program outputsp
can you pls help me
consider below tc
my solution,
s1 = pbdtm, s2 = pbdm
, output =d
jury's solution,
s1 = pbdtm, s2 = bdtm
, output =t
pbdm < pbdtm
why my solution is incorrect?
bdtm
<pbdm
Anyone has done B I find it tricky and difficult. If anyone was able to do please help me...
You have to consider 3 cases:
O and P are closer to B than they are to A. That means that both O and P are both in the circle around B, so the radius is chosen as the bigger distance of the two to B
O and P are closer to A than they are to B: Similar as case 1
One of them is closer to A and the other is closer to B: That means the circles are going to intersect, so you take the distance between A and B into account as well, while making sure that the points P and O lay in the circles
In case 3,is that perfect to just take distance from a to b and divide by 2? Because the points are inside them this is not guaranteed. The only thought for which i Didn't solve it.
No, because if you take the distance between A and B only, it might be the case that P doesn't lay in those two circles.
I was able to get AC with binary search, which was very obvious.
The tricky part was writing code to check if your radius (w) was valid. There are only two cases; if both the origin and the point P can fit in the same circle, and if they are in separate circles. If they are in the same circle, (i.e if the distance of (0, 0) and (px, py) to the center of the circle is less than your radius), then yes, they fit.
If they are in different circles, then both circles must touch each other or overlap (i.e 2 * w must be >= the distance between the centres of the circles).
Then you can binary search. Instead of incrementing/decrementing by 1s, do so by 0.0000001
I did some case work :
Case 1 : starting and ending points will lie in circle having 'a' as center i.e. dist(a, origin) <= dist(b, origin) and dist(a, p) <= dist(b, p) then only lantern a is relevant so we can set ans as max(dist(a, origin), dist(a, p))
Case 2: starting and ending points will lie in circle having 'b' as center similar to case 1 but lantern b is relevant
Case 3 : the starting and ending points lie in different circles, so we take the answer as the maximum of the distance between origin and the closer lantern, distance between target and closer lantern and half the distance between the lanterns (as this time we need both the lanterns so their circles must intersect or touch each other)
Maybe Case 1 and 2 are irrelevant but I came up with this during contest so no optimisations :)
In case1 Your distance is max(dist(a,origin),dist(a,p)). Not max(dist(a,origin),dist(b,origin))
my bad,, thx
IMO it's even easier than A
is D some well known trick?
See here.
No answer is just the product of $$$'?'$$$ indexes
yeah why :/
Skipped D, solved E, after seeing submissions on D I am very confused on why it works
Just consider how the answer changes when a new character is appended to the end.
Read the string from right to left instead, and figure out how many possibilities there are.
How you solved E. Is there a well-known technique? Help me out.
How to solve E? QAQ ~
Sort the programmers in decreasing order by their strength; if we want to complete a subset of projects, it's optimal to use a prefix of the best programmers. Let $$$dp(S)$$$ be the minimum prefix needed to complete a subset of projects $$$S$$$. Let $$$nxt(i, j)$$$ be the minimum number of programmers needed to complete project $$$j$$$, if we're starting at the $$$i$$$'th best programmer in decreasing order (i.e., we use programmers $$$i, i+1, \dots, i+nxt(i,j)-1$$$).
Then for $$$j \not \in S$$$, we can update $$$dp(S \cup {j})$$$ with $$$dp(S) + nxt(dp(S), j)$$$. The values of $$$nxt$$$ can be precomputed in $$$O(NM)$$$, and computing $$$dp$$$ can be done in $$$O(M 2^M)$$$ using bitmasks. There's a bit more work to be done since we have to reconstruct the answer, but that's entirely routine.
How do you precompute the values of $$$nxt$$$?
For a programmer $$$i$$$, let's find the minimum value $$$x$$$ such that programmers $$$i-x+1, i-x+2, \dots, i$$$ can complete project $$$j$$$. The inequality $$$\frac{B_j}{x} \leq A_i$$$ must hold, so $$$x = \lceil \frac{B_j}{A_i} \rceil$$$.
This tells us that $$$nxt(i-x+1, j) \leq x$$$, since it takes at most $$$x$$$ programmers if we start at $$$i-x+1$$$. In addition, $$$nxt(i, j) \leq nxt(i+1, j) + 1$$$. Therefore we can compute $$$nxt(i, j)$$$ for a fixed $$$j$$$ in decreasing order of $$$i$$$.
is E bitmasks again?
What a pity, got WA on problem D because I forgot to judge s[0] == '?' in the first output...
i got 2 WA for that one mistake. Luckily fixed in the last minute
imho ABC harder than usual. And can anyone please tell how to solve E, thanks a lot!
What's the idea behind C? How to solve it?
Can someone please explain in detail. (I was halfway there.)
what is ur thought process?
the String can be divided in inc,inc,inc,dec,dec,dec parts. Then we can find the right part to search in using basic maths.
Then just simulate the process.
What's the right approach??
lets stimulate the deletion: traversing from left to right, for each element we'll remove the elements(which are not already removed) to it's left which are greater than the current element. While removing we'll store the indexes of the deleted in order of their deletion. Note that the above part can be done using stacks
Now we'll see the length of the segment for the given n and build that string by using the indexes in the reverse order, and then just print the element at the required index in the new string.
Hmm. This is how i exactly implemented it. I knew the approach but lack implementation part.
I did it using stack. Coz what you care about is the elements at the front. While your current element is less than last element of stack , keep poping it out. Finally your stack will be of length l or you may terminate in middle if length is reached.Just add index of string to the answer. For finding length and index you can use an O(n) loop which adds i where i goes from n to 1 and compare it with pos each time.
Yeah makes sense.
Why the heck, stack didn't came in my mind.
Guess this is what happens when you give contest after months.
Thanks though!!
In my opinion, B and C are harder than D.
maybe you are too good at combinatorics :)
Why was C so hard? Even my O(n) solution gave TLE.
std::string::erase is linear in time complexity.
https://cplusplus.com/reference/string/string/erase/
This means your code is $$$O(N^2)$$$
Yeah just realized that was the problem. How do I do it without std::string::erase?
Use std::set for the indices of the string? Think more about this
Another idea, use a prev array, where prev stores the element before the current idx. So at the start prev[i] = i — 1. When element prev[i] (which is the element before i) is deleted, prev[i] will then become prev[prev[i]]. Make sure you move on from the current element when prev[i] < 0.
Maybe you can use crope,it is $$$O(\log n)$$$
Maybe you can use stack.
Anyone know how to solve F ?
Turn back time and assume that at moment $$$0$$$ diamonds $$$2$$$ are stolen and at moment $$$d$$$ diamonds $$$1$$$ are stolen.
For $$$t=1,2$$$ cameras, the time interval to turn it off is determined. For each $$$t=3$$$ camera, it has $$$2$$$ choices:
Note the left endpoint of each interval $$$\in { 1,d+1 }$$$. If a decision has been made on what to choose, by Hall's theorem, the illegitimate $$$\Leftrightarrow$$$ appears in at least $$$1$$$ of the following cases:
Let's assume, $$$t=3$$$ are turned off in $$$[d+1,s]$$$ by default. Each time, find $$$\min r$$$ such that $$$>r-d$$$ cameras need to be turned off in $$$[d+1,r]$$$. At this point, we need to pick a $$$t=3$$$ camera in the interval and change it to $$$[1,s],[d+1,d+s]$$$. It can be found that the larger the $$$s$$$ chosen, the easier it is to satisfy all the $$$2$$$ restrictions imposed by Hall's theorem. Scan $$$r$$$ while maintaining the stack of $$$s$$$ of $$$t=3$$$ cameras in $$$[d+1,r]$$$, taking the top of the stack ($$$\max s$$$) each time.
If $$$1$$$ of Hall's theorem is satisfied by this scan, it is straightforward to determine $$$2$$$ once. This is because changing any $$$t=3$$$ makes the $$$2$$$ restriction tighter. Thus the problem is solved by enumerating $$$d$$$ at the beginning and sweeping $$$2$$$ times, with total time complexity $$$O(n^2)$$$.
I'm ashamed of myself for accepting without thinking that in problem D, I fixed '>' as N, N-1, N-2, ... and '<' as 1, 2, 3, ...
i did the same thing.
Well, You're not alone.
Same :(
OMGOGMG IM REACHING SPECIALIST YAYYYY
The problems were actually good. Got stuck in B itself, and took almost an hour to solve it..
I tried solving B with Binary Search, but was getting wrong on Test Case 2. Any hints? https://codeforces.net/contest/1886/submission/227399641
'if (r + r < dist)' is the problem.
A doesn't have to overlap with B. Everything could be done with 1 lantern.
Wow, thanks. I changed the solution now. And it worked. https://codeforces.net/contest/1886/submission/227436004
How you decided that maximum search space for r will be 1e10 ?
It should be much smaller than 1e10. just think how big r could make circle A or B covers both O and P.
Can anyone help me with problem B why I am failing on 2nd testcase 227433725
double num3 = ((px - bx) * (px - bx) + (px - by) * (py - by));
variable error. u did px-by not py-by.Thanks,after submitting for 15 times I don't realise this silly mistake
Can random work for E? I basically tried to shuffle the projects and even though I did a silly mistake in the contest, I'm wondering if this idea would work in the end 227434343.
Thank you.
What was the intent of making the answer be output on a single line in problem C? Was it to make implementing the checker easier?
The checker for this problem wouldn't have been a difficult one to implement imo. And I don't think printing in the same line would had have any impact on it..
it's actually very convenient to test your program, since you can query for all positions of the same string and get the resulting concatenation.
Personally, I found it very convenient for testing purposes. I would start with a string, delete $$$x$$$ characters, and then I want to check if my program handled this correctly, so I set up my input to write all characters of that resulting string (so the test cases involve the same original string with the position range corresponding to my desired reduced string). I even wrote a separate program to generate such input text, given the original string and position range.
I don't know if this relates to the reasoning behind why the output was in one line, but I definitely appreciated this!
Video Solutions: ABC
Video Solution — Problem C: Better Explanation.
mathforces
Could anyone tell me what i am doing wrong with problem C, my logic is that we always have to remove the first i where s[i]>s[i+1] if there is no such i, remove the last character in the string repeatdly until you reach the ans, i implemented it using linked lists My code
Found the error i was taking the pos in an int variable fml
Could someone assist me in debugging problem C? I'd like to understand what went wrong with it.
My approach is quite inexperienced.
Problem C
Thanks.
You don't always remove the maximum character. For example, if your string is baz, removing b gives you az, but removing z gives you ba. Here, az is lexicographically smaller than ba, so you remove b instead of z.
The correct character to remove is the leftmost character which is bigger than the character in the next index.
That being said, even if you remove the correct character, your approach of manually finding the character to remove and appending the string would take $$$\Theta (n^2)$$$ time. For $$$n$$$ as high as $$$10^5$$$, this will definitely result in Time Limit Exceeded in later tests.
Hello I have followed the same idea, removing leftmost s[i] when s[i] > s[i+1]. It runs in O(n) time. The no-spaces-bw-testcases rule makes it impossible to find where I'm going wrong. Please help me if you can.
My Code
I checked the submission details and found one problematic test case:
Your program outputs
k
, but the correct output isa
(reduced string isakb
at that point)aw nuts, messed up with the loop condition. Accepted now :). Thanks so much!
Why did my submission for E fail on test 16?
Here you need to find the real "lowest" one, not from the first one, because the first one might be dropped.
Accepted, thank you so much!
For Prblm D we can go like this, We will start filling from backwards.
Initially we will have n elements in our hand,
Suppose at a position i, we had x elements in our hand left to be filled somewhere, Now if s[i]=? Implies that we can't fill the ith position by the maximum or minimum among the x elements which we have, so we have x-2 choices
else if s[i]!=? Then we have to either fill it by the minimum or by the maximum hence only 1 choice
Simulating the above logic finally boils down to
at ith position we have either i-2 choices if s[i-1]=? else 1 choice
Considering 1-based indexing.
The solution to D is intended to be done in reverse, which makes everything far simpler, but how is it equivalent to doing it normally?
So for reversed approach, while you are not seeing a ?, your permutation is fixed. The moment you see a ? You cannot remove first and last element which means you can remove any of the remaining i-2 elements.
In forward approach, as you go on filling your array , you set some unknown numbers in your set. The moment you see a ? you are like I can fill this number in any position in my set except the first and the last position so in total again i-2 options
It's not about Monocarp performing the operations in reverse; we still assume Monocarp performs the actions in the order specified, but our analysis considers the number of possibilities in reverse order.
Consider the last character; when Monocarp added the last integer at the end of the activity, what could this integer have been? If the last character is >, then this means that the last number Monocarp added must have been $$$n$$$ (only one possibility). If this last character is <, then this means that the last number Monocarp added must have been $$$1$$$ (only one possibility). If this last character is ?, then this means that the last number Monocarp must be between $$$2$$$ and $$$n - 1$$$ ($$$n - 2$$$ possibilities). We can then extend this argument to all indices in reverse order.
Yeah I later realized that looking at the operations in reverse is equivalent to looking at them normally. It doesn't change the answer at all and is far simpler than doing it normally
If you have solved the basic DP tasks from atcoder, the D is a no-brainer problem. 😶 https://atcoder.jp/contests/dp/tasks/dp_t
but you didn't solve it using dp
great!I get +70 points!
And i will get candidate master only +9!
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
it was a really great contest and i learnt a lot from it
The problem D in this contest is very interesting