Здравствуйте, уважаемые участники сообщества Codeforces!
Начиная с Codeforces Round #327, я буду координировать подготовку регулярных раундов и прочих контестов, которые проводятся на платформе Codeforces. Обещаю приложить максимум усилий, чтобы улучшить качество подготовки контестов, хотя это и будет проблематично сделать — Zlobober установил высокую планку. Давайте ещё раз поблагодарим Максима за хорошо проделанную работу!
Завтрашний раунд проводится на задачах Московcкой городской командной олимпиады по программированию среди школьников. Пусть вас не смущает, что это школьное соревнование, — среди участников есть золотой призёр IOI 2015 и несколько кандидатов в сборную России этого года, поэтому мы постарались сделать все задачи интересными, а некоторые ещё и сложными. Уверен, что каждому из вас должна понравиться хотя бы одна задача предстоящего раунда.
Задачи были подготовлены коллективом московских авторов в составе (список пополняется): Zlobober, romanandreev, meshanya, wilwell, glebushka98, timgaripov, thefacetakt, haku, LHiC, Timus, Sender, sankear, iskhakovt, andrewgark, ipavlov, StopKran, AleX. Руководство подготовкой осуществляли ваш покорный слуга GlebsHP и председатель жюри олимпиады Андреева Елена Владимировна.
Отдельно благодарим Delinur за перевод условий на английский язык и stella_marine за вычитку.
В каждом дивизионе будет предложено для решения пять задач, разбаловка будет опубликована позднее (не будем нарушать эту традицию).
UPD. Время раунда. Обратите внимание, что во многих странах мира этой ночью переводят часы, а в России не переводят — не пропустите случайно раунд :)
UPD2. Обратите внимание, разбаловка как бы намекает, что надо прочитать все задачи! Div1.: 750-1000-1250-1750-2500 Div2.: 500-1000-1750-2000-2250
UPD3. Результаты раунда и разбор будут опубликованы позднее, когда завершится официальное соревнование.
UPD4. Системное тестирование завершено, доступны окончательные результаты, открыто дорешивание задач. Поздравляем победителей в первом дивизионе:
UPD5. Появился разбор.
Nice... :/ A school contest that lots of students can't join in it...Cause we are at school that time :/
Your profile picture is dank my friend.
On Sunday o_0?
Schools are open Sunday in Iran.
TIL
in Egypt also schools are open in sunday
Good luck!
Scoring distribution?
Also, gotta love weekend contests. ;)
What's the duration of the round? It is 2 hours on the list of upcoming contests, but the email says it will be 2.5 hours.
My bet — somebody forgot to change contest duration in that email, and 2.5 stays from previous round :)
Welcome aboard! Great deeds await us.
Good luck GlebsHP
and Good Job dalex !
It will be good job if I bring back my yellow.
Actually I'm surprised that nobody noticed that, I was just looking through recent actions and saw that Gleb had edited Mike's blog...
Now Zlobober will enter the contribution list. BOOM straight to the top.
I think that he will not enter the list for awhile
"Уверен, что каждому из вас должна понравиться хотя бы одна задача предстоящего раунда." Ловлю кароче на слове. Если мне не понравится ни одна, то вы можете искупить свою вину подписавшись на мой математический паблос http://vk.com/turingprekols .
I realise that number of contest that made in this time increase why??? some of us have school and others have a work some times i missed lectures to enter the contest i think it is good to make it around 7 , 8 o'clock after finishing our work in order not to be busy
Tomorrow round will be held using the problems of Moscow team olympiad for high-school students.
Obviously, at the same time.
thanks for clarification I think that the contest made by codeforces XD
How come AleX's contribution be minus when all his blogs and comments got no downvotes?
Some of his comments in Russian got negative votes.But I still think it's unreasonable because most of them got positive votes.
Sorry, I just know that comments in Russian won't show in the English format. Thanks for the answer.
Maybe he deleted some of his blogs...
http://mirror.codeforces.com/blog/entry/8963 I think this explain why
In the last three contest my rating is decreased .I hope this time my rating will be getting up :D
Hope for the best :D
Heartily Welcome & All d Best GlebsHP
Thank you Zlobober for the great job u have done! :-)
Now it is time to rest,but start to brain storming. Good Luck for every one.
very long questions :(
Omg it started on 9AM not on 10AM local time.
Ну и как искать максимальное независимое множество в графе сравнимости?
Как этот граф нормально строить в таких ограничениях? Стандартная штука с n типами разделителей, кажется, не должна влезать.
Я Ахо-Корасиком строил за O(|S| + N2). Идея в том, чтобы хранить терминальные ссылки на вершины, в которых кончаются строки, а потом пропустить каждую строку через АК. А потом пытался сделать какую-то жадную фигню. Конечно, не получилось. 13850184
Так что насчет графа-то?
Я умею размер ответа по теореме дилворта вроде. Написал тупость за n*len, получил локально тл и забил на задачу.
https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%94%D0%B8%D0%BB%D1%83%D0%BE%D1%80%D1%81%D0%B0
бесит задача(
А ответ-то как восстанавливать?
Становимся в верхние элементы цепей, если из какого-то из них достижим другой, спускаемся им вниз. Это O(n3) в худшем случае, реально сильно быстрее наверняка.
Ужас, а слона-то и не приметил.( Вот так доказываешь в кружке по математике теоремы, а задачи все равно не сдаются!)
По теореме Кёнига; собственно в статье на вики это написано.
Восстанавливать можно абсолютно также, как и в задаче о поиске максимального независимого множества в двудольном графе: после поиска парасочетания обе доли разбиваются на достижимые и на не достижимые. После этого из этих четырех множеств легко получить ответ.
Так а как его строить кроме как Корасиком? Я написал, получил ВА8 из-за какой-то дебильной баги, но на претестах работает 2600мс и еле-еле упихивается в ML, на систестах наверняка бы и упало. Собственно, так почти у всех, кто сдал эту задачу, и произошло
Скорее всего, никак. Если бы ограничения были более дружественные, можно было бы суфф структурами. А что плохого в Ахо-Корасик?
А как учитывать вершины-концы строк, достижимые по суффиксным ссылкам?
Я просто сказал, что учтем самую нижнюю достижимую по суффссылкам, а потом в конце за n2 все обработаем: если i выше j в дереве на суффссылках, то добавим соответствующее ребро
Спасибо, зашло.
Не понял вопроса.. Можно подробнее?
Если для каждой вершины, посещенной в Корасике, искать все терминальные сверху по суффиксным ссылкам (если хочется в графе проставить все-все ребра), то это будет O(len * n), что уж точно не пройдет по времени
Ну можно преподсчитать для каждой вершины term[v] — ближайшая достижимая терминальная по суфф ссылкам, а потом обойти терминальные в прядке уменьшения длины и cnt[term[link[v]] += cnt[v]. Ну и понятно, что когда строку пропускаем через автомат вместо cnt[v]++ делать cnt[term[v]]++. Чтобы в итоге чисто с терминальным поддеревом работать. У него уже размер небольшой.
Да-да, я что-то такое делал: предподсчитал term[v], потом когда скармливал строки, просто ставил ребро из i в stringNum[term[v]], а потом еще какие-то ребра добавлял, как ниже написал
Плохого в том, что, лично у меня, на систестах в ТЛ скорее всего бы не запихалось. Возможно, не совсем аккуратная реализация, наверняка, если суффссылки проставлять не рекурсивно, будет быстрее, но это уже какое-то запихивание
Ну тут уж напрашивается вопрос о том, что же автор хотел сказать такими странными ограничениями на длину входа.
Такая длина ввода была выбрана нами для того, чтобы суфф массив за
не проходил, а также чтобы отсечь решения за O(nL). Авторское решение было с Ахо-Корасиком, написанным с помощью BFSа. Но так как TL был поставлен как минимум в 3 раза от авторского(а у ikatanic вообще в 6 раз быстрее ограничений), то должна проходить и любая рекурсивная реализация.
А зачем отсекать суффиксные структуры в этой задаче?
Потому что смысл в очередной задаче вида "о, а давайте напишем любую суфф структуру и не будем думать"? А так красивое и простое решение, чтобы придумать которое достаточно знаний ЛКШ группы B-A'.
то есть, давайте напишем Ахо-Корасик и не будем думать — хорошо, а любую суф структуру — нет?
Я уж молчу про воспользуемся "общеизвестными" теоремами из теории графов и не будем думать.
Эм, для начала задачу нужно решить. На наш взгляд решение данной задачи очень красивое и нетривиальное, состоит из двух частей (построение графа и применение теоремы Дилворта). Например наши лучшие школьники почти с нуля придумали вторую часть решения, но граф строили за
, потому что не придумали как быстрее. Не понимаю, чем вы недовольны — для вас задача слишком простая или слишком сложная??
PS Мы специально не валили никакие линейные структуры данных. Если они у вас работают долго — неудача.
Да хорошая задача. Кому-то просто надо попробовать порешать задачи НЕ на строки, а не бомбить с того, что в Е просят Дилворта =)
====================================================
Ну, моё недовольство касается двух пунктов.
Отсечение суффиксных структур, обоснованное по сути тем, что авторам они не нравятся. Вот вы говорите, что не отсекали специально линейные структуры, а у вас есть хоть одно решение с ними? Рискну предположить, что нет, т.к. специфика их такова, что константа как по памяти, так и по времени будет минимум в два раза больше при той же ассимптотике.
Существенный упор на "широко известную в узких кругах" теорему. Ну, туда же идут задачи, которые совсем тупо решаются если применить БПФ, дерамиду, автомат
или прочие штуки, которые все умеют, а я — нет.Ну так пусть перестанут их давать на кф :(
Третий контест уже с последней задачей про строки за последнее время! Вот отвлекаюсь на них и не могу насладиться нормальными задачами.
Чувак, ну признайся уже, тебя бомбит, потому что оказалось, что есть задачи на строки, которые adamant не может решить =)
Ну я так понимаю, уже независимо от того, что я напишу, тебя будут плюсовать за остроумность и думать, что у меня просто бомбит?
=========================================================
Вообще удивлен, что к этой задаче есть претензии.
Почему отсекать решения за
и O(Ln)?
1) Они асимптотически медленнее. Кажется, все спортивное программирование об этом.
2) Хрен с ней, с асимптотикой — они реально, блин, медленнее в разы!
Почему мы не сделали так, чтобы линейные решения с суфструктурами проходили? Занятие весьма бессмысленное :) Есть решение, которое гораздо проще по набору используемых техник и которое в разы быстрее. В любой задаче есть практически неограниченный спектр решений, совпадающих с предполагаемым по асимптотике, но имеющих бОльшую константу. Если вы считаете себя сумрачным гением некоторой техники, которая позволяет писать несколько более медленные, но гораздо более клевые решения, это целиком и полностью ваша ответственность, чтобы ваше решение уложилось в ограничения; Заколачивать гвозди микроскопом тоже надо уметь.
Наезд на теорему Дилворта вообще носит характер "вот козлы, дали задачу на теорию, которая мне неизвестна", тут комментировать не буду.
Одна из самых клевых задач за последнее время, имхо.
PS Мы на прошедшем четвертьфинале совершили ровно такую же ошибку из разряда "горе от ума". Ну захотелось нам использовать подъем сетов по суффиксному автомату вместо префикс-функции, ну словили мы ТЛ. Пойду-ка я наеду на жюри, что такое клевое решение не прошло :)
============================================================
2) Ну проблема не столько в том, что там теория, которая мне неизвестна, сколько то, что её применение безыдейно. Поправь, если я не прав в этом утверждении.
Я, кстати, не зря упомянул БПФ. Была вот недавно div. 1 D (кажется, твоя?), которая совершенно тривиально сводилась к нему. Ну, БПФ мне было известно только в самых общих чертах, я скопипастил его с е-макса и сдал задачу. Тогда мой наезд на БПФ был столь же бессмысленен?
1) Такое ощущение, что здесь снова откуда-то убеждение, что это просто моя личная обида. Да нет же, я строковую часть вполне спокойно написал с помощью АК (и я даже считаю, что это наиболее клевое решение из возможных). Просто я внутренне нахожу отсечение суфф структур неправильным, ведь идейно по сложности решения с ними не сильно отличается от такового с АК, может даже напротив они сложнее. Для меня это что-то в духе того, чтобы зачем-то отсекать
от 
(т.е. несжатие координат от сжатия в ДО).
Существует суффиксный массив за линию, утверждается, что он работает с хорошей константой и маленьким overhead-ом по памяти. статья и реализации.
Авторское решение с Ахо-Корасиком ест 200 мегабайт памяти, по-этому ML был 512. TL был выставлен более, чем в 3 раза от авторского. Если вам приходится так все упихивать — то возможно вы что-то делаете не так...
After Mathematics and Physics problems in codeforces rounds...
coming soon: chemistry problems in codeforces
I hate math and physics problems too but the one about Chip and Dale is easily solvable by binary search + calculating distance between two points.
I had to solve triangle using cosine theorem and then use ternary search (search for minimum of function). Does the problem have simplier solution?
Here is my solution:
if it is possible to reach to the destination point at some time T1, then it is possible to reach there for any T2 > T1, since you can just stay where you are (you are always faster than wind so it can't force you to leave your position). So with binary search you just have to check whether it is possible to reach the destination in exactly T seconds. To check that at first calculate the position to which wind will bring you if you will not move at all and then check whether you can get to destination from that point in T seconds (sqrt(dx * dx + dy * dy) <= T * u).
LOL, me so noob %)
I've solved the triangle and found O(1) solution for the case wind doesn't change, and then used search among angles of movement before wind changes :)
Also, I'm quite sure, that it is possible to find O(1) solution for whole problem, but it requires mad_math_skillz*long_time
Also my current solution gives information about direction to fly before and after wind changes. It would be pretty if problem required it in output %)
btw, thank you, aram90
I'm pretty sure I have an O(1) solution. Coded after the end of the contest, working for the samples. Waiting to be able to submit it. Anyway, the idea:
First solve it without wind change. Basically, you need to set your direction so that your net velocity points straight to the target. If you draw some vectors, you'll see that you have two sides and the angle opposing the longer sides in a triangle and you need to figure out the third one. As sur said, you can do this with the cosine theorem (or you can forget easy solutions and instead find the intersection of a circle and a line like me...).
If solving this for the first wind velocity results in a time needed that is greater than the given T, you know you'll reach the target after the wind change.
For this case, consider a coordinate system "fixed to the air", i.e. consider a system where the wind's effect is replaced by the goal point moving in the direction opposing the wind's velocity. Now look at the path of the goal point. Before time T, it's moving with some velocity, reaches some point, then changes its velocity, and somewhere after this change is the time when you can reach it.
But at this point, the weird movements at the start don't really matter. It's the second movement you want to calculate with. But it only starts this after T. So how do you make it simpler? You pretend that it was moving in the same straight line before T.
So you move the goal position by the distance it would cover with the first velocity until T, then "wind back the clock", pretending it had the SECOND velocity all along. You set the goal position to this new point. Take care when considering the direction of the wind, its opposite, and subtraction of the opposite... If you have the V and W vectors as given in the input, and G goal position, its new position is G + (T*-V) — (T*-W) = G + T*(W-V).
This problem will be equivalent to the original, because if you consider it as the "goal point moving", it's in the same position at the same time when you can reach it. And now you can solve it with the previous method.
And yup, got AC for O(1) after some debugging: 13860359
Solving it for no wind change by intersecting a circle and a line using an ugly quadratic equation. The interesting part is the rest — modifying the parameters to find the intersection when the wind does change as described in the long comment.
Lovely soln :)
Please tell me how. My binary search solution have got WA on pretest 4.
Cool, looking forward to it.
Chip has two recessive genes for blue eyes and Dale has heterozygous brown eyes. Meanwhile Dale has the gene that makes it impossible to roll his tongue on the same chromosome.
Dale and Chip have a litter of little rodents together. Take as input the name of their baby chipmunks and the probability of DNA crossing over during meiosis. Give as output the chances that a mutation in any given codon will switch an amino acid and give the baby chipmunks purple fur.
Div2 Bwas exactly same problem came in ACM ICPC Dhaka Regional 2014. That's why people from Bangladesh could solve it earlier.However, Problem set was very much enjoyable! Thanks to the setters! :)
hahaha !! that's right !!! the only difference was we had to replaces a with b in ICPC Dhaka regional 2014 and today we had to swap.
This
swapis equivalent to tworeplace. So, it has no difference except doubling the number of query.:P
yep
Does it actually matter?If the problem was C/D then it would matter.I think none of the coders could use their previous code.And problem B is never that much difficult.So it doesn't effect that much because most of the coders who can solve B always they will take just few minutes to solve it.
well, I got really stuck on that Div2 C.... Probably sohuld have just started to solve next problems
Div2B WA in pretest 1?
Div 2 B WA in pretest1?
I solved it with O(26*m+n) complexity...
Here is my code... Div 2 327 B
Thanks Mayank! Elegant solution. :)
C has very weak pretests
Is a nightmare.
I thought the nightmare was something like:
Those are the easy cases for the correct solution. The tricky corner cases are when the 3 paths intersect on a tile such that it contains '1', '2' or '3'.
Isn't there just two cases?:
— Connect any 2 pairs of components with shortest routes
— Connect all 3 components to the same free cell with shortest routes
The answer is 0.right?
Right, I had to resubmit twice due to this case (my solution was printing 1).
Oh come on, I said to myself "I will handle the 0-case at the very end", and forgot it, of course. Nightmare.
"It is guaranteed that initially it is possible to reach any cell of any state from any cell of this state, moving only along its cells."
I hacked with this test, so it must be according to the statement. And my common sense tells me it obeys what you said as well.
Ohh never mind, I thought the two 3s on the top were part of the map, sorry.
Not sure if I'm the only one who didn't like the problems :)
Pretty sure you're not alone. I don't like it either but that's just because they are quite difficult for me. The problemset itself is quite nice.
My C also failed the system tests.. now I totally hate the problemset :P
How to solve Div. 2 C?
by coding of course
Brilliant sir
My solution was based on the following observations:
a_0 and a_n are always stable.
b_i = a_i if at least one of the adjacent values is the same as a_i. Consequently, b_i = 1 — a_i if both of the adjacent values are different (for i in [2,n-1]). Moreover, a_i will be stable if it is part of a continuous subsequence of the same values.
Let A be the string of values given. In this string, there exist at least two stable values (namely the end points). Let S be a substring of A such that the end points (p and q) of S are the only stable points in it. Without loss of generality, assume that p = 1. Then, the substring S' formed by removing the these two points must be alternating (either of the form 0101...0101 when q = 0, or 0101...010 when q = 1 ). In the first case, S' will eventually become 1111...111 as consequence of the previous observation. In the second case, S' will become 111...000, where the amount of 1's and 0's are the same.
I almost did the same.But i don't understand why i got WA in pretest 6.Can you check what did i miss here? My Code By the way,is there any case for which the answer will be -1 ?I didn't find anyone!
Try this test case: 4 0 1 0 1
The answer should be 1 0 0 1 1
The longest alternating sequence is the answer. If it starts and ends in same digit, then every digit in between becomes that digit. Else, if it starts and ends in different digit, then there are equal numbers of 0's and 1's serially.
Basically there are stable and unstable intervals. If anywhere in the segment you find
00or11, then they are not going to change, but any segment such as010or101010is going to change, depending on what stable intervals they are surrounded by.Finding the intervals is a nice application of regular expressions,
This splits something like
110010101110100(I added doubled the ending coordinates, as they are stable too) into[('', '11'), ('', '00'), ('1010', '111'), ('01', '00')]. From there you just have to change the unstable'1010'into'0011'and'01'into'10'and you're done...and another way with regexes using lookaround: if repetition
"1 - NUMBER_1, NUMBER_1"+is surrounded with"NUMBER_1,NUMBER_1"from left and with"NUMBER_2"from right, then it changes to"NUMBER_1" * (length_of_repetition / 2) + "NUMBER_2" * (length_of_repetition / 2). e.g. 13873903how to solve div2 E? Как решить div2 E?
For Div2 D can anyone show me how sample case #2 works? Cant understand how 11.547005383792516398 come out. I think it should be 20/sqrt(3);
20/sqrt(3) is 11.547005383792516398, isn't it? :P https://www.google.co.in/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=20%2Fsqrt(3)
wtf im so noob :( my mental calculation become worse and worse after high school
I think we will see a lot of WA on the fourth task.
Div2 C....I thought its my lucky day when reading till second last paragraph of a problem
Haha me too :P
Can you find any case that answer "-1"?I puzzled it for a long time
My solution without "-1" case was accepted on pretests. Final sequence always exists.
You shouldn't consider that fact a proof.
I ran my slow solution for all binary sequences from 0 to 2^20, not a single one got stuck. Enough of a proof?
Of course it is not enough for a proof, it may work to feel save in the middle of a contest, but it wasn't a demonstration at all. BTW, the proof is not hard.
hi all this constet was one of the best contest that i participate in it :) ty all hf;)
Thank you very much!This is my first contest in CF.I really have a happy time!Expect next contest!
А можно поподробнее, когда ждать результатов? Ориентировочное время-то известно наверно?
Судя по информации здесь, результаты будут не раньше 4 дня.
Раз такое дело, почему бы не проводить раунд по официальным соревнованиям так, чтобы он заканчивался примерно в то же время?
тогда теоретически участники оф соревнований могут слить условия до начала раунда на кф
Результаты, конечно, будут сегодня, но ближе к вечеру. Благодарим за понимание.
Потому что мы наиболее свободны в середине контеста. В начале решаем какие-то внутренние проблемы, а в конце печатаем дипломы и т.п.
Результаты и разбор появятся после закрытия олимпиады, ориентировочно в 7 часов вечера.
при всем уважении, мне кажется, что нажать кнопочку "начать системное тестирование" не такая уж ресурсоемкая задача... я не говорю про обновлнеие рейтинга, проверки на читерство, итд а просто проверить решения на правильность и дать возможность дорешивать
Я отвечал на вопрос о времени проведения раунда.
А давай теперь на вопрос о результатах :) Люди интересуются, почему бы не сообщить их участникам пораньше, на этот счет же есть официальная позиция наверно?
When will the closing ceremony finish?
Yeah I too is waiting for Editorials.
Please feed us with editorials so that I can go back to sleep!
Why Div.1C is C ?
Why in the previous contest div1 D was D?
why "why" is why ?
Div 2 C >>>>...> The Great Wall Of China (For my rating). :-( When can I cross it?
problem c ,, div 2 , when the answer would be "-1" ,, i think there is no possible case where the answer is "-1" ,, is it ?!!
The answer is never "-1". It can be shown easily by induction (a1 never changes, and if numbers a1, ... ak never change after k steps, then ak + 1 cannot change after k + 1 steps).
When is the closing ceremony of the official competition? (How many hrs from now?)
How to solve Div2 C other than simulating?
Notice that any substring containing more than one consecutive zeroes/ones will remain as it is, so the only case we have to think about is 10101... If you notice carefully, after each move the leftmost and the rightmost digit of this substring will become safe (it will become equal to whatever is beyond it), so you can easily come up with a O(N) solution. So we just have to update cnt as max(cnt,(length of unsafe substring+1)/2))
Div-2 C >>>> The Great Wall Of China..(for my rating) :-( When can I cross it?
Расскажите D
Две динамики по типу рюкзака. В первой dp[i][j] = максимальная сумма для i элементов, которые мы можем поставить в конце первых k элементов не более чем за j операций. Во второй dp2[i][j] = минимальная сумма для i элементов, которые мы можем поставить в начало последних n - k элементов не более чем за j операций. Ответом является минимум из всех возможных сумм
.
То есть, мы берем t каких-то элементов из первых k, и заменяем их на какие-то t элементов из последних n - k. Для этого сдвигаем и те, и те к "границе", и за t2 операций свапаем их.
Спасибо, понял!
А у меня была динамика dp[len][m][s] — минимальная сумма первых m элементов в перестановке, которую можно получить из первых len элементов , потратив на это s обменов. Переход в такой динамике — O(1), ответ будет в dp[n][k][0..s].
Looking at the hacks, looks like DIV2D / DIV1B will give many WAs..
What was the hack that dreamoon_love_AA used four times?
I think many competitors didn't consider, that tau-corss-shape road may be shorter, than two roads connecting two pair of countries
Oops, sorry, my comment applies to Div2E/Div1C
If you write something like while(hi-lo > 1e-9) and using variable with double, or you set hi < 5e7, you will fail in following testcase:
10000 10000 -6470 -10000
969 1000
616 748
616 748
And what is the output of this test case?
My program give 50211053.368784316000000000.
O.o? Why does while(hi-lo > 1e-9) break? Does it time out?
What is wrong with while(hi-lo > 1e-9), exactly? I used long double there.
I guess long double will pass it.
I have used float..should I expect a WA? UPD: I have used double..I forgot..got AC
Yes.
Of course. I believe we should never use float.
precision killed me...
Кто-нибудь получал ответ 3.7657803760 в Div1B?
Да, это вроде если ветра во второй части пути не в ту сторону посчитать.
Ага, если оптимизировать отдельно первый участок пути и отдельно второй, так и получается.
Я думал, что так делать не оптимально, но до сих пор не понимаю почему (
Ну например, если в двух частях пути ветры будут (-20, 0) и (20, 0), то они могут уравновеситься в итоге, и поэтому выгоднее будет их игнорировать, а не тратить время на борьбу с ними. Да и вообще в оптимальном ответе, скорость дирижабля (относительно воздуха) должна быть постоянной в течение всего пути.
У меня получился 3.6689300537
Tasks were ok, the idea for the second is pretty standard, the third task is cool, the fourth is good, but I couldn't solve it on the time. The fifth task I didn't understand.
But the texts were awful. In the first task we have one not important part, in the thrid task the main thing wasn't on the right place ( ai=0 or ai=1) and samples in the fifth task weren't explaned...
Thank you for the contest GlebsHP, I am waiting your new round !
I solved Div2 A and Div2 C easily, but for some reason I had quite a lot of trouble with Div2 B. The only way I could think of in the end was to keep swapping integer arrays to denote swap of two letters. Does anyone have a better way ?
How do you solved Div2 C?
You have to find all alternating sequences. The longest alternating sequence will provide the first answer.
My algorithm is based on the followings:
1) If the alternating sequence has odd length , then the sequence has same bits on both the side (You can easily prove how). So this sequence will eventually be consumed by those bits to become stable.
2) If this sequence has even length , then the sequence has different bits in each side (Again, the proof is easy). First half of the sequence will be consumed by the bit on the left and the second half will be consumed by the bit on the right.
3) Step required is ceil(length/2). The answer is the maximum of them.
Solution passed the pretests. I am a little bit worried about the -1 case though. I am pretty sure this case doesn't exist. But I couldn't prove it.
yeah, passed system test. So -1 case doesn't exist (Proved) :v 8-)
You can make temporary mapping array 'a' -> 'a' ... 'z' -> 'z', simulate on it for O(26*m) and apply it to string for O(n)
you can use a array f[] to store the letter's meanings.
and for every swap operation , you can updata your f[] array in O(26) Time.
Please use update instead of "updata". There is no such word.
Besides, I don't like your avatar.
Me neither.
How long till the closing ceremony?
Results will be approximately at the 19:17 GMT+3 25.10.2015
Really?How did you know?
И все-таки, чем обоснована задержка систестов? Не совсем понимаю, как это может повлиять на официальное соревнование.
Вероятно тем, что участники теоретически могли бы проверить свое решение на всех тестах, не тратя попыток на основном соревновании.
А почему на основном соревновании есть доступ в интернет? И в любом случае, тут половину решений уже рассказали.
Ну ведь детей отпускают в туалет, там они могут посмотреть всё, что нужно
Набрать код на телефоне во время контеста, потом пойти еще раз и посмотреть результат, при этом получив пару часов штрафа за поздний посыл?
Посмотреть чужие решения и тесты
На онсайте нет доступа к CF и они не могут участвовать и там и там.
Great problems ! I would have loved to spend more time solving problem D during the contest, lost so much time to understand that I needed "cin.ignore()" in problem B :(
Thanks for the contest.
At least are we going to be allowed to check others submission's ??
Is there any information on when the closing ceremony will finish?
A round announcement without thanking MikeMirzayanov :D
Why should we wait with the results until the closing ceremony's end?
This is to keep up the excitement of the on site contestant until the declaration of the winner names at closing ceremony.
*Pending system testing
More than 1 hour and even system testing not started. So, how its 1 hour rating system :P
When the closing ceremony will end ?? :(
Кто-нибудь может объяснить, почему в задаче Div.2B может быть ошибка на претесте 1, которая пропадает при замене scanf на cin в считывании символов, которые мы будет менять местами?
И разве претест 1 не совпадает с тестом из условия?
cin >> char >> char считывает c автоочищением потока (поправьте, если я не прав).
cin >> x >> y; //Считает x и y, как бы ты ни писал их — через пробел или нет
scanf("%c%c", &x, &y) считывает строку и подставляет значения в x и y, исходя из нее
То есть, если ты вбил "2 3", то scanf посчитает, что в x надо записать '2', в y — ' ', и оставить "3" как то, что не записалось в переменные (или как-то так)
Я это установил во время контеста экспериментальным путем и с помощью костыля избегал этого (а именно — считывал второй символ повторно).
У меня это решение проходило оба теста из условия, однако на сервере выдало WA1.
Причину этого я так и не понял.
В любом случае спасибо за объяснение.
Вроде как можно написать вот так:
scanf( "%c %c", &x, &y );
Зафейлится при вводе следующей пары символов, ибо перевод строки — тоже символ
Добавим перевод строки:
scanf( "%c %c\n", &x, &y );
Правда тогда может зафейлится на последней строке, если в ней этого перевода нет.
Тогда зафейлится на первой строке, причем с TLE, причину этого я еще не понял, но как это выглядит: считал первую пару символов с переводом строки, и scanf ждет еще какой-то символ, в результате первая пара символов начнет обрабатываться только после ввода второй пары.
P.S. Отмена, это наблюдается в 2015 студии, на 2010 все будет работать норм.
Чтобы учесть все пробелы и переводы строк лучше вот так:
перед каждым %c пробел — это пропуск пробелов и переводов строк
А вот это круто, спасибо.
Это гарантировано стандартом?
думаю, да. Также как
scanf("%d %d")считывает второе число, пропуская лидирующие whitespace (и переводы строк и пробелы).A single whitespace in the format string validates any quantity of whitespace characters extracted from the stream (including none). (whitespace characters include spaces, newline and tab characters) cplusplus.com
В случае со scanf, лучше было бы считывать не (char char), а (char[2] char[2])
Мой тебе совет: научись один раз использовать getchar() и таких проблем не будет возникать. Сможешь считывать любые данные, которые поступают на вход, да еще и быстро. Да, возможно по началу долго писать такой ввод, но потом данный скил сохраняет время и нервы на контесте :-) Успехов!
Не рекомендую такой подход. Все задачи обычно стараются составлять так, чтобы посимвольный ввод не требовался. Чтобы задачами занимались, а не вводом. getchar() не скипает за тебя пробелы/табы/переводы строк, можно напороться на что-нибудь неприятное или просто писать больше кода, чем требуется.
Как balalaika выше ответил, легче и лучше просто читать %s в char[2].
Помню задачу, где если считать double и потом попытаться умножить его на что-то, да бы решать задачу в long long, получится погрешность и WA. Необходимо было вручную строкой считывать его и переводить в long long.
Что мешает так же с помощью %s в строку считать, а потом переводить? =)
А вообще, сколько же знаков было в той задаче, что нельзя было просто 0.5 добавить перед переводом в целое? Как здесь, например: http://mirror.codeforces.com/blog/entry/20683?locale=ru#comment-254477
Не знал про такую магию)
No sign of closing the closing ceremony.
What is wrong with Div 2 B solution? Both fail on testcase 1.
Brute force — https://ideone.com/YvASbz Runtime Error — https://ideone.com/cy83S0
Why kill the time? plz start the system testing. Every one waiting for system testing.
I think it is because of the onsite events. They cannot start system test now. If they did, there would not be much fun in the closing ceremony(or something like this).
Please notify us with any comments. What causes this delay?
UPD3. The results and the editorial will be published later, after the closing ceremony of the official competition
Seems like contest is not of 2 hours but of entire day ;)
System testing started. Feeling emotional :P
Finally system testing started !!!! -_- :D
why TLE?
System testing finished but practice mode is not enabled! Why?
UPD. It's now fixed.
Прождали систестов, теперь вперед ждать обновления рейтингов! Хэй!
рейтинг можно посчитать самому, формула открыта же
Maxim, 1k_trash и я недавно набросали расширение на хром. В любой момент времени на контесте у вас есть такая колонка, что весьма прикольно. Если предикшн совпадет с результатом, то допилим и на днях опубликуем.
а у вас оно как считается — прямо в браузере или на сервере? Я вчера тоже сделал сайт на эту тему, чтобы потратить сгорающие промо-коды с hackerrank, но амазон затянул с активацией ec2-инстансов для моего аккаунта и запуск пришлось отложить. А теперь видимо и вовсе отменить, чтобы не плодить велосипеды)) Если надо, могу поделиться дампом раунда #326, на котором тестировал формулу
Сейчас будет смешно: считаем за N2 * log(N) на джаваскрипте)))))))
у меня вообще нету опыта в этой сфере, так что мы были бы рады любой помощи)
Как же так можно, не ждать часами результатов раунда?
Да.
расходимся
Я немного потьюнил формулы:
contestant.delta = (contestant.needRating - contestant.rating) / 3;->contestant.delta = (contestant.needRating - contestant.rating) / 2;Фух, спасибо! :)
Еще ждать дорешки приходится.
still not able to see testcases and submissions :(
Why is there so much delay? 1. there was delay in testing 2. now practice mode is not enabled 3. there is no editorial uptil now. 4. I can't see other's submissions.(What is the point of making submissions invisible until system testing is over)
Please do it quickly.
5)Rating has not changed yet
Was worried about plateauing for a while but it seems like I'm still improving!
Feel free to upsolve and read other contestants code. Yes, i'm feel free while the others codes are blocked <3
I am a Div 2 participant. My submission for question 1 was processed by the server twice. Hence there were two submission both at the same timestamp. Also, I was penalised 50 points as resubmission. Why did this happen? Can something be done regarding this?
Why rating change is so delayed ??
Why only Div. 1 winners ? What about Div. 2 winners (or top 5) ??
Is this round even rated ? !
Ah i wish it is unrated. :-P
Hope it too.
UPD4. The system testing is over, results are now final. Feel free to upsolve and read other contestants code. Congratulations to Div. 1 top-5:
How?
.
By asking the other contestant to share his/her code via ideone (feel free to ask them to share their codes :P )
Then how can we see the test cases? :D
who told you to feel free to see the test cases? :D
Still unable to "read other contestants code"
"I give you A you give me B"... this won't be considered as cheating now :P
Rating — time limit exceeded.
these people have no idea what theyre doing
Was this round rated? Or is the rating change delayed for some reason?
I have been starting to wonder the same thing. And it was my first time solving C too :/
well this problem C was the only problem C in these recent contest which needed a bit of thinking :) others were just brute force and corner cases (we call it tof in persian )
Actually, I need to rephrase. It was my first time solving 3 problems. And yes, I think you are right. In some of the previous contests, I somehow found B harder than C.
lol be happy u still have some coffee mine is finished :/
Editorial?
*waiting
(irony of a meme: there is no edit option to correct spelling or grammar)
CF skatilsya, ranshe lu4she bylo((
We can't "read other contestant's code" yet GlebsHP :P
Atleast make the testcases public. Can't wait to see where i went wrong in Div2 C.
try this :) 101010
Getting output:-
2
111000
correct try this 5 1 0 1 0 1 and 5 0 1 0 1 0 and 5 0 1 0 1 1
2
1 1 1 1 1
2
0 0 0 0 0
1
0 0 1 1 1
correct ! I have no idea then :) what is the order of ur algorithm ?
It's O(n) Finally found out the mistake. Implemented it in the wrong way. Thanks for your help.
ur welcome
I am quite disappointed in today's problemset, especially since there was like 20 people involved in preparing the contest. For me ideas for B, C, D are quite old and standard (and I'm guessing many people feel the same way, as there are 45 people passing all 4 problems, and much more passing pretests). And did authors know that D has observation that s < 6000? How can it worth 1750 points?
It is impossible to have five problems with new idea every round. What we try to achieve is to offer something new to everyone. The result is that for almost everyone there will too easy and too hard problems, but at least one problem will be the right challenge to his\her solve\write abilities. Problem E was your challenge yesterday.
Zlobober back maybe ? :D
Looks like GlebsHP is counting rating manually :)
or maybe code that computes rating is like this:
hi first thank GlebsHP for prepare The Contest, the problems are very nice and creative:) but system rating... :(
For those interested, here is a much easier version of three states. http://www.usaco.org/index.php?page=viewproblem2&cpid=88
The problem is very simple anyway :)) In my opinion, it was the easiest div1 problem from the contest
Finally we can see submissions. I hope ratings will be updated soon. :)
Never had such bad experience before. Everything seems messed up. :( system testing has finished 3.5 hours ago but, no rating change. Still can't see others code and test cases !!
Now you can.
They should change Codeforces' logo for this blog to something like
13849187 , what is wrong with this code? Why is the output blank? It runs fine on my compiler
http://mirror.codeforces.com/contest/591/submission/13860498
Don't use gets(). Try it with cin.
Never use both c++ io and c io while you have closed the synchronization of them using "ios_base::sync_with_stdio(false)".
Finally rating change. o_o Waiting for saturday contest. :)
waiting for solutions for the contest...
Editorial in Russian will be published in approximately 10 minutes. Unfortunately, English one will be published only tomorrow.
How to solve problem D? I used ternary search to find the best angle we have to move until time t and them go directly to destination. (or go to destination under t seconds). but my code couldn't even answer the first test case. here's my code http://mirror.codeforces.com/contest/591/submission/13852036
You don't have to care about the angle, all you need to care about is the time taken. Say that you're making a guess that the trip will take h seconds, and the other variables are as given in the problem statement. That means that during that trip you will be moved to the direction vx,vy for min(h,t) seconds and to the direction wx,wy for max(h-t,0) seconds. When you know this, you can move your starting position to x = vx*min(h,t) + max(h-t,0)*wx + x1 and y = vy*min(h,t) + max(h-t,0)*wy + y1 to compensate for the wind, and pretend there's no wind. Then you can just check whether you can get to the destination from your new starting position in h seconds. Now that you can check if the trip can be made in time h, you can just make a binary search.
Московская командная олимпиада школьников по программированию добавлена в тренировки.
Лига A и Лига B соответственно.
Не добавлены авторы у контеста div2.
