Привет, Codeforces!
12 апреля 2015 года в 19:00 MSK состоится очередной раунд Codeforces Round #298, для участников из второго дивизиона. Участники первого дивизиона приглашаются поучаствовать вне конкурса.
Задачи для раунда подготовили Максим Мещеряков (Neon) и Данил Сагунов (danilka.pro). Надеемся, задачи покажутся вам интересными.
Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon и за идеи некоторых задач. Так же выражаем благодарность Виталию Аксёнову (Aksenov239) за прорешивание задач.
Участникам будет предложено шесть задач и два с половиной часа на их решение.
UPD: Распределение баллов 500-1000-1500-2000-2500-3000
UPD2: Соревнование завершено! Спасибо всем кто участвовал!
UPD3: Поздравляем победителей!
UPD4: Добавлен разбор
Why minus ? When I wrote this comment, scoring system wasn't announced. Also there wasn't even a " scoring system will be announced later " message
I'm not a racist, but just because of your color :D
Is it a new meta on CF to make 2.5 hours rounds?
It should be Dynamic Scoring :)
So , people don't like dynamic scoring??
Every new thing is hated in the beginning :p
:) Good luck
add me, i am blocked
don't mind me : http://codeforces.me/blog/entry/16607
В рассылке написано что продолжительность раунда 2 часа. Кроме авторов и номера раунда иногда нужно менять и продолжительность)
I think it will be a good contest wish succes for every EXPERT
Why only experts??? O_O
They want it ...
XD
i hope you all know who is going to win this round!
Iam sure you are the winner :P
I hope to participate in Round #299 with (div.1) :)
six problems.Time duration 2.5 hours.
Coding Time
yes
There is some issue.. i m always getting wa on pretest 1.. i checked my ans
i m sorry.. it is my mistake.
GLHF guys :)
Sadly Codeforces system seems not working properly as my submission gives wrong ans before starting evaluation :(
i m sorry,, it is my mistake
The statments was very dificult to understand. problems are good but it takes very large time to understand a problem. Agree : +1 Disagree : -1
Disagree -1 XD
It's so clear to me. But I can't solve problems. I'm a noob :(
I will see you soon.......
Every body, Ehsan.poursaeed wants that you give me -1 and give him +1. see his conspiracy. Don't give him +1. but if you like give me -1
The pretest #15 of problem E doesn't have the visited stop list sorted. This costs me 45 minutes :( Was any one affected by this?
I liked the problems :)
How to solve second problem?
It's dynamic programming. DP[current second][last speed]. But I spent a lot of time on understanding the statement.
You don't need the dynamic programming. You just need to run from zero to t and update the speed using greedy approach. Check out my solution.
Exactly. You just need to always increase the speed until it's possible to get to the required final speed in the remaining time.
V increasing while we can decrease V to Vlast
I think this idea in contest,but can't implement.How to implement?
You can see my submission. I used exact this idea :)
print(sum(min(v1 + d * i, v2 + d * (t - i - 1)) for i in range(t)))
increase our speed as fast as we can. Also with decreasing
(can't code without brackets highlighting :( and forget we need sum it, not print :( )
This problem can be solved without using dynammic programming .. just traverse first from left to right and then right to left maintain minimum of both side at each second . sum them up :)
if v1 + (t-1)*d <= v2, we know the best way is to increase the velocity by d every second. Otherwise, the speed would first increase to a top speed, let's say Vmax, then decrease to v2. We can enumerate the top speed Vmax to find the answer.
maintain 2 arrays of size t.
first has first element as v1 and contain maximum speed that can be attained at any time by increasing previous element by d.
second have last element as v2 and contain maximum speed that can is possible at any time by increasing later element by d.
example- if v1=10 and v2=30, t=5 and d=4
array1- 10 14 18 22 26 array2- 14 18 22 26 30
add elements from array1 to answer untill array1[i]<=array2[i], then add elements from array2.
int main(){ int v1,v2; cin >> v1 >> v2; int t,d; cin >> t; cin >> d; int ans=0;
}
i did it without dp.... simply take a array 'A' of size t; A[1]=v1; A[t]=v2;
for<- 2 to t-1 A[i]+=d;
and traverse from back and check if abs(A[i]-A[i+1]>d) make abs exactly d...by changing A[i];
then add all A[i];
thnx, can you give correctness proof?
You can solve it by 2 pointers..
arr[0] = v1; arr[t — 1] = v2; int s = 0, e = t — 1; for (int i = 0; i < t-2; i++) { if (arr[s] <= arr[e]) { arr[s + 1] = arr[s] + d; s++; } else { arr[e — 1] = arr[e] + d; e--; } } ll ans = 0; for (int i = 0; i < t; i++) ans += arr[i];
How to solve D? I think that I got the idea but I had 4 unsuccessful attempts. I know that we have to change the remainders in order 0-1-2-0-1-2-0-1-2-... but maybe I implemented it wrong.
how to solve problem D handshakes ?
Bipartite matching !!
can you please explain the idea ?
let's suppose the entering position are from 0 to n-1...
since a team of 3 can be formed, so in general student with 'i' handshakes can go at positions i,i+3,i+6,i+9... (because additional 3's can form a team resulting in 'i' handshakes).. (make edges correspondingly to form bipartite) so Now the question reduces to bipartite maching of n students with n positions.. :)
Building the graph seems to work in O(N^2) at least for me. Am I missing something?
Yeah, even bipartite matching takes O((n^2)*sqrt(n)) hence ,I think this one will get tle...
I only used DFS for this :) but didn't managed to fix it during the contest
http://codeforces.me/contest/534/submission/10685298
take into account we don't need some of the structures declared... because I changed my mind during the coding and forgot to delete them
My kind of brute-force algorithm couldn't pass pretest 9 but I think the idea is correct.
Store the people in an array of vector, where vector v[i] stores people shaking hands with i people, initialise current index of all vector to 0.
Now start from 0, if current index of v[0] is less than v[0].size(), it means there is a person that can enter now.add this person to solution vector, increment 0 to 1 and repeat.
If, current index becomes >= v[i].size(), then check for current index that are possible, eg. for i=7, other states possible are 7-3=4, 4-3=1 and so on.If you cant find any valid state that has current index < v[i].size(), break out of loop.
Edit: The idea is correct.It passed the system test after removing a stupid bug.
We only need to simulate the whole thing. But, we postpone groupings as late as possible.
Let's say there is X ungrouped people and next one comes. First check if there is exists (remain) a person who shake hands with X people. If yes, allow him to shake hands with X people and add 1 to current no of ungrouped people.
If not, form a group and try again, no of hand shakes becomes
X = X - 3
. Repeat if necessary. If ultimately not possible because there is not enough people to form groups anymore, outputImpossible
.D solution:
Simple greedy: take the largest numbers first, e.g. 0 1 2 3 4 5 6 7, 5 6, 2 3 4, 0 1 2.
Ok, How is about 0 1 2 3, 0 1 2 ?
Oh, I understand. You try to increase number of people at first.
I solved with greedy :D
200000 stack
If in Problem 'A' n=4 testcase was not included in pretests, no. of hacks could be more!!
Тест 68 — очень хороший. Несколько TL по D, несколько WA по E, несколько TL по F.
I see several people, including me, failed on system test 50 for problem C. Any idea what it may have been?
Your A must be define as a long long... I have hacked 9 people like you :)
but there written n,A <= 2·10^5, in test 50 A is 99964566758, am I misunderstand something?
n ≤ A ≤ s , not 2 × 105
I have changed all variables to long long, except n, A((. thanks
I think A is not necessary to take as long long, rather sum in his case. Thanks. :)
You have declared sum as int, but if I give you 200000 times 1000000 as d? Then the power goes to 11. Thanks. :)
Заполним бесконечный массив следующим образом: 0 1 2 ... N-1 N N-1 ... 1 0 1 ...
Можно ли в этом массиве выделить два отрезка длины M, сумма элементов на которых будет равна, но отрезки будут состоять из разных элементов?
Ответ: нет.
P.S. Не стоит жадничать на константы от которых не сильно изменяется время работы программы, но при этом может упасть решение.
I have done 4 problems and in my view, the difficulty level was C,D,A,B. Problem B just ruined my contest. -_- However, I have enjoyed the problem D very much. Thanks to the Almighty, thanks to the problem setters, thanks to all. :)
Ну вот как не сказать... Задачи просто КЛАСС...!!! Огромное спасибо авторам.
Can somebody explain why http://codeforces.me/contest/534/submission/10677423 submission passed test case no 50. The coder in the above solution has used int type for all the values and is still successfully dealing with large inputs. HOW? Costed me a unsuccessful hacking attempt.
X + Y — Y would always result in X even if overflow occurs.
As you can see in case 50 the answers are equal to the input.
Впервые написал решение задачи D
@
Упало по времени — больше 1000ms
@
Меняешь vector на массив и cout на printf
@
AC за 124ms
10685565
я думал ну совсем все знают что делать...
В решении с ТЛ ты удаляешь из начала вектора. erase() работает за O(N).
Это же решение только будем удалять из конца вектора, а не из начала.
А у меня вот нет Erase, но все равно TL :) Не подскажешь, почему? http://codeforces.me/contest/534/submission/10681843
Вместо подсчета cnt нужно выпрыгивать из цикла сразу как не получилось найти следующего студента. Иначе на тесте скажем 0 1 ... 99999 0 0 0 0 0 0 ... 0 будет с 99999 пробегать до 0 на каждый 0 в списке (за квадрат).
PS: у вектора есть метод .back() ;)
Да, язык не причем, косяк исключительно алгоритмичекий, спасибо сенсей! :)
И за back спасибо :) я в плюсах нуб, вот-вот с паскаля перешел :))
У меня в решении по E достаточно было изменить
3
на4
и WA68 превратилось в AC.UPD: Хотя то что решение заходит при
4
— это из-за слабых тестов. Моё решение бы упало при N = 200000, M < N / 2, и более менее нормальных остальных значениях.Где разбор. Вот не понимаю этого отношения к делу в принципе. Неужели так трудно написать разбор до раунда?
Вокруг есть добрые люди, которые могут объяснить задачу по лучше всякого разбора, если их вежливо об этом попросить.
Вы, видимо, совсем не поняли, о чём я написал.
Я понял. Но хороший разбор задач — это не только описание идеи решения, это еще и анализ решений, посланных во время контеста. Авторы задач не всегда знают все способы решения собственных задач. Во время проведения онсайт соревнований на разборе часто можно услышать "несколько команд пытались вот такое заслать и у кого-то даже получилось" или "одна команда нашла более простое решение, чем авторское". Но так как у нас онлайн соревнование и проанализировать посылки всех участников невозможно, то в разборе скорее просто может быть упомянуты идеи решений отличных от авторского.
Nice problem set can't wait to see tutorial of D
Is something with std::set solution wrong or just mine is incorrect (why?)? I got TLE on test #46 ;-; http://codeforces.me/contest/534/submission/10685572
you used std::lower_bound, which has linear complexity
use set::lower_bound and you get AC: 10685831
use
s.lower_bound(x)
instead oflower_bound(s.begin(), s.end(), x)
This have been discussed many many many times in Codeforces
Thank you so much :)
Could you refer me a blog where this has been discussed?
I've seen this discussion couple of times on similar situation: some guys ask why his solution fail, another reply that
lower_bound(s.begin(), s.end(), x)
has linear complexity. But it's hard to find comments, so I can't give you links.I couldn't find anything on google search as well.Maybe we can formalise it here. So what it means is that lower_bound(), upper_bound() have linear complexity(I highly doubt that) but s.lower_bound(x) has O(logn). But I have passed programs having O(n*logn) with n<=10^6 using lower_bound().If lower_bound() is linear then complexity would have been O(n^2) (impossible to pass).Is this valid for set only or is it true for vector, array also?Is its complexity based on array configuration or what?
And one more thing, as far as I know c++ stl is highly optimised. So how come lower_bound() is linear, because I sure can implement this in O(logn)?
I'm pretty sure
lower_bound()
is O(log) for vector and array (but of course it is assumed that the vector/array is sorted).The thing with
lower_bound()
onset
is that, you do not have random access in O(1), so probably it was implemented in a way that makes it O(N). I think it is stupid design of this C++ STL that allows people to use the library wrongly like that.I have a TLE on system tests, but I used 3 smaller multimaps(each element only in one multimap, depending on shakes[i]%3 and I cycled between them) and used insert, lower_bound ( s.lower_bound) , erase, empty operations. What could go wrong? Isn`t is supposed to be N*log N solution? Or is it not good enough? http://codeforces.me/contest/534/submission/10675989
You gave link to another solution.
For your D, it looks like good, but it gets TL on N=113 which is weird. I ran your solution locally and it spits error in free(). I guess it's because you access myit while lower_bound can return a.end() (so myit does not point to an element) and then you erase myit -> undefined behaviour. Very strange it gets TL on CF...
Add check myit != a.end() and I hope it will pass.
Thank you. Changing one of "Impossible" conditions from (a.empty()) to (myit == a.end()) helped. It was my first time using map, I will watch out for it in future.
Хорошие задачи, спасибо авторам за раунд! Но дорешивание то откройте=)
فارسی زبونا همیات کنین
Why this solution gives WA for problem-B? Plz, help me--> 10682655
When calculating DP you are setting your initial ret value to be 0. However, your recursive call can return you negative infinity, because there is no solution. Since you update ret to be a max of a previous ret value i+get(...), you lose that information. So for a state that doesn't lead anywhere, you will return 0, which is wrong. As a result, when the correct solution is 1+2+3+4+5+6+5+3+2+1, your program can do 1+2+3+4+5+6+7+8+9+0 (10 can't reach 1, so we use 0).
Change line 50 from
ret=0LL;
toret=-inf;
and you'll get an AC :)Good luck!
D:Different teams could start writing contest at different times. the number of student -3 or -3*t(t=1.2...) it take me long time to understand the problem
Where can I find the rules for the scoring? Thanks in advance.
Thanks for the problems. It was a great contest with very nice problems.
Can someone explain why my code for C TLEd? http://codeforces.me/contest/534/submission/10682828 Shouldn't it be O(n)? Or do you need to somehow print more efficiently?
As far as I can tell you just need to switch to faster i/o methods.
Scanner.nextInt
andScanner.nextLong()
is REALLY slow. You should useInteger.parseInt(sc.next())
andLong.parseLong(sc.next())
.If it is not sufficient, you must implement method to parse integer.
:\ :\
For problem A — Exam why is the following output wrong for input 6?
6 Output 5 2 4 1 3 6 Answer 6 5 3 1 6 4 2 Checker Log wrong answer Jury has better result: 6>5
Because 6>5, as it says.
Found the mistake. And it's silly!
Мне кажется, в задаче F довольно слабые тесты. Удивился, что у меня решение отработало всего за 140мс, решил посмотреть тесты. Во-первых, вероятно, для некоторых решений самым сложным тестом будет:
но этого теста нету в тестсете. Во-вторых, там вообще нет тестов, где a[i]=10, а такой тест может не только быть сложным по времени, но и отследить некоторые ошибки (например, использование десятичной системы счисления для хранения состояния массива a[i]). Думаю, надо подобные тесты добавить хотя бы в дорешивание.
UPD: авторы добавили 3 теста с подобными числами, спасибо!
А как ее вообще решать?
Я написал какой-то перебор с запоминанием и тупыми отсечениями (если уже поставили слишком много/мало групп, выходим) и получил TL. Неужто выпиливание векторов правда все ускорит?
Я писал ленивую динамику с состоянием из трех чисел bool D(Col,Mask,Val) — True, если мы можем расставить клетки, начиная со столбца Col, в предыдущем столбце мы закрасили клетки, соответствующие значению Mask (по одному биту на клетку, итого, максимум 2^N значений), а в строчке i мы должны создать еще C[i] групп, где C[i] — i-я цифра в разложении Val в системе счисления по основанию 11 (т.е. Val соответствует массиву из N чисел). Соответственно, перебираем, какую маску поставим в текущий столбец (неплохо бы заранее посчитать, какие маски для него подходят, т.е. соответствуют значению b[i]), пересчитываем Val (если начали новую группу черных клеток в строке) и переходим к Col+1. Итого, M*2^N*(M/2+1)^N состояний и пересчет за 2^N*N. Получается огромное число (порядка 1.6*10^10), но, во-первых, не все маски подходят под b[i], во-вторых, за счет "ленивости" динамики куча состояний не обрабатывается, в-третьих, гарантируется, что ответ существует, поэтому можно надеяться, что он найдется намного раньше, чем мы пройдемся по всем состояниям.
Думаю, если вместо одного числа (Val) использовать вектор, да еще и состояния хранить в Map, например, то такое решение получит TLE.
Да, я так и делал и получил TL :)
У меня такое же решение. С одним отсечением, когда количество блоков уже больше чем надо, не прошло (TL). Добавил отсечение, когда блоков слишком мало (а можем добавить не более (W-x)/2+1 где W-ширина, а x — текущая ячейка) — зашло за 436мс.
Только я не очень понял что значит "ленивая" динамика, я проходился слева направо, обсчитывая все неотсеченные состояния (т.е. решение не найдется раньше чем дойду до конца).
Под "ленивой" я имел ввиду следующий подход: сначала вызовем функцию поиска ответа для начального состояния (столбец 0, маска 0, значение Val соответствует изначальному массиву a[i]), потом находим все возможные переходы в (P+1,Col',Val') и рекурсивно вызываем функцию поиска ответа для этих состояний. Тогда мы обработаем только те состояния, до которых можно добраться из начального.
Удивительно, насколько изменится время работы, поменяв мапу на массив и вектор на число. Если раньше всё это у меня падало на 16 претесте, то сейчас зашло за 31 мс (+ если уже не сможем в строке добавить оставшиеся группы — выходим).
When will the editorial be published?
Is there a problem with submitting? Why can't I submit now?
Edit: It is fix.
I seem to be getting TLE on case #72 of problem D: Handshakes. I am using a Hashmap<Integer, ArrayList> which stores the keys as hand shakes and indexes of people in the arraylist. Code runs perfectly. Its based on the same idea as @_spartan has written. Any optimizations?
Edit: As hellman1908 suggested, the complexity increases. So i changes the ArrayList to a Stack since the order does not matter and VOILA, AC :D
http://codeforces.me/contest/534/submission/10687311
You remove elements from the beginning of it. In ArrayList I guess it's O(n) so total complexity is O(n2). Remove last element and it will pass
Is there any editorial links for the contest? sorry if I missed one thanks :)
How to solve Problem 'A'?
What is Logic behind it?
Adjacent elements should differ by at least two, so if you enumerate first the odd numbers and then the even numbers you have a correct solution. For example, n = 5: 1 3 5 2 4
This algorithm doesn't work when n < 5. In these cases, solve it on paper and hardcode into your source.
it is actually works n < 5 except the fourth :)
n = 2 (1, 2), n = 3 (1, 3, 2) does not work also.
where i can read analysis ??
My accepted solution for Problem — 'C' used binary search: http://codeforces.me/contest/534/submission/10684361. As far as I can see, no one else had used binary search to solve this problem. I am not able to digest this. What obvious thing am I missing?
Probably you would do better if you think the problem in two cases: + when all the other dices do their best + when all the other dices do their worst (summing 1 each)
this give you a range of points you need on the a_i dice you are working on (once at a time), and of course tells you the amount of points (or faces on the dice) that you will never see to accomplish A points.
Hope this helps http://codeforces.me/contest/534/submission/10679438
I applied exactly the same concept as you are mentioning, if you look into my code, it's doing the same thing — finding minVals for all dices and then maxVals for all dices.
To get those minVals (and maxVals), I have used binary search (and you are saying that the minVals would simply be 1 for each die). Can there not be a case when the minVal for a die be more than 1? (I could not come up with a proof that there cannot be such a case. If someone has any, then please let me know.) To be certain of the correct answer, I used binary search to get the minimum values for each die and then the maximum values..
think about this example
1 8 9
I hope I am getting your point, but if you are asking for a counter example where the lower value a dice MUST have this is the easiest case, obviously your lower value is 8, so your upper value, giving you 8-8+1 possible valid dice' faces (thus 9-valid = 8 not used faces).
you did the same job as others! but your time complexity is O(log(n)) and other's is O(1)
:D
Great round, I like how many variants people wrote to solve problem D, really creative.
In case of Problem-B it is given "the absolute value of difference of speeds between any two adjacent seconds doesn't exceed d."
and this also " Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by d meters per second in absolute value "
so for first case is it also possible that speed will be constant after 2 second I mean 5+6+6+6=23 2nd second value change by 1 and after that speed not change could be answar
Am I wrong?
You are right, but the task wants you to output maximum possible value, and your 23 is certainly less than correct 26.
Ok I got it "maximum possible value"
I missed this phrase
How to solve the problem F? Who can help me ?
Notice that in a given row there can be maximum of 10 blocks (because we have at most 20 columns, and each block must be separated from next and previous block by at least one free cell). Also notice that we can encode any tiling by m integers as bitmasks (so that 0-th bit of every integer gives us the first row, 1-st bit gives second row, and so on) up to 25.
Given that, let's do dynamic programming: dp[num_placed][r1][r2][r3][r4][r5][last] = true or false. It means, that we've already filled num_placed leftmost columns, and we must build r1 more blocks in first row, r2 more blocks in second row, ..., r5 more blocks in the fifth row; and last is the bitmask of last placed column. Let's estimate number of states: 21 * 115 * 32 = 108. Not all possible states are reachable.
Instead of doing dp, I've made a backtracking, because it effectively visits all reachable states, with memoization it is done only once, and with some heuristics (for example, if we must place 5 blocks in some row and there are only 3 columns left, we can say 'goodbye' to this state immediately) it works even faster.
But if you prefer dp approach, the main observation here is to encode [r1][r2][r3][r4][r5] as a single integer in numeral system base 11 (because each ri have possible values from 0 to 10), that makes coding more convenient.
oh!Thank you very much.Your analysis is so distinct.And the search with memoization is more convenient to write.
In case of Problem-C
for the case 2 3
2 3
will not answar be 1,1
instead of 0,1 If second dice could not show 3 then this condition also apply for 1st dice too can't show 3 also?
I think then s=d1+d2+d3...dn condition will not satisfy
1st dice cannot show 3 by definition: d1 = 2, so it can only show 1 or 2 (but not 3, 4, 5 or any greater value).
by mean defination you mean this line?
"s = d1 + d2 + ... + dn."
No, I mean second sentence from the problem: "The i-th dice shows numbers from 1 to di".
Tutorial ?!
What was this word "Tutorial"?
Let's hope that the author haven't posted it yet because he wants to make it more understandable and detailed :)
Please anyone tell me , why this solution for problem-D is WA on test-9 ? Isn't it a correct order ?.. Sol:-> 10692139
No, it isn't a correct order because if 2 shakes hands with 0 guys, then 7 will shake hands with 1 guy instead of 4 guys :)
Think Problem A pretests without test 5 -> Hacksss :)))
In problem 534D - Рукопожатия my code got AC 10687529 but when I try this test case : 5 0 1 2 0 4 it says Impossible but I think it should be possible with answer 1 2 3 4 5
How come?!!!!!!!
My code in problem 534D - Handshakes got AC 10687529 but when I try the test case n=5 - [0 1 2 0 4] it's output is Impossible but it should be possible 1 2 3 4 5 How come?!!!!!!
No, it is impossible. If 4 handshakes with nobody, then 5 could not handshakes with 4 people. "At any time any three students could join together and start participating in a team contest, which lasted until the end of the day. " "so when another student came in and greeted those who were present, he did not shake hands with the members of the contest writing team." You assume the 1 2 3 formed a team so 4 handshakes with nobody then 5 can only handshakes with 4. So it is impossible. Sorry for my bad English
I was misunderstand this part of the problem.. thanks :)
If the 4th person shook hands with 0 people, how could the 5th person shake hands with 4 people?
The answer is indeed Impossible.
where are the editorials
Please publish the editorials for the round!!
Ребят, подскажите идею для E. Есть мысль пытаться каким то волшебным образом определять для каждой станции, может ли она быть начальной/конечной, но эта мысль мне как-то не особо нравится
А по-моему, это хорошая идея. Стоит лишь заметить, что тип точки (начальная/конечная) не так важен. Пусть все такие
'волшебные'
точки будут начальными, остается перебрать лишь направление движения на старте.Теперь нужно всего лишь написать функцию, которая проверяет совпадает ли путь для заданной стартовой вершины и направления с путем, указанным во входных данных. Эта функция также может попутно считать длину пути. Вышеуказанную функцию можно реализовать за
O(N)
.Остается лишь заметить, что
'волшебных'
точек лишьO(1)
.How to solve Problem-D
I mean from where I should start?
First,You should count a[i]. a[i] is the number of students who shook hands i times. We define cur .cur is the number of student who we can shake hands with now. In the beginning cur=0.
if a[cur] > 0 , it tells us we can add a student who will shake hands cur times in the permutation.And than
a[cur]--
(because we use a person)else cur-=3 (3 student start writing a contest) until (cur<3 or a[cur]>0)..
2.1 if (a[cur]>0) is same as 1.
2.2 cur < 3 it means the sought order of students doesn't exist.
My english is very poor. You can see my code 10681578..I hope you can deal with it!
Can you explain why this solution works?
Sorry,I can't prove it.
Here is the editorial, but for some reason it is not attached to the contest
Sorry,wrong contest.
hello I am tired , trying D problem
someone can help me !!!!! why does it give me runtime error on case 46 ??? 10733747
that is my code
thanks for advance everyone
10734329
thanks you!!! but could you explain me ?? what happen ??
current = (*it).first; s[where].erase(it);
why it doesn't equals to
s[where].erase(it); current = (*it).first;
You erase
it
and after you use invalidated memoryI get it. thanks you !!!
Спасибо за раунд, он мне очень понравился