Доброго времени суток)
Приглашаем вас на последний раунд в уходящем году Good Bye 2013. Этот раунд будет не совсем обычным, потому что он будет общим для участников из обоих дивизионов.
Задачи для вас готовили авторы Геральд Агапов (Gerald) и Свечников Артур (ikar). А также, в проведении раунда нам помогал Павел Холкин (HolkinPV). Также говорим спасибо Виталию Аксенову (Aksenov239) за помощь. Традиционно хочется сказать слова благодарности Михаилу Мирзаянову (MikeMirzayanov) за системы Codeforces и Polygon, а также Марии Беловой (Delinur), которая перевела условия задач.
UPD: Распределение баллов по задачам похоже на стандартное — 500-1000-1500-2000-2500-3000-3500
UPD2: Спасибо всем кто принял участие, надеемся что всем понравились подготовленные задачи. Разбор.
UPD3: Поздравляем победителей последнего раунда в этом году. Рейтинг будет обновлен в течение нескольких часов.
1. BaconLi
2. Egor
3. liympanda
Желаем всем участникам удачи, высокого рейтинга и удовольствия от решения задач)
2013, давай, до свидания! :)
Is there a handle changing feature?
No, you can only choose the handle name when you register, then you will not be able to change it later.
Maybe you misunderstand him, usually at the end of every year there's a gift from codeforces to its users, last two years it was allowing to change the handle and ahmed.korayyem asked if codeforces will allow changing handle this year too.
BTW, why are you surfing codeforces in incognito mode?
Oh, sorry for my misunderstanding.
Actually I use normal mode when surfing on codeforces, but when I want to visit codeforces "register" page without logout I have two options, open other browser software or use incognito mode, but it's faster to use incognito mode, so I use it :)
Actually it happened last year. (http://codeforces.com/blog/entry/6290)
I would like to change my handle this year too as a Codeforces gift.
Hello, but gifts are things other people give to you. They are not things you request, and then get.
I mean, I could be happy if I see a Mike post saying: "You can change this year your handle as a Codeforce gift like last year. Enjoy it."
It seems this contest would be rate?
Yes, for both the divisions.
Although have lessons tomorrow morning, going to take the one of the most important contest:) That's why I love Codeforces!
Just want to get a good ending for this year.
ahh... at last a post about 'Good Bye 2013'.
will the problems be as hard as div2 contest or div1 contests?
happy new year to all ... last contest of this year ..... so get highest rating .. wish u all the best for all
Good luck!!!
Advanced Happy New Year to everyone :)
Can we have hints on problems' difficulty? I can't imagine how the contest is going to be rated and the same problems will be for both divisions!
Good Luck to everyone...!!! And Happy New Year...!!!!!
how many problems there will be??and i think as the contest for the end it would be better to have extra duration.
много участников!!!КРУТО!!!
Остается надеяться что CF устоит при таком нагрузочном тестировании.
Well, actually it's good bye GPA! Having an exam tomorrow out of 30% and I still don't know what the course is all about and yet I'm taking part in this contest :D :D
Me Too :D
LOL :D :D
Me Too :D
why BaconLi got +25 and xa.mohsen got +2 only with same comment????? ( ! )
I have got GPA of 4.
like a boss.
Good for you :D Mine is 3.66 but it will drop like hell after this semester :D :D
Hey guys ... as 2013 is ending , i wanted to start a fresh new year training on problems , i aslo have some questions on this , so if anyone would answer me , and gimme some help .. I'd appreciate this :) And Happy New Year everyone :D Happy Coding ... :D
GL HF everybody :D Happy New Year 2014
Also, good fun && have luck!
I never really understand why the score distribution is announced during the last minutes before the contest? Can somebody explain me this? :)
One million dollar question !
For this contest, obviously to hide the fact that there are 7 problems instead of 5 :3
"Score distribution will be announced before the contest."
contest starts in 30 seconds!
Happy new Year! Good luck in new year!
Уж можно было подождать до конца контеста :o
Будет ли разбор?
Can anyone tell how solve 379F - New Year Tree ?!
http://codeforces.com/blog/entry/8929#comment-146418
Should we check every most distant from the root vertex?
I think this is a old problem, as you can find it here http://www.codechef.com/COOK38/problems/RRTREE ( Editorial in this link too)
I enjoed the contest, but the problem F is really well-known.
UPD: english one take a look at problem H
And problem A is from Codeforces Gyms (2013-2014 CT S01E01, problem J)
Well, I can excuse Div2-A =)
On problem C I made this:
while (vet[u] <= l) ++vet[u];I realized that it would time out after locking :/, but then I remembered that GCC might optimize this stupid mistake I've made, and it did! :D Bye bye 2013!!
Holy random? I successfully hacked person with
while(v[i].a<=v[i-1].a) v[i].a++;and g++ too:)I failed to hack someone's code that had a similar loop and I was wondering how did his code pass! Now I've got the answer!!!
can u please expain what is wrong in this loop ?
Simulate the code with this test:
Good bye
Codeforces Roundfor this year...Insha'allah... we will meet again... :)
Спасибо за раунд!
Посылал исправление по E за 6 секунд до конца контеста. Сервер сработал — включилась страница "Мои посылки". Однако там ничего нового не было. Допуская, что я опоздал, это какой-то баг (и я должен был видеть эту посылку с вердиктом out of contest), или это так и надо, что посылка как бы не существовала вообще?
We get "Happy New Year!" instead of "Accepted". So nice!
At first, thanks for this great contest! I enjoyed it very much except for one thing.
Because of "Codeforces is temporary unavailable", I lost some hack points that I should be able to get... Although it's my fault that I came up with a powerful corner-case late, but why codeforces server have been weak for a long time in spite of much demand? I really want codeforces team to strengthen the server...
Any better idea on D than a hardcore DP + Euclid's Extended Algorithm (which i didn't manage to implement, by the way).
My solution was something like this:
Let X = s1, Y = s2. We count the number of appearances of X, Y, XY, YX, YY (you can prove that XX doesn't appear). In the latter three, at most one "AC" can appear, so you bruteforce all 8 possibilities. You don't need Extended Euclidean; the bounds n, m ≤ 100 are very forgiving for an immediate brute force.
(I'm not sure what you mean by hardcore DP. In my opinion, my solution above is not DP at all, so probably different solutions.)
(My solution turns out to fail, so it might not be the correct approach. Take the above with loads of salt.)
WA 23?
I have the same solution and got wa 23 : \
You must prevent overflow while calculating count of AC's in tested variant.
No, your solution seems ok, I simply missed the fact that I can brute-force through all cases in ax+by=x, your solution was the same as mine. What i called hardcore DP were some recurences I used instead of simple formulas to write the solution faster in order to calculate the number of X,Y,XY,YX,YY,XX (that's why I used DP, I didn't have to treat cases like nu XX and different formulas). Somebody else also told me about this solution and his also failed because of www.wolframalpha.com/input/?i=50th+fibonacci+number (int instead of long long)
Yes it is correct.
AC sol: http://codeforces.com/contest/379/submission/5585945
note, I for some reason also take into account XX, YY :|
how to prove it?
My solution has a recursion to calculate the how many AC are in kth term, inside a dp that generates a possible second starting string, inside another dp that generates a possible first string. Is that hardcore enough? :p
Yes, it is. Your recursion used memoisation I supose? Can you explain a little bit more of your solution, please?
Well, at first I thought knowing the number of AC in each of the first string would be enough. If no. of AC in first is 3 and in second is 4, then the third will have 3+4 = 7. Then it will continue like fibonacci sequence. But then I realized, what if the string is like this ABBBBBA and CBBBBC.
Even though the first and second string has count zero, third string has count 1. So, in order to generate the sequence, I must know the starting and end letter of each string, along with the count of AC.
So I used dp to generate the first string. Only three letters would be used in the string, A, C and any other letter ( I used B ). So the parameter was dp ( first letter, position in the string, last letter used until now, number of ac ). At each position I could place one of the three ABC. I proceeded accordingly.
Once I reached the end of first string, I called for the second string right from there. I had to carry few information from first string to the second. The first and last letter and number of AC in the first string. Apart from these, everything else was same for the second string.
So the second dp parameter was this dp2 ( first letter of first string, last letter of first string, number of ac in first string, first letter in second string, position in second string, last letter in second string until now, number of ac in second string ).
Once I reached the second string, I called a function to calculate kth term. I passes the following info to the function recursion ( f1, l1, ac1, f2, l2, ac2 ). Using this info, I could calculate kth term in O(k).
Here is my submission: 5581341. Seems like a lot of calculation but it's really not a lot. Each of the table is filled only once.
Bruteforce. Count of "AC" in s1, count of "AC" in s2, first and last letters of both strings ('A', 'C', or any other). And then for that information we can calculate count of "AC" in k-th string.
And total time is (n / 2) * (m / 2) * 3^4 * k ~ 10^7.
Can someone explain why my submission to D fails?
http://codeforces.com/contest/379/submission/5584738
3 1 1 1
Answer is:
A
C
Thanks,yes I forgot to take into account the case (n==1) || (m==1)
hey, how did u move to the next line without leaving an extra line (between A and C)? i didnt know it was possible to do that without using
Blockoption.All we need is just some
magic =)
the
Acceptedverdicts have been changed toHappy New Year!how cool is that? :)Now, if someone had 0 accepted submissions, they're also in for a bad year :)
Эээ. На задаче C у меня с TLE упал QSort + обработка за O(n) на Паскале. Так ведь не должно быть, не правда ли?
Если qsort без рандомизации, то вполне можно и сломать. А если pivot выбирать как-нибудь банально — вполне можно упасть на взломе кого-то еще с таким qsort
Почему же? Всё правильно. Кто-то не умеет писать qsort с рандомом.
Класть антиквиксорты в тесты — пошлость.
Возможно — просто добавлены взломы.
Да? А расскажи мне, как ты относишься к хешам по модулю 264?
Хэш хэшу рознь. Но писать тесты, фактические, валящие по константе конкретные реализации оптимального алгоритма — это как-то не особо спортивно, IMO. Но если тест действительно из взломов, то у меня претензий нет.
Что такое "по константе"?
QuickSort в среднем случае работает за
.
Многие сортировки в худшем случае работают за
.
QuickSort в худшем случае работает за O(n2).
Отношение
константой не является.
«По константе» значит «валит лишь отдельные реализации алгоритма». От шаффлинга массива оценка худшего случая квиксорта не изменится, однако, почему-то, считается нормальным, что решение с шаффлингом проходит несмотря на свою квадратность.
Неправда ваша. Оценка среднего времени по худшему тесту очень даже меняется.
«По константе» значит «валит лишь отдельные реализации алгоритма».
Обычно «по константе» значит совсем другое: например, что решения с
операций проходят, а с 
уже нет, при том, что эти константы 10 и 15 очень вероятны при решении задачи.
От шаффлинга массива оценка худшего случая квиксорта не изменится, однако, почему-то, считается нормальным, что решение с шаффлингом проходит несмотря на свою квадратность.
Если перемешать массив детерминированно, такую сортировку тоже можно взломать... А вот если инициализировать датчик случайных чисел временем запуска программы — уже нет.
Если перемешать массив детерминированно, такую сортировку тоже можно взломать... А вот если инициализировать датчик случайных чисел временем запуска программы — уже нет.
В худшем случае любой quicksort работает за O(n^2) — хоть с шаффлингом, хоть методом Синглтона, хоть чем угодно ещё. Этот факт не меняется от того, можно ли сгенерировать конкретный тест, на котором это будет происходить.
Если рандом инициализируется внутри программы чем-то изменяющимся, то тест стабильно валящий такой quicksort сделать невозможно.
Для любого теста существует вероятность что на нем quicksort будет работать O(N^2), поэтому мы и говорим о матожидании времени работы. Но под этим понимается никак не среднее время работы на случайном тесте, а среднее время работы на худшем тесте (немного грязное определение конечно, но смысл я думаю ясен).
Справедливости следует сказать, что нам нужно не стабильно валить quicksort, а хоть один раз из нескольких попыток. И свалить не в самый плохой случай, а в долго работающий.
Но и это сделать не представляется возможным :)
А вот это — неправда. Существуют алгоритмы выбора опорного элемента, дающие производительность
даже в худшем случае. Идею можно почитать тут.
Стоит добавить, что, как и в случае фибоначчиевой кучи, на практике так обычно не делают, потому что константа великовата. На практике используют Introsort, основная идея которого — переключиться с Quicksort на Heapsort, если глубина рекурсии становится слишком большой.
Кстати, мне вот на языке D приходится писать
sort !("a < b", SwapStrategy.stable) (arr)вместо простоsort (arr)каждый раз. По аналогичной причине:sortв D 2.064 иногда работает за квадрат. В 2.065 будет, скорее всего, таки исправлено.Чистое любопытство и оффтопик: а как от этого спасает «стабилизация» сортировки?
Замена qsort На merge sort?
Судя по названию enum'а SwapStrategy, его значение не должно бы менять алгоритм сортировки (:
Там просто запускается TimSort вместо QuickSort, если этот параметр равен
, в худшем за O(n2) и при этом был стабильным.
SwapStrategy.stable. Это фактическая деталь реализации, никак не следующая из названия... Хотя, действительно, я не знаю алгоритма сортировки, который бы в среднем случае работал заНу, берём квиксорт и лексикографически сортим им таплы (элемент, его_изначальный_индекс), не?
Действительно :) . Что-то я протупил...
Ну, видимо, это всё-таки медленнее, чем заменить QuickSort на изначально стабильный алгоритм.
Антиквиксорт — это ещё нормально. Пошлость — антиджаваквиксорт)
Как ты вернулся в оранжевые, если я все еще ношу твои штаны?
Ну, у меня в ИТМО неплохая стипендия — новые купил :)
Видел ещё, как минимум, одно решение, упавшее с самописным qsort на том же тесте. Возможно, тест как раз подобран таким образом, чтобы qsort, в котором медиана выбирается таким образом не проходил.
О, мой тест. Строится довольно просто. Меня самого когда-то почти так же взломали (я не использовал randomize), вот теперь и ты научишься на олимпиадах писать с random'ом.
Did you guys notices that in status page instead of accepted, it is showing happy new year ??
Happy New Year!instead ofAccepted....Nice way to wish us... :)
Like this innovative idea ... :)
Ох, повезло же мне с комнатой. Пространство для взломов ну просто неограниченное.
What a perfect contest! I loved it so much! I would like to thank all of the authors and the preparation team! Happy new year to everyone!
fail of the year? 5573462
how? o.O
It is not enough time to write 300000 long long numbers with cout. His solution wrote only the part.
sync_with_stdio to false?
he didn't use cin/cout, so sync_with_stdio wouldn't take affect must be the sort function with terible random then o.O
rep(i,0,n) cout << A[i].ans << " ";
oh, sorry my bad :p
I try it with sync_with_stdio(false) but still TimeLimit :-??
with sync_with_stdio 5586030
with scanf and printf 5586108
both of them TLE :D
Try it one time with
intinstead oflong long.In general case using
long longcosts so more thanint.Wish it works in your case.
It is surprising, I used cin/cout and it passed
There are two sort in this, which accounts for double the runtime. And then adding to that, there is the cout function.
It's surprising. I got accepted with two sort functions and using cout : 5578740
He didn't pass references in sort comparator.
Problem A is exactly same as uva 10346 — Peter's Smokes.
lol, there is at least 6-7 similar problem like this at UVa. That's why it is the giveaway problem of the contest :)
LOL, the fan in your profile image moves while looking on the screen and not directly looking to it, and it stops when just directly look at it :)
Happy new year~ However, who can tell me why I WA at test #22? 5584508 I can run a correct answer on my computer. TAT
I have submitted the problem C in java7 5577222 it got runtime error during the contest and I realized that why it got RE? so I submitted the same code in java6 in practice,it got accepted.5585065 Did it consider as accepted or not?
Your Comparator do not adhere to comparator contract — it should return 0 on equal elements. Java 6 sorting algorithm is implemented in the way that for all compariosions any outcome is possible, but int Java 7 sorting algotrithm (which is TimSort) sometimes only 2 outcomes are possible and when 3rd one is returned it is assertion error
Thanks thats why you are such a good programmer we learn the use only and you know the implementation of the method too.From next year I will use the library method when I know about it completely. As for my solution whether it will be considered as failed or passed because it got accepted in Java6(in practice though).
Минуты не хватило чтоб отправить D, однако прошла :(
My this code for problem C has given me TLE in 11th case ... As the input is very big, I'm unable to know the reason... would anybody help please ???
There's a while loop inside a rep(i, 0, n). The while loop may be executed as many times as the size of the bi's, which is O(n). Hence the overall complexity of this solution looks like O(n^2) which is not good enough since n could be 300000.
In while loop value of 'i' is being increased... it should be just like 'i++' portion .... total complexity should be O(n). Shouldn't it ??? Or am I missing something which isn't known by me ???
And the 10th case is big too... n=299999 ... I haven't got TLE in this case... :O
Actually I want to know the reason ... while submitting, I never thought about this verdict ... But I've got !!! Please clear me... :(
nevermind.
The variable comes from ai and is as big as 10^9, so even a single while loop may not end in time. The ai's in the 10th case is small but is large in the 11th case.
But I'm astonished that, I submitted without using that while loop... and got TLE too, at the same case ... :O
My submitted code without inner while loop is 5589598
what is the reason behind this ??? :O
I even didn't use STL map too ... :O
your solution with int instead of long long: 5589677
Thanks a lot... riadwaw
Now my code submitted in the contest time is AC too... while loop was not the problem... The reason is only
__int64...Too frustrated... didn't want such finish in this year ... ;(
Just for not knowing that __int64 takes more time than int...
Anyway, good thing is it's not in any onsite contest... (trying to take it positively, though failed) ...
Also you could pass the arguments of cmp by reference, like 5589749.
Thanks johnathan79717 ...
known another thing by you ... :)
You're welcome :)
А давайте как в задаче С подарим всем рейтинг?!
ага, мне бы например балов тридцать так =)
I would have passed F, if I would have used scanf instead of cin.
I did not expected that time limit would be kept so strict.
May be I should start using scanf and printf for each and every problem :(
Feeling very very bad :(
It is not a good gift at all :(
http://codeforces.com/contest/379/submission/5585325
http://codeforces.com/contest/379/submission/5581511
You may find this interesting: http://codeforces.com/blog/entry/5217
I know this, But most of the time, I use cin here in codeforces because they give a lot of margin in time in solutions, but this time I was wrong :(
I am wondering why they give 5*10^5 queries, they can simply give 10^5 queries as it is normally done, it would be possible to solve the problem without IO or constant optimization.
I have the same problem, but the problem is not in input, but also non-asymptotic optimize allowed to pass tests =(
Does anybody have any idea how will they give the ratings? Because this contest was very different from other ones. Div1 contestants were in the same place as Div2 contestants and the contest was rated for both of them. Will there be considered a Additional points for Div2 Participants? (Hope so!)
Since normal rating formula calculates the expected position based on your and everyone else's rating , there is no reason it wouldn't work fine in this match.
why it is wrong answer http://codeforces.com/contest/379/submission/5584330
You don't need this
ans='\0';when dealing with strings.thank you .....
Surprised to see Petr and tourist not try to solve number F!!!!Instead they were busy in hacking!!Whats the secret behind this???
maybe they didn't realize there are F and G?
They can't resist that when there are lots of gray and greens and blues in their room :)
I've spent more than an hour trying to solve F, but couldn't.
may be you were distracted by seeing lots of grays and greens and blues.. just kidding :)
This problem is almoust same with RRTREE.
Oh the last luckiness for 2013, I submitted my F in the last second :)) I had done F before, but at the last moment I realised that I got wrong range :< I resubmitted and lost about 600 point :'( However alright <3 Happy new year everybody <3
So sad:(
5583857 on contest
5585359 upsolving
A diff of the files would be more useful :).
actually you are peter50216 or rng_58 or not :)
or peter58?
Egor was real quick in problem D :D
О, я сейчас придумал классное решение F:
если есть дерево, где длиннейший путь с концами в x и y, и добавился лист z
то теперь длиннейший один из
x-y, y-z, z-x
А вообще что-то эдакое было на September Cook-off
5585408
Да, просто на контесте я придумал только за O(q*log^2(q)) и гораздо более объемное)
Была такая идея на контесте. Но я что-то не придумал как это доказать, не подскажите?
Так это сложно объяснить. Проще нарисовать.
Все знают, что диаметр можно искать так — берем любую вершину. Переходим в самую далекую от нее. И это будет один из концов диаметра.
Верно и обратное — если x-y — диаметр, а w — вершина, то наиболее удаленная от w — одна из x,y (может, есть и другие наиболее удаленные от w).
Из этого, если x-y — диаметр и подвесили z за w, то наиболее удаленная от z тоже x или y. (из факта выше). Отсюда и следует корректность решения.
Если это не так, то рассмотрим 2 пути — старый самый длинный и новый. Они либо пересекаются, либо нет. В первом случае найдем еще путь между ними. Если посмотреть на получившуюся конструкцию, то всегда можно построить путь как минимум нужной длины, выходящий из одной из изначальных вершин
И как посчитать 3 этих расстояния? Как решить проблему с вырожденными деревьями(
Расстояние на дереве ищется с помощью наименьшего общего предка, так как путь между двумя вершинами обязательно проходит через него.
спасибо, почему-то отмел LCA, т.к. хранил высоту и обновлял ее, а нужно было расстояние до корня.
Can anyone explain 379C - New Year Ratings Change New Year Ratings Change why 5579353 gives runtime error ] while submission id 5585888 gives accepted answer... Thanks in advance...
I think that your bool cmp is wrong. The bool cmp must return the value that a < b You can have more detail in here Sort
Still not getting why this is resulting in runtime error
A usual line in the quicksort function is like:
Now, consider an array of equal elements. For the above line to work, the
a[i] < a[x]part must of course return false for equal values. Otherwise, the indexijust walks outside the array (which may or may not result in Runtime Error). Your previous version of thecmpfunction however violated this, resulting in incorrect behavior for equal values:It returns true when a is equal to b, which is an error.
Addition: this error is similar to writing a comparison function which always returns true or always returns false. You can try for yourself to design an efficient sorting function which accepts such a comparison function and does not generate nonsense in this case.
Thanks for your response and information.
But wont our lives be easier to implement operator for structures and easily use sorting ? 5576735
If one day i decided to use two function to sort an array i would rather to var static variable in my class and a switch case in my operator<.
C++ allows to do it either way. It's up to the programmer to decide what's more convenient.
Such a bug can occur in a custom comparison operator operator as well as in a standalone comparison function, and will have the same consequences.
I don't know exactly how sort() works but the comparison function you give must be a strict weak ordering function, so in particular
cmp(x, x)should return 0.but why would that result in RTE?
Egor says this for same problem in Java — http://codeforces.com/blog/entry/10161#comment-156164
I hope that has nothing to do with same variable names for array a[333333] and rating a.
I had submitted this code in the contest
http://codeforces.com/contest/379/submission/5581511
and after the contest, I submittted this.
http://codeforces.com/contest/379/submission/5586307
And when I submit it after the contest, it gets accepted
May be time limit decisions are affected from the load on the server at that time.
Please tell me what reason could be for this undesired behaviour.
too bad, looks like load is the cause of that 50ms difference that took that away from you :(
I think this has made me learn few things
1. use scanf/printf everywhere.
2. try to do low level optimization when time limit of your solution is tight.
or better in case of cin and cout, use ios::sync_with_stdio(false). as scanf can be slower in case of "%c" and in that case we have to use getchar() for speed.
but that again has some issues, you can not interleave scanf/printf statements, As I have habit of using scanf/printf cin, cout alternatively, I will not prefer to use ios::sync_with_stdio(false);
pls update the ratings:)
F can be solved by either Heavy Light Decomposition or maintaining Diameter Pair with LCA. (HL: 1100ms, LCA: 550ms in C++) I had hard time implementing HL decomposition, I couldn't make it in time.
cognition solved problem A,C,B in 4:02 , 4:18 , 5:00 min !!!!!
LOL. seems he was not alone XD.
Yeah, seems strange. In problem B and C indentations are different. In B 2 spaces are used and in C tabs. Or he just wrote the contest on two different computers coding two problems simultaneously with each hand on each keyboard :D
The indentation is also different in problem A, so I think there actually were 3 computers and he coded with his feet or any other part of his body (I don't want more details :-) )
Does sharing an account break any rules? Though it's probably hard to prove.
Though he was not alone, he is not in the top 10...
I've conducted an investigation and banned him. There are multiple evidences that he took part unfairly :(
мне кажется или на это соревнование зарегестриловалось наиболее количество пользователей — 3945.
Еще бы чуть-чуть и было бы 4000!)
P.S.Если не прав напишите)
Почти, на квалификацию VK cup было зарегистрировано 4360.
Round statistics
pls change the ratings
I wonder, will cognition get banned?
Check the final standings again. cognition is no longer there. Probably removed. Also, setters congratulated Logic_IU for winning the round.
He was there, just before I posted the message.
Yes, removed. That's good.
Are they planning to update the rating next year or what?
Happy New Year to everyone!
I think if we have more problems in contest the results will be more reliable...
Wish we have more of these contest (Both Div , 7 Problems) in future...
i just noticed that
Acceptedhas been changed toHappy New Year!even in contests other than today's round. i wonder if this is intentional, or some kind of bug with the site?They probably replaced the string globally (the value of Accepted string) and hence the effect. :)
I doubt they intended it for all but maybe there's no easy way to do it for just one round.
Yes, the same message is in Russian interface. And how it could be a bug? :)
не могу ждать в конце года в рейтинге больше: (
cant wait for the year end rating anymore :(
https://pp.vk.me/c320524/v320524834/5f1a/jIzSfPkrraQ.jpg
какая все-таки хитрая эта D... (нет, я не проходил следующий тест ифом)
well by the server time it's the new year right now(happy new year) but the rates aren't updated yet.
It's still 24 hours left from this year.
please update the rating, I want to see the rating before sleep,TAT
UPD3: Congratulations to the winners of the last round in this year. Rating will be changed in a few hours.
You just shouldn't go sleep for a few ours.
hope ratings will be updated this year :D
please update the ratings quickly, wishing only a "Happy New Year" will not work
В задаче D верно утверждение, что если ответ есть, то его можно составить только из букв A и C?
Непохоже на правду. В тоже время, трех букв(A, C и еще какой-нибудь) точно хватает.
Для теста 6 1 2 2 вы не сможете составить ответ. А правильный будет иметь вид:
where are the ratings?! :(((((
it was really nice contest!
but is it possible that rating gonna be updated this year? or we'll have to wait for the next year? xD
being specialist, how did aangairbender manage to solve all the problems especially Problem G of Good Bye 2013 (which remained unsolved in the contest) in virtual participation? who is he?? who helped him (if someone helped him)
He used FPC to solve the problem. A bit unusual.
He seems to copy other's sources.
Where would he find the solution to G?
Here http://codeforces.com/contest/379/submission/5585359
from here :D
http://codeforces.com/contest/379/submission/5585359
Just finished coding problem G — it got accepted right after it passed the examples, but one hour spent coding it was so non-exciting to say the least.
How about a non-proliferation treaty on cactus problems? :) They rarely are conceptually different than corresponding problems on trees, but they are so much more painful to implement.
Actually, I had twice as much code as if it were problem on tree. And the extra code is almost the same, just new parameter when handling the cycle.
Well, you also have to find the cycles in the first place, correctly handle cases when several cycles share a vertex, etc. That's exactly my point — nothing conceptually different, but harder to implement.
Best formula to create
trashsomething "non-exciting to say the least" from the great problem.Really good formula, explains everything!
In this case the problem on the line would probably be worse than on the tree, though :)
I would say, that you can add one more step: instead of "problem on tree" use "problem on tree that contains the only cycle".
If possible:
Could you share your approach to problem G? At least an overview to be able to read your solution. Thanks.
OMG!!! i finished watching two movies after the contest, and rating is not yet updated. i dont have patience anymore. going to bed hopping that i will see updated rating in the morning.
Ratings have been updated, congrats to everyone and all the best in new year :)
Ratings are updated. Check it out :)
Ура! Я стал фиолетовым!
Finally after ~5hours waiting, Rating has been updated! Now I can sleep :) Happy New Year!
Great match! And I have got the highest rating in this round. It will be better if Welcome 2014 Round which has the same rule as Good Bye 2013 were added.
thanks for this awesome round! :D happy new year everyone...:D
Thanks for the round and interesting problems!
Congratulations for everyone, who's color was upgraded :)
actually, red to yellow is a downgrade of rating, not upgrade.
but yeah, good idea about the photo! :D
I think that's purple to yellow. To be more accurate, pink to golden perhaps? But we get the idea. It's cute.
+203 points, it was impossible :D Thank you Codeforces for the good year!
Happy New Year's Eve!
Screencast
Which soft do you use to grab screen? Does it work without fails and crashes?
CamStudio. Never crashed so far
Good bye 2013, good bye Div1!
Same with me ;) . But anyways Happy New Year in advance !
Next contest will be Welcome 2014?
for problem A, tests 16-21 are all same. why?
This was such a nice contest! I crashed D because I used some variables as int instead of long long.Still,I managed to get ABC pretty fast and as a surprise, the rating increased over my epectations.So, thank you for the contest, and also thank you for the site, it really made my day.Happy new year to everyone!
Думаю, таких контестов надо побольше. Вон, какие чудеса с рейтингом творятся когда дивизионы сводят. Заодно становится меньше тех, кто самым наглым образом посмотрев задачи, отказывается их решать.
А подробнее можно, какие чудеса с рейтингом происходят? И почему должно становиться меньше тех, кто отказывается участвовать после просмотра задач?
Потому что из-за них рейтинг неправильно рассчитывается для тех, кто посылает решения. Правильно должно быть так: зарегистрировался и ничего не решил --> занял последнее место.
Столько раз уже обсуждалось...
Как по мне, людей, желающих пожертвовать удобностью на пользу тому, что "их рейтинг будет чуть более правильным и адекватным" (хотя на самом деле мотив скорее "более крутым") — далеко не большинство.
Вы все ради рейтинга решаете что-ли? Если бы на СF рейтинг не мелькал перед глазами — я бы даже не знал, какой он у меня. Вот на ТС не знаю — есть себе рейтинг, ну и ладно. Какая разница? Эти рейтинги ведь вообще мало что отображают. Понятно, что красный и синий — это немного разные уровни:) Но остальное — дело дисперсии, рэндома и всего остального.
36 часов назад я был, скажем прямо, человеком с умственными способностями явно не выше средних, и IQ тоже. Я даже готов поспорить, что ощутимо ниже средних, если рассматривать только пользователей данного сайта. Чем там еще принято мериться? А, программирование. В АСМ я как бы тоже не особо преуспевал. Хотя в АСМ думать и быть умным не обязательно, поэтому здесь все далеко не так плохо.
И что, от того, что я получил +124 и стал красным — что-то кардинально изменилось за эти 36 часов?
А когда в следующем раунде я, допустим, опять получу -50 или -70 — это признак того, что изменения были в обратную сторону, мол, праздники дали о себе знать?..
Изменение рейтинга в одном контесте мало о чем говорит. Особенно в общем раунде, когда люди с относительно низким рейтингом могут прыгнуть выше головы. А по рейтингу за несколько контестов можно делать выводы, еще как можно.
По всей видимости, часть рейтинга перетекла из Div. 2 в Div. 1. На первый взгляд возможны такие последствия: средний рейтинг в Div. 1 поднимется, станет сложнее опуститься из Div. 1 в Div. 2; в то же время средний рейтинг в Div. 2 опустится, станет сложнее подняться из Div. 2 в Div. 1. Я бы не сказал, что это однозначно хорошо.
Ну, такие вещи являются неотъемлемой частью кф уже очень давно.
Вы делаете такие уверенные заявления, будто вам известны формулы вычисления рейтинга. Или есть на руках данные о том, как изменялась общая сумма рейтингов участников после каждого из последних раундов. Или еще какая-то полезная статистика. Поделитесь?)
По поводу изменений в распределении рейтинга: в идеале, как я понимаю, система рейтинга должна максимально соответствовать идеям Эло. Отсюда следует подчинение нормальному распределению.
Если на время забыть о существовании клонов, забивших пользователей и всего прочего, а втупую посмотреть на таблицу рейтинга — сейчас на переходе от div2 к div1 это как раз сильно нарушается. Нарисуйте график зависимости числа пользователей от рейтинга для графиков 1600-1699 и 1700-1750 и сами увидите, от 1700 вверх получается примерно по 50 пользователей на 1 единицу рейтинга и число довольно плавно и аккуратно падает к уровню примерно 30 для 1750; в то же время, от 1699 вниз — примерно по 30 пользователей на 1 единицу рейтинга вплоть до 1600.
В чем соль совместных раундов? В том, что после их проведения, если пересчет соответствует принципам Эло — новое распределение тоже должно быть ближе к тому, которое предполагает рейтинг Эло. Следовательно, если что-то куда-то перетекает — то только в ту сторону, в которую должно перетекать согласно с идеями системы рейтинга. Это все при наличии дополнительных условий вроде "таблица совместного раунда более-менее адекватно отображает реальную силу участников". Вчера было достаточно простых задач, чтобы в середине таблицы все как раз было более-менее адекватно.
Так что какими бы ни были изменения в трудности перехода с div1 в div2 и наоборот — картина должна была измениться в "правильную" сторону.
Первый раз участвовал в олимпиаде, код писал на Visual C++ 2010, при отправке задачи все время выдавало ошибку компиляции якобы "stdafx.h" не открывается, вопрос, каким образом мне отсылать код если без "stdafx.h" если на Visual studio 2010 од даже работать не будет??
Создать проект без precompiled headers в VS. (Консольное приложение win32 — галочка пустой проект)
Hello, 2014!! (in Japan)
So easy!
Great round to say good bye to 2013, I am equally hopeful for great contests this year!