By pikmike, history, 3 years ago, translation,

Hello Codeforces!

On July 16, 18:05 MSK Educational Codeforces Round 25 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 7 problems and 2 hours to solve them.

The problems were prepared by Ivan BledDest Androsov and me.

Good luck to all participants!

UPD: The editorial can be found here.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 halyavin 7 297
2 Shik 7 433
3 Kaban-5 6 132
4 sugim48 6 160

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 219:-58
2 kuko- 97:-2
3 uwi 85:-7
4 Yazmau 35:-5
5 aleex 25

929 successful hacks and 587 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A lewin 0:01
B bmerry 0:05
C shubhiks1032 0:06
D April_AA 0:06
E bmerry 0:24
F gvaibhav21 0:39
G iiiLoveYOU 1:06

• +166

 » 3 years ago, # |   +34 Silver Jubilee of Edu cf rounds! :O
 » 3 years ago, # |   +31 you forget thank MikeMirzayanov
 » 3 years ago, # |   -67 is it "is it not rated?" ?
 » 3 years ago, # |   0 When will be the next round ?
•  » » 3 years ago, # ^ |   +40 To see the following picture, it seems like the next Educational Round will be end of July. Educational Codeforces Rounds held once per two weeks approximately.
•  » » » 3 years ago, # ^ |   +26 To see the following picture, you just need eyes. ;)
 » 3 years ago, # |   +1 How to solve E, without WA on test 7?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Same question. I tried sorting all vertices by connectivity component, if they equals by count all children, if equals by number of vertex.
•  » » 3 years ago, # ^ |   +5 I only saw it in the last 5 minutes (which was just in time for me). The trick is to look at the problem backwards: determine which node gets the last label.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you please explain why it is optimal to go backwards?
•  » » » » 3 years ago, # ^ |   +23 We can prove it by contradiction. Take any graph with the smallest number of nodes for which this algorithm does not give an optimal labeling. The largest label must always be assigned to a node with no outgoing edges, but it can't be the largest of those nodes (otherwise the algorithm would give the optimal labeling). Lets call the largest node with no outgoing edges x and the node that has the largest label in the optimal labeling y. Then after labeling y with the largest label, the remaining part of the graph is correctly labeled by the algorithm (otherwise we would have a smaller graph for which the algorithm gives an incorrect result). This will first label some nodes greater than x and then it will label x. But we get a better labeling by labeling x with the largest label, y with the next largest and then label the same nodes as before. This is because of the nodes labeled so far y is the smallest node (since y < x and all other labelled nodes are greater than x) and in the partial labeling we have labeled the same nodes using the same labels. So we have a contradiction, which means our assumption was wrong and therefore there is no graph that our algorithm labels incorrectly.
•  » » » » » 3 years ago, # ^ |   0 Thank you. That is a really nice proof.
•  » » » » 3 years ago, # ^ |   +6 Let us have a random valid assignation.Let a_1 < a_2 < .. < a_i be leaves in our DAG. Then we can observe that given any assignation of the values, we can swap the values between leaves without creating a wrong solution, hence we know that the best answer will have the lowest value at the node with smallest index, second lowest value to the second smallest index ... and the largest value at the largest index.Now we can see that the value of a_s has to be be n. After having this value assigned, we can ignore node a_s because any value we assign to any node will be lower than n.Hence we can take out node a_s, and reconsider the new set of leaves, and apply the same argument assigning n, n-1 etc.The implementation can be done with a adjacency list (saving back edges) and a array to mantain the number of unprocessed child nodes.
•  » » » » » 3 years ago, # ^ |   0 Thank you
•  » » » 3 years ago, # ^ |   0 I tried the greedy approach and just wanted to give the first location the minimum number it can get. For getting the minimum number I reversed all the edges and tried to do a level order traversal until I reached a level where there were no vertices then I tried to give lowest numbers to the lowest level in a sorted order. But don't know why my solution gives MLE verdict Code
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 I reversed every edge, then applied greedy algorithm backwards (that is, we go through the new topological order assigning values from bigger to smallest with a priority queue to get the biggest value that can be inserted right now). This is a test that helped me6 56 2 5 22 14 33 1The answer should be 6 3 5 4 1 2
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -10 6 4 5 1 2 3WA7 tho.Reversed all edges and used bfs for enumerating at first the farthest layers.
•  » » » » 3 years ago, # ^ |   0 The answer should be 6 3 5 4 1 2 I will edit the post to have this
•  » » » » » 3 years ago, # ^ |   0 Well, yeah, I see where my solution went wrong :(
 » 3 years ago, # |   0 Could someone plz tell me why I'm getting TLE on Problem D Test 9? 28613487
 » 3 years ago, # |   +3 Does centroid decomposition pass the limits for tree queries??Or is it the intended solution?
•  » » 3 years ago, # ^ |   +10 The problem is with memory, my solution with centroid decomposition uses O(nlogn) memory and i've got mle. Maybe there are some optimalizations, but i think it wasnt intended solution.
•  » » » 3 years ago, # ^ |   0 Yeah . I thought of same problem and did not code it.
•  » » » 3 years ago, # ^ |   +5 I passed with centroid decomposition with time and memory (after the contest though).
•  » » 3 years ago, # ^ |   0 I got it to pass both the time and memory limit (barely), but looking at some other solutions, I am now quite sure it is not the intended solution :).
•  » » 3 years ago, # ^ | ← Rev. 2 →   +42 IDK about centroid decomposition, but this task has very simple solution with single dfs, that calculates minimum index on path from root (which is the vertex from the first query) to each vertex. May be it's not the intended solution =)
•  » » 3 years ago, # ^ |   0 Why do people always try to solve tree problems with centroid decomposition? :DThe problem at hand has a solution much simpler and more natural than CD.
•  » » » 3 years ago, # ^ |   0 I agree. I guess it is just the hammer-nail-thing Petr mentioned in one of his recent blog posts.Btw, my centroid decomposition solution from the contest was hacked (time limit exceeded), but afterwards I optimized my code somewhat and now it passes in 2.4 seconds (28668357).
 » 3 years ago, # | ← Rev. 2 →   0 why this submission is wrong?
 » 3 years ago, # | ← Rev. 4 →   0 Plz help me out here i think in problem C answer should be only 0 or 1 because when we have to solve the question from other judge then we will choose problem with maximum difficulty and after that we don't have to go any other judge again ..because now we can solve all problem of given list. EDIT: thanks for help , sorry it was my bad i thought from other judges we can select problem of any defficulty now i got itn thanks again
•  » » 3 years ago, # ^ |   0 For solving problem with maximum difficulty x , you should have solved a problem with difficulty of x/2 first.
•  » » 3 years ago, # ^ |   0 Test: 1 1 10Answer: 3
•  » » 3 years ago, # ^ |   0 He can only choose those problem from other judge if it difficulty <= ai/2. 3 3 2 1 15 Here he will choose 6 and 12, so answer is 2.
 » 3 years ago, # |   0 How to solve "Suitable Replacement" ?
 » 3 years ago, # |   +2 What is the hacking test for problem A? > <
•  » » 3 years ago, # ^ |   0 Diagonals
 » 3 years ago, # |   +5 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 3 years ago, # |   0 Hack window is n't opening for me.Anyone else facing the same issue?
•  » » 3 years ago, # ^ |   0 Same... It is for every edu somehow...
 » 3 years ago, # |   +14 My best 10 minutes in entire Hacking Phase
•  » » 3 years ago, # ^ |   +6 How did you hack the same person ___ more than once in tinny time ?
•  » » » 3 years ago, # ^ |   -10 I found a hack case which is good for being Memory Limit Exceeded. There are several AC submissions of ___ in problem G. I found that all of his submissions are similar. Hack one of his code for a MLE case. Finally, I hacked the rest of his submissions rapidly, almost the same time. This is why I managed to hack the same person more than once in tiny time.
•  » » » » 3 years ago, # ^ |   0 Wow, good job man.
•  » » 3 years ago, # ^ |   +9 :'( xD
 » 3 years ago, # |   +7 This man halyavin is B killer
 » 3 years ago, # |   -45 I like your all post. You have done really good work. Thank you for the information you provide, it helped me a lot. I hope to have many more entries or so from you. escorts in panchkula
 » 3 years ago, # |   +9 What's going on with the testing of the round??
•  » » 3 years ago, # ^ |   0 Aren't testing suppose to run after adding all the hack test cases? Is that over?
 » 3 years ago, # |   0 What is the correct answer for this test case, problem E:11 11 2I think: 1 10 11 2 3 4 5 6 7 8 9Am i right ?
•  » » 3 years ago, # ^ |   +1 No, the correct answer is 1 2 3 4 5 6 7 8 9 10 11
•  » » » 3 years ago, # ^ |   0 Is not 1 10 11 2 3 4 5 6 7 8 9 lexicographically smaller then 1 2 3 4 5 6 7 8 9 10 11 ?
•  » » » » 3 years ago, # ^ |   +1 u have to compare number by number 1 = 1 2 < 10 so 1 2 ... is less than 1 10 ...
•  » » » » » 3 years ago, # ^ |   0 Thanks
•  » » » » » 3 years ago, # ^ |   0 Why is 2<10 lexicographically? Can you please give definition of lexicographically smaller? I also thought that 10 < 100 < 101 < 2 < 20 < ... etc. when it comes to lexicographical order. Thanks.
•  » » » » » » 3 years ago, # ^ |   0 Read the statement more attentively:Permutation should be lexicographically smallest among all suitable.2 isn't less than 10 lexicographically but permutation [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] is less then permutation [1, 10, 2, 3, 4, 5, 6, 7, 8, 9]You can read about permutations here Generation in lexicographic order
 » 3 years ago, # |   +10 Sometimes i just wonder. How do the problem setters set the constrains such a way, that every time you will feel , may be an optimized brute-force may just get AC with milliseconds remaining, but in reality it gets TLE just for one or two milliseconds :') Not gonna fall into that trap again i say to myself each and every time :'v
•  » » 3 years ago, # ^ |   0 Well, maybe problemsetters code the solutions they don't want to pass beforehand and check them on tests? :DThough it's still weird to think about bruteforce (even optimized) solutions for tasks with big constraints. Which tasks did you imply?
•  » » » 3 years ago, # ^ |   +8 PikMike I was talking about problem F. I tried to do it with hash. But pre-calculation was N * N * log(N) which i thought may just get AC within time limit.But it gets TLE for some trivial and easy cases :|
•  » » » » 3 years ago, # ^ |   0 Oh, actually, before hacks there were a few AC solutions which included hashes. Still one modulo is hackable and we tried to make sure nobody is able to get AC with just more modulos.
 » 3 years ago, # |   0 Can someone help me with my code for 825C - Multi-judge Solving? It shows TLE for test 6 but in my system it gets executed in 0.029s.My submission: 28700456Help would be appreciated :)