Добро пожаловать на 2016-2017 CT S03E04: Codeforces Trainings Season 3 Episode 4. Продолжительность тренировки — 4 часа 30 минут. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.
Перейдите в раздел Тренировки для регистрации и участия.
Ориентировочный старт: 28 сентября 2016 г., 16:10 (Московское время).
Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.
Условия задач будут на английском языке, ведь мы же готовимся к ACM-ICPC!
Удачи!
How can I participate?
Visit Codeforces::Gym to find the contest and register.
I visited Gym but where should I click for registration?
The registration is open now
Can a team have more than 3 people?
team members can be more than 3 people but during the contest at most three of them can register in the team
Will there be any editorial after the contest ?
Will be there any editorial for all of these gyms (ACM preparation)? It is sometimes difficult to find proper solutions for some problems and having some editorials may help DIV2 participants a lot.
i disagree with (eat, sleep, code)
we don't come to this world just for this because there is one day which we will leave this world in that day.
The worst comment ever !! congratulations by the way !
salam
i said truth
not anything more
we don't come to this world just for(eat, sleep, code)
i don't think it is horrible.
i think that death is beautiful because i believe that there is another world after death
(i must eat, i must sleep, i must code) and i want to become red but (eat, sleep, code) isn't every thing for me.
You risk to leave this world and do not know what sarcasm means.
mike said his belief and i said my belief
if i made a mistake then mike made a mistake too.
The statements were horrible !!
My solution for F is, define nodes Dij ( ith door at j seconds ) and find Maximum bipartite matching between people and D (with Hopcroft-Karp). But I can't get accepted( at another Online Judge. I didn't try in this site ) Why is it wrong?
I solved it additionally with binary search. thanks
I was trying to solve it with a binary search and max flow but the result is TLE in test 2
How to solve L and J?
L: Use Dijkstra's algorithm to find shortest distance from start to each vertex. Then use DP[vertex][0 or 1] — number of shortest paths to this vertex or unit longer.
J: "Meet in the middle". You have about ((n^3)/6)^2 variants to make two or less transpositions. You can get all these variants for initial and sorted array. Then you can find the same arrays in these two sets. You can compare hashs of arrays.
Could you please tell how the answer to 2nd test case in J is 3 ?
I have tried many possibilities and still getting 4
5 4 3 2 1 -> 3 2 5 4 1 -> 3 4 1 2 5 -> 1 2 3 4 5
Could you elaborate a little bit more about dp in L, please? I tried to find every minimal distance from starting vertex and to ending one. Then I build a graph only of edges that lie on paths of minimal weight and minimal + 1. And from this data do dp like this:
If there are paths of minimal weight through current edge (v, u) then dp[u][0] += dp[v][0], dp[u][1] += dp[v][1]. And if every path through the edge is of weight minimal + 1 then I have no idea how to recalc dp.
It's simply dp[u][1] += dp[v][0] (right?)
If so then what to keep as dp state? I was about to save number of min and min+1 weighted paths from last to current (by doing dfs). If you push only min+1 paths then you lose nearly all of previous paths, don't you?
I wrote something like this but it's not working at all, obviously.
Though making dp[u][1] += dp[v][0] and dp[v][1] += dp[u][1] (second only in case it's not (v, u) edge that makes path of weight min+1) helps me pass tests like this.
How to solve G?
Can someone please help me with the solution to E?