### MikeMirzayanov's blog

By MikeMirzayanov, history, 4 years ago, translation, ,

You may print PDF-statements: http://assets.codeforces.com/statements/589.pdf

Recently 2015-2016 ACM-ICPC, NEERC, Southern Subregional Contest has been finished. On behalf of jury and hosts I congratulate winners and advancers to the semifinals. Prize places are (horray!):

• 1 place: Nizhny Novgorod State University #1 (Vladislav vepifanov Epifanov, Nikolay KAN Kalinin, Mikhail mike_live Krivonosov)
• 2 place: Innopolis University #1 (Evgeniy savinov Savinov, Sergey sokian Kiyan, Alexander map Mashrabov)
• 3 place: Saratov State University #1 (Edvard homo_sapiens Davtyan, Vitaliy kuviman Kudasov, Danil dans Sagunov)

On Saturday (October, 17) в 08:00 (UTC) we will host unofficial online mirror. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams. This will be a team/personal contest on Codeforces, with teams consisting of up to three people or individual participants. The contest will not affect Codeforces ratings.

For sure, it will be unrated contest. We recommend you to take part in teams. I think, the contest will be moved to Gym later.

Good luck!

P.S. We are aware that this mirror will overlap with some other online tournaments, but unfortunately we are unable to change the current time slot, due to the online mirror of the Moscow Subregional of NEERC scheduled on Sunday. All school teams are recommended to pay attention to Online-mirror of the Ural regional team championship.

• +235

 » 4 years ago, # |   +3 An hour after this contest ends, COCI contest starts. Tomorrow's gonna be intense! :D
•  » » 4 years ago, # ^ |   -17 I do not attend any of these. And i was not if there was a t-shirt prize. I will not code anymore. We have been a very good family so far, but i need to leave now. Good bye! ps : im so sorry mahmoudhassan :(
•  » » » 4 years ago, # ^ |   +44
 » 4 years ago, # |   -37 No T-shirts ?
 » 4 years ago, # |   -14 For how many Hours Contest will Run ??
•  » » 4 years ago, # ^ | ← Rev. 2 →   +7 So 5 Hours
•  » » » 4 years ago, # ^ |   0 May be not.There're ten minutes to prepare.
•  » » 4 years ago, # ^ |   0 You can see duration from this link Duration :)
 » 4 years ago, # |   -27 Please provide editorial and codes if you plan on moving it to gym.
•  » » 4 years ago, # ^ |   0 For what reason?
•  » » » 4 years ago, # ^ |   0 I don't know a lot about Gym contests, but I know this much that they don't allow you to look at test cases, as well as others' solutions. Thus, I was asking them to open others' solutions and test cases , and also provide editorials. That's all :)
•  » » 4 years ago, # ^ |   0 Did I get so many downvotes because I forgot to mention "after the contest" , as Gym problems don't let you look at others' codes, or test cases?Please tell me if the reason is something else, because I would like to know. I haven't practiced a lot of Gym problems you see. :)
 » 4 years ago, # |   +4 Will there be youtube editorial after the contest like last year ?
 » 4 years ago, # |   0 how will be the difficulty level of the problems?? Can we (newbie's) can solve these..
•  » » 4 years ago, # ^ |   +1 See the last sentence in the blog: there is a contest for low-level teams today: http://acm.timus.ru/contest.aspx?id=304
•  » » » 4 years ago, # ^ |   0 How do you know it is going to be easier?
•  » » » » 4 years ago, # ^ |   0 Just read the problems from the previous years.
 » 4 years ago, # |   +1 How to solve Problem F ??
•  » » 4 years ago, # ^ |   +6 Just make binary search by time near each food and then apply a greedy strategy : eat the most needed food, that will be ended soon. (how many this food we need — number of second it will be available). http://pastebin.com/0crsX2yH
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +8 How can you prove it? I can't understand.. I used maxflow algorithm and accepted!
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 can u please explain how did u solve it using max-flow ? and how u model the flow graph ?
 » 4 years ago, # |   +7 will test cases be public later? thanks
 » 4 years ago, # |   0 is it possible to solve G with square-root decomposition ?
•  » » 4 years ago, # ^ |   0 Yes it is. We did that.
•  » » » 4 years ago, # ^ |   +13 got AC after 36 attempts :3
 » 4 years ago, # |   +5 How to solve C?
•  » » 4 years ago, # ^ |   0 First trick: we need only first 60 concatenates.
•  » » » 4 years ago, # ^ |   +5 What's the next trick? We have TLE #11, our solution works about 30s on max test. It's quite straightforward, with complexity something like O(queries * log(r) * maxShift).How to solve it faster?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 My complexity the same is O(queries * log(r)). Next trick is recursion, if we want to know answer for k-th string on L,R we can use answer for k-1-th string for some new par L' and R'. k-th string can be split into four groups: [---p---][--s--][--s--][---p---] length of [s] it is t[k] (shift length)And now, clearly, we have 10 cases of calls in recursion, depending on location L and R.Next trick — |s| is small (<=100). In my solution i precalculate answers for all suffixes for all strings.For example, if L in 0th group and R in 2th we can use these values and just change R to R'. I think all 10 cases are easy except case L in 0 and R in 3. But if we built projection D of R [---p---][--s--][--s--][---p---] ..D...L__________________R...... then we can call value for segment [D+1, L-1] and subtract it from all count of symbols. If D>=L we need add it, ofc.
 » 4 years ago, # |   +3 can anyone share his algorithm about prob B? I only think of one with complexity O(n^2logn)
•  » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   0 about pro A?
•  » » 4 years ago, # ^ |   +3
•  » » 4 years ago, # ^ |   0 n^2 solution: Save all pairs (w, h) such thatw > h (swap them if needed). Sort in ascending order of w. Save all unique h values.For every unique h and i (i <= n) remember how many elements with height greater or equal than h there is on suffix from i to n.Then just iterate over w (in ascending order), inside this iterate over all unique h values, answer how many elements we have with height > h and having width not less than w in constant time.Solution: [submission:13688964]
 » 4 years ago, # |   0 How to solve problem K?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +43 Problem KThe key observation here is that every time we need to choose a task, we shouldn't look through all of them.Imagine we have a list of deques q, where q[t] is the deque containing all tasks with t[i] == t, ordered by l[i], then by i. Let's denote the minimal t such that q[t] is not empty, as minT.We can consider only deques q[minT], ..., q[minT + sqrt(10^5)]. Proof: If t[i] + sqrt(10^5) < t[j], then the function l[i] — (T — t[i])^2 is definitely less than l[j] — (T — t[j])^2, no matter what their l and t values are. So the tasks with t[i] > minT + sqrt(10^5) cannot be minimal.As all deques contain tasks ordered by l[i], then by i, just as in the statement, iterate over all t in the interval [minT, minT + sqrt(10^5)], and choose the best task from the first elements in deques.
•  » » » 4 years ago, # ^ |   +5 Thanks. AC :)
 » 4 years ago, # |   0 How to solve D?
•  » » 4 years ago, # ^ |   +1 O(n^2) . For Each , check others to catch up,This can be done in O(1) or using binary Search in Time.(O(log(n))
 » 4 years ago, # |   +3 what's the 10th test case in problem D ? -_-
•  » » 4 years ago, # ^ | ← Rev. 3 →   +8 Integer overflow probably. For me it failed on checking (f[i] - s[i]) * (f[j] - s[j]) > 0
 » 4 years ago, # |   0 Could someone post their code for A?
•  » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 [submission:13683752]
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 http://ideone.com/MR9MgN (Perl)
 » 4 years ago, # |   0 How to solve problem J ? if i can't move forward should I stop the robot ?
 » 4 years ago, # |   0 my solution for problem J(cleaner robot) is failing on test 15. Can anyone guess what would be wrong?
•  » » 4 years ago, # ^ |   0 mine too ! couldn't pass the test 15. 15 attempts, all failed ! :(
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 After WA15 I realized that it will be much easier to make more steps than it would ever need and increment answer on every new clean tile.And test I tried was like6 6 ...... ...... R..... .....* ...... ......
•  » » » » 4 years ago, # ^ |   0 can you please tell me the answer for this test?
•  » » » » » 4 years ago, # ^ |   0 14
•  » » » » » » 4 years ago, # ^ |   0 I realized that it will be much easier to make more steps than it would ever need and increment answer on every new clean tile? can you elaborate it?
•  » » » » » » » 4 years ago, # ^ |   0 In my solution I just make n2 * m2 steps. It's enough to get AC.
•  » » » » » » » » 4 years ago, # ^ |   +5 If one step is either moving or rotating, it's enough to make 4*n*m steps. Cleaner has only 4*n*m different states — each direction on each cell. We did it bfs-like, though — with vis[row][column][direction].
•  » » » » » » » » » 4 years ago, # ^ |   0 I agree It's not like I was trying hard to get this number, chose the one that will be under the limits.
 » 4 years ago, # |   0 what is the 15th test case of problem j??
•  » » 4 years ago, # ^ |   0 my code was failing on case 15 ... until i realized that i was checking for '.' on the next tile that the robot moves on , which is wrong ... because letters 'U' , 'D', 'L' ,'R' are allowed too ... got AC after fixing it :)
 » 4 years ago, # |   0 Can anyone share his code for problem J ?
•  » » 4 years ago, # ^ |   0 Maybe 1 10 .........UOR 10 10 .........* .......... .......... .......... .......... .......... .......... .......... .......... .........U
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 what are the correct output of these cases ?
•  » » 4 years ago, # ^ |   0 Although my code is very big...i have written it in a very simple manner putting all the different conditions...so you can easily understand the codehttp://ideone.com/EuC5xL
•  » » » 4 years ago, # ^ |   0 thanks. by the way, test cases are public now. so i found my bug. anyway thanks again for sharing your code. :)
 » 4 years ago, # | ← Rev. 2 →   0 can anyone guess what is test 15? question to those who passed the tests. I am curious in knowing where my solution is wrong
 » 4 years ago, # |   0 Did anyone solve Problem — G using segment tree?
•  » » 4 years ago, # ^ | ← Rev. 19 →   +17 Yep. Sort both the days and applicants (by di) in reverse order, process them in parallel. More specifically: when considering candidate i, it suffices to only consider the days j with tj > di (all other days are useless anyway). So we process the candidates by descending di, and for each candidate we would like to find the earliest time they could be done. Clearly if we only consider days j with tj > di, then the optimal solution will be some prefix of this sequence of days.You can use a segment tree where leaf j starts as (0, 0), and when you 'process' (more on this later) the day you set it to (tj, 1). Here the first value represents the total available time (we haven't considered setup time yet, but since we are going to maintain that for all days in the segment tree we have tj > di this day will still result in a net gain) and the second value represents the number of days over which this is spread. Combine two leaves with pairwise addition. The idea is now to insert each day j as soon as we process a candidate i with tj > di, because after that, all candidates will have a lower di value, and thus they can also use this day (recall that we process all candidates by di in descending order). You can achieve this quickly by also sorting the days in descending order and maintaining a pointer to the next day that should be inserted.After this, you can use the segment tree to compute whether a certain prefix of the days is sufficient. Query the interval [0, d) for some d, this will result in a tuple (time, days), the total amount of time and the number of days in this interval, respectively (amongst all days with tj > di). The candidate can then finish if and only if time ≥ ri + di × days. You can use binary search to find the smallest prefix, since, again, all days in the segment tree will result in a net gain (tj - di to be precise), so the amount of available time for a prefix [0, d) is increasing in d.After preprocessing my solution was because I was being lazy, but you can drop the binary search and find the optimal prefix in a single traversal in . Details are left as an exercise to the reader :)Code
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 TimonKnigge My idea was same as you but did it ascending order of . Couldn't figure out what's wrong :( Code
•  » » » » 4 years ago, # ^ |   0 Are you sure you are processing the candidates/days in the right order? You seem to process them in ascending order, not descending.
•  » » » » » 4 years ago, # ^ |   0 You wouldn't believe how stupid I'm. The problem was I take n as m and m as n. :( here is the AC Code
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 You can do it by ascending order too. For each , remove all and then find the result using segment tree.
•  » » 4 years ago, # ^ |   0 I solved using BIT in nLogn complexity. Code
 » 4 years ago, # | ← Rev. 2 →   0 forget it. Everything is alright. :)
 » 4 years ago, # |   0 i could take it just for about half because of school classes! but i enjoy it !thanks XD!
 » 4 years ago, # |   +3 No way to see other's code?
 » 4 years ago, # |   +6 How to solve problem H?
 » 4 years ago, # |   +3 Ideas for H?
•  » » 4 years ago, # ^ | ← Rev. 4 →   +13 Assume our graph has one connected component, then we can create roads.Hint: try to solve for a treeMore detailed explanation
 » 4 years ago, # |   +5 full of implementation
 » 4 years ago, # | ← Rev. 2 →   +1 The algorithm for the robot to move and clean the floor in the room is as follows:1.clean the current cell which a cleaner robot is in; 2. if the side-adjacent cell in the direction where the robot is looking exists and is empty, move to it and go to step 1; 3.otherwise turn 90 degrees clockwise (to the right relative to its current direction) and move to step 2. Input #15: 10 10 .********* .*.......* .*.*****.* D*.*...*.* .*.*.*.*.* .*.***.*.* .*.....*.* .*******.* .*******.* .........* How the ans is 10? Why not like this?
•  » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ |   0 You have an infinite robot movements on the first column: upwards-downwards.
•  » » » 4 years ago, # ^ |   0 Thank you Guy, I have done it. :)
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 look here "The algorithm for the robot to move and clean the floor in the room is as follows: 1. clean the current cell which a cleaner robot is in; 2. if the side-adjacent cell in the direction where the robot is looking exists and is empty, move to it and go to step 1; 3. otherwise turn 90 degrees clockwise (to the right relative to its current direction) and move to step 2. "
•  » » » 4 years ago, # ^ |   0 Thanks
 » 4 years ago, # |   0 what is test 13 of pro A?
 » 4 years ago, # |   0 Could someone explain the idea to solve Problem M?
 » 4 years ago, # | ← Rev. 2 →   0 Can problem K (King's Rout) be solved with dfs? I keep getting wrong answer for test case 13. Can anybody please tell me what this test case is? problem list submission
 » 3 years ago, # |   0 How to solve F using flows? Problem Link