Доброго времени суток, сообщество Codeforces!
В Саратове продолжается школьная олимпиада, поэтому мы предлагаем вам очередной раунд на базе школьных задач. Раунд будет предназначен для участников из второго дивизиона. Участники из первого дивизиона, как обычно, могут поучаствовать вне конкурса.
Раунд начнется 8 декабря в 13:00 MSK
Задачи были подготовлены сотрудниками и студентами Саратовского государственного университета, включая MikeMirzayanov, Fefer_Ivan, NALP, HolkinPV и меня.
Разбалловка стандартная: 500-1000-1500-2000-2500.
UPD: Поздравляем победителей:
UPD: Разбор задач.
Наконец-то анонс! Всем удачи!
What will be the scoring? Edit: Scoring added
I think scoring will be dynamic, because scoring of a first day of the competition (cf round #217) was dynamic.
What is dynamic scoring?
Experiment: dynamic problem max. scores
When the score for the problem depends on count of successful solutions.
I hate contests in unusual time (Do U know what is time?!)
I am coming
That's quite unfortunate choice of words :P
Forgot to register for the contest T_T. Realized when tried to submit :(
Found someone who wrote the following code
Tried to hack it with a test case where n is 100 ( My first attempt to hack a code in my life ) but failed. Is there any full proof way to make the code go out of bounds?
http://stackoverflow.com/questions/1239938/c-accesses-an-array-out-of-bounds-gives-no-error-why
Accessing an element outside array bounds is undefined behavior in C++, and this means that anything can happen: the program may crash, may print incorrect answer or may even work correctly.
what a greedy contest! :D
What is the logic behind Problem D?
You just need to simulate what the problem asked for. Fill certain container until it is full. Once full, pour the remaining water in the next container. If the next one is full too, try the next one until you find an empty container or you reach the floor. Finding the next container efficiently is the trick here. I used Disjoint-Set-Union data structure to quickly find the next container.
I used a segment tree, I initially thought of DSU but after that I thought that it would have too high of a complexity.
Why? If we use path-compression, isn't it just almost O(1)?
Disjoint-Set-Union is just enough... very small implementation... Nice problem :D
Seems I analysed it too superficial... alas, segment tree was good too.
I used the same idea in practise session but it is still showing TLE
Oops, my solution for Problem C & D both got WA6 unfortunately. Orz.
Как решать Dшку?
Почти наивно. Хранить сет всех неполных сосудов, которые еще не заполнены, и массив для поточного количества воды в сосудах. Если поступает первый запрос, найти lower-bound'ом по индексу первый неполный сосуд, и лить воду, пока можно, удаляя на ходу из сета все заполнившиеся сосуды и обновляя массив поточных количеств. А на второй запрос просто взять поточное количество воды в нужном сосуде из массива.
А я решал через СНМ. Хранил ссылку next, и если сосуд становился полным менял ссылку на ближайший неполный сосуд
Чтобы переходы между сосудами после заполнения работали за О(1), а не за логарифм — можно хранить незаполненные сосуды в виде двусвязного списка.
Но здесь оно на итоговую асимптотику не влияет, так как переходов в общей сложности будет не более N (очевидно, что мы не можем наполнить сосуд дважды).
what was the idea for E?
Was this to sort the input and work with k consecutive parts ??
I tried this and got WA on pretest 2.
Solution is correct. There might be bug at your implementation.
Nice contest with really fast system testing :D
Can someone help me with B?
My approach was: 1. Factorize a in powers of 2,3,5. 2. Factorize b in powers of 2,3,5.
Answer will be sum of differences of power. To find power, I found all powers of 2,3,5 uptil 10^5, for fast calculation. Yet, for test case -> 1,000,000,000 999,999,999 — it was taking more than 2-3 seconds.
finding powers of 2 could be done like this
Which is the test 32 ¿? I can´t see tests in submissions :( I got accepted in practice, but I cant´t imagine slow behavior for any test.
Using bitwise operation could be faster:
Хоть я сегодня слишком много бажил, но этот раунд один из самых интересных из всех что я писал:)
После системного тестирования поднялся на 70 мест. Круто!
а я на 7) но зато каких)
А я только на одно, даже как-то грустно.
ну да, 1-ый в соревновании, сама грусть(
А я упал на 500 мест
()
Я и на 350 поднимался :)
Как B решается
Очевидно, что наибольшее число, которое может получить лисица — НОД(a,b). Считаем его алгоритмом Евклида. После чего выделяем числа c и d — a/gcd(a,b) и b/gcd(a,b) соответственно. Пытаемся факторизовать их двойками, тройками и пятёрками. Если мы сделали это успешно, то пишем сумму двоек, троек и пятёрок в разложении первого и второго числа, иначе -1.
Я заслал простой бфс, подсчитывал до какого числа мы можем дойти из исходных и за сколько шагов. дальше просто ищем минимальную сумму для каждого числа, до которого можем дойти из обоих исходных чисел.
Как решалась Е?
Сортируем по координате, потом считаем все суммы расстояний на отрезках длиной k станций, выводим те, которые составляют минимальную сумму.
More info
Почему нельзя смотреть решения сразу после того, как закончился раунд? Раньше было можно. А теперь уже и систесты кончились, и все равно смотреть нельзя. Fix it please
Вчера так было из-за того, что задачи использовались в это время на локальном контесте школьников — как результат, их доступность мигала туда-сюда несколько раз на протяжении часа.
Вероятно, сегодня причина та же.
Это не только в этом раунде. Уже примерно около года такая фигня творится.
Контест просто КЛАСС...!!! Спасибо Авторам...!!!
wonder why my submission 5386072 (using recursion) gave MLE. my guess is that stack size of the judge is pretty low, because i used the exact same idea in practice submission 5388703 and got AC.
EDIT: i think the solutions and tests have not yet been made public, so u may need to wait for a few minutes to see them.
We can't see your solution.
I think that your solution made an infinite recursion. As I know, the stack size of the judge is equal to the memory limit of the problem.
When I try to see someone's solution here http://codeforces.me/contest/371/standings nothing happens. A pop up is there when I double click on the cell. But the submission link to show the user's actual code doesn't work for me. Any help?
You'll be able to see solutions after some minutes.
some errors ?
still not work now
Its working. Thank you.
В задаче С делал бин. поиск по ответу. На контесте сделал правую границу 10^16 на фул тестах получил WA16, в дорешке сократил до 10^15 все зашло) Видимо случалось переполнение long long. Было бы обидно потерять задачу на такой ошибке, если этот раунд был бы рейтингованным для меня)
Если я правильно понял, что делалось... Там при подсчёте того, сколько денег уйдёт на m гамбургеров может выйти число до 100 (цена одного элемента) *100 (необходимое для приготовления кол-во) *m. Надо учитывать такие штуки при решении.
Да, спасибо, я знаю. Я просто случайно дописал один нолик лишний и не заметил этого.
Потому что надо писать
(long long) 1e15
, и дописать нолик становится невозможноразве что нибудь изменится если без приведения типа к long long приравнять?
Ну это warning, а надо стремиться их избегать
А я вот потерял задачу сделав правую границу money+100, сделав её в дорешке money+101 успешно зашло. обидный затуп :(
Хм. А у меня money+100 зашло...
Ну бинпоиск можно поразному написать, в моем случае правая граница изначально должна была быть не достижимой, а money+100, очевидно, достижима.
А вот мне обидно... Вначале правая граница была 10^14, переслал поменяв на 10^16, неправильный ответ на финальном тесте 9. На дорешивании отправил 10^14, полное решение :(
Отличные задачи. Особенно D понравилась. Спасибо за контест.
I have a question about Problem B! In the first sample, how to get the output result 3 ????? I always think the result should be 2. That is, first, 20/2=10, then, 15*2/3=10, and over.
20=(2^2)(3^0)(5^1) 15=(2^0)(3^1)(5^1)
Make the powers equal, which will require 3 steps.
When Fox is dividing the cheese by 3, she TAKE 2/3 of it. So, if the size of cheese was n, after dividing it becomes n / 3.
Can anyone help figure out why my D is wrong at Test 6 Ans 34th ?? Thx.
Is there anyone love to share thoughts on problem E?
My implementation was sort station ids by their location. Then I guess the solution must be k consecutive stations. Then I scan from left to right. I got WA on 15.
Is my algorithm totally wrong or I missed something in my code? Thanks.
Your idea is correct but , update of 'sum' is wrong (at my opinion)!
That's true, so sad :(
I
А разбор задач будет?
UPD: Круто, разбор задач появился через пару часов, после этого поста, а меня минусуют...
Да
Минусуют, потому что разбор есть всегда...
Worst time ever :( Please move the hour or maybe the day xD