By BledDest, 14 months ago, ,

Hello Codeforces!

Good news! Harbour.Space is supporting the return of a new series of educational rounds on Codeforces! You can read the details in the blog post.

On March 27, 17:35 MSK will be held Educational Codeforces Round 18.

You will be given 6 problems and 2 hours to solve them. We hope that everyone, both novices and experienced coders, will find something interesting in this contest. The contest will be unrated.

The round was prepared by Mikhail PikMike Piklyaev, Mikhail MikeMirzayanov Mirzayanov and me. We'd like to thank Maxim HellKitsune Finutin and Alexey ashmelev Shmelev for testing the round.

Wish you enjoy the contest! Good luck!

UPD: Editorial.

UPD2: All successful hacks have been added to the testsets, all submissions have been rejudged. Thank you for participating in the contest!

•
• +186
•

 » 14 months ago, # |   +3 Can anyone confirm to me that this contest won't be rated, because im not sure
•  » » 14 months ago, # ^ | ← Rev. 2 →   +54 It is unrated like every previous educational round. Sorry that it isn't mentioned in the post.
•  » » » 14 months ago, # ^ |   +4 Added this information to the announcement.
•  » » » 14 months ago, # ^ |   0 thanks, i hope that it will be a good contest so that i can improve my skills :D
 » 14 months ago, # |   0 Unfortunately, it clashes with csacademy round 22.
•  » » 14 months ago, # ^ |   -11 You can compete in 2 contests at the same time
•  » » 14 months ago, # ^ |   +30 You can unregister 2 contests at the same time :D
 » 14 months ago, # |   -135 MikeMirzayanov** WHY TO ORGANIZE SUCH UNRATED CONTEST? IF ANYONE WANT TO LEARN HE CAN PARTICIPATE VIRTUALLY.AND IF ANYONE WANT TO SOLVE QUESTS LIKE THESE ROUNDS' THEN WE CAN USE TAG OF EDUCATIONAL ON PROBLEMS LIKE PTHER TAGS DS,DP ,GRAPHS ETC.SO,THERE IS NOTHING IN FAVOUR OF THESE KIND OF UNRATED ROUNDS**
•  » » 14 months ago, # ^ |   +5 OMG!!! Somebody is very angry...
•  » » » 14 months ago, # ^ | ← Rev. 2 →   -78 Yes,Your Father is Here and He is very angry.Go inside
•  » » » » 14 months ago, # ^ | ← Rev. 3 →   +23 OOPS!!! Somebody is really really very angry. I think you got enough downvotes to cool down now...... Otherwise, go to Himalayas and do some Meditation !!!!
•  » » » » 14 months ago, # ^ |   +9 Hey dude, say whatever u want but don't mess with people's parents, they didn't do anything to u, peace out :)
•  » » 14 months ago, # ^ |   +7 If you don't like, you can unjoin and nobody force you to register it.
 » 14 months ago, # |   -19 Making educational round be rated, the number of participant will increase a lot. Sorry for my poor English.
•  » » 14 months ago, # ^ |   +16 I see a lot of people apologizing for their English here. Why ? It is not like English is your first language. Chill man.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +10 Generally speaking, only 25% of world population speaks English, rest of the people use google translate and add "Sorry for my poor English" at the end.:-D Sorry for my poor English.
 » 14 months ago, # |   +13 Thank you Harbour.Space for Supporting........
 » 14 months ago, # |   -22 IS IT RATED!!?!?!?!?!?
•  » » 14 months ago, # ^ |   0 No. Read about education round.
•  » » » 14 months ago, # ^ |   0 OOHH NOOO SO SAD =(
 » 14 months ago, # |   +14 It's interesting that some of my friends are more interested in participating when it's not rated haha
•  » » 14 months ago, # ^ |   +13 they don't understand the true value of contest
•  » » » 14 months ago, # ^ |   +17 Honestly I think having fun competing is more important than ratings so I'd say that's kinda true
•  » » » » 14 months ago, # ^ |   +3 Yes.
 » 14 months ago, # |   +25 The issue with problem C may have affected some contestants. The round should be unrated.
•  » » 14 months ago, # ^ |   +94 Yay. I totally agree with you :)The organizer must have predicted this issue would happen and announced the round to be unrated before the round had started.
•  » » 14 months ago, # ^ |   -18 ARE YOU ON DRUGS?
 » 14 months ago, # |   0 E is so beautiful and amazing! Thank you!
 » 14 months ago, # |   0 Did someone else keep getting WA15 on F? If yes how did he/she fix it?
•  » » 14 months ago, # ^ |   0 I fixed, I found that i tried to maximize y/x, but actually we need to minimize it
 » 14 months ago, # |   +1 isn't E a binary search? get WA at test4!
•  » » 14 months ago, # ^ | ← Rev. 2 →   +8 Try this case 1 1000 
•  » » » 14 months ago, # ^ |   0 thanks, binary search seems not appropriate to this problem. I'm turning to learn with tutorial....
 » 14 months ago, # |   0 Will the test data be published now or one day later?
 » 14 months ago, # |   0 can anyone post code of first problem?
 » 14 months ago, # |   +7 Has "unused" hacked his own solution ?! Appears so to me !!
•  » » 14 months ago, # ^ |   0 Why on earth would he do that ?
 » 14 months ago, # | ← Rev. 2 →   0 Is F relative to Linear Programming? Using duality lead the problem to work with lines.
•  » » 14 months ago, # ^ |   0 i am not sure but i guess maintain an upper convex hull of points and checking if the query points are inside or not should work , something like this.
•  » » 14 months ago, # ^ |   0 It can be solved with geometry, we have to support two operations: add one point (mana cost, damage) and keep the convex hull of all the points so far. determine if after scaling the convex hull by t it intersects the rectangle (Maximum mana, Health)
 » 14 months ago, # |   +3 What does "unexpected verdict" mean when hacking a solution? I received it while hacking problem C.
•  » » 14 months ago, # ^ |   +1 Fixed!
 » 14 months ago, # | ← Rev. 3 →   +4 I tried to hack C and the verdict was "Unexpected verdict". What does it mean? **UPD**: It is now a successful hacking attempt 
 » 14 months ago, # |   -7 Why do I get Unexpected Verdict while hacking C?
•  » » 14 months ago, # ^ |   +3 Fixed
 » 14 months ago, # |   +5 What was the expected complexity of problem E?I guess I had a solution in nsqrt(max(ai)).
 » 14 months ago, # |   -8 I hacked a friend on a solution he sent after the contest finished but still got -1 on hacks. Is this intended?
 » 14 months ago, # |   0 Why so many people hacking their own solution?
 » 14 months ago, # |   0 What was the issue with problem C? I am unaware of it.
 » 14 months ago, # |   +3 Great contest! Are editorials for the problems going to be published? And when?
 » 14 months ago, # |   0 How to solve D?
•  » » 14 months ago, # ^ |   +9 notice that all values in left subtree < value at current node and all values in right subtree > current node and all values in this subtree are in some range [l , r] and the value at current node is (l + r) / 2. Using this you can find the node u in log(N) the same way as you find stuff in a binary search tree and then continue the traversal there while mainting the list of ancestors of a node.
•  » » » 14 months ago, # ^ |   0 I did that solution during the contest, but i keep getting WA on test 10, do you have an idea why that happens 25855671
•  » » » » 14 months ago, # ^ |   +1 I also got a WA on test 10, then I removed all the pow() operations and computed the values on my own, and this got me an AC. I think it's due to the inaccuracy of pow(), that you are getting a WA.
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   +1 Yup, the problem turned out to be bitwise operations, i simply changed the line root=1<<(levels-1); to root=(n+1)/2 and it got accepted.
•  » » » » » » 14 months ago, # ^ |   0 It should be 1LL << (levels - 1) — shift amount doesn't promote the type of expression to long long.
•  » » » » » » » 14 months ago, # ^ |   0 ohh so that was the problem. Thank you ^^ I will keep that in mind from now on
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I used two variables l and r to mark the leftmost (smallest) number and rightmost (largest) number of the subtree of current node. For 'L' and 'R' operations:When l = r, it means that the current node is at the deepest layer, so we should ignore these operations. Otherwise, shrink the range by making l = mid+1 for 'R' operations, or r = mid-1 for 'L' operations, where mid = (l+r)/2 (the current node).For 'U' operations:When l = 1 and r = n, it means that the current node is the root, and we should ignore this operation. Otherwise, check the (x+1)th bit where xth bit is the lowest bit containing 1. If that bit is 1, the current node is in the right subtree of its parent. If that bit is 0, the current node is in the left subtree of its parent. Expand the range by moving l and r pointers.
•  » » 14 months ago, # ^ |   0 I made a function that receives a number x and returns info = {value, level, left/right, difference with parent} about it in log(n).You can observe that for node x, value of left child is x-dif, value of right child is x+dif. dif reduces by 2 on each level.Using this, it becomes easy to process up, left and right queries.Here is AC code.Here is same code with comments.
 » 14 months ago, # |   +11 How do you solve E?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Let the number of ball in box noted a1 a2 ... an; First you will find the minimum ai in this array (marked as ak). Then, let's enumerate all size as (ak/1, ak/2, ... ak/ak), let pki = ak/i, if (ak%i == 0) we will try that (pki, pki+1) and (pki, pki-1), otherwise, we wil try (pki, pki+1); If we discover a pair (pkj, pkj+1) can combinate all box(a1,a2,...an), then we find the maximum size of set is (pkj, pkj+1); Output the sum of Pi = ai/(pkj+1) (PS: if (ai%(pkj+1)) != 0 then Pi = Pi + 1) for answer.
•  » » » 14 months ago, # ^ |   0 And here is my poor code... I'm sorry about I forgot it.25873907
•  » » » 14 months ago, # ^ |   0 Why we are treating the case when a[0]%k==0 differently?
•  » » » » 14 months ago, # ^ |   0 If ak%i == 0 then we don't know if (pki,pki+1) can combinate all box, If it can make it, they will be the maximum size. If not, then(pki-1,pki) also can combinate this box ak, so I think we should try this case.
 » 14 months ago, # | ← Rev. 2 →   0 Hi,Thanks to the organizers for these problems.Just to be sure : I get an error on the C, it's said my output is not "0", it's "0" followed by a random character. I think there is an error in the evaluation test. In fact, my string is obtained this way :string s; s=""; s+='0';The result must be : s=="0" (cast of '0' in a string format), don't you think ?Thanks, Regards.
•  » » 14 months ago, # ^ |   0 Sorry, my mistake. I've just found a bug in my source code. CodeForces forever !
 » 14 months ago, # |   0 How do I solve C?
•  » » 14 months ago, # ^ | ← Rev. 4 →   +3 Find K = sum%3. If its 0, you are done.Otherwise, you have to remove at max 2 elements to make it a multiple of 3.So there are few cases only that you have. I maintained a vector of pair for both cases, when K is 0 and when its 1. Find for each case the resultant string and take the one with minimum deletions. (Also for more optimization you won't remove digits like 3,6,9 anyway.) Here is the code.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 It can be solved with DP
 » 14 months ago, # |   0 How to solve C ? Is this a greedy problem ?
•  » » 14 months ago, # ^ |   0 It can be solved by dynamic programming.
•  » » » 14 months ago, # ^ |   0 isn't it able to solve with normal logic?
•  » » » » 14 months ago, # ^ |   0 You can, but probably you will have many bugs in code (like me :P). So, you can try :)
 » 14 months ago, # |   0 What is wrong with this approach of D ?IF str[i] = 'R' do curr_node = curr_node + 2^(tree_height-curr_height -1 ).IF str[i] = 'L' do curr_node = curr_node - 2^(tree_height-curr_height -1 ).IF str[i] = 'U' , I divide curr_node by 2 until it becomes an odd number. If obtained_number+1 is divisible by 4, this implies curr_node is right child of it's parent. currr_node = curr_node - 2^(tree_height-curr_height).Else currr_node = curr_node + 2^(tree_height-curr_height).I am maintaing curr_height accordingly at each step and also checking for the bounds.Getting WA at test case 6.
•  » » 14 months ago, # ^ |   0 I think the method you decide if a node is a left child or right child is wrong, because everything else that you said is like mine solution. Instead of checking if current_node is a right child or left child by some formula, I simply keep a stack on the moves I have made. You can look at my solution if you want 25872554
•  » » » 14 months ago, # ^ |   0 Actually, the solution worked.I had error in implementation. The algorithm is passing all the test cases.My AC Solution: Link
 » 14 months ago, # |   0 When are the editorials scheduled?
•  » » 14 months ago, # ^ |   0
 » 14 months ago, # |   -8 Somebody please HACK this — http://codeforces.com/contest/792/submission/25851911
 » 14 months ago, # |   0 the problem C's datas are too strong,,,I had WA many times.
 » 14 months ago, # |   +14 Someone pls help me with this. this program runs pretty well on my own computer. But it does not work in the test. It got wa on test 3, where the output should be all YES (and it is on my computer)25863026
•  » » 14 months ago, # ^ |   +1 Maybe the stl is different.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Well, when I switch to c++14 from c++11 I got more YES, but still wa on test 3. I feel quite confused.
 » 14 months ago, # | ← Rev. 2 →   +9 for problem A, there are more than 150 hacks in java.what's wrong with java ?
•  » » 14 months ago, # ^ |   +9 In problem A, Anti-quicksort hack cases work.
•  » » 14 months ago, # ^ |   +4 Java has a method called Arrays.sort(); that uses a quick sort method to sort an array. Quick sort's average run time is O(nlogn), but it's worst case scenario sort is O(n^2). People used a worst case scenario input/generator to hack many java solutions.P.S. To fix this just use Integer instead of int for your array since to sort objects, java uses a merge sort instead, which runs in time.
 » 10 months ago, # | ← Rev. 2 →   0 Could someone please explain this to me: In problem E, I used the solution to go from i to min in array a, and then check min/i and min/i + 1... I understand why and why we check these things ( for every element in a, x1 = a[j]/x, mod = a[j]%x, and if(!mod) just add x to ans, if not, check if(x1+mod<=x-1) add x+1... otherwise... return 0, it's not possible for this x). Now, my question is, is there a proof why this never exceeds the time limit (in fact, it doesn't seem to even get close to exceeding it)? Because the smallest element can be larger than 10^8?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +1 We don't iterate from i = 1 to , instead it's up to . When you want to divide some ai into k sets, each set will be of size . Therefore or . Thus, it's possible to check every case by checking up to the root. Since on each iteration we iterate over our array of size n, the time complexity of the solution is
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 Thanks for your time, I get that but I submitted a code which goes until m and breaks when a correct solution is found. But I only check m/i and m/i+1, whereas for it to mathematically be correct, I have to check for i+1 and i as well, however I don't and it still works, what am I missing? Edit: This is my submission (28747357)