Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By BledDest, history, 18 months ago, translation, ,

Hello Codeforces!

On June 05, 18:05 MSK Educational Codeforces Round 22 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 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. We tried to design the problems in such a way that both beginners and experienced programmers can find something interesting in the contest.

The problems were prepared by Mikhail PikMike Piklyaev, Vladimir 0n25 Petrov and me. Huge thanks to Maxim HellKitsune Finutin and Alexey ashmelev Shmelev for testing the contest!

Good luck to all participants!

UPD: The editorial is published.

•
• +207
•

 » 18 months ago, # |   +4 Hi every one.... is there any way to search problems by their tags? thanks
•  » » 18 months ago, # ^ | ← Rev. 2 →   +4 yes, just go to the problem section i.e.here and click on any tag written along with the name of the problem.simpler solution: — just google it... like "codeforces problems tag"
•  » » 18 months ago, # ^ | ← Rev. 2 →   +5 Go to http://codeforces.com/problemset/tags/tag1,tag2,..,tagn. So to see all problems about binary searching and graphs, go to http://codeforces.com/problemset/tags/binary%20search,graphs
•  » » 18 months ago, # ^ | ← Rev. 2 →   +1 or use this link: LINK ( I don't know does it have all tags or no )
•  » » 18 months ago, # ^ | ← Rev. 3 →   +6 why some people downvoted him? he just asked a question :(// now he is getting upvotes :))
 » 18 months ago, # |   -13 I'm new to codeforces and this is my first educational round! Excited! :P
 » 18 months ago, # |   -7 Too few comments! Isn't it weird?
•  » » 18 months ago, # ^ |   +1 Because this contest is unrated :V , I think.
 » 18 months ago, # |   0 Why is E not an interactive problem?
 » 18 months ago, # |   -19 Can someone solve me B?I have idea but can't implement.
•  » » 18 months ago, # ^ |   +15 You can find all unlucky years in log(r)^2, then just sort them and find maximum length between all pairs of neighbours in sorted array. Also check for segments starting in l, and ending in r.
 » 18 months ago, # |   +26 Stop killing the cute MO solutions xD.
 » 18 months ago, # |   0 How to solve F ?
•  » » 18 months ago, # ^ |   +9 for each edge find when its in the graph, after that something like this
 » 18 months ago, # |   +10 I should have copied my Persistent IT code instead of trying to re-invent it...
•  » » 18 months ago, # ^ |   0 Which problem did you plan to use Persistent IT on ?
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +1 E. I thought I had to have extra O(sqrt(n)) complexity, so I thought I had to use persistent IT. Only realized it at the last minutes and it's too late.
•  » » 18 months ago, # ^ |   0 You can use SQRT decomposition to answer the queries rather than using complicated Persistent IT
•  » » » 18 months ago, # ^ |   0 Persistent IT is not very complicated, in my opinion some SQRT methods are more tedious to implement.
•  » » 18 months ago, # ^ |   0 What is IT ? Interval Tree ?
•  » » » 18 months ago, # ^ |   0 Yes
 » 18 months ago, # |   +6 Nice problems! What were your solutions for C?
•  » » 18 months ago, # ^ | ← Rev. 3 →   0 Calculate all the distances from Alice and Bob, and find the node where the distance from Alice is maximum and greater than the one from bob, multiply that distance by 2 to get the number of moves.
•  » » » 18 months ago, # ^ |   0 But that won't work for all cases right? For your solution to be correct you must ensure that Alice won't reach Bob on all nodes in the path...rt?
•  » » » 18 months ago, # ^ |   0 why this solution is right ? can you give more details why we should do another dfs where from the position bob stands thanks in advance
•  » » » » 18 months ago, # ^ |   0 The best strategy for Alice is to always go down in the tree. Bob wants to survive for as long as possible so his best strategy is to go to the furthest node from Alice. As explained in the editorial, Bob needs to go up in the tree (by 0 or more nodes) to reach the branch that leads to the furthest node. Sometimes this cannot be achieved since Alice will be there before Bob. That's why you need to check both distances.I hope this helps. :)
•  » » » » » 18 months ago, # ^ |   0 thanks, now i understand it , thank you for your detailed explain !!
•  » » 18 months ago, # ^ | ← Rev. 3 →   0 Notice that Alice will walk down the tree to wherever Bob is, and that the number of steps it will take is just the depth of that path in the tree. That means that Bob should try to get to a node that has the greatest depth.If the root node is at level 0, and Bob's node is a level x, the Bob can walk up at most nodes up before choosing to go down the path that has the greatest depth. We can find the depths of the paths using a dfs.My Submission: 27589077
 » 18 months ago, # |   +1 Any hints on how to solve E?
•  » » 18 months ago, # ^ |   +15 Solve SPOJ problem DQUERY first, online using persistent segment trees.
•  » » 18 months ago, # ^ | ← Rev. 3 →   +8 For each i, compute bi the position of k - th number that equal to ai to the right (if there's no such position, bi = n + 1), then for each query, count from l to r how many number greater than r.PS: My solution
 » 18 months ago, # |   +60 pls make a div1 contest :'(
 » 18 months ago, # |   +3 when will we be able to hack???
 » 18 months ago, # |   +1 How to solve problem-B?
•  » » 18 months ago, # ^ |   0 Find out all the possible value of x^a + y^b and then fond the max range between l and r.
 » 18 months ago, # | ← Rev. 3 →   +10 Could one hack it :)It failed :(
 » 18 months ago, # |   0 can some one tell me the answer for the following test case for problem C 16 12 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 3 11 11 12 12 13 13 14 14 15 15 16i think the answer is 14. but seems its wrong please help!
•  » » 18 months ago, # ^ |   +1 You can copy the code of a couple of high-rating coders, run this case and, if their answer is the same, it is very likely that they are correct. My program outputs 16, but it might have a bug.
•  » » 18 months ago, # ^ | ← Rev. 2 →   +1 Answer is 16. Bob will walk down to node 16 and wait there. It will take Alice 8 moves to get there, so the total number of moves is 2 * 8 = 16.
•  » » 18 months ago, # ^ |   +1 The answer is 16 according to my code.
 » 18 months ago, # |   +11 Nice problems, Why the rated rounds are not like this round? :"D
 » 18 months ago, # |   0 A small doubt-: For problem B, test-case 13 is 14 2 732028847861235713 732028847861235713 if both the start and end years are same and my computation gives it as unlucky no, won't the ans be 0? Or is my computation of unlucky nos wrong?
 » 18 months ago, # |   0 Can anyone give me a simplified version of test 8 in problem C?
•  » » 18 months ago, # ^ |   0 Something like: 5 3 1 2 2 3 2 4 4 5 Answer should be 4.
•  » » » 18 months ago, # ^ |   +9 When you realized that you at got WA because of 2 character in the code...(Change db[u] < da[v] to db[u]+1 < da[v])
•  » » 18 months ago, # ^ |   0 I also got WA at test 8. I found one possible test case below.10 2 7 1 8 2 1 3 10 4 7 5 3 6 5 8 6 9 7 10
 » 18 months ago, # |   +28 FeelsBadMan
•  » » 18 months ago, # ^ |   0 FeelsBadMan(Got E accepted 10 minutes after the contest).PS: Btw, is there a fast way to insert image from computer?
 » 18 months ago, # |   0 Had any One Solve problem C using dp ?!
•  » » 18 months ago, # ^ |   0 I think it was a simple greedy type solution,using DP probably wont help at all,also the constraint were not DP type,I may be wrong though..
 » 18 months ago, # |   +44 I am getting WA on problem C for a case which is not valid and the case is also showing valid for hack input. But in the problem it is stated that "Bob starts at vertex x (x ≠ 1)." But in this case x = 1. Please check it.Here is my code: 27597100
•  » » 18 months ago, # ^ |   +3 yes same problem.
•  » » 18 months ago, # ^ |   +5 Sorry, this test is removed now. It was added after contest ended but it was wrong.
 » 18 months ago, # |   0 Is there any way to get the hacking tests so that I can verify my solutions?
•  » » 18 months ago, # ^ |   -15 It was possible if u resubmit until education round 19/20. Now not possible
•  » » » 18 months ago, # ^ |   0 All unique hacking tests are added to testset after the end of hacking phase. It holds for every round.
 » 18 months ago, # |   0 Any idea how to solve D?
•  » » 18 months ago, # ^ |   +6 SpoilerDefine dp(x, y) = maximum sum with the last element indices of the two subsequences being x and y (assume x > y). Each state (x, y) has transitions to (z, y) or (z, x) where z > x. Now we have an O(n3) solution, but we can consider only first z's that give valid transitions (independently for each type of transition (same/+1/-1/congruent)), so it becomes O(n2).My code is AC, and I hope it's correct :O
 » 18 months ago, # | ← Rev. 2 →   0 I got a wrong evaluation from Codeforces on Problem B. After the contest, When i checked the test case where i got Wrong answer. The output computed by Codeforces was wrong. I was getting a different output (the correct one) on all the other IDEs. Kindly look into this. 27593531 [Test #10]
•  » » 18 months ago, # ^ |   0 I submitted your code using GNU C++11, and it was accepted. I don't use C++ normally so I'm not sure why. I hope this helps you discover the problem.
•  » » » 18 months ago, # ^ |   0 Thanks. Thats certainly a bug then. Because, whatever gets executed in C++11 can get executed in C++14 in the very same manner.
 » 18 months ago, # |   0 can some one help me with this? There is an array of integers,we need to answer queries in this form. given L,R and A,B need to count number of numbers in range [A,B] in the subarray [L,R].each query should be solved in logn time.what is the best datastructure to use here?
•  » » 18 months ago, # ^ |   +1 Segment Tree.(AFAIK) You can get log(n) time per query with offline processing and segment tree. See SPOJ KQUERY problem for reference. (not giving details as you asked only the name of the data structure :P)You can do it easily with merge sort tree, a variation of segment tree, but time per query there will be (log(n))^2
•  » » » 18 months ago, # ^ | ← Rev. 4 →   0 In the problem KQUERY we put all the queries and the array elements and sort it.Then we process each element.if it is an array element we update the segment tree, if it is a query we find numbers in range [L,R].here we are exploiting the fact that all the numbers(elements) which came before A query are greater than k.But in my question the numbers should be in a range between [A,B].so how do we do that using offline approach? On the other hand the merge sort tree approach seems good.
•  » » » » 18 months ago, # ^ |   +1 Simple. Answer for range [A,B] = number of elements larger than A — number of elements larger than (B+1). So, for each range [A, B], you can find answer with 2 queries. kquery(L, R, A) — kquery(L, R, B+1) where kquery(x, y, z) returns number of elements greater than z in the subarray [x, y].
•  » » » » » 18 months ago, # ^ |   0 got it :D.Thanks for your time.love this community
•  » » » » » » 18 months ago, # ^ |   0 Now you seem happy after asking question from live contest.Cheater
•  » » » » » » » 18 months ago, # ^ | ← Rev. 2 →   0 well it is not the exact same question,I simplified it a lot and dont tell me you came up with the working of segment trees on your own.you had to learn it somewhere right? Long contests are meant to make you learn about new data structures and algorithms.I could have googled it anyway and got the same results.but i asked here to know different possible solutions and efficient ones.A lot of people copy paste some hard datastructures form internet.do you consider that cheating?I dont consider this cheating, it is a learning process
 » 18 months ago, # |   +32 Some of the successful hacks for problem C had incorrect tests in it (there was a bug in validator). We are really sorry about the issue! These hacks are now rolled back, all the solutions which were hacked now seem to be accepted. We should have worked harder on checking the correctness of all the checkers, validators and solutions. We will do our best to avoid further contests to have such major issues.
 » 18 months ago, # |   +13 The editorial is published.
 » 18 months ago, # |   0 Lots of hacks in problem B ..
 » 18 months ago, # |   +5 What's the recommended order for solving problems in a contest? Do we start with the easiest problem A first or is there a smarter strategy?
•  » » 18 months ago, # ^ |   0 Start with the easier ones first. You anyway have to do them at some point in the contest. So why not to finish them up asap and then devote your time in the tougher questions.
•  » » » 18 months ago, # ^ |   0 Because the points you will get in B decreases faster than that of A.
 » 18 months ago, # |   0 Test case 5 of prob D:109 6 8 5 5 2 8 9 2 2Answer given is 9. But shldn't it be 10? {6,5,5} forming one subsequence and rest all nums for the other.
•  » » 18 months ago, # ^ |   0 The rest will be {9, 8, 2, ...} and you can't take 2 after 8.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 Ok got it thanks... i thought differ by 1 meant in terms of mod 7
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 In problem C , My this submission getting WA on test 10 : 27605306 , what is the bug in my code ? can you help me please
•  » » » 18 months ago, # ^ |   0 WHat is the simplified version of test case 10 of problem C ? pikmike
•  » » » » 18 months ago, # ^ |   0 No idea. It's just a random tree.
 » 18 months ago, # |   -38 best joke ever
 » 18 months ago, # |   +1 I try to hack and all the website says is this: http://i.imgur.com/aoSKkAM.pngAnything I Should do?
•  » » 18 months ago, # ^ |   0 Happens to me a lot too, I just refresh the page over and over until it works lol
 » 18 months ago, # | ← Rev. 2 →   0 In problem C , My this submission getting WA on test 10 : 27605306 , what is the bug in my code ?
 » 18 months ago, # |   -29 Hi, very nice post. Microsoft Phone Number UK
 » 18 months ago, # | ← Rev. 2 →   0 Please ignore this. Doubt was resolved.
 » 18 months ago, # |   +34 F isn't original. In fact, I've used the same idea in a contest in our school around three years ago. Also, it can be solved by link/cut tree in time, which is better than the solution in the editorial.But since it's an Educational round I don't think the tasks have to be original. I've seen other tasks in ECR that are obviously not original as well.My code can be found here. You can see my poor coding style back then(therefore I had lots of trouble getting the input format fitted, even though there's only a little to be modified).
 » 18 months ago, # | ← Rev. 2 →   0 In problem C, my submission: http://codeforces.com/contest/813/submission/27662850) is giving correct answer on Ideone for the 1st sample test case but the same submission is giving WA on Codeforces. Can you help me please? Test case: 4 3 1 2 2 3 2 4