### MikeMirzayanov's blog

By MikeMirzayanov, history, 3 years ago, translation, ,

Today 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest will be held. On behalf of jury and hosts I wish teams to make happy their coaches!

You can watch the results by the link https://contest.sgu.ru/monitor/1.

And on Sunday (October, 23) on 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!

• +139

 » 3 years ago, # |   +11 Good luck for all!
•  » » 3 years ago, # ^ | ← Rev. 3 →   -62 Deleted!
 » 3 years ago, # |   0 Good luck to all especially CF users who are participating in NEERC. make us proud :3
•  » » 3 years ago, # ^ |   -7 they'll make you be sure of that :3
 » 3 years ago, # |   0 There seems to be a typo on the contests page; the contest tomorrow is named "2015-2016 ..." instead of "2016-2017 ...".
 » 3 years ago, # |   +45 The contest will not affect Codeforces ratings.For sure, it will be unrated contest. that moment when the author no longer can put up with "is it rated" comments so he repeats the information twice to make sure no one will ask it.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +23 But is it rated? Edit: I was joking, please don't downvote me.
 » 3 years ago, # |   +13 Contest clashes with Code Festival.
 » 3 years ago, # |   +4 Are problems going to be shuffled since we can see the results?
•  » » 3 years ago, # ^ |   +20 Yes
 » 3 years ago, # |   +17 Great contest! Is there something like official slides with solution outlines? I remember those are available for other ICPC contests like NWERC.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 +1. Would appreciate if there's any editorial for this contest esp. for problem F, K, and L (which are quite "untouched" by contestants).
•  » » » 3 years ago, # ^ |   +18 Here is all problem analysis in youtube (in russian but you can activate subtitle and select translate to english): video1 [problem (A,B,C) (E,J,D on CF)]: https://www.youtube.com/watch?v=ea-s_HBjPOo video2 [problem (D,E) (I,C on CF)]: https://www.youtube.com/watch?v=eh1WihY8iBY video3 [problem (F,G,H) (L,H,B on CF)]: https://www.youtube.com/watch?v=aEZCZZKzulg video4 [problem (I,J,K) (F,G,A on CF)]: https://www.youtube.com/watch?v=VxM_jAXakm4 video5 [problem (L) (K on CF)]: https://www.youtube.com/watch?v=Xk1fAIc3rQc
•  » » » » 3 years ago, # ^ |   +4 Haha, I just tried the auto-translate... Let's say it's.. interesting, but I haven't got the slightest what the author is actually explaining :D Thanks anyways
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0  > . <  I meant to upvote because I had the same experience but I accidentally clicked downvote instead, sorry.
 » 3 years ago, # | ← Rev. 2 →   +3 For Problem D, with this input : 5 2 10 5 4 1 7 14 10 12 4 10Why this output is considered as wrong answer? 5 8 10 12 46 48while jury's solution is 5 8 10 12 40 42i think it is possible for my solution.
•  » » 3 years ago, # ^ |   +3 According to your answer, you'll begin to cross the final bridge at time 34, not 40. Did you add t_i instead of actual crossing time?
 » 3 years ago, # |   +23 How did some people pass I with min cost flow? Wouldn't it TLE with these constraints?
•  » » 3 years ago, # ^ |   +8 In my case, I didn't know how to solve the "right" way so I decided to give it a try (and I had good reasons since I had seen someone pass this problem with a min cost max flow solution — the flow model is basically the same as problem I)The Big O notation is mean to flow functions, in practice they are usually faster than they seem. If you consider my code which uses SPFA (which has O(E) average shortest path) the code would be average O(V * E) still and I think it might be hard to create an O(V * E) SPFA case for the nature of the question
•  » » 3 years ago, # ^ |   +2 What is the expected approach for I?
•  » » » 3 years ago, # ^ | ← Rev. 5 →   0 we solved problem "I" with a greedy approach with O(n2log(n)) complexity.
•  » » » » 3 years ago, # ^ |   +3 My greedy approach for problem I is O(n^2) 21710921 and can be optimized further to O(n*log(n)) using two priority queues.
•  » » » » » 3 years ago, # ^ |   0 Do you care to describe your approach? I always like to see what people's reasoning was for a specific algorithm, beyond just the code :)
•  » » » » » » 3 years ago, # ^ |   +37 Sure, sorry for my bad code. I'll explain how I get my idea step by step: For simplicity lets define F(p,s) as maximum total strength by choosing p programming students and s sport students Immediately, I found very simple DP solution but O((n^3)/6) is surely TLE, so I tried to find if there is greedy approach At this point I think about easy case, for example what is F(p,0), it can obviously be solved by using greedy and sorting. To print the answer easily, I also define A[x]: A[x]=0 if x-th student is not chosen A[x]=1 if x-th student is chosen for programming team A[x]=2 if x-th student is chosen for sport team Next I asked myself if I can easily compute F(p,0) and A[x] for F(p,0) could I find F(p,1) and update A[x] for F(p,1), and if I can could I do it again for F(p,2),F(p,3),... until F(p,s)? Spoiler Alert: the answer is yes; here's how Before continuing let's I define: P(x) is programming strength "skill" of x-th student's S(x) is sport strength "skill" of x-th student's WLOG, I assume we already computed F(p,k) and A[x] for F(p,k) and we want to compute F(p,k+1) and update A[x] Split student to three groups: Group 0: containing x-th student with A[x]=0 Group 1: containing x-th student with A[x]=1 Group 2: containing x-th student with A[x]=2 Let's define C(x) as maximum strength gain if we choose/switch x-th student to sport team Ignore group 2 (because it already in sport team) in my code to ignore group 2 simply set C(x)=0 if x in group 2 because I know that C(x) for x in group 0 will be positive For group 0: C(x) is equal to S(x) because x-th student is unassigned to any team, so adding it to sport team will increase total strength by S(x) For group 1: C(x) is equal to S(x)-P(x)+P(y) because x-th student is already assigned to programming team, if he want to switch to sport team the total strength will change by S(x)-P(x), but at this point we lose one student in programming team, so we must assign y-th student to the team so total strength will increase by P(y) so C(x)=S(x)-P(x)+P(y), how to find y? just greedily find unassigned student (group 0) with largest P(y). In my code I use pointer walk to find y so the complexity in this step is amortized O(1). Done, all cases covered to find C(x) :) F(s,k+1)=F(s,k)+C(z), z is the index such that C(z) will be as large as possible. Formally C(z)>=C(x) for all possible x. If there are multiple z satisfying this condition you can choose any. Now for updating A[z]: if z is in group 0 simply change A[z] to 2 if z is in group 1 change A[z] to 2 and change A[y] to 1. how to find y has been explained before. if z is in group 2 then there's bug in your code or test case is out of constraints, it's simply impossible :) Total complexity is O(n^2), you can optimize it to O(n*log(n)) by using two priority queues one for keeping maximum of S(x) for x in group 0 and one keeping maximum of S(x)-P(x) for x in group 1. Took one full hour to write this, now I feel how hard CF contest author to prepare editorials for 5 to 7 problems. It make me appreciate it even more :)
•  » » » » » » » 3 years ago, # ^ |   0 Oh yeah, it's very hard to write good and intuitive algorithm explanations. And you killed it at this one! It's very much appreciated!
 » 3 years ago, # |   +3 It would be great if someone write a solution outline for this contest. Currently I am stuck on problem A and I will appreciate a hint.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 The best way to lower the points of the player with most points is: Lower him at the same time as other players that have most points.So you need to lower him until there is at least a pair of players with most points and the rest is easy because you can lower all the players with same points at the same time by grouping them in a smart way without ever lowering the player with least points.
 » 3 years ago, # |   -12 Great contest!!!I have a question in problem "I" I found a dp solution with the DP state (position , needed_sportsmen , needed_programmers) but that would give TLE and MLE because it's 3000 * 3000 * 3000I think the solution is dp with some optemization but I couldn't find it can someone give a hint please !!!thanks in advance.:)
•  » » 3 years ago, # ^ |   -13 Why the downvotes I'm only asking for help ???
•  » » » 3 years ago, # ^ |   0
 » 3 years ago, # | ← Rev. 2 →   -21 WTF problem A : Toda 2 ~ Dota 2...
 » 3 years ago, # |   0 What is the expected approach for E?
•  » » 3 years ago, # ^ |   0 simulation
 » 3 years ago, # |   -29 .............................dgdbfhkj
 » 3 years ago, # |   +3 Can anyone prove why greedy works for E? Apparently we just have to consider the teams who will have their score decreased after freezing (call these down teams) and the teams who will have their score increased after freezing (call these up teams), and start unfreezing from the up teams in ascending order of a[i], then unfreeze the down teams in descending order of a[i]. If there are only up teams then unfreezing them in ascending order of a[i] will be the optimal strategy and similarly when there're only down teams. However, why can we consider them seperately when we have both types?
•  » » 3 years ago, # ^ |   +20 If you have two teams, one of which has positive delta and the other one has negative delta, it doesn't matter in what order they are unfrozen. Answer is increased by the same value in both cases. So it's enough to consider positive and negative teams separately.
 » 3 years ago, # |   0 How to solve Problem A (Toda 2)?
 » 3 years ago, # | ← Rev. 3 →   -48 sorry a kid wrote
 » 3 years ago, # | ← Rev. 2 →   0 Don't understand dp solution for problem I on Codeforces (C in the editorial). Assume that sorted students by decreasing of a[i].We have 2d dp[i][j] with states: i — length of prefix we already processed, j — size of people who goes to team A.And we have following dp formula (it is how I see it): dp[i][0] = b[i] dp[i][j] = max(dp[i-1][j] + b[i], dp[i-1][j-1] + a[i]) But it will give correct answer only if total number of students is same as sum number of contestants in both events. In other case we can latter optimize and make swap of people we take. But I don't get what I am doing wrong.Test case where given strategy will not work: 5 2 1 5 5 3 1 1 6 6 3 5 5 
 » 3 years ago, # |   +15 Is there English Editorial/solution sketches available for this contest?