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!
MikeMirzayanov, head of judges.
Good luck for all!
Deleted!
Good luck to all especially CF users who are participating in NEERC. make us proud :3
they'll make you be sure of that :3
There seems to be a typo on the contests page; the contest tomorrow is named "2015-2016 ..." instead of "2016-2017 ...".
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.
But is it rated? Edit: I was joking, please don't downvote me.
Contest clashes with Code Festival.
Are problems going to be shuffled since we can see the results?
Yes
Great contest! Is there something like official slides with solution outlines? I remember those are available for other ICPC contests like NWERC.
+1. Would appreciate if there's any editorial for this contest esp. for problem F, K, and L (which are quite "untouched" by contestants).
Here is all problem analysis in youtube (in russian but you can activate subtitle and select translate to english):
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
> . < I meant to upvote because I had the same experience but I accidentally clicked downvote instead, sorry.
For Problem D, with this input :
5 2 10 5 4 1 7 14 10 12 4 10
Why this output is considered as wrong answer? 5 8 10 12 46 48
while jury's solution is
5 8 10 12 40 42
i think it is possible for my solution.
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?
How did some people pass I with min cost flow? Wouldn't it TLE with these constraints?
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
What is the expected approach for I?
we solved problem "I" with a greedy approach with O(n2log(n)) complexity.
code: http://codeforces.net/contest/730/submission/21712213
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.
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 :)
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 choosingp
programming students ands
sport studentsImmediately, I found very simple DP solution but
O((n^3)/6)
is surely TLE, so I tried to find if there is greedy approachAt 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 chosenA[x]=1
if x-th student is chosen for programming teamA[x]=2
if x-th student is chosen for sport teamNext I asked myself if I can easily compute
F(p,0)
andA[x]
forF(p,0)
could I findF(p,1)
and updateA[x]
forF(p,1)
, and if I can could I do it again forF(p,2),F(p,3),...
untilF(p,s)
?Before continuing let's I define:
P(x)
is programming strength "skill" of x-th student'sS(x)
is sport strength "skill" of x-th student'sWLOG, I assume we already computed
F(p,k)
andA[x]
forF(p,k)
and we want to computeF(p,k+1)
and updateA[x]
Split student to three groups:
A[x]=0
A[x]=1
A[x]=2
Let's define
C(x)
as maximum strength gain if we choose/switch x-th student to sport teamIgnore group 2 (because it already in sport team) in my code to ignore group 2 simply set
C(x)=0
ifx
in group 2 because I know thatC(x)
forx
in group 0 will be positiveFor group 0:
C(x)
is equal toS(x)
because x-th student is unassigned to any team, so adding it to sport team will increase total strength byS(x)
For group 1:
C(x)
is equal toS(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 byS(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 byP(y)
soC(x)=S(x)-P(x)+P(y)
, how to findy
? just greedily find unassigned student (group 0) with largestP(y)
. In my code I use pointer walk to find y so the complexity in this step is amortizedO(1)
.Done, all cases covered to find
C(x)
:)F(s,k+1)=F(s,k)+C(z)
,z
is the index such thatC(z)
will be as large as possible. Formally C(z)>=C(x) for all possiblex
. If there are multiplez
satisfying this condition you can choose any.Now for updating
A[z]
:z
is in group 0 simply changeA[z]
to2
z
is in group 1 changeA[z]
to2
and changeA[y]
to1
. how to findy
has been explained before.z
is in group 2 then there's bug in your code or test case is out of constraints, it's simply impossible :)O(n^2)
, you can optimize it toO(n*log(n))
by using two priority queues one for keeping maximum ofS(x)
forx
in group 0 and one keeping maximum ofS(x)-P(x)
forx
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 :)
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!
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.
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.
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 * 3000
I think the solution is dp with some optemization but I couldn't find it can someone give a hint please !!!
thanks in advance.
:)
Why the downvotes I'm only asking for help ???
WTF problem A : Toda 2 ~ Dota 2...
What is the expected approach for E?
simulation
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?
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.
How to solve Problem A (Toda 2)?
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):
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:
Is there English Editorial/solution sketches available for this contest?
How to solve J (Bottles)?