Привет, Codeforces!
Добро пожаловать на последний раунд Codeforces в 2014 году, Good Bye 2014! Этот раунд очень необычный; Во-первых, раунд начинается 30 декабря в 18:00 по Москве. Во-вторых, раунд длится 2.5 часа. И в третьих, раунд будет общим для двух дивизионов, что означает, что Div1- и Div2-участники не будут разделены.
Задачи подготовлены мной (.o.) и Seunghyun Jo (ainta). Это наш второй раунд на Codeforces. После нашего первого раунда случился чёрный день Codeforces, и мы надеемся, что в этот раз ничего подобного не произойдёт :D
Спасибо Won-seok Yoo(ainu7), который тестировал раунд и обусждал с нами набор задач.
Также мы хотим поблагодарить некоторых людей, без которых этот раунд не состоялся бы. Максим Ахмедов (Zlobober) сильно помог нам в подготовке задач. Мария Белова (Delinur) перевела условия задач на русский язык. Михаил Мирзаянов (MikeMirzayanov) создал прекрасные сайт Codeforces и систему Polygon. Они также заслуживают аплодисменты!
Разбалловка будет оглашена перед началом раунда, как обычно.
Мы желаем вам всем удачи. С новым годом!
Просьба оставлять комментарии на английском языке, если вы хотите, чтобы авторы смогли их прочитать.
UPD (2014-12-30 17:34:48) Разбалловка будет выглядеть следующим образом: 500-1000-1000-1500-2750-2750-3500.
UPD (2014-12-31 12:49:05) Sorry for updating in English. Round has finished, congratulations to the winners!
Also, thanks to Marcin_smu, who solved problem G after the contest for the first time.
UPD(2014-12-31 12:51:08) Sorry for updating in English. Editorial is published. Currently, only A-F is available, but I will add G as soon as possible. Sorry for the late editorial.
UPD(2015-01-02 21:30:44) I wrote the editorial of G. Sorry for the late update..
Why I give -88 for this comment "Happy New Year !"?
You Give negative -10...-100 :D
Hi,Happy New Year!
hello Happy New Year
dis like me pls
If you like ... I give it you !
tanx
to keep everything zero-sum, you guys can upvote me as well :)
"создал прекрасные сайт"
На русский Google Translate помог перевести?
UPD Понял свой баг.
Вообще-то тут нету ошибки, слово "прекрасные" относится как к "сайт Codeforces", так и к "систему Polygon"
просто Google Translate лучше шарит в русском =)
It is rated? Happy New Year!
yes :))
yes
2 people said "yes" one of them has -16 while the other has 0.
No, there's a difference , one of them is smiling.
talking seriously, khashi246 is just a spammer look at his previous comments
I think we should stop commenting in this particular spot. It looks like there is a dislike party B)
That's not how this meme is used... * * Flies away * *
First positive up votes from the beginning....What's the matter? I am curious about it.
Уходящий год был непростым (2014 = 2*19*53). Непростыми будут и следующие два года, а вот 2017 снова будет простым. :)
does
division combinedthat means div1 contestant can perform hacks on div2 contestants ??Yes. And div2 contestants can perform hacks on div1 contestants too)
As far as I know, being in Div1 doesn't necessarily mean you hack better than others. See the nice summary of hacks and see how there are blues and purples mixed with oranges and reds.
...we need a special contest based solely on hacking.
That's presumably because division 1 participants can only hack other division 1 participants, and vice versa. Most of the low division 1 crew (people like me who only get A) got to division 1 in the first place by cleaning up "easy" hacks (things like overflow, bound checking, etc.). If every contest were division-combined, I'd guess that the best hackers would be oranges with a couple of blues/low purples thrown in (i.e. those who will finish the problems they can do fairly quickly and have the ability to hack others accurately).
thats exactly what im counting on after reading all problems and solving what i can solve. its just most contestant strategy is to solve the first three problems and start looking for hacks so i have to be fast. I hope for alot of green color in hacks and submissions but not in rank color :D
Ah, true, Div1 contestants can only hack Div1 contestants. I forgot that difference.
What if they put Div1 and Div2 contestants in separate rooms, like they do for Div2-only contests?
I have no idea, haven't seen a contest for both divisions before.
No, check the past Good Bye contest. Both divisions are merged, so Div1 contestants can hack Div2 and vice versa in this round.
Or at least it should be so if they keep the tradition...
Its a positive feedback loop; remember your ecology folks!
Is it going to be rated?
Of course!
Good Bye 2014 has a lot of blogs , a separated blog only for discussing score distribution and you ask it's rated or not :D unexpected :D
It was asked hour before you asked — http://codeforces.net/blog/entry/15465#comment-203696
I missed it because everybody who asked that got so many negative points that they were hidden :))
Not when I answered, but maybe that is the reason why I have so many downvotes :-D
Or maybe there is a conspiracy and downvotes are the tool to hide the fact it will be rated :-D
Could you please tell me how many problems in this contest?
There are 7 problems. I forgot to add that in the announcement. I'm sorry for that.
I wish score distribution will not be dynamic :)
I'm expected to take this contest!
But I'm little nervous I'll not perform well because it haven't programmed for half a year.
Good Bye 2014 — Good Bye div_2 Hello 2015 — Hello div_1 Good luck to all members of div_2 Happy new year!!!
I think it will be successful contest for all. Good luck to all participants!
Is there a handle changing gift from Codeforces like last two years? :)
Based on that, I'd say there will be...
Bredor)) http://6.firepic.org/6/images/2014-12/30/y8v19jxmqy9q.png
Windows ?! Really ?!
Hope for high rating .
Last year in "Good Bye 2013", We get "Happy New Year!" instead of "Accepted". what about today?
Will we be able to change our handles this year? :)
I think, that you missed it this year, but BaconLi asked whether one can change the handle next year already — http://codeforces.net/blog/entry/15465#comment-203758
wow this is...
At least 50% of comments are "hidden because of too negative feedback" :)) Dislike me plz ;;)
Happy Everyone! I think the Good Bye 2014 contest will be a interesting and funny contest. Tonight will be a while night.
Hello beautiful :)
Аctually +1.
Most comments are Hidden.I do not like it. Because Everyone cannot read that comments? So everyone try to Like that comment. At least no click buttom down vote::i do not like it. we see in facebook ..there is no unlike or i do not like it.
I'm very happy to hold this special round. Good luck for everyone!
Damn! I have a final exam tomorrow :( but I so wanna participate in this round.... :/
Will there be any souvenirs? We want T-shirts!
If you win the entire contest, I will give you a t-shirt
OK, I'll try!
If I was not able not to do it, can be my goal of the new year.
Happy new year! :D
YuukaKazami has registered for this contest :D http://codeforces.net/blog/entry/14798
But he didn't participate, It's your fault :D
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░████████░███░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░█████████░░███░░░░░░░░░░░░░░ ░░░░░░░░░░░░░███████████░░░██░░░░░░░░░░░░░ ░░░░░░░░░░░░██████████░░░░░░██░░░░░░░░░░░░ ░░░░░░░░░░██████████░░░░░░░░░██░░░░░░░░░░░ ░░░░░░░░░░█████████░░░░░░░░░░░██░░░░░░░░░░ ░░░░░░░░░█████░░░░░░░░░░░░░░░░░██░░░░░░░░░ ░░░░░░░░████████░░░░░░░░░█████░██░░░░░░░░░ ░░░░░░░░░░░███████████████████░░░░░░░░░░░░ ░░░░░░░░░░░████████████████████░░░░░░░░░░░ ░░░░░░░░░░██████████████████████░░░░░░░░░░ ░░░░░░░░░████████████████████░░██░░░░░░░░░ ░░░░░░░░████████████████████░░░░██░░░░░░░░ ░░░░░░░████████████████░░░░░░░░░░██░░░░░░░ ░░░░░░████████████░░░░░░░░░░░░░░░░██░░░░░░ ░░░░░████░░██░░░░░░░░░░░░░░░░░░░░░░██░░░░░ ░░░░███████░░░░░░█████░░░░░░█████████░░░░░ ░░░░██░░████████████████████████░░░░░░░░░░ ░░░░░░░█████████████████████░░░██░░░░░░░░░ ░░░░░░███████████████████░████░░░██░░░░░░░ ░░░░██████████████████████░░░░░░░░░██░░░░░ ░░██████████████████████░░░░░░░░░░░░███░░░ ░███████████████░█░░░░░░░░░░░░░░░░░░░░██░░ █████████░█░░░░░░░░░░░░░░░░░░░░░░░███████░ ░░░░░░░███░░░░░░░███████░░░░░░██████░░░░░░ ░░░░░░░░███████████████████████████░░░░░░░ ░░░░░░███████████████████████████░██░░░░░░ ░░░░██████████████████████████████░███░░░░ ░░░█████████████████████████████░░░░░██░░░ ░░█████████████████████████░░░░░░░░░░░██░░ ░█████████████████████░█░░░░░░░░░░░░░░░██░ █████████████████░█░░░░░░░░░░░░░░░░░░░████ ░░░░░███████████░░░░░░░░███░░░░████████░░░ ░░░░░░░░░░░░░░░░███░█████░█████░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░█████░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████░░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░███████░░██░░░░██░░██░░███████░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░░░░░░██░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░░░░░░██░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ HAPPY NEW YEAR EVERYBODY !!!
Hmmmm I'm wondering why this contest isn't held tomorrow......
What are you guys hoping the problem names are?
A. New Year and Implementation
B. New Year and Sorts
C. New Year and Easy DFS
D. New Year and Maths
E. New Year and More Maths
F. New Year and Impossible Problem
G. New Year and An (Not) Easy Problem About Trees
Finally you got some upvotes. :P
I was right for A and B !!
And D, to an extent!
And G too.
Many participants solve B by Floyd... I think E should be New Year and Maths once more
In order to prepare exams, I haven't written code for a long time.
upvote for your avatar
The avator only mean that I worship XiDada
Note that this is also contest number 500 (id from the URL). Lots of anniversaries :)
number of participants is more than 6000 now. I hope that nothing happen to codeforces servers in this round :D
We aim for over 9000.
More than 6000 users are registrated for the contest! I think it will be the record.
OnCe uPoN a TiMe..
wow! so many participants! i think it's the first time we have ever reached 6000
"Thanks to Xellos for giving us some ideas." Why do I have the feeling the contestants won't like those ideas?
You can see here that my argument is tailored on a specific round, so I am equally worried about that :D
GOODBYE 2014!! hope 2015 a better year
wish a HaPpY NeW YeAr with good rating for all =D
Difference between the starting time of the contest and end of registration now decreased to 2 minutes :) (earlier it was 35 minutes)
6250 registrants! What a record! And registration ends before contest starts only 2 minutes.
Anyone noticed it's the 500th contest?
Can't submit :( Like I am not registered, though actually I am.
Seems I am indeed not registered. ok..
Hi, I just realized that the contest started 15 minutes ago. I didnt know that the registration closes 5 mins back as this is my first live contest. Is it possible to enter now? I have already completed problem 1 locally.
Good Bye 2014 and Div. 1 )))
Good bye 2014 and EXPERT :D PUPIL here i come xD
A lot of submissions are in queue
you have to add some time ...
Goodbye div1 :( was fun while it lasted
My last submission was 5minutes before the end of the contest — after end of the contest I still didn't get the verdict :( .
And at last, you got Accepted~ Congratulations~
Thanks man — no complain about that one :)
At problem D: "It is guaranteed that wj is smaller than the current length of the rj-th road.". why?
because each year when they repair a road, it gets shorter!
His question was: Why does the problem need that constraint? My solution doesn't care about that.
Because it makes statement more clear.
No, it doesn't. It's at least 2 extra sentences.
Well, without it the "after any changes Wi<=1000 will also hold" sentence must be added to clarify the upper limit of edge weights.
But this constraint is actually exist.
Yes, that was my question; thanks for clarifying!
Because nobody wants to make straight road bent.
Not necessarily. Downhill roads in winter are overkill when straight.
But they do not take much time to pass! At least in one of the directions.
Как делать последнюю когда один вниз идет, а другой вверх? А то я час писал её, а потом понял, что не умею с этим случаем разбираться.
В Е решение — отсортировать запросы и дерево отрезков? Или я ошибаюсь? У меня был час =_=
Сортируем запросы по убыванию правого конца, храним актуальные палочки в стеке, ответ на запрос -- разность между координатой конца и начала минус сумма высот актуальных палочек. Можно даже фенвиком сумму считать.
Можно делать онлайн двоичный подъем по количеству удлиненных палочек.
how to solve E .
Offline — just sweeplining in a smart way, one BIT helps calculate the answers.
I normalized each domino — max(l[i], l[i-1]-(p[i]-p[i-1])) and use sum on segment tree <a, b-1> but it gets WA on test #7. What did I do wrong?
Anyone know why you get WA7 here?
It's also possible online.
Let F[i] be the solution for query (i, n). First of all you compute all F[i]s and store them in minimum segment tree. It can be done in
time, if you do it cleverly, going from right to left.
Let M(a, b) be minimum of all F[i]s for
. Answer for query (x, y) is F[x] - M(x, y).
In fact F[] can be done in O(n) with a stack. And M(x, y) can be done by union-find sets. 9316327
I don't understand why the answer is F[x]-M(x,y). Can anyone please explain?
Executing plan (x, n) costs F[x] and it makes all dominoes between x and n (inclusive) fall, so it also makes y fall. Therefore, one way of executing (x, y) is to execute (x, n). However, this might be an overkill, as you may pay for dominoes that are behind y. So you need to subtract M(x, y).
The reason why we subtract M(x, y) and not just F[y] is that there might be some domino close to y (from left side) that is much longer than y and therefore has better range than y.
Thanks. I get it now.
I don't think I understand your solution Baklazan. How does subtracting the minimum ensure the lowest possible value?
Assume we can execute plan (x, y) for cheaper than F[x] - M(x, y). Then we can do the following:
We extend some dominoes in such way, that if we push domino x after extending, domino y will eventually fall. We will do this for as cheap as possible, so it will cost less than F[x] - M(x, y). We will denote price of this step C.
We find such
, that F[z] is as small as possible (so F[z] = M(x, y)).
We extend some dominoes in such way, that if we push z after extending, n will eventually fall. We will do it for as cheap as possible, so it will cost F[z] = M(x, y).
Now we can push domino x. We are guaranteed that y will eventually fall by step 1. That means that all dominoes in range [x, y] will fall, so z will also fall. Step 3. guarantees that n will fall as well.
Therefore we have effectively solved query (x, n) for C + M(x, y) < F[x], what contradicts the definition of F. Thus our assumption must be wrong.
E can be reduced to heavy path decomposition. For each domino you should find which is the last domino that falls down if you push the current domino. Now the answers can be converted into edges in a tree (or eventually, multiple trees). You need to process some other information also, but the cost of each plan is the cost of the path between x and y in the corresponding tree.
Can it be done using MO ?
I finished solution to problem F 3 minutes earlier than contest end, but failed to submit it due to network reason....... so sad to say goodbye to 2014 TAT
what is the idea behind F ?
WTF with B?
Union Find!
BFS. FTFY
BFS was within time limit? D:
BFS is the fastest thing possible, it runs in O(M + N) (with M 1-s in the matrix, they're edges of the BFS'd graph). Just see my code for how it's done.
I'm crying.
Also, nice C++ Template.
use to all pair shortest path to generate the new matrix where position i and position j can be swaped or not ,then just find normal two loops from 1 to n getting 1 in its lowest index and so on
Can't submit in the last 2 minutes :( I can't access Codeforces page quite frequently during the contest.
Ну почему не сделать так, чтобы при взломе перенос строки в конце добавлялся автоматически?! В полигоне же это сделано. Неприятно, когда в конце контеста из-за этого не проходят взломы, и при этом система жутко тормозит, так что это даже невозможно исправить.
Возможно, это повод реализовать фичу типа "очереди на взлом": когда взлом решения стоит в очереди, это же решение можно взламывать, но очки получает первый взломавший. Хотя на обычных раундах проблем с проверкой взломов вроде не было, но в этот раз в конце они тестировались около 5 минут.
Разве в полигоне это сделано? Вывод генератора тестов берётся как есть и потом проверяется валидатором. Логично, что для генератора тестов на CF делается то же самое.
EDIT: Понял, это про ввод теста вручную.
well done codeforces team :) ... today contest ran smoothly (the server didn't crashed) even in the record high participation.
I frequently can't access Codeforces and missed the opportunity to submit in the last 2 minutes of the contest.
I would not accept this contest if my rating drops to yellow because of this issue ><
question B was just made for hack Lol floyd warshall
Floyd-Warshall is a huge overkill in my opinion. I did a simple DFS to get connected components, and most people did BFS or union-find.
It's a two-line algorithm (especially when I have REP(i,n) macro), much faster to code than BFS/DFS, and the constraint is small. Why not? :)
for-for-for is simpler than DFS, isn't it?
Seems like I found another person that can't remember names in algorithms :D
What do you mean :) ?
Do you think Floyd does not work in B? I used it! and I got AC.
http://codeforces.net/contest/500/submission/9317990 what is wrong with this problem B code
I just changed your transitive closure (Floyd Warshall) and got AC here, hope it helps!
thanx ..mother of mistakes :(
What was the hacking case in B?
3
3 1 2
001
001
110
What is the correct output to that?
1 2 3. Many people that don't pre-process the matrix first gives2 1 3.I think a lot of solutions that just swapped stuff in strange ways would fail on
The optimal series of swaps (elements, not positions) is
(3,2) (1,2), not(3,1), although the latter gives a better intermediate result.(inb4 ninja'd)
Thanks for the explanation guys. Will take this learning into 2015 — never underestimate Div2 1000 and greedy doesn't always work for apparently "easy" problems.
same here lesson learned :) going to green today
I was testing some of the first in the standings solutions and was wondering shouldn't this
have as correct output
1 3 2 6 4 7 8?The output I saw was
2 3 4 6 7 1 8but the 1 could be swapped with the first number. Am I wrong ?Invalid input. The matrix has to be symmetric.
you're right, I missed that from the problem statement, thanks!
P[] must be a permutation, but {7, 3, 4, 6, 8, 1, 2} doesn't.
I used
to hack several people who just swapped every time it would give a better result (e.g. i<j and p[i]>p[j]).
7 1 3 7 4 5 6 2
0000000
0010001
0100000
0000000
0000000
0000000
0100000
wrong output: 1 2 7 4 5 6 3
answer: 1 2 3 4 5 6 7
can you help me where i got wrong . what i did was take two arrays . sort one of them .then for each A[i]!=Bi and B[i]<A[i] check if they can be swapped . if they can be .do it .else continue;
Your idea is wrong; it is not always optimal to swap when possible. See the above cases.
lesson learned I thought i can move out of div2 today but looks like i have to spend some more time here :)
4 2 1 3 4 0001 0001 0000 1100
I got — 1 2 3 4
после прошлого раунда упал кф, после этого упадет мой рейтинг))
нет
My soln to B got hacked, submitted 5 mins before end of contest and then got verdict after contest :/
Good Bye 2014. Hello 2015 World!
How I can solve problem B?
You have a graph with nodes numbered 1 to n. Each node has a value.
All you have to do is, within each connected component, sort the values.
After that is done for all the components, just print the values in nodes 1 to n :)
Website crashed as I was clicking submit button in the last minute, didn't come back up until the contest was over. My solution will most likely fail but I think Codeforces stability is a serious issue. Often during the competition I couldn't access the website for a minute or so, and it would crash from time to time.
On the bright side, the queue was doing impressively fine with 5000 users solving.
But this is the case in every contest I participated in last few weeks. Typically it's not problem for me, because I'm not submitting in last few minutes, but even without submitting I'm getting "too busy" message quite often...
I think this should be solved with high priority.
Is someone recording the contests (something like Petr's screencasts)? That could be good evidence...
Thank you for nice problems! And there were weak pretests at A and B so hackers enjoyed this round.
good buy 2014 == hello 2015 == hello newbie
dis like me pls
in Problem A is output case insensitive ?
I suppose yes, because standard yes/no checker in polygon is case insensitive.
thank you :)
Yes, outputs for YES/NO problems are generally case insensitive. (I knew this because I looked at Polygon, randomly browsing to its default checkers, and saw that there is a checker for "YES/NO problems, case insensitive".)
ninja'd
thank you, now everything is clear in my mind :).
Что такого в седьмом тесте задачи Е? Перевести ответ в рубли? Некоторые палочки замешаны в бетон и не падают?
In case I get a good place:
Hey, that's me!
How to solve problem D?
how to solve D???and what concepts to know for it??
calculate number of times an edge will be used in all the permutation. which will be equal to x+1*(n-(x+1))*(n-2) x=no of child of a node of the edge and divide it by nC3 and reflect the changes after each query
UPD Its correct.
You could also use the fact that E[X+Y] = E[X] + E[Y], coming to the fact that you only need to calculate \sum d(i,j), and calculating in a similar same way
The easiest way is to notice that expected value they ask for, is just: Sum of distances between all pairs of vertices(i,j), multiplied by 3 (because there are 3 Santas) and divided by n(n-1)/2 (number of pairs of vertices)
The only non-trivial part of the above quantity is sum of distances. It can be rewritten as: Sum of (for every edge e) cost[e]*frequency[e], where frequency[e] is number of paths in the tree that pass through that edge. Notice that if we know frequency[e] for every edge, we can easily answer every query in constant time by subtracting (change of cost of edge)*frequency[e]
So, the only thing left is to calculate the frequencies for every edge — and they are static (do not change in time). How to do it? The way I approached this problem is by making DFS from vertex 0, that returns number of vertices in the subtree below. Then you can notice that for every edge (u,v) the numebr of paths that pass through it is: (number of vertices in the subtree) * (N-number of vertices in subtree).
Great explanation! Thank you.
For the first part, why is it that we can just multiply the sums of all distances by 3? Doesn't this mean we will count the same edge 3 times? As in, we might be choosing the same edge 3 times and associating it with a triple, whereas the only "valid" triples are those that have 3 distinct edges.
If this doesn't make sense, I can try and clarify.
Good to see somebody enjoying my explanation :) (below, I will use E(X) to denote expected value of X)
We need to calculate
E( d(i,j) + d(j,k) + d(i,k) ),
where expected values are taken over every triple of distinct numbers i,j,k. Thanks to linearity of expected value (http://en.wikipedia.org/wiki/Expected_value#Linearity), we can rewrite this as:
E(d(i,j)) + E(d(j,k)) + E(d(i,k))
Since every of those three terms is independent of the remaining two, we can just calculate first one — the other two will be the same. Thus, what we need is actually equal to:
E(d(i,j)) * 3
with expected value (still) taken over every triple of distinct numbers i,j,k. But since k is absent in this equation, we may as well drop it, leaving taking average only over all PAIRS of distinct numbers i,j. Which is what I wrote above. I hope that is more clear now.
I submitted an answer for "D" (forgot to remove my extra cout's) but due to the huge queue, I got the judgement at the end of the contest. WA on pretest 1 on the correct logic. :'( . A bit harsh on late submitters?
Is the System test cases are weak in problem A? How this solution passed the system tests as it has no return word before solve function in solve function?
I think the last thing that was returned remains on the stack.
That template, omg :)
I think the explanation of andreyv is more acceptable. Though he did a silly mistake but he is a great coder in real life. He is an ACM ICPC regional contestant. How strong is his precode! OMG!
This solution invokes undefined behavior. Undefined behavior means that anything can happen, and in this case "anything" was to "work correctly". So, this solution just got lucky.
But the solution is not perfect. As far I think, It needs just more test cases to behave "incorrectly".
No, not in this case. It probably returns the value in a register(I have not read the assembly code generated for this program, but it is usually the reason why such programs work). So it always works properly on a particular machine(even though it has undefined behavior). Adding more tests cannot help here.
Yeah! I think you are right! He is really lucky one! Really amazing!! :)
I learned this type of coding form my Guruji sir Ananta Jalil (http://en.wikipedia.org/wiki/Ananta_Jalil). he can make impossible possible. just joking it was a silly mistake. :P
It looks like not only your code has flaws, links as well :-)
Ananta Jalil
now its ok :D
So many failed system test for problem B on test 15 :O
Has someone some smart insight why we can ignore book weights in problem C? I solved it, but I did a lot of testing before submitting, because I cannot see clearly why that works...
Well, after reading any book, for the next operations, the original position is irrelevant, because it is now on top of the stack. To ensure the minimum answer, put a book B under any book A read before it, because otherwise you lift book B an extra time, and when you get to reading book B, A is on top anyway. This is my reasoning (might seem unclear), and it doesn't use the book weights except finding the actual answer.
Because after a book is first used (the weight lifted at that time is independent of the book's weight), the number of times it'll be lifted is uniquely given (since the order of books above it at any time is uniquely given by the sequence of readings).
I more question related to our answer
Even if we count weight of the book, it is same problem, or not?
Eh, right. It's always just +constant.
No matter what happens, when we want to read book X, we are required to lift all books appearing between X in the reading order and max(beginning, last occurrence of X). If we place the books from top to bottom in order of their first appearances in the reading order, that it's easy to see that we'll be lifting only required books. Hence, we cannot do any better.
The easiest way for me to see this was to look at a single pair of books i and j.
If we only look at these two books, we will only contribute to our total cost whenever we "switch" which book is on top (i.e. if book i was on top, and book j is chosen to be read or vice versa).
Now, clearly, the optimal ordering is one where the first book chosen is put on top first.
Any idea what is the 22nd testcase on D?
While any individual member of sum (using your variable names) is up to 10^18, the whole sum is up to 10^23, so it's insufficient to store that in long long. I used long double for summation only (individual members were calculated as long long) and it passed.
The answer at any point of time is
where xi and yi is the number of vertices on both sides of edge i. You can shorten both sides by n - 2. After that both numerator and denominator can be stored in a 64-bit integer. So the only floating point operation needed is the final division.
1.5 hrs system test.
No submissions for problem G?? so hard or wrong??
It was the most wonderful contest in this year!!!
Petr will be the third target :)
You will be red too probably.
You are right, yaaaay! :D
Congratulations! :)
Thanks a lot, although it won't be long before I come back :)
Who was the 2nd..??
rng_58 Edit: Check this.
What was testcase 15 in problem B testing? Or: what was the common mistake of those solutions that failed systest 15?
I think it were test cases already discussed in this question... Or your code is working for those test cases ?
My code is okay, but I'm wondering about multiple solutions in my room that I didn't hack.
I hacked 6 solutions during the contest that just did the swaps greedily (if i<j, a[j] < a[i] and ok[i][j], swap). I guess test 15 is the first to fail that. There are lots of easier tests to fail that, of course (read above for lots of examples).
Is this rating contest?
http://codeforces.net/contest/500/submission/9317990 what is wrong with this problem B code
This is the easiest I found your code is not working for
Correct answer is
1 2 3 4 5your code returns1 3 2 4 5edit: wrong submission, let me check later
its giving 1 2 3 4 5 only
I went from blue to orange directly! WOW!!
:D :D :D :D :D
Nothing better than starting 2015 with 2015 rating xD
tourist would not agree
haha, you're right
I think taking 404th place feels better x)
404th? 404? Then, where are you? :))
4 поинта до красного. Обидно немного, хоть и не рассчитывал на красный цвет.
Petr > 3000 !!!
crossed 1800 mark for the first time :) ... new rating 1854
736-th place, +177 rating, how is it possible? I can't understand.
Because most of the top rated people participated, I think. I got 505th and got +366!
The inflation problem for combined division contests is even more serious than usual.
Here is my idea:
With division 2 contestants participating, it is easier for blue, purple, yellow and red to get a high ranking in percentile.
With many top players participating, the average rating is raised.
That's why division combined contests are mostly rating boosts.
Main problem behind such assumptions is that we actually don't know how rating works :D I've heard that formulas are made in such a way that sum of ratings after round does not increase; and there are also some "magic constants" to prevent inflation, so sum of ratings after round should even decrease.
I guess we should take a look at performance of these users who had their first rated event today — if their average rating is below 1500 now, then they may be one of the reasons of inflation; maybe some of them will not compete anymore, some other will just violate rules and create another account after bad performance today, and it's a boost for our rating.
I've already told MikeMirzayanov about problem with fast rating inflation few weeks ago, and i guess that after this round he'll agree that some changes in rating formulas are needed :)
red-colored before 2015! (although i feel like failed in this contest)
Same feeling bro.
I'm in the club, 2227 — same rating here! I feel like I did my best tho ;d
My first submission to D failed pretests because I tried to output a long double with printf("%Lf") (it does work on my computer, but not in MinGW due to a bug), is it possible to have it accepted? (it is not my bug)
Also, I do not understand this portal, is there any way to see all the recent posts? (I can only see all the recent comments in "Recent actions")
For what it's worth, you don't get penalty when your solution fails pretest 1.
Yes, I know. But I got less points than I would get if it was judged as accepted (I was unable to find any bug, so I have solved E and returned to D later).
Hello. Would you please explain me why in here:(http://codeforces.net/contest/500/submission/9326013) output isn't in double? I casted everything to double and I don't still know why this happens.
You should use std::setprecision or printf rather than std::cout when there is constraint about absolute or relative error.
Default "cout" of double always prints 6 significant digits. setprecision or printf is definitely required.
It was a pleasure to compete together with div 1's coders. Happy new year!
Под Новый год мечты сбываются! Ура!
Finished coding problem D just 1 minute after contest (wait long time until practice mode open, and submit it and got AC). Why I'm so slow to implement something, I lose my rating this time :(
Btw, happy new year.
Quite strange behavior of the testing system.
During systests this submission gets TL15: 9311938. The same code in upsolving gets RE15: 9326201. And in my local Unix system this buggy code runs correctly.
Small fix makes this solution Accepted: 9326316
Is there any explanation?
9326834 AC using MS Compiler.
The heap buffer overflow your code caused truly may lead to anything (even possibly arbitrary code execution?), including infinite-loop.
It may also be a little bit random due to "what is next to your buffer" on different runs, so the behaviour is not strange (though getting such TLEs is rare — Congratulations! achievement unlocked :D)
My 8th raising up contest in a row! :D
For some reason using long double instead of double gives extremely weird output for me but works on CF. Output in my PC for first case is:
-26815615859885194000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000.0000000000 -2.0000000000 -0.0000000000 -2.0000000000 -0.0000000000
AC code: http://codeforces.net/contest/500/submission/9326579
Any idea what the problem is?
Edit: Actually following line gives -2 as output:
cout << (long double) 3;
Happy new year. I am red coder, good surprise ^-^.
CONGRATS :D
thank you, happy new year, wish you the best
Я продолжил прошлогоднюю традицию менять цвет после написания Goodbye. Yellow color is a good New Year's present :)
Nice round. One question about rating calculation: is the weight given to a new contest > 50%? The rating changes seem fairly drastic in some cases.
Made a small mistake in problem D (using long long to calculate the sum) and ranked only 185...But very surprised when my rating changed...2138+=92... Good Bye 2014 and Happy New Year!
Имхо в контестах для двух дивизионов, таких как этот, рейтинг пересчитывается с слишком большой амплитудой. Было бы правильней добавлять 0.6 — 0.7 от того, что добавилось при текущих формулах.
Причем похоже это не работает для топов. tourist, Petr и rng_58 заняли три первых места (как они и должны были в соответствии с их рейтингами), при этом их прирост рейтинга был раза в 2-3 меньше, чем их же прирост с аналогичными результатами за прошлые раздельные контесты.
So happy to end this year with my highest rating. I would say that Problem E is beautiful even though I made many stupid bugs. There are many solutions with different approaches.
WoooW I am a Master.Thanks for a great round !
your graph is motivating :D
talking about motivating graphs — (http://codeforces.net/profile/netman)
Thank you really really thank you you've made my day :) XDD i cant be any happier
Why there isn't a Hello 2015 Round?? It will be nice
Let's have a rest.
Look at Gym.
Wow, I hadn't seen it, it looks wonderful, but why are them at Gym?? aren't them regular rounds?? 3 hours long and simultaneously, uhmm?? we will see... thnks for the advise, M
I'm very disappointed about my result :( Hope the next contest will be orgranized soon!
I gained +304 points!! Is there anyone gained more points than me?
ahmad_mamdouh +407 :P
And also looking at his performance in Good Bye 2013 — I bet he already wait for Good Bye 2015 :)
i gained +351 xD
Maybe the biggest gain ever: mrloser, +444!
wow~
giant rating_increase (dreamoon_love_AA) :P
YouAllHaveMeizi Master in the first contest
В этом году мне больше понравилось :)
Round______________raiting_before______place______delta
Goodbye 2013_______1578_____________1207_______-25
Goodbye 2014_______1584_____________913________+237
Есть такое:
Round______________raiting_before______place______delta
Goodbye 2013_______1483_____________1454_______-21
Goodbye 2014_______1765_____________482________+226
Rating is broken.
congratulation~
There is something very strange behind rating formulas. While we clearly see overall rating inflation (number of red coders increased by ~10% after a single contest...), top participants got very small rating improvement today. rng_58 have +4 and Petr have +6 today; tourist have +14 only, while he had +37 in Round #282 — and today he beat both #2 and #3 of world ranking, while both of them were missing round 282.
It may be that the formulas to avoid rating inflation affect very high rated coders much more than they affect the rest.
As you said, problem with such speculation is that we don't actually know how rating works. But we do know this update was completely broken.
Isn't it how it should be?
When more new people are registered in codeforces, there should be more red coders. If one can beat a half of red coders participating, he/she should become red too rather quickly. It would also be strange to make one yellow just because new people came. Imo, some percantage of colors needs to be maintained.
On the other hand, it should not be that difficult to get to the top. I guess one will need to win 30-40 rounds in a row now to claim the first place(assuming tourist does not participate or takes the second place in all the rounds) in the rating, and this is probably a mistake. That is, the rating of the tops should grow slower, or else they will become unreachable if they participate often (at least, until they are alive:).
We should probably pay less attention to the numbers being added to rating, and to look more at how consistent the percentage of the colors is. My guess is that it is reasonably consistent. The problem is that there are many people who are registering new accounts and do not participate later. Those people should probably be excluded from the rankings after some time, like it is done in topcoder, or even by resetting their rating, so that there will be no people who accidentally became red due to wrong formulas and do not participate any more. And the formulas should be revised to support the consistency within the 'active group'.
I don't see why inflating top ratings is inherently a bad thing if it reflects how much better they are from the rest of us mortals. If someone is beating tourist consistently, the rating system should ensure that that person catches up to him quickly. This can be done through volatility scores, for instance -- someone that is consistently performing outside of their predicted range should be allowed to have very large rating increases. The codeforces philosophy of making rating updates independent is misguided, in my opinion.
But I'm not entirely opposed to having small increases for top players. The point was more how drastically different the rating changes are in regular div 1 rounds and on this round, which demonstrates the rating system has failed to show any sign of consistency. Or you agree it is reasonable for tourist to gain more rating from winning #282 rather than Good Bye 2014 (with a lot more participants, and in which he beat #2 and #3)?
Why the rating formulas aren't public?? Is there a special reason??
Hm, when is the editorial ETA (estimated time of arrival)
This year it was "Accepted" instead of "Happy New Year"....
How could I print a long double with printf? I used %Lf and got WA, is %lf correct?
%Lf is correct. The problem is with Windows's C runtime, which doesn't recognize 80-bit long doubles.
The safest way is by far to convert to double first, then print using %f, and it's what I would recommend.
If you really want printf to print long doubles and you're not using MS C++, the compiler has its own version that seems to work, called
__mingw_printf. I don't guarantee that it's decently fast, correct or available though.BTW, will there be tutorials of the problems?
Yes, be patient.
I appreciate the efforts you put in to make this contest possible but without the editorials its all useless.
Editorials ... please.
.o. is writing editorial now. It will be posted soon.
"soon" is very vague.
In the past editorials have sometimes taken more than 4-5 days To appear. Be patient.
Take your time guys. A good late editorial is much better then an early bad editorial.
Sorry for the late editorial. It is published now.
There should always be a MAX pretest.
Most of the bad submissions would either timeout, or give WA in such case, whichever the problem it has. What would be the use of hacks then? Moreover, max tests would overload the servers even more — and I think Codeforces are already having troubles serving so many people at once.
We are waiting for a perfect editorial for Good Bye 2014 yet.
Sorry for the late editorial. It is published now.
Hello,
For B Question I first found the transitive closer of adjacency matrix then performed bubble sort greedily. Can anyone please tell me what is wrong in this? or any testcase which will give wrong result on this approach. My code is working fine for this Case also I am unable to see Testcase 15.
Hi, I believe your transitive closure code is wrong. Changing the order of the variables in the loops gets AC.
=)
h4eigfnw'rfgephgne f[mdasfmte;dgmflCa
Good Bye 2014,New Year Permutation: The test case 15 does not satisfy the constraint of the problem A[i][j] = A[j][i], kindly correct this. (When I tried submitting my code that uses only the upper triangular matrix I got wrong answer on test case 15 however when I submitted the same code with the modification to use the entire matrix for dfs it got accepted)
No, the test case is correct. I just verified it.
9399277
In this case, you just said that all test cases are wrong :D
Why can't turkeys enjoy thanksgiving?
Your solution was wrong, because it only checks vertices from i + 1 to j. The solution doesn't consider paths like 1-5-3, because 3 is not in the range [5 + 1, n].