Привет, Codeforces!
22 августа, в субботу, в 19:30 MSK состоится 317 раунд Codeforces.
Раунд подготовили для вас сотрудники компании AimFund: Kostroma, riadwaw, yarrr, gchebanov, ArtDitel, SirShokoladina и zeliboba.
В каждом из дивизионов участникам будет предложено пять задач и два часа на их решение. Разбалловка будет статическая.
Благодарим Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Polygon и Codeforces, координатора задач Codeforces Макса Ахмедова (Zlobober) и Марию Белову (Delinur) за перевод условий на английский.
В первом дивизионе будет разыграно 200 футболок c символикой нашей компании. Прочитать подробнее про нас и наши вакансии можно на сайте aimfund.ru и в анонсе этого раунда.
Этот раунд подготовлен в рамках программы "5 лет CodeForces", как часть нашего подарка сообществу. С этого раунда на CF начинается серия thanks-раундов, которые посвящаются людям и компаниям, пожертвовавшим значительные средства.
Всем удачи и высокого рейтинга!
P.S. Для участников петрозаводских сборов в четверг в 8 вечера будет организован фуршет в Пауланер Бройхаус.
P.P.S. Разбалловка: 1 дивизион 750-1250-1500-2000-2750, 2 дивизион 500-1000-1750-2250-2500
P.P.P.S. Топ-20 участников второго дивизиона также получат футболки.
P.P.P.P.S. Друзья, с большим удовольствием сообщаем вам, что мы начинаем отправку наших фирменных футболок их счастливым обладателям по всему миру. Надеемся, что они вам понравятся, и вы будете носить их с удовольствием :)
Непонятно про дивизионы, скажите я могу выграть футболку или нет???? http://codeforces.net/blog/entry/19327
Я не разбираюсь в дивизионах подскажите пожалуста!!
Если ты до начала раунда перейдёшь в div1, то да, у тебя все шансы.
Если что, ты во 2 дивизионе.
А как перейти??? Если это ьесплатно то я не против
Возможно, ты сможешь найти человека, который за ночь сделает контест, договориться с Майком и поставит его на 21.08. Так что всё в твоих руках. Дерзай!!
Тут был неудачный сарказм.
Тебя кстати тоже
Почему нету футболок для второго дивизиона? Если подумать у участников первого дивизиона есть футболки по сравнению второго дивизиона. Если не дадите футболок тогда вообще не делайте раунд для второго дивизиона
А ты решаешь из-за футболок?
Нет конечно. Сколько человек участвует на втором дивизионе? Примерно 2500 — в топ 200 войти не очень легкая работа. И надо убрать фейк аккаунты — например участие минимум в 10 раунде
Что за бред? В div2 слабые участники,которые "не заработали" такой трофей(футболку).
И помимо тебя 2 дивизион будут решать около 4000 человек, которым не важно, дадут футболку или нет
Думаю получит футболку им не помешает
Это лишь обесценит моральную цену футболки.
Будешь ли ты рад если получишь футболку?
Нет, т.к. я недостаточно силён, что бы получать футболки на контестах
Мне кажется что любой будет рад награде за свои умения(и не имеет значение уровень этих умений)
Я например получив свою первую футболку был сильно рад(ВКОШП 2014), по правде говоря не одну, а сразу две =)
Мне кажется это довольно разумное решение. А то глядишь, и топ div 2 будут занимать ребята, которые ни разу не участвовали в соревнованиях.
Так почти на всех div2 раундах в топе 5 "ребята, которые ни разу не участвовали в соревнованиях".
Сначала хотел написать: почти на всех div2 раундах в топе 5 чёрные, но понял, что меня могут неправильно понять. :)
Черные... А ведь те кто не правильно понял твой коммент по сути являлись бы расистами, а значит ты бы получил от них респек(в виде +)
А если добавить условия -- участие минимум 10 раунде
Это глупо, меня до сих пор бесит что надо принять участие в 30 контестах, что бы получить тренерский доступ =(
Если бы футболки были бы и во втором дивизионе, то получили бы их скорее всего вторые аккаунты участников из первого дивизиона.
В чем фишка футболок? Они что-то в итоге дают?
Простите меня, если это глупый вопрос, и я не вижу чего-то очевидного, просто я не очень глубоко погружался в спортивное программирование :)
Если выиграешь 20 футболок, то тебя пригласят в тайное мировое правительство.
Просто для вознаграждения и нечего больше
Футболка для того, чтобы надеть ее лет через 7-10 и все знали какой ты старый :-)
If you in div2 and you want win T-shirt upvote this comment
You know if they do that nothing changes...
Cause all of div.1 programmers will join in div.2 by another account and not only you won't get any t-shirt but also you may have worse rank and rating...
Would be interesting with 10 extra T-shirts. For the first to solve each question.
Hmmmmm... :/
It's a good idea at all but again nothing changes for div.2 users i guess...(at least for problem C,D,E div.2)
Be careful. When someone says 10 extra T-shirts, It means first accept for each question and each division.
I knew that...
But the div.1 participants again will join div.2 and they have better chance to get t-shirts(also they can use 2 accounts and if they didn't success to get t-shirts in div.2 they will fight for top200)
Maybe you are right, I was not careful, I have to accept my mistake.
Really? Why do you think all the people are like you? Contests are for challenges and learning more.
this round is not combined. so "Top 200 participants" means?
Top 200 of Div. 1 according to the email they sent.
Is it rated round?!
Yes, as usual
Thanks :D
I think it should be combined division round :)
Sorry, but we haven't got appropriate problems for combined round.
Then, Top 200?
Top 200 will awarded T-shirts
Okay, but it's a bit sad. Combined rounds are great :P If you want, and if you have time for it, you can think about change it to combined round, for example taking some problems from div2, other from div1 and maybe add one additional problem? I think cf community would really enjoy it, am I right? :D
"Combined rounds are great" — no, they are not. Actually I'm very happy that this round will not be combined.
Why? I'm actually unsure on the matter and I think it'd be interesting to hear opinions from both sides.
Basically because there are huge rating rises and problems tend to end up unbalanced with too many easy ones for a red (that's a thing with normal rounds as well, but a gap between C and D out of 5 isn't as bad as a gap between F and G out of 8).
The authors of the round probably realised it.
yes,separate round gives more learning opp. to the newbies .
Am I the only one around here,
who feels that combined division round causes worse rating inflation.
My friend increases rating very heavily, even skips a color (blue to orange, skipping purple) on a combined division round.
I think the reason is that many who have been away from competitive programming for a while comes back for the combined rounds. Their rating will be at the level when they were at their top, but now they are rusty so they will lose points on average meaning that everyone else will gain points on average.
But because of rating inflation, those who comes back after a long time doesn't have very high rating.
Rating inflation only effect div 1 since the flow between div 1 and div 2 is so slow. That's another thing, rating can only enter div 1, rating never leaves div 1 except for combined contests. I wonder how TC handles this, they don't have combined contests right and the rating have been pumped from div 1 to div 2 for like over 10 years right?
I checked some old accounts now, most have rating curves roughly like this:
http://codeforces.net/profile/hos.lyric
You can't really see the rating inflation on them since most of them haven't gained anything the past 2 years even though they played continuously. If they had stopped for 2 years instead and then came back they would definitely have too much rating!
There were old legends about some company planning to run their round within the next month... :D
Looking forward for your round guys!
Div 1 users : "It's time to register for Div.2" :((
why would div1 users want to register in div2?
cuz when its not division combined , getting Tshirts in div2 is easier in for low rated div1 users :)
It's written that top200 in div1 will receive t-shirt.
oh sorry
Здравствуйте. Хотелось бы узнать, что это вообще за организация такая и чем она занимается? И какая конкретно роль столь уважаемых в мире СП людей в этом коллективе?
Тут имеется некоторая инфа.
Oh Yes,I think this contest is like Goodbye contest and All user Receive high rating
Футболки — забавно. Среди всех раундов Codeforces в в которых разыгрывались футболки я не получил обещаного приза ни с Rocket Fuel, ни с MemSQL, ни с Croc. Вы все просто по привычке обещаете футболки, или правда они есть?
А я одну футболку получил... На ней написан размер M, но по виду она однозначно S, на что организаторы только пожали плечами.
Помнится 5 месяцев назад вы писали
В течение месяца мы планируем провести свой раунд=)Возможно, это значить — как в Италии: ответ на "когда будет раунд" всегда остаеться "в течение месяца".
Упершыню бачу, каб ты размаулял па-руску. А так зразумеешь?=)
Упершыню бачу, каб ты размаўляў па-руску. А так зразумееш
ь?=)Видимо в Корее не очень хорошо с белорусским языком.
Вот не надо, у меня 7 было в школе)
Меня из-за тебя заминусовали, бульбоед
Обидно наверное...
Hello, what do you mean by "Scoring system will be static" ? what's the difference with the last round ?
"Scoring system will be static" it is mean, that scoring system won't be dinamyc (max scores for problems you will know before round)
Though its very obvious only Div — 1 will get t-shirt and they should get but it will more exciting for all Div — 2 coders like me if we get a chance to complete with Div — 1 coders . A collaborate Div 1 & 2 round will be more interesting for everyone and Div — 2 coders get a chance to win t-shirt also .
If it's combined, ((we will fight to win a t-shirt but nothing will happen as usual)) :D
I didn't perform well any of previous collaborate contest but i like these contest most because one can get the proper picture of his/her current state . So just the opportunity to participate with Div 1 coders is enough for me :D
when you want to give t-shirts. you must prepare one both division contest.(like round Codeforces Round 300)
There are 0 participants from div2 in top 300.
You can't say that man...
We have lots of phenomenons like this all the time
Now a div 1 once a div 2 coder :p you never know :D
thanks for preparing this codeforces round.
Come on! you gotta give Div2 participants something. Even a "Random x from top y" would be fair.
Where can we see the t-shirt's.
Вcем УдачИ ЗавТРА!!
Пысы чото я не нашел в правилах что жедать удачи плохо http://codeforces.net/help#q6
не трогайте больше мои коменты если сами правила не знаете!!!
Хитрец, закрыл восклицательным знаком + и -
Мы не имеем четкого Великого-Свода-Правил-Поведения-На-Codeforces.Твой коммент возможно удалили потому что ты прикрыл восклицательным знаком + и -Ну и что, что он закрыл + и -? Можно просмотреть исходный код — удалить текст поста — поставить максиману плюс)
Я ничего не прикрывал это кодфорса прикрыла. Я просто пишу текст а кодфорса должна следить чтобы он правильно выглидел и ничего не прикрывал
Вот почитай https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D0%B2%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B6%D0%B5%D1%80%D1%82%D0%B2%D1%8B
Я тебя не обвинял.
That's sad for div 2. Even "random x from top y" method would be great. But thanks for the contest anyway.
This would be a good time to get red + T-shirt!
Meh, I'm too slow for red...
Ah well, just one contest wrong.
I guess if they had 400 t-shirts they would give 1 each to both division's 200 toppers. But they only have 200 t-shirts.
If they give T-shirts to Div.2, we will be seeing loads of fake Div.2 users.
Ok, That makes sense.
how about allowing div 2 users to submit div 1 D and E if they solve upto div 1 C ? ( no extra time )
Yeah, surely, imagine how exactly that should look like and how big changes this will demand in whole system of Codeforces ( ͡° ͜ʖ ͡°)
if a div1 user makes a fake account for div2 contests it shows that he/she is more programmer than human!
i think being human is more important than being programmer!!!!
If you believe in God,... It's good to know that "**God is also a programmer**".
Never go full retard.
of course every programmer is a human :)
Depends on if you consider computers that can program as programmers.
We are all machines developed by nature and evolution :)
That is debatable. Prepare for downvotes, my friend :(
I think we are computers which run the programs written by God. So God is a programmer.
Will it be possible for you to provide T-shirts to some(your limit) top div2 rated contestants?
i'll buy an account gg easy
I don't know he got -30 by just proposing something. Seriously, what's wrong with these people? I honestly think that there can be very few people who can still perform in div1 top 200. And if you offer a very few T-shirts in div2 as he suggested, many coders in div2 can be challenged to perform well. It will be an inspiration for those who can win in div2.
There will be a lot of fake accounts from div 1, because it's easy to win div 2 than being in div1 top 200.
Yeah possible. But if one can win in div2 and solved same quality problems as in top 200 in Div1, Why not give a T-shirt? ( Since div1 and div2 doesn't have same problems, it is troublesome I guess).
Codeforces Round 300. No div2
Zeptolab code rush. No div2
Good bye 2014. No div2
In Codeforces Round 300, there are two div2 participants though :P. Imagine if you were one of those guys, and you don't receive T-shirt.
But I see what you're saying. It is not gonna happen 99% sure.
If you are good enough to get top 200 in div 1 then it takes just a single contest to become div 1 so they can only blame themselves for not doing the contest held a week ago.
If it is the unlikely case that the person have only memorized solutions and thus can't reliably get into div 1 then you could argue that they aren't worth a T-shirt even if they did well in this specific contest.
I mentioned that.
I did not find too many points.
непонятно, чем занимается ваша компания. Торгует на рынке? или только продает софт для торговли? хотя философия это тоже интересно конечно)
В анонсе по ссылке, указанной в посте, есть ключевые слова, по которым можно поискать информацию, и там даже есть некоторое обсуждение в комментариях. Если кратко, то вот этим.
I speek Croatian and Croatian is similar to Russian, can I also apply?
Good luck :)
No luck just skill
Good skill :) ???
Skill and accuracy and speed too.
Bless All!
233
I think I will solve 2 questions today
Not important how many problems you solve...
Wish you learn new things... ;)
wooow You are my hero :)
prince of Persia said : "you wan't to " accept " or you want to "solve" ??? " :D
or learn?
I think we can do it!
А где находится Пауланер Бройхаус? И как туда попасть :-)
отель Park Inn у ЖД вокзала, вход со стороны перекрестка)
ООО прям из окна квартиры видно :-)
Good luck everyone! :)
Is scoring the same for both divisions?
No, post fixed
Last one isn't usualy 2750, right?
сложно
Tough set. I guess those t-shirts are really special.
div0 contest :))
I think that's a great idea. One more division for the Gods :)
But it'd require to prepare 2 more problems for a contest...
How to solve 572D - Минимизация?
Ребята из Aim Fund, вы вообще слышали что-нибудь о простых задачах?
Когда несколько красных собираются — то получается такое
Did anyone else get WA on problem B test 10?
So many times. And I think I figured out why: you are supposed to take the least cost sell orders, and print them descending. I think :P
I coded A and B very fast but I faild at the same point, Damn my luck.
From what I see in statement ,in the order book for sells they are sorted descending.Even if you want to take first s lowest agg sells. Tricky statement.
Yes. Then I found that I hadn't noticed this : "A buy order is better if it has higher price and a sell order is better if it has lower price". After considering it, passed.
Then I got WA for some other reason, wonder what. Any tricky cases?
I noticed this with 1 minute left. I barely missed the submission window(was typing the cout statement once contest ended, last line of code -.-)
Ah, that makes sense. Such a shame that there was only one example.
Along with 4 failed attempts, yes (
По ходу много народу забило на контест, увидев задачу А :-)
А как решить?
Например, перебрать одну сторону, а для остальных посчитать число вариантов за O(1). Понятно, что если одна сторона зафиксирована — в геометрическом смысле надо найти количество точек в прямоугольнике, от которого что-то отсекли прямыми вида x + y = C. Это можно посчитать, поразбирав случаи.
Я это и написал. Отличная задача A на 130 строк
130...... у меня 24.....
Если ты хочешь увеличить ровно на l см, то ты это можешь сделать (l+1)(l+2)/2 способами.
Далее смотришь, сколько способов тебе не подходят. a+la<b+c+lb+lc
b+lb<a+c+la+lc
c+lc<a+b+la+lb
Я не уверен, но мое предположение было, что может не выполняться максимум одно неравенство. Рассмотрим первое например:
a+la >= b+c+lb+lc
a+2la >= b+c+l la >= (b+c+l-a)/2 То есть (b+c+l-a)/2 = x — минимальное кол-во см, которое надо добавить к a, чтоб получить вырожденный треугольник
Отсюда, кол-во способов, чтобы нарушить первое неравенство (l+1-x)(l+2-x)/2.
Аналогично рассматриваются последние 2 неравенства.
P.S. Сильно сбивчива мысль, ибо сам не понимаю, как это работает да и работает ли.
Я почти забил, но потом что-то сказало: "Ты что, тупой что ли, не можешь A решить???"
В результате, я заслал A за две минуты до конца... Фиг знает зачем:D
А я заслал ТЛьное решение за 10 минут до конца и потом сделал 11 неудачных взломов... Фиг знает зачем :D
P.S. Послал бы ты своё решение пораньше — и тебя бы попробовал взломать =)
Неожиданный поворот, div2 всё-таки получит футболки... =)
Не, ошибся, решило больше 200 человек.
Она очень просто решается от обратного, подсчетом количества неправильных троек. Фиксируем значение большего числа, получаем ограничение сверху на прирост к меньшим двум, отнимаем от ответа количество способов разделить этот прирост между ними.
I am impressed. Thank you for round anyway.
So light pretests for div2 C( My solution with O(n^2) complexity passed them, but I know there will not be such luck on final test. So I interested how to solve it faster?
How would be a n^2 solution for it? Couldn't even think about it!
Set A and B, and you can count how many possible C there are.
Will this get TLE?
For sure.
Just calculate the inverse instead. The total amount of ways you can increase is
(l + 1)*(l + 2)*(l + 3)/6, then you just remove all cases that don't work.You can't form a triangle with a set of numbers if one is larger or equal than the sum of the other two, so just iterate over all increases (O(n)) of a, b, and c and for each increase reduce the answer by the amount of ways to increase the other two such that their sum is less than the largest one.
Like this:
It is probably a stupid question, but why ~~~~~ ll d = min(l, a — b — c); ~~~~~
Its the amount of increases that you can distribute between b and c. Of course you can't distribute more than l and if you distribute more than
a - b - cthen the triangle becomes valid.Thank you. I learned a lot...
nice and simple solution thanks :)
How is it intuitive that there are no overlaps? When you're increasing 'a', you also increase 'b' and 'c' On a closer look, when you increase 'a', and hence increase 'b' and 'c', for those values always 'b'<'a'+'c' and 'c'<'a'+'b' But this wasn't really intuitive :|
Why the total amount is
(l + 1)*(l + 2)*(l + 3)/6. I am a little bad in maths.You should divide l indistinguishable elements to 4 groups: (increase a, increase b, increase c, do nothing). Using stars and bars technique we get
Thanks a lot riadwaw...
It's probably stupid, but could you explain how did you get formula for calculating total amount? Thanks in advance.
UPD: Same comment as above, sorry for duplicate.
suppose we increase a,b,c by x,y,z
fix z then the triangle ineq conditions reduces to let v1 = x+y,v2 = x-y
x+y >= max(0,(c+z)-a-b+1)
x+y <= l-z
x-y >= b-(c+z)-a+1
x-y <= b+(c+z)-a-1
subject to above contrainsts,we hvave to find all such pairs such that v1%2==v2%2 and v2<=|v1|
to do the rest, you need to analyse each interval properly.
the hardest contest i have ever seen.
Div1 — A today is so mind-blowing (harder than Div1-B IMO). Is there a simple way to solve it?
I tried iterating through all ways of adding an amount to a and then binary searching for the min and max values for b, therefore fixing c but could not get it to work. Is this a valid solution?
... And how to solve problem A (div. 1)?
How div1 B is solved by a lot of contestants it's very hard!! maybe a lot of them are going to fail system test?
div1 C is far easier than div1 B but they both have almost the same points!! I didn't submit my solution because of this reason
I can prove my solution at div1B and it's not that hard
div1 B is dynamic programming + some greedy approaces. Actually if you can notice, that elements, which absolute difference is taken are located in non-intersecting sequences. Also it is obvious, that elements in such sequences are neighbours in sorted array. So you should find the optimal way of splitting the sorted array in "blocks", minimizing the target function. In fact there is no more, then 2 different length of blocks are possible, so you can do DP in k^2.
Yes, this is the only observation required to solve this problem that there wont be more than 2 different lengths. Thanks for the explanation dude :)
Not exactly. C demanded a lot of stupid code, while code for B was pretty easy. C was not idealogically complicated, but not fun to code and multiedges stopped me for half an hour.
I have implemented it in simple way:
handle cases for variables appearing only once and variables appearing twice but in same sign and check which nodes are satisfied.
put all unsatisfied nodes in priority_queue such that the top is the node with least degree, each time pop a node from queue and select arbitrary edge connected with that node to make that node satisfied , then delete that edge(the other node degree is reduced by 1) , if in some moment degree of a node which is not yet satisfied is 0 then "NO" otherwise "YES"
didn't even have to check for trees or search for cycles
and you even don't have to handle cases you described separately.
You wont solve 1 C if you haven't seen the problem before since it is a huge research topic.
Also you wont improve if you care about points, better to fail and learn than to not try at all.
This particular case it's not a huge research topic and I think I solved it(or at list I have a good and proved idea, maybe some bugs but I have a good idea) without meeting it before
Oh, I read the problem wrong >.<.
Aparently, me too=)))I thought that you can have just -2 and 2 ore just one of them but you can have two of -2 or two of 2 which is very easy tot treat.I don't really understant why did they do that :(
Div1 — B is just DP: imagine we will build each subsequence {a(i), a(i+k), a(i+2*k), ..} seperately, and to make the result minimum, each subsequence must be sorted. We will have to build
cnt1 = n%ksubsequence of lengthn/k+1andcnt0 = (n-cnt1*l1)/l0subsequence of lengthn/k. Sort array a in ascending order. In order to minimize the result, there must be no pair of two subsequence that intersect with each other. So, this problem could be reduced to: finding a way to split array a (after sorted) into cnt0 continous subsequence of length l0 and cnt1 continous subsequnce of length l1. Notice that cnt0*cnt1 <= n, so a DP with complexity O(cnt0*cnt1) would work.You wanted to say cnt0*cnt1<=(k*k), no?
Wow, that's actually a solution I was trying to code during the contest! Can you please describe your DP a bit more detaled?
B was very nice and much easier than A, at least in my oppinion. I needed about 10 minutes to figure out the dp after I read it but I still have no clue about A :(
That CNF-2 (Div1-C) is easy but hard to implement (many corner cases)
If you compute the number of degenerate triangles and substract this number from the total one is very easy but it's hard to think.I guess this was the slution without corner cases
Did you mean Div1-A?
Yes I saw it later when I already had -30 contributin :)) but it didn't make sense to refer at div1C.There were 3 cases in my solution and I treated each of them in one line.Any way sorry for misunderstanding
It may be implemented without corner cases:)
У меня одного Диниц не работал в C и пришлось прибегнуть к бурундуковой магии?
Судя по результатам на претестах — у очень-очень многих Диниц не работал) У меня тоже, между магией и Хопкрофтом-Карпом я выбрал Хопкрофта-Карпа.
Хорошо хоть в претесты включили такой тест, а то было бы вообще трололо.
Upd. В следующий раз сделаю выбор в пользу магии :)
А зачем Диниц? Нужно же просто проверить, что в каждой компоненте связности есть цикл.
C/Div 1: Без потоков: Выкидываем все дизъюнкты из одной переменной. Дальше определяем любую переменную. Не более 1 дизъюнкта снова имеет одну переменную.
Диниц легко завалился =) С паросочетаниями сложнее, Куна и Куна с жадником завалили, а реализация от бурундука на таких графах работает за
=)
2E/1C was quite interesting I know what I was supost to do but I didn't have time to implement it, stil I liked that problem. Can't wait to see the editorial :)
Yeah basically the problem is equivalent to "Given a graph can you direct it's edges so that each node has an in degree at least one".
You can always do that as long as the graph is not a tree. And if it isn't finding a cycle and then directing all edges outward from that cycle does the trick.
But yeah I also ran out of time to implement this.
... as long as each component of the graph is not a tree ...
number_of_contests_with_only_D++ :(
Why would you write underscore at the end of variable? Awful.
it was not the only stupid mistake anyway :P
Actualy it is widely used convention if we are talking about nonpublic attributes of classes :).
НИКОГДА не стоит писать контест, находясь на отдыхе на море. Сначала под окнами закатили концерт, пришлось уходить в коридор. Там, разумеется, никаких условий типа стола, но фиг бы с ним. А под конец еще и свет вырубили, разумеется с вайфаем вместе.
таже фигня. Лежа на кровати в духоте. За окном играет местная музыка, и кошка орет.
So Cool. Congratulations to the winners.
And is this be standard from now on. New round every Saturday?
I got TL on the 6th pretest (Div. 2 C), and that in 2 minutes before closing... I... I could solve it... Arghh!
Anyway, it was a great round!
Me too, but it seems that there's a O(n) aproach, so we couldn't solve it actually hahahaha
Why is system testing stuck at 75%?
Check div2 — testing runs fine there.
I guess all graders are grading Div2 at the moment
Я думал, будет интересный контест от крутой компании с задачами из их программистской жизни, а дали какую-то унылую нежизненную математику. Дизлайк.
Ну и привет фиолетовый, мда.
"Тупая математика для дебилов!":DDD
я сюда кодить прихожу, математики мне на матане хватает
Я бы из матана и КФ выбрал КФ
Компания занимается алготрейдингом, в нашей работе много математики.
Ума не приложу, как задача А могла возникнуть в разработке какого-то из алгоритмов (сейчас прочитал Е и недоумеваю еще больше). Кстати, не включать в претесты лонг лонг довольно-таки некрасиво.
Межнар по математике недоволен тем, что в контесте много математики. So confusing :(
В A были претесты на long long, например 6-й.
Прощу прощения, если задел чувства кого-то из авторов, просто неприятно в очередной раз заканчивать контест с 0 - 1 задачами из-за переполнения int.
Задача А и какая-либо другая с этого контеста скорее всего не могли возникнуть в нашей работе, но мы дали те задачи, которые нам самим показались интересными.
Идея по E:
Факторизуем все числа. Если ответ существует, то для каждого простого в нём выполняется
или привычнее: 
, где gi — степень, с которой простое входит в ответ, ai — степень, с которой входит в i-ое a и bi — в i-ое b соответственно. Таким образом для каждого простого имеем набор остатков по различным модулям из чего по КТО можно восстановить (модули не взаимнопростые, это решается тем, что рассматриваются дополнительно остатки по всем числам вида pk, где p простые, на которые делятся bi) остаток от деления на их НОК, он же минимальная возможная степень, с которой данное простое войдёт в ответ. Возможно, к этой степени прийдется добавить НОК несколько раз, чтобы он был ≥ наименьшего из ai. Если для какого-то из чисел bi равно нулю, тогда ответ получается однозначно и его нужно просто проверить отдельно.
Ок или не очень?
Там нельзя независимо рассматривать простые.
А что насчёт такого решения:
Факторизуем все числа. Заметим, что в каждой геометрической прогрессии участвует немного простых(около 20 вроде бы), а так же что если множества простых для 2 прогрессий не совпадают, то решения нет. Теперь превратим каждую геометрическую прогрессию в набор арифметических. Отбросим более-менее очевидный случай 1 простого(правильно ли я понимаю, что большинство решений на нём падало?:)). Рассмотрим каждую прогрессию, как прямую в не более чем 20-мерном пространстве, если среди них есть 2 не параллельных, то пересечём их(или скажем, что решения нет) и проверим, что точка их пересечения принадлежит всем прогрессиям. Случай всех параллельных по сути эквивалентен случаю 1 простого — там нужно проверить, что сколько-то арифметических прогрессий имеют общую точку.
Похоже на правду, правда там будет пара нюансов в реализации
Где теперь fail? :)
Is it possible to change something in code after the contest has finished if it is only 1 operator , I mean switch = and <= ?
No.
yep change it and also you can submit it in practice :D
Why not? Every one can. But really do you think it will be judged again?
You can submit in practice after the grading finishes, but it will not affect how you performed during the competition.
Sure, why not? You are allowed to change up to 10 letters in your solution after the contest, so remember that your variable names should be short, because that way you will be able to do more changes.
haha :P
Some contest allow minor changes like that , that's why I asked
"Some contest allow minor changes like that" — yyyy o_0. Can you give me an example of at least one :P?
Мир сейчас тежол... Нафига такие сложные преколы придумывать...
А когда фуршет будет? Сегодня, прямо сейчас, или завтра?
В четверг
В Четверг вечерком.
Thanks for preaparing this great round, also thanks for t-shirt :D
t-shirt!
Я одна поняла, что в задаче Div1 C все переменные должны быть использованы? Хорошо было бы уточнить это в условии.
from 25 to 1300, such is life in codeforces.
Как поднять свой уровень математики? =)
решать математические задачи))
Such a sadness that nice Egor solution for problem D had minor bug :(
Двое первых из div2 решили лучше, чем двухсотый из div1. И один из них явно не фейк. Может футболку?
.. и может ну нафиг эти разделения, если победитель из DIV2 рвет половину участников DIV1? ))
The contest was great !
Really hope that Round 318 will also give 200 T-shirts.
typically how long does it take before the rating changes? it was a great (hard) contest! :P
15-20 min
could any body please say me what is the calculating way for first contesters?
starting rating assumed as 1500
okay but how the rating changes?
this and this may help.
Is it just me or does that picture with the formula seem like gibberish to anybody else?
А фуршет сегодня? Там чет никого нет :-(
I think the problem statement for Div 1 C is unclear. In the problem statement it is written
We know that each variable occurs in at most two clauses (with negation and without negation in total)
Therefore, I thought that when a variable appears twice, the variable and its negation will both appear. Fortunately, there is test case 3 that shows that this is not true, but I did not have enough time to update my solution when I realized that.
two in total means 0+2 and 1+1 and 2+0 , no ambiguity in that
I don't see how that can be understood like this. Moreover you have "at most" which suggests that sometimes it can be one (or maybe even zero?), so there will be no place for variable and its negation at one time.
Yes I know that there can be zero or one of the variable. What I meant is that the addition (with negation and without negation in total) sounded to me like we can get any subset of the set
{negation, without negation}
and thus in this case {negation, negation} is not possible.
Just a wrong character on code of A, and using 109 as inf on code of B but answer can be 2 * 109. Why I can't learn anything? :(
Late for the contest for 30 minutes, still got the T-shirt
what about editorial??
Screencast
If you wouldn't shed tear when I type long[] allCumulUpds = new long[n + 1]; instead of m + 1 you have no soul
Authors have soul, I am sure. I remember Bambi’s Mother Dies, Mufasa Dies, and so on when we watched this bug realtime in your submission.
What does it mean to watch a submission realtime if you are author of a contest?
Authors can open any solution during the contest. Also avaliable results at final testset.
I noted that in this problem n denotes number of edges and m number of vertices, what will lead to inevitable errors, so I declared them as "cl" and "var" what makes it much harder to misuse them. Second technique I use is to always declare arrays of sizes of sufficient constants, here 3e5+5. Any of those two things will prevent you from making this bug :).
EDIT: Heh, it seems that I messed up problems ^^. First remark is no longer relevant, however I guess second still stays.
But 2nd technique may lead to other bugs, like Petr described in one of his recent weekly reports
Hmmm, yeah, I guess you're sufficiently experienced to be acknowledged with both technique of making array of a 'just right size' and technique of making it big beforehand : D. Hence, my comment was probably anything new to you :P. However I use it like this for almost all my coding life and I don't remember any case when it caused a bug. Orrr maybe, concluding from what Petr has written it may prevent us from noting some bugs rather than cause them — I guess there is some tradeoff (pretty much like always). However I am a guy really prone to mistakes you did this time, so I will stick to my method.
What tool do you use to parse contest problems ? Is there any github repo ?
I use CHelper
Will check it out, thanks.
Aha ..T-shirt! It's my first time to receive gift from Codeforces.. Here is my question. When will the T-shirt be sent? I can't wait to wear the lovely T-shirt!
Can someone provide an editorial? Thanks
As always you may ask specific questions in comments. Now part of tutorial is published
With respect to C I would be very interested in a discussion of how to implement the problem well specifically the part of finding the cycle in the component of the graph and then directing all the edges.
If one attempts to find the cycle with a DFS one processes nodes until an edge is found between the node we are currently processing and a node we visited earlier.
It is very unclear to me how to write the recursive function so that once we find such a cycle we can exit the recursion and along the way store the cycle in some sensible way.
What I do for this is maintain a DSU while adding edges, and then when an edge is found connecting two vertices in the same set, we know there exists a cycle from one vertex on this edge.
Then, we can run findcyc() from such a vertex, keeping the current dfs stack, until it reaches the starting vertex again — which it must due to the earlier argument. Thus, our cycle is isolated. Another nice thing here is that we can direct the edges along the cycle in findcyc() itself.
Next we dfs() from every node on the cycle to direct the edges. 12656691
Any other approaches?
Come to think of it with the approach you describe (which I think is the nicest one) you don't need to find the cycle and then separately perform DFSs at all.
If you start the DFS from the node on the cycle you can simply direct all the edges (that haven't been directed yet) away from the current vertex. This way every vertex has an edge pointing to it (the one that caused them to be thrown on the "stack") and eventually some node also has an edge to the starting node.
So you only need one DFS per component assuming you can start with a node on the cycle.
Not really proud of that code, but maybe you can get an idea how to do that by dfs: http://codeforces.net/contest/571/submission/12659401
Condition on finding cycle is
that means, I have visited that neighbour earlier and I'm not looking at the edge I used to be in current vertex.
My dfs returns int. "If dfs returns nonzero value than cycle exists and returned vertex lies on a cycle and I have already assigned logical value to it". Whenever recursive call returns nonzero I stop executing and pass that value higher.
You may also appreciate version with exceptions http://codeforces.net/contest/571/submission/12667656 :P. Finding a cycle can hardly be called 'exception', but exceptions can help you unwind stack of function calls without passing intermediate values.
This is my solution: (I use outgoing edge instead of incoming edge) 1.Keep removing vertices with degree 1, and assign its only edge to it.
2.Now there are only vertices with degree>=2. Find a vertex which has no outgoing edge. Starting from this vertex, find an unused edge and pass through this edge. Now we find an outgoing edge for this vertex. Keep doing this to the vertex on the other side of previous edge until a vertex which already has an outgoing edge is reached. It is guarenteed that we can always "go out" from a vertex with no outgoing edge because there are at least two edges connected to it.
3.If there are still vertices which has no outgoing edge, do step2 again. Otherwise, orient all unused edges arbitrarily.
Screencast with Burunduk and hearthstone :D
P.P.S. Top-20 div2 participants will be awarded t-shirts.
So genius that say this after contest :D
Guys looked at the results and understood that participants from div2 earned T-shirts too, cause solved many problems. Why not?
And now in next contest we'll see div1 guys playing with fakes in div2, hoping for such P.P.S. once again :)
Add simple rule that he/she participated minimum 10 contest
O_o
So new users can't join the contests???
Bad idea at all...
Usually who win div2 — are div1 users. New user can't win contest or get top-20 in one contest.
They can if they have done competitive programming in other places like icpc or tc.
Ermm, having reached 3rd place in div 2 on my first contest, I beg to differ. And if you look at the standings, there are 4 more unrated people in the top 20.
First codeforces Tshirt :)
always getting wrong answer on 10th test case.iam unable to figure out .can anyone please help me :) .the link for the submission (http://codeforces.net/contest/572/submission/12670760)
10th test was about wrong S and B priorities. You should write out B with bigger price and C with lower price.
That P.P.S made my day... :3 :D !!! Thanks all... !!!!
Было бы хорошо, если бы всегда нерейтинговые топ20 див2 получали по футболке от организаторов.
"С этого раунда на CF начинается серия thanks-раундов". Такой вопросик: а сколько их будет?
Если предположить что 10000$ = 1 thanks round -> 27498$ / 10000$ = 2 rounds
Вроде бы было 5-6 донатов на 1000$, то есть примерно столько. Но когда я прочитал "В вашу честь будет проведён раунд", я думал, что готовить его будет CF, а не компания-спонсор.
Just asking out of curiosity, did you consider using the new dynamic scoring system with 250 points gaps?
If you did, what was the reason behind choosing the standard scoring system instead?
In short, all of us do not like the dynamic system, so we have not even considered it =)
Why? So far, according to my contest experience, there were situations that dynamic scoring would have given more appropriate scores rather than standard but have not seen the same thing for the opposite. The only problem that dynamic scoring might cause was certain formulas that can lead to different points just because of 1 submission, but now it's only 250 points which is fairly good I think. For instance, it could have fixed the point distribution in this contest too, esspecialy for A-B and C-D.
I've no doubt that all scoring systems common feature is fairness as far as it's same for all the contestants. But it would not hurt to make things better, right?
Contests are supposed to be fun and dynamic scoring makes them less fun for me since its stressful not knowing how much the problems are worth.
Well for me, it's more stressful when you do not know if the problem you are working on worth it's points.
Then why do you gamble by skipping problem A, B and C? Usually A gives the most score per effort, then B, then C, then D and lastly E, so doing them in any other order is a risky gamble.
Edit: While on the other hand with dynamic scoring the effort per problem ratio can be all over the place, usually A gives the least score per effort in those contests meaning that you must try to game the system instead of just focusing on solving problems.
Because solving just A and B is boring and I want to give more time to harder and more interesting ones. If I would have started from A and B, there would be no time for D at all. The question is if you have the power to lead all of the contestants(by setting scores) would you encourage harder problems or not?
Since they can set the scores however they want they obviously want the easier problems to be worth it, if they wanted the harder problems to be worth more they wouldn't set A and B to be 750 and 1250.
Oh, you're the first person I see which doesn't hate dynamic score :P. I like to know what is the value of a problem beforehand. Dynamic scoring often can lead to weird strategies like skipping A and B, because they will be worth 250 and 500 pts or sth like that. What matters is also strategy, not only problem solving skill and you have to admit that choosing D as only problem to solve was not best choice =). I guess that probably it was twice that hard to solve D than ABC combined, so what you did was probably harder than what I did, but my place was significantly better :P.
I like dynamic scoring too, and I believe it would be more fair if it was applied for this contest , because how can a problem which is solved the most(problem B) have almost the same points as the problem solved by few people(problem C)!!
Haha, that said just after stating that C was far easier than B http://codeforces.net/blog/entry/19863?#comment-247365 XDDD
first problem I tried during the contest was B , but I couldn't solve it ,I thought it's harder than usual div1 B problems, so I moved to C , the idea came to me very quickly but it took me some time to code it, after finishing I saw that B was solved by a lot of contestants even more than A , and C is solved by low number of contestants so I decided to give up.
I posted that comment immediately after the contest finished I was trying to express my surprise of number of people who solved B , I didn't know that I'm only missing an observation to solve B , it wasn't that hard as I thought.
in the end, a lot people solved B and that's what matters so it should not have that much of points
Just 329 people solved B, it was way harder than your average B problem. Also I really dislike contests where the easiest problem is too hard since then lots of people chickens out and it gets hard to gain rating.
Разбор будет?
Зачем? Задачи вроде простые.
P.S. В самом низу анонса разбор.
Возможная причина №1: Для человека это не такие простые задачи
Возможная причина №2: Человеку интересно сравнить подходы решений
P.S. Всегда ваш Капитан
Это был сарказм.
Спасибо за этот замечательный раунд. Задачи просто супер особенно С и D, в которых нужно много думать (например, мне пришлось думать больше, чем идёт раунд)), но зато пишутся они очень быстро. Наверное это наибольшая похвала составителям, если участникам захотелось докрутить задачи после контеста.
just a friendly reminder, it's analysis not analisys (last link of the blog)
Thanks
Is it normal that I got no message, e-mail or anything regarding the T-shirt? (I got 3rd in div 2.) I added my address details to my profile the day after the contest. This was my first time competing so I'm not really sure how things work around here..
Only for Top 200 Div.1 users.
At the end of the post, added after the contest ended: "P.P.S. Top-20 div2 participants will be awarded t-shirts."
When will the T-shirts be sent?
Will the t-shirts be sent to other countries like China?
I still haven't received my T-shirt. Is there any information on when they will arrive (in the Netherlands)?
I don't know, but we will send it to you.
I still haven't received my T-shirt. Will it still be send?
Hi, all T-shirts have been sent as I know.
Was that long ago? I think my address is (and was) up-to-date.
Hi , even I haven't received my T-shirt please look into it
I too haven't received it yet.Is there any mistake?
Finally, just received my T-shirt today! Thank you Aim Fund, Thank you MikeMirzayanov :D