Всем привет!
Через несколько дней (24 июля, 19:30 MSK) состоится Codeforces Round #193 (Div. 2), который был подготовлен мной. Те, кто уже вышел в первый дивизион, традиционно могут поучаствовать в раунде вне конкурса.
Хотелось бы поблагодарить Виталия Гриднева (gridnevvvit), Павла Кунявского (PavelKunyavskiy) и Дмитрия Иванова (DmitriyIvanov) за тестирование задач, координатора раундов Геральда Агапова (Gerald) за полезные советы и Марию Белову (Delinur) за перевод условий на английский язык.
Всем удачи и высокого рейтинга!
UPD1. В раунде будет использоваться динамическая разбалловка (см. здесь). Задачи будут расположены в порядке возрастания предполагаемой сложности.
UPD2. Опубликован разбор задач.
UPD3. Рейтинг участников обновлен. Поздравляем победителей, решивших 4 задачи:
Посмотрел результаты ваших пред. раундов. Готовлюсь к испытанию мозга)
I hope, the contest will be as good as round 192, I hope there is clear explanation and good picture like in the past :)
thanks :)
Ваши контесты заставляют подумать!и мне это очень нравится)
First , Thanks For Round Preparation. Second , Hope from you not to follow the rule of "The lower rate problem setter The higher problems difficulty" :).
Just to remember my previous comment ,for me the problems was very hard to understand
I guess the rule really applied for this contest. The problem statements were too much painful to understand. :/
A was badly written
Когда уже будет контест от Sereja?
Serega — Sereja
This is not about asking up-votes , because sincerely I could not care less about that, but I would like to ask the dear down voters, what is the logic of negatively rating my comment, and the one below positive ( nothing personal with the windoro, just an example ), when they almost say the same thing ?
PS:Now you have reason to down-vote.
Even I understand you. Don't try to search the logic — it's Codeforces, upvotes and downvotes appears randomely.
For instance, like now.
Sometimes I am surprised to find that some comments that have good/helpful content being downvoted... so I just give them an upvote to balance it out >:)
Wish everyone & myself a good rating~
I think there will be short and not mathematical problems
So many contest on codeforces. Feeling really fantastic! (Y)
time is no very good for me.
Чем выше рейтинг — тем легче задачи: закон Codeforces.
А наоборот закон работает?
хочешь гробовой контест подготовить? :D
Уже три идеи есть, но пока нет на них решений -(. Подожду, пока еще две придут, и "гробовой контест" готов!
Жаль что пересекается с Барселона-Бавария
Динамическая разбаловка — это заманчиво. Было бы интересно узнать, из каких соображений обычно принимается решение делать ее или нет. Предполагаю, что основная причина — расхождение мнений организаторов относительно сложности задач, но хотелось бы официальную версию.
Я, конечно, не огранизатор, но думаю, что задачи "не очень стандартные", поэтому и динамическая разбалловка. Ну и поэтому "расхождение мнений".
Ну... по поводу "обычно" я ничего сказать не могу, только про данный случай. Решение принято при причине наличия определенных трудностей в сравнении задач по сложности. Как сами понимаете, при статической разбалловке будет не очень хорошо, если вдруг окажется, что задачи разной стоимости сдало примерно одинаковое количество человек. Это сразу же вызовет шквал негативных комментариев. Вот во избежание такой ситуации мы и решили использовать динамическую разбалловку. Кроме того, разошлись мнения по поводу стоимости первой задачи проблемсета, если давать статическую разбалловку — это стало дополнительным аргументом.
Я так понял, что первая задача баллов на 1000 тянет?
Так считает Gerald. А я не согласен. Контест покажет, кто был прав :)
Ну а на динамической стоимости обе задачи в итоге будут по 500!
What is the dynamic score distribution ?
Task score depends on number of people solving the task. More in detail: link
good luck to all...
Slow testing again...
OK. I am not so good in English. But the problem description is too bad.
Protip: repost this in the English thread to get more upvotes
the problems don't look like div2 to me
Хватит ныть. Просто решайте. Потом всех протестируют.
25 страниц очереди, да вы гоните
18 mins have passed and i am still waiting for my judgement. Its not easy moving on to the next problem knowing your queued solution might be wrong.
is the problems statements (in English version of codeforces) written in English?
I can't understand the problems at all!
I give up the contest , one hour of contest passed and I still can't understand problems A C D E
I think so
Same here :(
I guess meaning of A . Luckily,I get AC. But I spent an hour and a half on a guess！！！
If the test is so slow, I think this contest should be unrated.
I hope it
Could someone tell me why my submit is in queue while other submits behind me is tested? THX~
First Codeforces was temporary unavailable, after that I submitted my solution, but it takes more than 20 minutes in queue and...
I am waiting..........to see my first submission status. I think this contest should be unrated.
My first submission is 14 min after contest but it still in queue. In current standing I see Egor accepted C 30 min after contest. The system test work down, i think i should sleep and ignore this contest
http://codeforces.net/blog/entry/8063#comment-138056
Oh common what's happening. Why did some people get answer for their submissions on B 30-40 minutes into contest and I didn't have an answer for 30 minutes after I submitted 15 minutes into the contest. What is more I got a wrong answer and instead of searching for a mistake 20-30 minutes in contest I have to search for an error 50 minutes after beginning. This is way to big loss of points ....
The language of each problem statement is very accurate but yet very advanced. While I appreciate the comprehensive context , I still think it's a disadvantage for those who are less skilled in English.
Yeah, "A student's life is fraught with complications. Some Berland University students know this only too well. Having studied for two years, they contracted strong antipathy towards the chairperson of some department. Indeed, the person in question wasn't the kindest of ladies to begin with: prone to reforming groups, banning automatic passes and other mean deeds. At last the students decided that she just can't get away with all this anymore..." It's just too hard to understand !!!
It took 10mins to understand each questions
Очередь слишком большая и она сущетвенно будет влиять на результаты. Я думаю, что контест объявят нерейтинговым. Зачем в претестах давать тесты на полных ограничениях? Это существенно тормозит проверку!
the level of these problems is very high compared to average Div-2 problems....wonder why??
This has been the case with recent div2 only contests.
Also, including all kind of tests in pretest has also become a routine. Most contests don't have many hacks.
+1 on the hacks comment!!
Посмотрите на количество участников — обычно в див2 учавствует не больше 2000), а сейчас 3500. Вот поэтому все так и тормозит.
2030. И это 2 дивизиона вместе, так что всё как обычно.
Apparently it is not guaranteed that being an excellent coder leads you to develop a reliable and fault-tolerant web application. Right, CodeForces?
Задача D: могут ли быть случаи кроме полного графа и набора одиночных "палочек" ?
Да. k = 2. UPD: Других случаев нет.
А можно пример для n > 3?
1 -> 2, 2 -> 3, 1 -> 3, 2->4, 4->5, 5->2. Везде двунаправленные ребра.
Ну как минимум еще бывает много маленьких полных графчиков размера k + 1.
А можно пример? Что-то не могу представить такую картину для k > 1.
Да, правда, я ошиблась, так не бывает.
В любом случае, верное решение (ну, одно из них) не зависит от того, как выглядит граф.
Объясните, пожалуйста, в чём некорректность такого рассуждения в С:
p-k приказов заведующая не выполнит. Выберем из всех приказов p-k с минимальными Bi (все равно она их не станет выполнять, так как недовольство ректората будет минимальным).
Из оставшихся приказов выберем k приказов с максимальными Ai (она эти приказы обязательно выполнит, так как p-k приказов, которые она не выполнит, мы уже выбрали, и, таким образом, у нее прибавится максимальное количество седых волос)
некорректность в том, что при равенстве седых волос надо максимизировать недовольство ректората, а при таком решении оно не максимизируется.
Вот! Этого-то я и не учел! :) Спасибо!
Так нет же, при равенстве Ai выбираем тот приказ, у которого максимальное Bi.
Или вы что-то другое имеете в виду?
Вы в начале уже выбрали приказы с минимальным B_i, там и ошибка.
Ну например: n = 3, p = 2, k = 1 (надо выбрать два приказа, один из них будет выполнен)
3 3
2 2
1 1
Вы сразу берете последний, а надо как раз его и не брать.
Одна проблема в том, что среди этих p-k выбранных вначале приказов и остальных могут быть приказы с одинаковым недовольством ректората — например, если у вообще всех приказов одинаковое недовольство. Впрочем, это не помогло мне сдать задачу.
As Killever said: "First , Thanks For Round Preparation. Second , Hope from you not to follow the rule of "The lower rate problem setter The higher problems difficulty" :)." 2 days ago, and has a lot of negative feedbacks! But he was right!
No one believes me :)
Спасибо большое авторам за хороший контест!
Также СПАСИБО всем, кто участвовал в Codeforces Round #193(Div.2)!
Вангую коменты о сложности раунда
for B problem, is it available to solve it other than use segment tree ?
You don't need a segment tree, there are no updates at all, so you can precompute everything you need. In my solution i compute F[i], which is what the answer would be for just one segment, using only the numbers from 1 to i. And then let's say that the begginning of the second interval is at Z. Then the current answer is Sum(Z,Z+K-1)+F[Z-1], you can simply check all possible begginings of B (from K+1 to N) and pick the one that has the largest answer. You can calculate Sum(a,b) constantly after linear precompute :) Hope i helped
thx for the answer, i will see your code and take my time :)
I am not expecting the system testing to start soon. Rather I'd go to sleep.
It's started.
Could someone give me hints about problem D? My idea is the following : We take a sile V, suppose there is direct passage to P siles from V. If P>=K, then we can pick subsets from those K vertices and the sile V will be their adjacent sile, since its mentioned that there is only one adjacent sile to a subset of K vertices, and obviously V is one. Every sile from those will be chosen in exactly C(K-1,P-1) subsets, and therefor an edge connecting V and some sile Z, will be used exactly C(K-1,P-1). Knowing that we can sum all the edges outgoing from one sile and then multiply it by C(K-1,P-1) , and doing that for every sile we get the total sum, now we have to divide it by the total amount of subsets of K vertices we can pick, which is C(K,N). However since P is different for each sile, i couldn't find a way to avoid using large numbers and therefor couldn't get my solution to work. Is that the proper idea or am i too far :P?
[C(A,B) = Binomial Coefficient]
I think it's correct, but use C(K - 1, P - 1) instead. I submitted the same thing with binoms in long double, hope it will be enough.
UPD: it is enough.
Yea, sorry, it's C(K-1,P-1), edited. However why does it work? I am surprised it works since binomial coefficients are usually really large... It will be interesting to see a proof why it won't overflow
I think if both the nominator and denominator are very large, precision errors appear only after the decimal point separator in the resulting number. But if they are small, then precision errors should be negligible in nominator and denominator.
The reason why the binomial coefficients do not grow large is that for this special graph, K can only be 1, 2, or N-1.
This property makes the binomial coefficients very limited in range.
Thanks, that's a very nice observation! I feel a little bit stupid now — my solution does not use any properties of the graph — it is just a brutal bignum computation but somehow it actually works, and it would (in a way) work on any graph.
Why?? How do you prove it?
I mainly got it from observation and then verified it with the test data. Indeed the K=2 construction is already quite tight in constraints. K=1 and N-1 are trivial. However I tried but could not come up with a proof for the other cases. Hope that there would be an editorial for that.
It's really depressing when I know it's enough.... I got the formula, did some preprocessing to check overflowing, and after knew it will overflow (I checked C(2000,1500)), I closed the problem. Poor me, LOL.
oh . how much i miss round 192 :D
Same code, 46 minutes in queue :(
Yeah, after this round! I never rate a round tutorial before I participate in the round. To muslims: I was fast, and azaan was in the contest time, I just participate in this round for 40 minutes. Excuse me, but it was the worst contest I ever participate in Codeforces.
in my country, the contest time is about 4-5 hours after azaan :)
just dont participate if you have other important things to do, and if you still insisted, you shouldn't say the worst time
remember, there is different place, different time, and different religion for others
I'm not talking about the time! I'm talking about the problems!
oh, sry, i misunderstood that.
he said:" I was fast, and azaan was in the contest time, I just participate in this round for 40 minutes"
You did not misunderstood.
How lucky am I! I passed E at the last second!
long in-queue is still the most annoying problem. this problem affects the ranks directly.
Forgot to mark one flag in solution to problem E, and hence I was outputting the correct string, but not lexicographically smallest, but just the one with the maximal number of '1's. Failed on test #169 (last test case). It seems that my luck was a little bit less strong than test cases this time.
How to do C?
To be honest,I don't think the problems description is pellucid...
How to do C?
Can someone clarify me this sentence in problem D :
"The insurgents studied the polygon plan and noticed its unusual structure. As it turned out, for any k-element set of silos S there is exactly one silo that is directly connected by a passage with each silo from S (we'll call this silo adjacent with S)."
How is it possible to this test case be valid :
5 2
-1 -1 14 3
19 -1 1
-1 6
0
Silos set S = {1, 2} (number 1 and 2 silo) have 0 adjacent silo, right? Silo 1 is connected with 4 and 5, and silo 2 is connected with 3...
Editorial was out 30 minutes ago, but no one announced it!
It's just my opinion, but I think CodeForces should balance the difficulty between Div 1 and 2 more. With solving 3 problems, you can place on top 20 in Div 2, and will be promoted to Div 1. In Div 1, with solving 1 problem, you can't stay longer and will be kicked to Div 2. I got this many times, do well in Div 2 but not good enough in Div 1.
My example for "easier" difficulty is TopCoder. In Div 1, you will be sent to Div 2 only if you can't solve any problem. Maybe the difference comes because the problem's count is differ (3 on TopCoder and 5 on CodeForces). Or maybe the competition here is intended to be more strict?
Just my opinion, it's not a bad thing actually.
I see
I can understand that English isn't necessarily the first language of everyone (it isn't mine either). But the problem statements today were simply too hard to understand.
The description of Problem A seemed unclear (e.g "if j ≥ 4 and the players who had turns number j - 1, j - 2, j - 3, made during their turns the same moves as player bi on the current turn, then he had drunk a glass of juice" — who is the 'he' referring to? The current player, or the players in the last three turns? Why is the whole description of the game in past tense?). The first paragraph of Problem C looks like it is fresh out of Google Translate (not that it mattered for solving the problem, but still).
I hate to be a grammar Nazi, but this really makes a difference in programming contests.
I agree. This problem took me a minimum of 10 minutes to understand, I honestly lost track. I initially thought it was 30 but then checked my submission time. For my first contest on here, this was really disconcerting.
Things that threw me:
Mind you, English IS my native tongue, which might actually have proved to be a disadvantage here.
you can learn russian as a workaround ;)
If only there were more hours in a day.
Actually the Russian statements were hard to understand too.
Примечательно, что сегодняшний топ-100 не пестрит вновь зарегистрировавшимися.
Horrible problem statement !!!
even though i submitted A a bit earlier than everybody else and hence wasn't in queue for very long time, i was still greatly affected by it....when i submitted A i was 7th in standings and i remained in the top 20 till about 30 minutes into contest, so i thought B must be very difficult as very few people had done it till then, and i tried to hack instead of attempt B....after 50 minutes into contest i had moved to 400th in standings, i was like WTF!!!
Codeforces, please do something to fix the lengthy queue problem! ur coders, for god's sake!!
Exactly... It really happens... Specially for the coders like us(Specialist, pupil & newbie). We have to keep an eye in the standing too. But when this situation occurs, it is really difficult to realize the difficulty of the problems. :(
Again, if I submit a problem but if it stays in queue for the long times, then it's hard to give concentration to another problem. And if I get "wrong answer" verdict after a long queue, it effects standing too. If I get this verdict few minutes ago, I can re-think my solution few minutes ago. Thus I could submit the problem again few minutes ago saving time penalty.
I think(like many others commented in this blog), contest should be unrated when "long time queue problem" happens. It will be fair, I think.
Hmm, I totally agree with you except the last paragraph of your comment. There are usually some technical problems in CF contests, like long queue or server down, but the circumstance is the same for all coders. So I think there is no reason to make the contest unrated because of "unfairness".
Ok... Lets see two cases :
Case 1: Usual contest. No problem of long time queue. Mr. A submitted a solution and the solution is ok. Mr. B submitted a solution but "wrong answer"(You know, it can be happened even for a Grandmaster too). He resubmitted it within one or two minutes. And this time it is ok.
Case 2: The contest like last one. Mr. A & Mr. B both submitted a solution and there is no verdict. After 10 or 15 minutes the verdict is given. Solution for Mr. A is ok and solution for Mr. B is wrong.
Now think, In last contest, someone got verdict even if he/she submit a solution later while the contestant had submitted a solution earlier didn't get any verdict. So there are many chances for some other contestants to enter between Mr. A & Mr. B in the standing.
I've told "unfair" thinking this. And in my view this two cases can never be same. In case 2, if there is no "long queue" problem, Mr. B could get a chance to resubmit his solution within one or two minutes. But for "long queue" problem, he didn't get this chance. Moreover, some other contestants also entered between Mr. A & Mr. B.
The descriptions are so bad!!!
The problems are translated well , but all problems are too long ! Shortering some problems will be better .
My idea in problem D is: Take an arbitary silo u and check the total danger of all possible S which are adjacent to u.
Let deg[u] be the number of silos which has a passage to u. Consider an arbitary passage (u,v) which has danger c. Assume that (u,v) appears in S, then the total danger increases by c. So we must find out how many times (u,v) appears, which is equals to how many S which contains (u,v). We must choose (k-1) other silos from the set of the other (deg[u]-1) silos, so it would be C(deg[u]-1,k-1).
Every passage from u appears exactly C(deg[u]-1,k-1) times, so let s[u] be the sum of the danger of all passages from u. The total danger of all possible S adjacent to u is: s[u]*C(deg[u]-1,k-1).
Then, the answer of the problem is: (s[1]*C(deg[1]-1,k-1)+s[2]*C(deg[2]-1,k-1])+...) / C(n,k) (C(n,k) is the number of all S possible)
The problem here is: how to handle the C(n,k), which should be huge?
I use Extended in Pascal and /C(n,k) by every s[u]*C(deg[u]-1,k-1). It's easy to see that C(deg[u]-1,k-1)/C(n,k)=k/(n-k+1)*(deg[u]-1-0)/(n-0)*(deg[u]-1-1)/(n-1)*...
It's not very precise and I got WA on test 21:
Output
1999999999
Answer
2000000000
Anybody has an idea how to handle this? Coding big number would be too complicated.
Just use Java: 4158861
Was a tough contest indeed as the problem statements were complicated to understand.Hopefully will get better problem statements from the next contest..
Сдал E в дорешке с +6. Делать строки с пробелами некрасиво.
I'm trying this problem:
http://codeforces.net/contest/332/problem/B
CF shows WA for the 1st test case.
Test #1
Correct output
And my code gives correct output in my PC and in Ideone too.
http://ideone.com/cTqaKy
But it gives
in CF!!!
http://codeforces.net/contest/332/submission/4171816
Can anyone please tell me where is the problem? :O