By BledDest, history, 12 months ago, translation, ,

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 PikMike Piklyaev, Vladimir 0n25 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.

•
• +151
•

 » 12 months ago, # |   +35 WOW !! Editorial has been published before the contest.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +19 Sorry, we fixed it now.Anyway, it was a link to the ER22 editorial, so it would not help anyone with this round.
 » 12 months ago, # |   0 Please correct the time of the contest
 » 12 months ago, # |   -59 Today is Champions Trophy Semifinal INDIA vs BANGLADESH ....Timing issue
 » 12 months ago, # |   -12 servers are getting really slow. Hope the contest won't be delayed
•  » » 12 months ago, # ^ |   0 The contest will surely delay, it is tradition.
•  » » » 12 months ago, # ^ |   +26 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.
•  » » » » 12 months ago, # ^ |   +8 Of course. The round won't be delayed but the solutions will be failed to judge.
 » 12 months ago, # |   +64 Judgement failed??
•  » » 12 months ago, # ^ |   +22 Judgement failed, too >:'(
•  » » » 12 months ago, # ^ |   +22 too
•  » » » » 12 months ago, # ^ |   +17 too
•  » » » » » 12 months ago, # ^ |   +16 too
•  » » » » » » 12 months ago, # ^ |   +16 too
•  » » » » » » » 12 months ago, # ^ |   +12 too
•  » » » » » » » » 12 months ago, # ^ |   +10 too
•  » » » » » » » » » 12 months ago, # ^ |   +13 too
•  » » 12 months ago, # ^ |   -8 Mine also >-<
 » 12 months ago, # |   +1 What is Judgement Failed?
•  » » 12 months ago, # ^ |   +3 same here
 » 12 months ago, # |   +54 Me too! Don't worry. Round will be unrated. xD
 » 12 months ago, # |   +8 Are pretests too weak? I am submitting crap and they all are getting "accepted" as of now.
 » 12 months ago, # |   0 Large amount of hacks on A and B is coming...
 » 12 months ago, # |   +3 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! :)
•  » » 12 months ago, # ^ |   +16 the answer is always l[i] or r[i] + 1 for some i , so just coordinate compress these points and then use normal segtree.
•  » » » 12 months ago, # ^ |   0 Nice :) thanks
•  » » 12 months ago, # ^ |   +5 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.
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 I think when we pushdown lazy tag it will expand more nodes so not just 64 nodes per update ,I guess
 » 12 months ago, # |   +3 How to solve F and C?
•  » » 12 months ago, # ^ |   0 C was a binary search :)
•  » » 12 months ago, # ^ | ← Rev. 5 →   +7 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)].
•  » » 12 months ago, # ^ |   +5 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
•  » » 12 months ago, # ^ |   0 In Cn=10 s=9 ans=1 n=11 s=9 ans=2 . . n=19 s=9 ans=10 .. .. .. .. n=100 s=99 ans=1 . n=101 s=99 ans=2 .. .. so on
•  » » 12 months ago, # ^ |   0 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)
 » 12 months ago, # |   0 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.
•  » » 12 months ago, # ^ |   +2 this.
 » 12 months ago, # |   0 How solve D? :'v
 » 12 months ago, # |   +10 can we get AC with a NlogN solution in problem D ?
•  » » 12 months ago, # ^ |   0 I got AC with NlogN.Click
•  » » 12 months ago, # ^ |   0 Maybe, At least NlogN solution can pass pretest
•  » » 12 months ago, # ^ |   0 Yeah I got AC for now with something that looks like nlog^2n
 » 12 months ago, # |   0 Why i cant double click on submissions to hack it???
 » 12 months ago, # | ← Rev. 2 →   0 Can't wait until tomorrow to see the verdict. Please try to hack my C. I haven't used binary search or dp. code
•  » » 12 months ago, # ^ |   0 brute force is enough for C. Dont worry!!
•  » » » 12 months ago, # ^ |   0 okay, thanks!
 » 12 months ago, # |   0 How to solve D with O(N) complexity?
•  » » 12 months ago, # ^ |   +5 here you go.
•  » » 12 months ago, # ^ |   +12 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
•  » » 12 months ago, # ^ |   0 The basic idea is for each i find Nmx[i] — the number of subarrays that will have a[i] number as maximum. Then do final_answer += Nmx[i] * a[i]. Similarly find Nmn[i] — number of subarrays in which a[i] will be the minimum number, and do final_answer -= Nmn[i] * a[i].Nmx can be found in O(N) time. To find Nmx[i], you have to find Rmx[i] and Lmx[i] such that a[i] is maximum among all numbers in the segment [Lmx[i], Rmx[i]]. Rmx and Lmx arrays can be obtained with a forward sweep and a reverse sweep of the original array. Similarly find Nmn array.
 » 12 months ago, # |   0 How to solve E? I could feel the use of tries but I couldn't come up with a good idea.
•  » » 12 months ago, # ^ |   +9 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
•  » » » 12 months ago, # ^ |   0 Thanks!
 » 12 months ago, # |   0 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?
•  » » 12 months ago, # ^ |   +65 Hacked.
•  » » » 12 months ago, # ^ |   0 What test did you use? I thought about adding 50000 numbers than query 50000 times.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 That's exactly what I did. Code#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define f first #define s second #define ll long long #define ull unsigned long long #define mp make_pair #define pb push_back #define vi vector #define ld long double #define pii pair #define y1 sda using namespace std; const int N = int(3e5), mod = int(1e9) + 7; int q = int(1e5); int main () { cout << q << endl; for(int i = 1; i <= q / 2; i++){ cout << 1 << " " << 2 << endl; } for(int i = 1; i <= q / 2; i++){ cout << 3 << " 1 2\n"; } return 0; } 
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 12 months ago, # ^ |   0 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.
•  » » » » 12 months ago, # ^ |   0 I just took K = 50000.
•  » » » 12 months ago, # ^ | ← Rev. 3 →   +30 What about this one?
 » 12 months ago, # |   0 The editorial is published.
 » 12 months ago, # |   +3 This was another great educational round from your part, I liked the problems a lot, keep up the good work.
 » 12 months ago, # | ← Rev. 2 →   0 I am not getting problem A ,I mean why does not (x2-x1)%x==0 and (y2-y1)%y==0 work?Please explain.
•  » » 12 months ago, # ^ |   0 Plus you need to check ((x2 — x1) / x + (y2 — y1) / y ) % 2 == 0 because there are no rules that move only x or y.
•  » » » 12 months ago, # ^ |   0 but also number of moves in x and y-axis can't be given by (x2 — x1) / x, (y2 — y1) / y because in 0 0 0 6 and x=2,y=3,no of moves in x axis is not(0-0)/2 .
 » 12 months ago, # |   -8 Why my MEX queries does not work? Here's my code: Solution#include using namespace std; typedef long long ll; struct interval { int a, b; int k0; int k1; bool L[2]; //L[0] - i ka pakeisti visus neesamus //L[1] - i ka pakeisti visus esamus interval *left = NULL; interval *right = NULL; void fix() { if (L[0] == 0 && L[1] == 1) return; if (left) { if (left->L[0] == 0) left->L[0] = L[0]; if (left->L[0] == 1) left->L[0] = L[1]; if (left->L[1] == 0) left->L[1] = L[0]; if (left->L[1] == 1) left->L[1] = L[1]; } if (right) { if (right->L[0] == 0) right->L[0] = L[0]; if (right->L[0] == 1) right->L[0] = L[1]; if (right->L[1] == 0) right->L[1] = L[0]; if (right->L[1] == 1) right->L[1] = L[1]; } if (L[0] == 0 && L[1] == 0) { k0 = (b - a + 1); k1 = 0; } if (L[0] == 1 && L[1] == 1) { k0 = 0; k1 = (b - a + 1); } if (L[0] == 1 && L[1] == 0) swap(k1, k0); L[0] = 0; L[1] = 1; } void init(int x, int y) { a = x; b = y; k0 = (b - a + 1); k1 = 0; L[0] = 0; L[1] = 1; if (x != y) { left = new interval; right = new interval; left->init(x, (x + y) / 2); right->init((x + y) / 2 + 1, y); } } void q1(int l, int r) { fix(); if (r < a) return; if (b < l) return; if (l <= a && b <= r) { L[0] = 1; L[1] = 1; fix(); return; } left->q1(l, r); right->q1(l, r); k0 = left->k0 + right->k0; k1 = left->k1 + right->k1; } void q2(int l, int r) { fix(); //1 -> 0 if (r < a) return; if (b < l) return; if (l <= a && b <= r) { L[0] = 0; L[1] = 0; fix(); return; } left->q2(l, r); right->q2(l, r); k0 = left->k0 + right->k0; k1 = left->k1 + right->k1; } void q3(int l, int r) { fix(); if (r < a) return; if (b < l) return; if (l <= a && b <= r) { L[0] = 1; L[1] = 0; fix(); return; } left->q3(l, r); right->q3(l, r); k0 = left->k0 + right->k0; k1 = left->k1 + right->k1; } int MEX() { fix(); if (k0 == 0) return b; if (k1 == b - a + 1) return b + 1; if (a == b) return a; if ((left->MEX()) != ((left->b) + 1)) return left->MEX(); return right->MEX(); } }; int main() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); int n; cin >> n; ll t[n], l[n], r[n]; setX; for (int i = 0; i < n; i++) { cin >> t[i] >> l[i] >> r[i]; X.insert(l[i]); X.insert(r[i]); X.insert(r[i] + 1); } X.insert(1); mapID; mapID_; int u = 0; for (ll i : X) { u++; ID[i] = u; ID_[u] = i; } interval *M = new interval; M->init(1, u); for (int i = 0; i < n; i++) { int a = ID[l[i]]; int b = ID[r[i]]; if (t[i] == 1) M->q1(a, b); if (t[i] == 2) M->q2(a, b); if (t[i] == 3) M->q3(a, b); cout << ID_[M->MEX()] << "\n"; } } 
 » 12 months ago, # |   0 It seems like that several past educational rounds are full of data structure problems XD
•  » » 12 months ago, # ^ |   +14 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...
 » 12 months ago, # | ← Rev. 2 →   0 For B. Makes And The Product I don't know why my logic won't work27820072Basically I am counting the frequencies of smallest 3 distinct elements. For example 1 1 1 2 2 3 3 3 3So the frequency is 1 -> 3, 2-> 2, 3->4 Call them k1,k2,k3 for smallest numbers a1,a2,a3If k1>=3, it means the constituents of my minimum product all come from a1...So it is k1 choose 3else 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 2else if k1==1 and k2==1, then i have to choose one a3, k3 choose 1 way of doing that.
•  » » 12 months ago, # ^ |   0 overflow.(btw, you declared n as long long and answer as int lol)
•  » » » 12 months ago, # ^ |   0 I have used long long but still someone has hacked mine. code
•  » » » » 12 months ago, # ^ |   0 if(x != y and x != z) should be if (x != y and y != z)
•  » » » » » 12 months ago, # ^ |   0 I am so stupid. Thanks!
•  » » 12 months ago, # ^ |   0 Your logic works, but the result of k1 choose 3 doesn't fit in an int type, you should use long long int.
•  » » » 12 months ago, # ^ |   0 Damn it! I have gone rusty.
 » 12 months ago, # |   0 214 successful hacks!! Great!
•  » » 12 months ago, # ^ |   0 As usual :D
•  » » » 12 months ago, # ^ |   +23 There is just too few tests for such tricky problems. Authors often use Educational Rounds as an excuse to be a bit lazy.
•  » » » » 12 months ago, # ^ |   +2 Which problem was the tricky one?
•  » » » » 12 months ago, # ^ |   +23 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?
•  » » » » » 12 months ago, # ^ |   0 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?
•  » » » » » » 12 months ago, # ^ |   0 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.
•  » » » » » » » 12 months ago, # ^ |   +29 Use multitests
•  » » » » » » » » 12 months ago, # ^ |   0 Great point! Why didn't we even consider it previously? Thanks, next round will definitely include multitest in problems B or C then.
•  » » » » » » » » » 12 months ago, # ^ |   0 Because everyone hates multitest? You don't feel progress while fixing bugs and yet still getting WA2.
•  » » » » » » » » » 12 months ago, # ^ |   0 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?
 » 12 months ago, # | ← Rev. 2 →   0 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.com/contest/817/submission/27832753
 » 12 months ago, # | ← Rev. 2 →   +5 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.com/contest/817/submission/27881187