Hello Codeforces!
On June 15, 18:05 MSK Educational Codeforces Round 23 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.
The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 problems and 2 hours to solve them.
The problems were prepared by Mikhail awoo Piklyaev, Vladimir vovuh Petrov and me. Huge thanks to Alexey Perforator Ripinen, Alexey ashmelev Shmelev and Maxim HellKitsune Finutin for testing!
Good luck to all participants!
UPD. I am pleased to announce the 2nd Hello Barcelona Programming Bootcamp in collaboration with Moscow Workshops ACM ICPC, which will be hosted by our partner Harbour.Space University together with Moscow Workshops ACM ICPC, ITMO University, Moscow Physics and Technology University, Saint Petersburg State University and Codeforces!
UPD: The editorial is published.
WOW !! Editorial has been published before the contest.
Sorry, we fixed it now.
Anyway, it was a link to the ER22 editorial, so it would not help anyone with this round.
Please correct the time of the contest
Today is Champions Trophy Semifinal INDIA vs BANGLADESH ....Timing issue
servers are getting really slow. Hope the contest won't be delayed
The contest will surely delay, it is tradition.
Hey, it's a tradition for usual rounds but not for ERs! Previous 5 rounds started at the time they were scheduled.
Though I really don't like current condition of servers too.
Of course. The round won't be delayed but the solutions will be failed to judge.
Judgement failed??
Judgement failed, too >:'(
too
too
too
too
too
too
too
Mine also >-<
What is Judgement Failed?
same here
Me too! Don't worry. Round will be unrated. xD
Are pretests too weak? I am submitting crap and they all are getting "accepted" as of now.
Large amount of hacks on A and B is coming...
I think problem F could be solved using segment tree if the interval was smaller... Can it be solved using a lazy-constructed segment tree? (we create nodes as we need them)
Thanks! :)
the answer is always l[i] or r[i] + 1 for some i , so just coordinate compress these points and then use normal segtree.
Nice :) thanks
I think we can compress the value of L and R and then build a segment tree with the new value (1 — 200000) and then use lazy-constructed segment tree as you said.
Sparse Segment Tree gives MLE on test 15 :( But shouldn't that pass the ML? It creates ~ 64 nodes per update. Each node has one long long and one short.
I think when we pushdown lazy tag it will expand more nodes so not just 64 nodes per update ,I guess
How to solve F and C?
C was a binary search :)
the sum of the digits can't be large, so there's not many numbers x such that the check x - digitsum(x) > = s is interesting. Check them all and add the rest in O(1), I checked only the interval [s..min(s+200,n)].
It can be proved that if a > b then a — sum_of_digits(a) >= b — sum_of_digits(b) so we can do binary search to find the smallest n that n — sum_of_digits(n) >= s
All numbers from s+9*18+1 to n are really big. So you can check numbers from s to s+9*18 and add max(0, n — s+9*18)
C is really a brute force problem.
It was supposed to be A.
Just iterate through s+1 to max(n, s+160) and find where
this condition met -> (s+i) — sum_of_digit(s+i) >= s.
then just print (n — (s + i) + 1).
if not met then just print 0.
Thanks, finally understood it after 3 years.
Any idea for D? I thought something on basis of RMQ and adding one element at a time to the array. But it is TLE easily.
this.
How solve D? :'v
can we get AC with a NlogN solution in problem D ?
I got AC with NlogN.
Click
Maybe, At least NlogN solution can pass pretest
Yeah I got AC for now with something that looks like nlog^2n
Why i cant double click on submissions to hack it???
Can't wait until tomorrow to see the verdict. Please try to hack my C. I haven't used binary search or dp. code
brute force is enough for C. Dont worry!!
How to solve D with O(N) complexity?
here you go.
For each element, let the number of subarrays in which it is the min be cnt_min[i] and the number of subarrays in which it is the max be cnt_max[i]. Answer is sum of arr[i]*(cnt_max[i]-cnt_min[i]).
To find cnt_max[i], for each index i, find the closest indices to its left and right such that value there is > arr[i]. This can be done in cumulative O(n) time using stack. Similar for cnt_min[i].
Take care of duplicate values.
Code
The basic idea is for each
i
findNmx[i]
— the number of subarrays that will havea[i]
number as maximum. Then dofinal_answer += Nmx[i] * a[i]
. Similarly findNmn[i]
— number of subarrays in whicha[i]
will be the minimum number, and dofinal_answer -= Nmn[i] * a[i]
.Nmx
can be found in O(N) time. To findNmx[i]
, you have to findRmx[i]
andLmx[i]
such thata[i]
is maximum among all numbers in the segment[Lmx[i], Rmx[i]]
.Rmx
andLmx
arrays can be obtained with a forward sweep and a reverse sweep of the original array.Similarly find
Nmn
array.How to solve E? I could feel the use of tries but I couldn't come up with a good idea.
Read this tutorial to learn how to solve similar problems involving XOR using trie.
In this problem, maintain a trie in which numbers are inserted/removed in the decreasing order of bits in their binary representation. Now, for the query part, just traverse along the path specified by P and consider all cases in which you can get XOR < L.
eg. if next bit of P is 0 and next bit of L is 1, you can add all the numbers along the 0-edge to the answer and then move along the 1-edge (because for all numbers inserted in subtree of 0-edge, their XOR with P will be < L).
You can see all the cases in my code. Code
Thanks!
Constraints in the problem E are so good that an
O(Q^2)
solution gets AC (it's not that the tests are weak: I can't make it run for more than ~1.5 seconds).Was it intended?
Hacked.
What test did you use? I thought about adding 50000 numbers than query 50000 times.
That's exactly what I did.
That's weird. I didn't try this hack because it worked less than <1.5 seconds using custom invocation (and even a little bit less locally with actual input reading/printing the answer).
Cool. What's the idea of your test case? I tried to do something like adding different numbers K times and than making N — K queries (choosing K to maximize the run time), but it didn't work.
I just took K = 50000.
What about this one?
The editorial is published.
This was another great educational round from your part, I liked the problems a lot, keep up the good work.
Why my MEX queries does not work? Here's my code:
It seems like that several past educational rounds are full of data structure problems XD
They are :c We really try to balance out problemsets but everytime it ends up with lots of ds problems.
I guess that it is actually fine in context of ERs because education in competitive programming is mostly about learning algos and data structures. Still somehow I am not pleased with the quality of contests...
For B. Makes And The Product I don't know why my logic won't work
27820072
Basically I am counting the frequencies of smallest 3 distinct elements. For example 1 1 1 2 2 3 3 3 3
So the frequency is 1 -> 3, 2-> 2, 3->4 Call them k1,k2,k3 for smallest numbers a1,a2,a3
If k1>=3, it means the constituents of my minimum product all come from a1...So it is k1 choose 3
else if k1==2, then i just choose one of a2, which gives k2 ways.
else if k1==1 and k2>=2, then number of ways is k2 choose 2
else if k1==1 and k2==1, then i have to choose one a3, k3 choose 1 way of doing that.
overflow.(btw, you declared n as long long and answer as int lol)
I have used long long but still someone has hacked mine. code
if(x != y and x != z)
should beif (x != y and y != z)
Your logic works, but the result of k1 choose 3 doesn't fit in an int type, you should use long long int.
Damn it! I have gone rusty.
214 successful hacks!! Great!
As usual :D
There is just too few tests for such tricky problems. Authors often use Educational Rounds as an excuse to be a bit lazy.
Which problem was the tricky one?
Well, most of the hacks are made on easier problems. We can't add too many tests for them as it can lead to big server load. I won't deny that we don't try that hard to make tests as strong as possible but it isn't easy to cover all the cases with 10-15 tests.
There is just about couple of dozens successful hacks for D-F. I suppose that is fine, isn't it?
Server load is definitely a concern. Do you know how bad it is in practice? May be we can afford more tests from B onward?
I'm not sure. As far as I can guess from usual rounds, ~30 tests for task with ~20 submits per minute is about the limit (considering submissions for all problems, not only this one).
Though it's hard to determine submissions rate before the contest. Adding more tests is always risky.
I suppose that we can try pushing this limit a bit by rearranging tests. I don't think that A can have more tests than it currently does but for B it's possible, I think. We will try to increase this number in next round.
Use multitests
Great point! Why didn't we even consider it previously? Thanks, next round will definitely include multitest in problems B or C then.
Because everyone hates multitest? You don't feel progress while fixing bugs and yet still getting WA2.
It's not a problem to make a couple of somewhat hard testcases of 1 test and place it right after samples...
Does everyone really hate it that much?
Can anyone explain me D&C solution for D? Because solution with stacks looks awful. I was thinking D&C on contest but couldnt solve it. Edit: got it. This solution helped me: http://codeforces.me/contest/817/submission/27832753
Would you please update the Python2 version for the judging system?
This submission is said to be runtime error for python 2.7.3 while it works perfectly on my macbook with python 2.7.11.
http://codeforces.me/contest/817/submission/27881187