By PikMike, history, 14 months ago, translation, ,

Hello Codeforces!

On April 15, 17:35 MSK will be held Educational Codeforces Round 19.

This Educational Round is held as Harbour.Space university initiative. It's the second round supported by Harbour.Space. You can read the details about the cooperation between Harbour.Space and Codeforces in the blog post.

Some educational programs in Harbour.Space are interesting for most Codeforces users. One of them is Data Science Program. Here is few words from Sergey Nikolenko, Harbour.Space lecturer and Senior Researcher, Steklov Institute of Mathematics at St. Petersburg Russia.

The round will be unrated for all users and it will be held with extented ACM ICPC rules. After that 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 prepare such problems that both novices and experienced coders will find something interesting in this contest.

The round was prepared by Ivan BledDest Androsov, Mikhail MikeMirzayanov Mirzayanov and me.

Wish you enjoy the contest! Good luck!

UPD: Editorial

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Reyna 6 214
2 tqyaaaaaaaang 6 230
3 nuip 6 303
4 W4yneb0t 6 341
5 lexuanan 6 457

Congratulations to the best hackers:

Rank Competitor Hack Count
1 step_by_step 40:-7
2 halyavin 44:-17
3 STommydx 20:-5
4 yp155136 18:-2

234 successful hacks and 308 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 gainullin.ildar 0:04
C fanache99 0:09
D Reyna 0:21
F skywalkert 0:40

•
• +134
•

 » 14 months ago, # | ← Rev. 4 →   -29 It overlaps with GoogleCodeJam round 1A !UPD: It doesn't overlap .. thanks for yinanzhu and KieranHorgan
•  » » 14 months ago, # ^ |   0 so, go for only one, which you like more!
•  » » 14 months ago, # ^ |   +4 Actually It doesn't.
•  » » 14 months ago, # ^ |   0 You must messed up the time zone of either contest. Hope you find out before it's too late.
•  » » » 14 months ago, # ^ |   +2 Google code Jam round 1A Educational Codeforces Round 19
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +10 Exactly. When the educational round starts (16:35) 11 hours after the Code Jam round ends (05:30).
•  » » » » » 14 months ago, # ^ |   +3 OOPS, I missed it, I'm very sorry .. thanks KieranHorgan and yinanzhu
 » 14 months ago, # |   -42 is it rated?
•  » » 14 months ago, # ^ |   +28 Really?
 » 14 months ago, # |   +30 Why not all the contests have clear problem statements like this one. Thank you for this interesting contest.
 » 14 months ago, # |   +16 How to solve F?
•  » » 14 months ago, # ^ |   +31 I don't know the time complex of the std. But the time limit makes me think that the std have the time complex of O(n2).My solution's time complex is , and it costs 858ms.First it's easy to come up with the DP of O(n3). Then let's look at the programme carefully, and we can find out that it's very similar to Knapsack problem. And this classic problem have a classic way(divide each original item into items) to optimize it to We can use the same way to opimize the original problem. Then we solve the origine problem in
•  » » » 14 months ago, # ^ |   0 Can you provide a link or even better explain it yourself the details of the optimization ?
•  » » » » 14 months ago, # ^ |   0 My solution is quite strang and not elegant. I recommand you to read this guide:http://codeforces.com/blog/entry/51567?#comment-354676. I think this guide is more easy to understand and to write the code.
 » 14 months ago, # |   +8 very interesting problem set. I hope to see more problem set like this! :D
 » 14 months ago, # |   0 Can anyone tell me why im getting TLE on E. My idea is precompute for every k below 1000 in O(N) each and just simulate all k bigger than 1000 (worst case scenario is 100 operations if im correct) 26393091
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 The precomputation is probably too slow. Change 10^3 to sqrt(10^5) and it will probably pass.Edit: you didn't calculate the dp properly http://codeforces.com/contest/797/submission/26394436
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 I still get TLE even with this :/ 26394497
•  » » » » 14 months ago, # ^ |   0 Check the edit up there /. You can't use 1000 not because of time but because of overflow on short int operations.
•  » » » » » 14 months ago, # ^ |   0 Thank you man!
 » 14 months ago, # |   0 Did someone pass TL42 with mincost maxflow on F?
 » 14 months ago, # |   0 Never thought I could make more points than some reds or oranges. Strange contest =)
 » 14 months ago, # |   0 How to solve C ????
•  » » 14 months ago, # ^ |   0 You can solve it greedily. for (char c = 'a'; c <= 'z'; c++) { // Try to place current character 'c' in the target string. } 
•  » » » 14 months ago, # ^ |   0 I am so dumb :( ....I really do not know anything :(
•  » » » » 14 months ago, # ^ |   0 How did you manage to solve A and B if you consider yourself as dumb? :)
•  » » » 14 months ago, # ^ |   0 What special about test case 17? could not pass case 17 after multiple tries. my solutions:- 26491308 , 26469800
•  » » » » 14 months ago, # ^ |   0 got the case where it is failing input :- abcfefg output :- abceffg
 » 14 months ago, # |   0 Can someone explain to me why in the second test for E the 8th number is 2? 10 3 5 4 3 7 10 6 7 2 3 10 4 5 2 10 4 6 9 9 9 2 5 1 6 4 1 1 <- 5 6 6 4 p = 1, a[1] = 3, k = 1, n = 10;Initially p = 1. After first operation p = 1 + 3 + 1 = 5. After second operation p = 5 + 3 + 1 = 9 < 10. What am I missing?
•  » » 14 months ago, # ^ |   0 In the first operation p = 1 p = p + a[p] + k p = 1 + 3 + 1 p = 5 In the second operation p = 5 p = 5 + 7 + 1 p = 13 p > 10
•  » » » 14 months ago, # ^ |   0 Ah, I see. Thanks! I completely missed the fact that when p changes the array element chages as well.
 » 14 months ago, # |   +40 Please discuss the approach for problem F.
•  » » 14 months ago, # ^ |   +16 You can solve it using dynamic programming. Let DP[j][i] denote the minimum cost to assign the first i mice to the first j holes. For each state, iterate over the leftmost mouse you will assign the jth hole to. This takes O(m*n*n) time. But notice that for a fixed j, the optimal left-point is non-decreasing for non-decreasing i, i.e. optima[j][i] <= optima[j][i+1]. So you can speed up the DP using divide-and-conquer optimisation. Code
•  » » » 14 months ago, # ^ |   0 How do you deal with hole capacities and the fact that contiguous mice are not necessary assigned to the same hole?
•  » » » » 14 months ago, # ^ |   +4 The group of mice assigned to some hole is always contiguous, i.e. there will never exist a situation that a,b,c are three consecutive mice (in increasing order of coordinate) but a and c are assigned to hole-1 but b is assigned to hole-2.And what do you mean by how I deal with hole capacities? If I have to assign some suffix of the first x mice to hole j, then I can assign atmost the last capacity[j] mice to hole j.
•  » » » » » 14 months ago, # ^ |   0 Just a moment after I posted, I realized sorting was enough to assign contiguous mice to a hole.As for the hole capacities, yep, I meant that (and I missed it's as simple as that!)Thank you :)
•  » » 14 months ago, # ^ |   0 Please also discuss the approach for problem E.
 » 14 months ago, # | ← Rev. 2 →   0 Can someone please help me in finding mistake in my Solution for problem C.
•  » » 14 months ago, # ^ |   +1 Your code fails for this testcase : abcbabbccYour code outputs aabbccbcb whereas the correct answer is aabbbcbcc
 » 14 months ago, # | ← Rev. 4 →   +3 Can someone tell me where I am wrong in D?I made a fucntion checkValid which takes node,l,r as arguments. And marks true if value[node] lies between l and r both inclusive. Then, I call checkValid with left[node], and with the intersection of (-inf,value[node]-1) and (l,r). The same process is repeated symmetrically for right node.I am getting WA at Test Case 20. And my answer differs by 1 from expected answer.Submission Link: 26396243
•  » » 14 months ago, # ^ |   +3 There were two mistakes.One was a syntax error at line 92. Second mistake was I was remembering the nodes which are visited instead of values.AC solution: 26398128
 » 14 months ago, # |   0 No successful submissions on E in Python 2 or Python 3. I tried to rewrite one Java solution to Python, it TLE-ed on test 7. Isn't the time limit of problem E too tight for Python?
 » 14 months ago, # |   +6 It's my first time to try hacking here on CF. Not sure how it works. It seems to be just stuck loading forever. Is this supposed to happen?
•  » » 14 months ago, # ^ |   0 Reload
•  » » » 14 months ago, # ^ |   0 I tried reloading many times, and also clearing my browser cache/cookies before trying again. This happens after I submit the input for hacking by the way.
 » 14 months ago, # |   0 Can anybody tell why my code is failing in one of the tests ?? https://pastebin.com/GC45xUAa
•  » » 14 months ago, # ^ |   0 26389948^This implementation is similar to yours. You can refer to this one.
•  » » » 14 months ago, # ^ |   0 Its quite confusing . He has considered even more cases . Can you read my code once and tell me , which case I might be missing ??
 » 14 months ago, # |   +17 That's how you try to cheat even in an unrated round!!ScreenShot
 » 14 months ago, # | ← Rev. 2 →   +6 I noticed that if I submit a solution after a previous solution got hacked, then my new solution runs only the original system tests, and not the hack(s) that caught my previous solution(s). That's too bad, because that way I can be "Accepted" again without fixing my problem (in fact, I have no idea whether I fixed my problem unless the hacker is kind enough to keep trying the hack on my new solution).UPDATE: Appears to be fixed now.
 » 14 months ago, # |   0 http://codeforces.com/contest/797/submission/26402069 why this submission always wrong at 25th test case???who can help me ??
 » 14 months ago, # | ← Rev. 3 →   0 Nice contest and nice problems
 » 14 months ago, # | ← Rev. 4 →   0 My java solutions with proper documentation Hope it helps.
 » 14 months ago, # |   0 nice warm up round man.... thanks for all these... i luv this website <3
 » 14 months ago, # |   +1 I'm unable to submit a solution for the contest. It shows that System Testing is going on, while it was over hours ago.On clicking the submit button, it shows the message "Practice is allowed only for finished and unfrozen contests".
 » 14 months ago, # |   +3 Is it normal that problems B and C now have duplicate tests? For example, there is the test #48 "1 // 1" that repeats further as #50, 51, and 54. Problem C also has such tests, e. g. "a" by #40, 41, 42, 45, 47, and 51.
 » 14 months ago, # |   0 What is the logic behind problem E?