Уже сегодня состоится четвертьфинал ACM-ICPC в Саратове. От лица жюри и организаторов желаю командам порадовать своих тренеров и руководителей. У вас всё получится!
Наблюдать за текущими результатами соревнования можно будет по ссылке https://contest.sgu.ru/monitor/1.
А уже в воскресенье (23-го октября) в 11:00 здесь состоится неофициальная трансляция прошедшего соревнования. Вас ждут интересные задачи, которые жюри постаралось сделать интересными как для начинающих, так и опытных участников. К участию приглашаются как команды из 1-3 человек, так и индивидуальные участники. Контест не будет влиять на рейтинг Codeforces.
Конечно, контест будет нерейтинговым. Рекомендуется командное участие. Скорее всего, позже он будет перенесен в Тренировки.
Председатель жюри MikeMirzayanov.
Т.е. задачи сегодня во время соревнований нельзя будет посмотреть?
Если вы находитесь в Саратове и являетесь тренером/руководителем команды, то задачи вам раздадим в печатном виде. Иначе получить доступ к задачам по время соревнования, увы, не выйдет.
До трансляции в электронном виде распространять не стоит. Потом — пожалуйста.
Эх... придётся идти за валидолом в аптеку.
Good luck for all!
Deleted!
Не знаю, на каком уровне произошла опечатка (baylor, локальная регистрация, заполнение базы вручную), но в таблице есть "Belgorog State U #1".
А в чем ошибка? Действительно есть команда Белгородского государственного университета.
Последняя буква g вместо d
Желаю участникам!
Так себе пожелание)
Fixed
it's not a hard contest for an IOI man like me =))
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?
Разбор задач: https://www.youtube.com/playlist?list=PLSqW9Jap9R88u6Yoch5XhlMmUmm1PvZlt
Ставьте лайки, подписывайтесь на канал.
Блин, круто! Вот такие должны быть разборы у каждого контеста =)
Порезала по задаче https://www.youtube.com/playlist?list=PLYOhi118RAVDSxLf3J9oMIuurR49nQsjW
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 choosingpprogramming students andssport 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]=0if x-th student is not chosenA[x]=1if x-th student is chosen for programming teamA[x]=2if 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]=0A[x]=1A[x]=2Let'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)=0ifxin group 2 because I know thatC(x)forxin 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),zis the index such thatC(z)will be as large as possible. Formally C(z)>=C(x) for all possiblex. If there are multiplezsatisfying this condition you can choose any.Now for updating
A[z]:zis in group 0 simply changeA[z]to2zis in group 1 changeA[z]to2and changeA[y]to1. how to findyhas been explained before.zis 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)forxin group 0 and one keeping maximum ofS(x)-P(x)forxin 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.
People didn't get AC 7 problems must be mentally retarded :))
People didn't get AC full must be mentally retarded =))
I want to ask something about the complexity of the min cost max flow it runs so fast
O(N^2 logN).
Because you need to run Dijkstra's algorithm N times, and the number of edges in the graph is O(N).
And it's russian thread.
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)?