On Mar/05/2019 18:05 (Moscow time) Educational Codeforces Round 61 (Rated for Div. 2) will start.
This round is organised in collaboration with Hello Muscat Programming Bootcamp and supported by Sberbank, General Partner of the boot camp and one of the largest banking leaders of Eastern Europe, providing thousands of jobs and innovation in the financial industry.
As the Hello Muscat Programming Bootcamp’s General Partner, Sberbank made it possible for students from some of the world’s top universities to attend the bootcamp, by sponsoring their participation. This includes students from Saint-Petersburg State University, Moscow Institute of Physics and Technology (MIPT), Penza State University, National Research Mordovia State University; MRSU, ITMO, Higher School of Economics / Moscow, Volgograd State Technical University, Lobachevsky State University of Nizhni Novgorod, Moscow Aviation Institute, Tyumen industrial University, University of Haifa, Northern (Arctic) Federal University, Saratov State University, Ural Federal University.
Hello Muscat Bootcamp will take place from 9th to 15th of March, and 120 students from 24 universities, including MIPT, Saint Petersburg State University and University of Tokyo will compete and practice side-by-side, smoothing the road towards the April World Finals in Porto.
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 7 problems and 2 hours to solve them.
The problems were invented and prepared by Roman Roms Glazov, 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 participants!
Congratulations to the winners:
Congratulations to the best hackers:
And finally people who were the first to solve each problem:
UPD: Editorial is out
Wish interesting tasks!
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
omfg i cant waitr
i guess most of cf users are poor
I thought you stopped leaving such comments because of fear to be banned
it was sarcasm, dude, i don't fear
Hope test cases will be stronger than previous. Good luck Happy coding
I hope the contest is not declared unrated this time and no technical issues or unethical behaviour from the community members.
I want high rating.
Wish you happy coding =)
I want easy tasks so I can get high rating!
Dude, with easy tasks everyone will solve them, so it become a speed contest, which is not "educational" and doesn't make sense, cause we are here to learn and have new ideas ...
I want hard tasks so others can get low rating!
thanks you for getting low ratings everybody!
if you want high rating you must have good rank the rating depends on rank not how many tasks you solve :)
if you solve more tasks you have a higher rank
I always hate delays But could you please start contest later? We have just left school (Also i know that i am not an important person but i think for most Iranian person this time is really bad)
This website is not for Iranian only !
Don’t talk with full mouth
in this case your fully right! ;))
This wouldn't have been a problem if you stuck to the terms of the nuclear deal
Please suggest some problems like C today for practice
I think you solved the problem in a more complicated way. It has simpler solution using some prefix sum and iteration without anything special.
thanx , man ! :-)
Why my code got Runtime error on test 1 on problem C, while same code works fine locally and ideone
How to solve F?
dp1[l][r][a] = Minimum to delete all in range l..r except for character a dp2[l][r] = Minimum to delete all in range l..r
Can you please explain time complexity of your code and how does it pass , as to me it seems that the time complexity is O(26*n^3).
It is O(26*n^3), and the constant is low enough.
You can straight up solve for DP(i,j) = answer for substring s[i:j]. It takes O(n3) time and O(n2) memory. See my solution here.
How to not get MLE on G?
Was D binary search + simulation?
How to do the simulation?
Greedily charge the laptop that will run out of power the earliest.
Yup. However, you should probably do simulation in O(n + k) to avoid TL.
How to do the simulation? :)
I think storing a[i]/b[i](how many minutes can laptop run without charging) and taking minimum every minute will work.
What Jakube said. I did it by maintaining such an array that i-th its cell contained all the indices of laptops to run out of power on minute i.
Use priority_queue with the eariest (t[i] = a[i]/b[i]+1) on top. Each time you will take the top and add to its a[i] by x then push it in priority_queue. Note that if you take a laptop with t[i] > k then you can stop it immediately. Sorry for my bad English
I tried to implement your solution to problem D but i was surprised this morning that i was hacked, what's wrong?
His approach might got TLE if implemented poorly.
So what's the catch, how to avoid TLE?
Refer to Pik's comment right above. Instead of p.queue, use arrays.
Very tight time limit on problem D. You still even get TL with O((n + k log n) * log(2e12)) solution.
But I pass with 2432ms time :v
You got too much luck yesterday bro :D
How to approach problem E? It seemed more like math/greedy than anything else, but I couldn't come close to a solution.
Well, model solution does something like that:
Let L be the least common multiple of all numbers from 1 to 8 (L = 840). Then, if in the optimal answer we need to use c items of weight i, we may write c in the following form: , where . Then we may merge items of weight i into p items of weight L, if we fix q.
This allows us to use the following dynamic programming solution: dp[x][y] — the maximum number of items of weight L we may obtain, if we tried x first types of items, and got total weight of y while using less than items of each type. Note that the second dimension should have size 8L, since it is the maximum possible sum we may obtain in this case.
But it seems that some participants used different heuristics and random. We aren't actually sure if such solutions should fail.
I decided to post my randomized solution as a blog post because I thought it was a pretty interesting, unintended solution :)
You could solve it my noticing that if the total sum is bigger or equal than W, the answer must be between W-8 and W. So I approached the total sum to between W and W+8 greedly removing the itens and then I checked if I could remove the difference between the actual sum and the answer, this could be done using smaller knapsacks as the difference would be no more than 16.
Just the problem was searching range. I was in a fear as hell. Codeforces should check their algorithm time complexity, not just tight range.
Is O(n * logn * log(2e12)) expected soln of D??
How to solve F??
I think so, but with bad optimization you'get TLE on 22 or 27th test case.
was intended. It was more like "I'd like you to do linear simulation but won't mind if you sqeeze extra log on top of it".
The check function is linear time.
Let dp[i][j] indicate minimum number of ways to delete the substring from i to j. Now there are 2 possibilities either character at i and character at j are equal or not.
If str(i) == str(j) then dp(i)(j) = 1 + dp(i + 1)(j — 1) Else dp(i)(j) = min( 1 + dp( i + 1)(j) , 1 + dp(i)(j — 1))
I think D deserved just a little higher time limit. My O(log(1e12)*(k*log(n)) soulution didn't pass, I tried to optimize best as I could.
I passed with the same complexity, but I had to use
priority_queue, got 3 TLs because of
Oh.. I didn't know that priority_queue is faster.. Thanks
std::multiset is god-awfully slow. It's also sometimes possible to replace the implementation with a std::set<pair<T, int>> instead.
Well, I did with set<pair<long long,int>> it didn't help.
I hate such problems. Why Codeforces push us hard as hell in terms of time limit? I think correct time complexity is enough.
See the other comments, the intention was that the simulation is run in linear, not
O(n log n), although given the limits, just
2 * 10^5I too thought linear time isn't needed.
Then it's my fault :( I couldn't get any linear simulation ideas
It was 2e5 but it was also 1e12 which significantly bumped the binary search constant.
Well it is just a constant
2x, and overhead for multiset is probably
3-4xor even more, so I usually disregard whether the binary search is
log 10^18. But that is my fault :)
Ye, it probably did. Should've either set it the way you won't think of or make the constraints a bit lower.
When you made constrains higher at the begging it was "clear" to me that you raised because such solutions :D
I was more afraid of some linear simulations not passing. I believe, you'll have to set something like 10 seconds for any to pass, not only optimized ones.
Instead of using set, you should just put the element that you are sorting your set by, as an index in a vector because once you delete an element form the set you will never insert a smaller one back, so you can somehow call the set monotonous. Here is my solution with complexity O(log(1e13)*(N+K))
why n(log^2(n)) gives TLE in D ?
Because it exceeds time limit.
What was testcase #5 in C?
Check : 4 4 1 1 2 2 3 3 4 4
So shitty D
Problem C ?? Approach to solve problem like this ??
Here is possible to use partial sums approach. Also, you can use the event-based approach.
Any reading material you have in refernce to it.
Sure! https://csacademy.com/contest/round-61/task/paint-the-fence/statement/ Look at an editorial, the task is very similar to problem C.
Given an array of numbers, partial sums is a technique used to get in O(1) the sum of numbers in an interval
[l, r]. It works by iterating from zero to the length of the array adding up for every position the sum of the previous position. So if your partial sums array is called
sumyou can get the sum between
[l, r]by doing
sum[r]-sum[l-1]. Precalculate the partial sums array will take you O(n), where n is the length of the array.
In this case you can do the partial sums array such that
sum[i] = kif there are
kworkers to paint the i-th fence. To make the partial sums without iterating from
revery time, you can simply add 1 to
sum[l]and -1 to
sum[r-1]because you know in that positions someone will start painting and had finished painting respectively. Finally you make the sums, such that sum[i] += sum[i-1].
Now you can make partial sums again but counting the number of fences to be painted by zero, one and two painters respectively, to easily know for each interval
[l, r]how many fences will not get painted if the corresponding painters covering that interval are not hired.
Note that this technique is useful for problems that does not have updates over the values of the array. If you find a problem where you can do partial sums and your algorithm does not pass in time because the update queries, try something like Fenwick Tree or Segment Tree.
Number of people who solved D are too misleading, I read it very late (It's my fault).
For problem D: Beginning of 4th second both laptop has [1,1] charge but there was still one minute to finish. How does the answer be 5?
I just missed this got wrong answer at 12 :(
The charges at the beginning of the (k + 1)-th minute don't matter.
But it was 4th second.
1st second- 1st laptop
2nd second — second laptop
3rd second -1st laptop.
4th second ??
Am I missing something? -_-
They have [1, 1] at the beginning of the 4-th second. That is ok, they are non-negative. It doesn't matter what they become at the beginning of the next second.
How to solve C if constraints were 10^5 ?
Easier B than A is now regular event. We should try solving B first from next contest.
Really nice C ..haven't seen such a C in a while
Can someone explain C a bit please? It seemed like a really neat problem, but sadly haven't seen anything similar before.
P.S. That problem A was so wrong for so many reasons...
Hint: Use a difference array to count how many painters paint each block in O(n). Then do some O(n2) brute force(Try picking any two painters and leave them aside).
More about the difference array
Woah thanks so much!!! I actually thought of that type of array, but threw that idea aside thinking it was unnecessary... Thanks so muuch!
Why is this dp(problem F) wrong?
dp[i][j] is the answer for the substring s[i..j]
For every string s, let the last character I'll delete (in the optimal way to delete all of the string s) be C. Since that will be the last character, the answer will be 1 + the sum of independant answers for the substrings that you'll get once you delete every occurence of C in s. So I go through all possible characters from 'a' to 'z' and sum up the answer for every substring between two occurences of C in s, then add 1.
It's exactly like going backwards in the optimal process of deleting equal substrings.
I realise it's not the same dp as most solutions, but I believe the logic is correct..
Suppose the string is "aaqwertyaaytrewqaa". You want the last character deleted be a
"aa"+ "qwerty" +"aa"+ "ytrewq" +"aa"
If you do "qwerty" and "ytrewq" independently you spend 6+6=12 steps.
If you do substring "qwertyaaytrewq" at once, you spend only 7 steps.
That's why it's not always optimal to do them independently.
I think in some circumstance that isnt the optimal way. Example: acbabca. Your solution will get 5 but 4 is the answer.
Yall got any idea why this 50850982 gets WA?
D passes with priority queue, exceeds limit with sets.Good question overall
Same. Statement is very poor.
Why would you need either of those?
When you know your accepted solution is wrong so you hack yourself
Edit: See Hack
Many tasks can be found on informatics.msk.ru
Can someone please explain this solution?
https://codeforces.com/contest/1132/submission/50833595 (Author: PrakharJain)
It's a simple and nice solution, but I fail to understand how it works.
For a particular subarray [i, j], I'm just iterating through all possible positions k which would form the last position of the segment which would be deleted together. The character at k should be same as in i, of course. And, then in the transition we can stop considering one of the positions (either i or k as they are deleted together). So, both the transitions: ans = Math.min(ans, recurse(i, k — 1) + recurse(k + 1, j)); or, ans = Math.min(ans, recurse(i + 1, k) + recurse(k + 1, j)); should work.
But consider this case abaca in this case answer is 3 when you want answer for [1,5] you will take recurse(1,2)+recurse(4,5) and both have values 2 and 2 and their sum is 4 but we want 3 as our answer.
Also, recurse(1, 5) = recurse(1, 4) = 3. So, it'll take this minimum value.
Why does this 50854241 give TLE . I wrote a recursive solution and then memoized it. Can you please provide a test case other than sample test case so that I can verify my answer irrespective of TLE as the 4th test case has |s|=500.
Your solution seem to me O(n^4) because of substring calls inside the iteration. Store the intermediate states using indexes and not the strings.
In problem A test case: 0 1 1 0 should print 1 because i can do just like that "() ()" I've been hacked because of that
You have one pair of "()" and one pair of ")(". So whatever you choose first, it is not correct.
How to solve C for n, m = 106?
C is just the k=2 case with n,m <= 5000 of the problem above, which can be solved in O(nk+nlogn).
Can C be solved in linear time?
if i hack a solution after the contest in educational round do i get points or not ?! thx in advance :)
Please Help : Any way to remove TLE in F using map
How to solve G??
first for each index i find the maximum index j such that j < i and aj is greater than or equal to ai,call this last[i]. this can be done in linear time using a stack.
consider ans[i] as the answer if we start our sequence from position i.now make a maximum segment tree on ans values and iterate i from 1 to n there are two cases :
i > k : in this case remove the value from position i — k and add 1 to positions in range [max(last[i] + 1,i — k + 1),i] , now the answer for query ending in position i is maximum value on our segment tree
i <= k : in this case you just have to add 1 to positions in range [last[i] + 1,i]
omfg bad pretests.........
Has anyone solved C using DP?
I got MLE right on tc 1 !!!
I used DP to solve C click here
Just as of now I realized how atrocious pretests of problem C were. My solution got like, 4 critical flaws right within.
And none of them got caught during contest time. I fixed one by one and got WA one by one at tests that are obviously not pretests.
Having a closer look, such tests are not really too complicated (yeah, I would blame myself as well for not testing properly and got hacked/WAs, but it's irrelevant here), making the issues going way worse.
Really wish Educational Rounds never got such incidents ever again.
P/s: For a brief overview, I calculated the number of cells being painted once/twice obviously wrong and still ACed before hacking phase lol.
I got 2WA(typos) during the contest.
2 more WA during up solving.
why my submit be hacked?
my a problems have be hacked ,can you give me some adives?
for the test 1 0 3 1 your code gives the answer 0,but true answer is 1,because the string can be (( )( )( )( ));
oh ,i have know thank you.
How to solve problem E？
DP or some brute-force
Oof my A got hacked, of all things. There goes my rating...
Why have the ratings not changed yet?
System test haven't started yet.
Getting older waiting for the system test o_o
Why the rating didn't change?
Is it unrated?
Or The system testing didn't finish?
My rating changed as soon as I write this.
I wonder why this solution gives a TLE on test case 9 in problem — C (https://codeforces.com/contest/1132/submission/50857265). I went through other solutions and they were more or less same as mine (2 cumulative arrays).
You have an error on line 19, you have
pair<int, int> parr[n];but it should be
pair<int, int> parr[q];.
Can someone please comment more on this solution http://www.usaco.org/current/data/sol_lifeguards_platinum_jan18.html for problem C?
I implemented the method of above link, check my code. https://codeforces.com/contest/1132/submission/50925460
please publish editorial with neat codes.
When is the tutorial going to be published?
Pretests for C should have been stronger
Everyone is protesting C against weak pretests.
with this contest I finally became blue! it took a long time what eventually I made it :))) If you are also struggling to go Cyan -> Blue, keep it up because it is worth it!
How to solve 1132G - Greedy Subsequences
waiting for editorial
When you screw up the competition and get demoted to blue, but out of pure spite you want to bring everyone else with you.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Third question(C) is little bit more tricky from last div2"s third question.
Well, luckily, the next div2C is more likely to be even easier than edu C!
I dont like the way how announcement of prob.C works. When I read "**so you decided to hire q painters to paint it**", in my mind had a confusion, if q painters would paint all the sections or not, but then I answered this for myself that "**q painters to paint it**" meaned all sections would be painted if q painters all worked. Because I joined virtual contest, so I got wa, and the question came back again with another answer: may be not all of sections would be painted, and I tried again and got ac. For now, I still wonder, if someone want to paint their fence, they must make sure that all their fence is painted, or maybe Im just a stupid man try to talk bullshit without anyone's care. Plz tell me your opinions, thanks alot.
RIP. I should do all possible cases for Binary search of Binary search
I am very interested in how the top hackers find our wrong solution and hack us(Just interested, I know why i was hacked).
-- I solved BCF and my A was hacked and I have the same score as others who solved ABC QAQ
As we all know that this educational codeforces round had 12 more hours to hack any solution.Maybe there was somebody interested in hacking solutions or they wanted to get a higher rank. So they tried their best to hack others' solutions(Holland_Pig's own opinion).