Hello Codeforces!
On Jul/08/2022 17:35 (Moscow time) Educational Codeforces Round 131 (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!
Our friends at Harbour.Space also have a message for you:
Hey, Codeforces!
Welcome to the 131st educational round hosted by Harbour.Space and Codeforces.
Quite exciting, isn’t it? Now it's time for you to dive deeper into the competitive programming world with the 10 days intensive Summer Camp organized by Harbour.Space and Leagues of Code.
Don’t forget about the discounts for participating in our Summer Camp. Every member of the Codeforces community gets a 30% discount for on-site participation or a 50% discount for online participation with promo-code CFLOC2022.
Our Summer Camp is a training program that will teach participants competitive programming. It will take place in Barcelona and online on July 18-29, both participation formats are available.
We are inviting students ages 10 to 24, interested in improving their skills or seeking intensive, high-level training prior to the IOI. Teachers in the camp will be ICPC World Final Silver medalist 244mhq, SWERC 2022 Winners MaksymOboznyi, ICPC World Final Champion pashka and others. Participants will be divided into classes based on their level and previous experience. Classes will be held in English.
Good luck with the round!
UPD: Editorial is out
Problem A is a XOR Problem :D
upd.: why so many downvotes?(
Rare to see no constructive algorithm in this contest.
****
say something irrelevant: what happened to the last div2? my little ratings is missing. hope i can get them back in this round. TAT
New ratings should soon be returned
I shook hands with almost all grandmasters in the blog and all candidates
excited for my first round
I know about the A problem and I am gonna reveal it I am 100% sure it would be of xor :|
More like :^
.
What’s up with people commenting about Div 2A being a xor problem? Do people hate bitwise operation problems? I always thought problems about bitwise operations are possibly one of the most versatile topics, from basic observation problems all the way up to like FWHT, and one should definitely practice them and for most “easy” problems, the most you have to do is knowing the basic properties+considering each bit separately. Lmk if you disagree
I am really struggling to solve bitwise questions. Any tips?
Well, I guess that xor is an uncommon topic for beginners, so appearing on div2A would be a bit scary to them. But I don't think they were that bad, after a few rounds I got used to those problems and it was pretty fun solving them too
Don't even see how you needed XOR here — there's only 3 cases:
Edit: I misremembered the question, the answer is 2 only if all the spaces are filled.
Oh this comment was written before the contest in response to some people above complaining about xor problems lol.
Oh, I see. My bad for misunderstanding then.
I saw someone else complain about it which was why I responded, but they might have been complaining about a previous contest as well.
high HOPES with this round
can anyone guess the rating level of 3rd problem in today's contest?
<2100
spermutation forces
Everything is correct with my code for problem C, but I'm getting WA on test case 2
That means your code is not correct.
Can it be solved by heap?? just asking
Yes, its possible. Look at my code that I submitted after contest.
Good round, interesting tasks. Although i'm too weak to solve most of them during the contest.
Thanks for the round, thanks for Codeforces.
Waiting for the result and rating change... (I'm so unwilling to receive such a low rank...)
God, how much more time will it take to reach Cyan?
Overall, a balanced educational round
Hmm, D doesn't budge for me :D.
Any tips? Only thing I've realized is that we always know where 1 is but other than that it may depend :<
If $$$\lfloor \dfrac{i}{a_i} \rfloor$$$ is equal to $$$b_i$$$, it means that $$$a_i$$$ should be in some segment of integers. For each $$$i$$$, generate this segment, and then match each value from $$$1$$$ to $$$n$$$ with a segment greedily.
I find the segment thing. I just did'nt know how to match the values from 1 to n.
I though that sorting the segment by length could help. But it's gives WA
Sort by left border, then keep a data structure that stores all currently opened and unmatched segment, sorted by their right border. When we come across a number while iterating from $$$1$$$ to $$$n$$$, we match it with an open segment with the lowest right border (because it will become unsuitable earlier than other segments).
Why is it incorrect to just sort by the right border only ?
why does sorting the segments by length in ascending doesn't work ?
Suppose there are two segments with values $$$[1, 2]$$$, one segment with values $$$[3, 3]$$$, one with values $$$[4, 4]$$$, and four with values $$$[5, 8]$$$. Then, these four are the longest ones, but no point from $$$1$$$ to $$$4$$$ can be matched with them. So we need to start with the ones with the minimum left border.
Would it be possible to get the total number of valid permutations to get sequence b?
I was thinking in terms of the total number of segments that have the same closing time, but could not reach a conclusion.
Looking at the solves, probably my solution is way too complicated and there is something simpler..
First decompose each element into the ranges it can exist if the answer is k (which is i+1 to n if it is 0, i/(k+1) + 1 to i/k otherwise).
Keep these ranges grouped by starting position (and also sort by length). Now, for the i'th turn do the following
1: Add the smallest range by length from the i'th group (i.e. all ranges that are of the form [i,?]) to your processing group. 2. Remove the smallest range from your processing group. Place the index of this range at position i 3. Whichever group the range you just removed was from, add it's smallest range to your processing group.
Submission:
163296621
In D we can calculate foreach position a minimum and a maximum value, consider them to be segments. Then sort these segments by the min value.
Iterate all numbers i from 1 to n, and foreach number collect all segments with $$$min<=i$$$. From these collected segments choose the one with minimal max value, and mark that segment as used.
It took me ages to get the formulars for min and max by trial and error. How is this done correctly in time?
$$$min=((i+1)/(b[i]+1)+1$$$ ???
$$$max=(i+1)/b[i]$$$ for b[i]>0 ???
Dang really nice solution.
Hmm maybe it would be easier just binsearching min and max for each segment :D?
I guess that would be simplest for me, thanks for suggestion, did not thought of that.
x>=k*y and x<=k*y+y-1 if x/y=k. Using these two inequalities you can find range of y.
I had zero trouble with the formulas, but I struggled for ages with coming up with some range assignment algorithm...
It is simple sweepline. Of all the segments currently open you should assign the current number to the segment that closes earliest which is obvious.
Thanks — I suppose I'm new to this idea, it wasn't obvious to me
the same
Yeah so you know that floor(i/ai) = x, i/ai <= floor(i/ai), i/ai <= x, ai <= i/x,
floor(i/ai) + 1 > i/ai, x +1 > i/ai, ai > i/(x+1)
and that's how you do it
$$$\lfloor{\frac{i}{a[i]}} \rfloor$$$ is $$$i \; div \; a[i]$$$. And $$$i \; div \; a[i]$$$ is the $$$max$$$ number $$$v$$$ such $$$a[i] \cdot v \le i$$$, but $$$a[i] \cdot (v+1) > i$$$.
Couldn't find the formulars but managed to binary search it :3.
Is greedily giving tasks to workers with no task right approach for C?
Advanced Binary Search (like Book Allocation Problem) will do for C.
How did you conclude it is solvable by binary search? I could only think in the greedy direction
good job, the tags are: binary search,greedy. you have to apply the binary search algorithm to find the minimum hours needed. for example if 100 hour is enough so what about 50? not enough? ok maybe 75 will be enough. every time you change your range you have to check: can the first worker finish his favourite missions in (mid) hours? if he can finish so he can also work on some other mission that will take 2 hours so the first worker will do: fav + (mid-fav)/2. if he cannot finish in (mid) hours he can only work on: (mid) missions. and you have to do this for every worker with a for loop (or a while loop) if the total sum of the missions that the workers can do is greater or equal to (m) then the time you choose is a good answer, save the answer and move to a smaller range, but if it is strictly smaller than (m) it is not valid and you need a bigger (mid). :)
we can just notice that if we can finish all the tasks in x days, we can finish them in x + y (y > 0) days as well, and at opposite: if we cant finish in x days, we cant finish in x — y days as well. and it's direct hint for binary search (but i confess i was thinking about greedy solution for about half an hour...)
Binary Search Approach will work
it's not too easy to implement — eg i was thinking about it for a half an hour, then i just wrote binsearch, which was really easier than the greedy solution
Assign all 1-tasks to the workers, maintain the assigned tasks per worker in a list.
Also maintain the last finish time of each worker in a queue, or sorted set.
Then take first/earliest worker and last/latest worker from the queue, and asign a task from the latest to the earliest, put both again with the updated values onto the queue.
Repeat until first and last differs by at most 2.
I did the same thing but I am getting TLE.
https://codeforces.net/contest/1701/submission/163271995 This is my code.
Can you tell what's wrong?
I guess it should be >2 here:
while(maxh.top()-minh.top()>1){
Just assign all workers to tasks they can do with max efficiency.
Now place them all in set. As long as largest element and smallest in set differ by >=3
Reduce 1 from your largest element
add 2 to your smallest element
(you're simulating giving a task from one worker to another)
In the end output the largest element in set
Yeah, I thought of that, but I'm struck in getting largest and smallest duration after every simulation. How do we efficiently do that?
Multiset if you're using C++.
The element at M.begin() is the minimum; the element at M.rbegin() is the maximum.
If you have a multiset of workers' task durations, repeat the following until the
min duration >= max duration - 2
: subtract one hour from the highest duration, add two hours to the lowest.In your solution for C, why did you delete the lower bound of lo and hi instead of deleting lo and hi itself?
To be completely honest, it’s because I’m not very good with multisets so I do the safest possible thing. I only really took up C++ last year and before that I used Python, so my skills have a long way to go.
The specific reason is that in the past I’ve made errors by accidentally deleting multiple instances, or the wrong iterator, and I know for sure that lower_bound is safe. One day I will bother to learn how everything works properly.
Why couldn't the memory limit for E be 512 MB? I think my solution would have passed 163297562. I didn't have the time to make optimizations :(
Still thanks for the round.
Oh, I'm really sorry about that. I thought to make it 512MB but when I was calculating something like "5000^2 integers", I found that it is only about 100MB, so I decided that even two such matrices will fit and I decided to keep the memory limit as it is. :(
UPD: Though, I just replaced all int matrices with short matrices, and your solution passed with 157MB peak memory used. I'm not blaming you, just informing that you could do something like that in the future. Because, for example, in this problem you couldn't meet any numbers greater than $$$O(n)$$$, so short is more than enough.
Ohh, slipped through my mind that shorts are of 2 bytes. Thank you.
Why is this approach incorrect for D?
Every index i is satisfied by a range of values: [ (i+1)/(a[i]+1), i/a[i] ]. Now I sort the ranges increasing based on their left boundary. Now in these ranges, every value from 1 to N is covered atleast once, because it's given that the answer is always possible. Now I greedily give values 1 to N to the respective indices of these ranges in sorted order. I feel intuitively that this should work but it doesn't.
Consider the segments in sweepline fashion. In all the segments that are currently open you should assign the current value to the one that closes the earliest. If you assign values in the manner you said then this wouldn't happen.
Ahh got it.. Thanks.. Basically what I did would fail for cases where, let's say a later index has only one range ending at it, but this range gets assigned a former index because I'm sorting by starting points only
what if n=3 and the ranges are (1,3) (1,3) (2,2)? I had also encountered the same problem but then realised that you have to sort by right boundary. I may still FST tho idk.
In that case you would assign (1,3) first and then (2,2) next and then (1,3)
yeah that's what i am saying that you have to sort by right not left
range of values is [ (i/(a[i]+1)) + 1, i/a[i] ] or ( i/(a[i]+1), i/a[i] ]
1
7
0 0 0 2 0 6 2
Should be [X,X,X,2,X,1,3] (remaining numbers can be anything greater than their index)
Fuck you and your shit harbour space, this is a disgusting contest. downvoted
You should actually say that to your brain :)
What can be the difficulty rating of C?
around 1400 I believe.
1300
Can anyone give me a hint on C ... like what I can try on that ??
Binary Search the Answer. See this and this
Ok thanks
Binary search is fine but overcomplicated.
Think of it more simply. Assign all tasks to the skilled person initially. Under what circumstances can you continue to make improvements?
To give a hint: if someone is idle for 3 hours and there are tasks ongoing in that time, they could have done a 2 hour task and taken it from someone else.
Ok thanks :)
Too standard and FUCKING STUPID problem F. How can this *1400 problem be put in the position of F??????
You guys just downvote for my protesting the contest??
I read both A's and B's statements incorrecty, and both of my solutions for wrong problems passed 1st tests :((((((
Can anyone give a small testcase on which my submission gives wrong answer. This is my submission. 163284420
bruh imagine you're a vendor and tell that the project can be finished in 343599 hours
and then the next vendor finish it in 2 hours xD
Yeah I'm not getting why it's giving wrong answer. I just want to see small testcase on which my submission fails.
The problem are actually the large test cases since q and p can become very large. Make q and p long long and your solution should be correct.
Thanks... Why I'm so dumb...
I just realized that i made the same mistake. But somehow my solution passed ...
i have a question with problem C
from this code 163304299, i had a integer flow. so i change all int to long long like this 163303533, then i got correct.
plz tell me why...
your rest can be negative number, and it can be less than INT_MIN.
Why My solution for question C keep on giving wrong answer answer on test 2 I am using binary search https://codeforces.net/contest/1701/submission/163306213
Problem C. Hello, can not imagine counter example for this approach, can you please help? Thanks.
map<int, int> a
keys of which are corresponds to worker itself and value is corresponds to the current worker's worktime. Eg. ifa[i] = n
, then workeri
is already workingn
hours. On starta[i] = 0
forall i.Let
i
be the specialist for the current work. Then, if we use him, work will be finished on aa[i] + 1
hour. Otherwise we can take non-specialistk
with minimala[k]
and finish this work ona[k] + 2
. So just took a minimum between those two.k
, thena[k] += 2
, elsea[i] += 1
.a
and find maximum.Here is my code.
Had a similar error, try this:
1
2 6
1 1 1 2 2 2
Your code gives 4, answer is 3.
https://codeforces.net/contest/1701/submission/163296776 Can you please help me find an example where this greedy solution does not work?
1
5 15
5 5 5 5 5 5 5 5 5 5 1 2 3 4 5
Correct answer: 5. Your answer: 6.
Hi Guys, What could possibly be wrong with my Problem C submission https://codeforces.net/contest/1701/submission/163308184
My approach is very greedy, but it seems to work.
Is there a way to get the buggy test case? Any kind soul help this poor fellow here please.
You fail this case:
1
6 9
1 1 1 2 2 2 3 3 3
Ans = 2, yours = 3
Anyone Solved Problem C using Priority Queue? My solution is passing most of the tc. Anyone understanding the problem with my code please help Solution Link: https://codeforces.net/contest/1701/submission/163305827
https://codeforces.net/contest/1701/submission/163281220 Here is my shitty but AC for now solution. Binary search is probably easier but I still can't solve any binary search problems that aren't leetcode easy so it never occurred to me during the contest(should probably start practicing it lol) plus I am addicted to using priority queue. I saw some people use multiset though which also seems way easier. I initially tried multiset but switched to priority queue. It is not the multiset fault though, I just had wrong idea at the time. I also don't know how to analyze algorithms but I am pretty sure my solution is $$$O(n \cdot \text{log} N)$$$ which is fine for 200000. Hopefully I don't get hacked lol.
**Update : ** I resubmitted my solution with comments and removed some extraneous code which should make it clear what the code is doing.https://codeforces.net/contest/1701/submission/163322218
I made video Solutions for A-D in case someone is interested.
Can anyone point me to more problems like D that I can practice? It would be a great help. _Wizard_King_ mentioned in the comments "It is simple sweepline". Where can I practice more of such problems. (thanks)
This, This, and This
I coincidentally did 1348F - Феникс и память a few days ago, which had the same idea as problem D of this round.
Instead of gaining 100+ points, I'm going to lose 50 points because I forgot about longs on question c, sad day for me.
Can someone point out what's wrong with my submission. Failing on TestCase 3. https://codeforces.net/contest/1701/submission/163279323
What a pity. I could have made a D
Will we get rating for this contest
Standings for individual divisions are broken: Division 1, Division 2
When will the editorial be available?
I don't seem to understand the time limit for F because there's a normal $$$O(Q \log M)$$$ solution using a lazy segment tree
One of the implementations stores a $$$3 \times 3$$$ matrix in each segment tree node, and the operations are like "multiply by a $$$3 \times 3$$$ matrix on segment". I decided I didn't want to cut it off.
Thank you for the explanation, that's reasonable. I thought there was some kind of $$$O(\sqrt Q)$$$ stuff involved.
Any hints for problem E?
Sorry for my impatience, could anyone explain me the solution to problem E?
Please tell me how the problem F is solved.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
I couldn't register for the camp on time, is there another camp anytime soon?