Round 1 will last 24 hours and start December 7, 2013 at 10:00 AM PT.
The top 500 people will advance to the Round 2. In addition, anyone that scores the same number of points as the person in 500th place will also advance to Round 2
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 164 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.05.2026 00:34:53 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Where is the announcement? Like it was in qualification
UPD It was boring to debug "Labelmaker", until I got output PKUPERCUPTEAM
The link is posted. Good luck!
Why I can't get access to tasks round 1?
This link don't work.
It should work, so sorry for the silly question: have you solved at least one problem in qualification round about 2 weeks ago?
No, I don't know, sorry.
Can anyone explain me third case in "Coins Game". Of course if it isn't illegal.
I believe any discussion is illegal. Solution on specific test case can help you to solve problem.
Considering it's a small case, you can solve it yourself, manually. Just write the possible arrangements and strategies on them on a paper, and try to see which is the best one.
Yeah you are right. I thought a little bit , then i found optimal arrangement.
мне кажется, или первая задача (Labelmaker) почти тоже самое, что [problem:http://mirror.codeforces.com/contest/1/problem/B]?
ПС я говорю, про похожесть условий и никого не призываю обговаривать решение до конца контеста
Если это считать "похожими", то тут 50% задач баяны...
Что должно выдавать в D(40) на тесте N = 20, K = 1, A[i] = 50 (для всех i = {0, ..., 19})? А еще спешу огорчить тех, у кого в B(20), на тесте 3 7 7, выдает 9:(
У меня 647.
О, а как тогда B решать?
У меня 643. Мне это уже не нравится)
Вот теперь это уже не нравится мне :D
А, фух, не ту задачу посмотрел, 643, всё ок.
Case #1: 643
51 53 58 59 61 65 67 71 73 77 79 83 89 97 101 103 107 109 113 127
643.
When will results be announced ?
Can someone explain their solution to the 40pt question?
I tried dynamic programming with a state of
dp[N]{set of primes used} = minimum cost.On its own that wasn't fast enough, but it was possible to prune the search significantly by calculating an upper bound on the answer with a simple greedy algorithm and rejecting anything which would lead to a cost greater than that.
How many primes do you need in the worst case to generate the answer?
It seems that very stupid upper bound is 36 (number of primes greater than 50) but then the number of states is huge.
Did you use map for memoization?
I tried all coefficients up to 500 and, yes, used a map<vector,int>. eduardische's comment looks like a better way to keep track of state, assuming it works.
Code here (guaranteed to not be correct).
20 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
answer = 19, cause you cant left 0, cause gcd(0,2) = 2 :)
Should not this case be caught by the last example?
Yeap, seems like, but i checked my test on hex539 solution, and he has 18.
But may be no, cause on last sample you have to keep one zero, but in this case you have to remove all of them.
It's 18, because you need just 18 ones, one zero and one 2.
Yeap, but gcd(0,2) = 2, and 2 > 1.
Oh... whoops. Well, I wouldn't have points for that problem anyway, I just did a simple backtrack (I've got nothing to lose by trying :D).
Ah I see, the last example is only there to ensure that noone misses the edge case (0, K, ..., K) and that is different from your test
Thanks, I've updated my comment.
Looks like there are several nasty edge cases. This solution could probably get around them by having an extra bit of state, [used_zero].
The whole case "any number is zero" can be gotten rid of quite simply. If there's any zero in the solution, all other numbers must be K; otherwise, just increase all zeroes to ones.
We can notice that it is only worth using primes >50 on its own, so we can have dp[N][mask][order of first unused prime >50]. This adds an extra dimension of N size but reduces the amount of primes to 15.
If you sort the ages and process them in the non-descending order then once you have used a big prime you won't stop and will use only big primes hence. So your last dimension seems redundant.
Not true. Maybe we can get somthing smaller than the first unused prime >50 later with combination of first 15 primes.
If it will help later then it will help "right now" as well so we can switch them: remember that the ages are non-descending.
Ok, indeed, thank you.
I just implemented a brute force search with pruning and it was efficient enough. However, I didn't consider some special cases with zeros. :/
What I did was quite simple.
Initially I hardcoded the first 64 primes and pre-calculated the bitmasks representing which primes were used in each of the possible numbers' prime factorisations. (overkill, I know)
Afterwards I dealt with the simple case of all A[i] <= K (in this case, we make all members of the new array to be K, except for if there are any zeroes, one of them can become a zero). If this does not hold, I initially bounded the solution with using only K * P[i] as my new array, where P is an array of only primes.
Now I performed a simple brute-force recursion. It takes parameters of the current sum, index, bitmask and number used). It starts a for loop from max(previousNumber + 1, A[i]/K). If the current number in the loop doesn't violate the bit mask already there, it is placed in the i-th position and we move on. I disable recursing into impossible solutions by enforcing that the elements of the new array must be in increasing order; hence, if I have just added the number X to my array and I have Y numbers left to place, then the sum is bounded below by prevSum + Y*X + Y*(Y+1)/2 (the case where the following numbers are: X+1, X+2, ..., X+Y). If this lower bound is greater than the already found minimum, we can safely stop recursing.
This turned out to execute quite quickly on my machine (the time spent on a file with 1000 random test cases with N = 20 was negligible).
Here's my code.
Hmm, did you consider cases like
4 1, 1 1 2 3, where you might need to select a 1 twice? The answer will be0for this case.Yeah. I handle the array members that are less than or equal to K separately from the others (as you can see from my code).
Here is my solution based on backtracking, it corrected after considering the case 12.
А что с Preventing Alzheimer's делать? Кроме перебора, что-то ничего не придумалось (( Но это долго...
Не долго!
Думаю, очень много 2-х попадает и часть 3-х. У многих вторая падает на тесте "3 7 7". Если что, ответ 8.
у меня такого инпута нет)) есть 3 4 4 так и должно быть?
Да ни у кого такого инпута нет, зато есть аналогичные. Если на этом падает, то и на них тоже упадет.
А как решалась задача правильно?
Большинство (как и я), насколько я понял, засылали фигню, типа оставим m свободных, по остальным равномерно распихаем и попробуем обновить ответ.
n- кол-во банок, k- кол-во монет, c- кол-во монет, которое надо забрать я делал так:
1) если банок больше, чем монет, то ответ (n-k+c)
2) проверим возможно ли ни разу не выбрать пустую банку и забрать нужные С монет. для этого должно быть (k/n)*n>=c и соответственно нужно с ходов
3)
иначе с+1, для этого мы в (n-1) банку кладем k/(n-1), а в последнюю все оставшееся, возможно 0. ну и далее из каждой банки берем k/(n-1), можем указать на пустую только раз (это есть n-ая банка)валится на 8,9 тестах (999999 1000000 1000000 1000 12345 12340)буду счастлив, если я решил правильно, а красненький нет))
счастья не произошло у меня задача упала((
Их не обязательно оставлять свободными, можно в них класть k % (n-m) монет (если при этом ни в одной из m стопок не выйдет больше чем k / (n-m) монет)
По крайней мере это проходит тест 3 7 7
P.S.: и это прошло =)
Я написал динамику F(n,k,c) представлял через F(n-1, k — full*i, c-full*i) где full — число монет в банке N, при этом считая что в банках 0..N-1 монет не меньше. Изначально работает медленно, но если full пускать по уменьшению, и отдельно обработать случай k<n, то быстро.
P.S. прошло
Правильно вроде бы так. Переберем максимальное количество монеток, которые положим в одну емкость. Тогда в некоторых емкостях будет ровно столько и (возможно) еще в одной емкости оставшиеся монеты.
Решалась очень просто — напишем несколько решений, сравним их с полным перебором и то, которое проходит, зашлем. http://pastie.org/8537897
Мне показали решение в одну строку:
return c + max(0, n - k / ((c + n - 1) / n));.Я сам перебирал размер максимальной кучки, а также их количество. Тогда среди оставшихся кучек нам выгодно разделить монетки поровну, причем надо следить чтобы размер всех остальных кучек был меньше максимального, который мы перебираем. И отдельно рассмотрел случай, когда во всех кучках одинаковое количество монет, а оставшиеся монеты мы выкинули вообще.
А как нужно разложить в кучки, чтобы ответ получился 8? До меня пока что не доходит :(
3 3 1
тогда если ты попробуешь взять вторую монетку из кучи и она есть, то в кучке точно 3, а если нет — то в остальных точно 3
Спасибо, теперь понятно
-удалено-
3 3 1
1 3 3
UPD ниче я слоупок, три человека опередили пока я три числа писал О.о
может кто-то подробно написать, как четвертую (Preventing Alzheimer's) решать?
Можно динамикой за 2^15*20*20*150. На самом деле, там гораздо быстрее выходит.
Задача понятно как сводится к такой: дан набор целых положительных чисел, требуется некоторые числа увеличить так, чтобы они все стали попарно взаимнопростыми. Нужно минимизировать суммарное увеличение.
Отсортируем все числа по неубыванию. Теперь запустим динамику, где состояние — это номер текущего числа и маска простых чисел, которые были использованы хотя бы в одном из рассмотреных чисел. Тогда для текущего числа мы можем просто перебрать его новое (увеличенное) значение и если набор простых в его разложении не пересекается с маской, обновить динамику. До 50 есть 15 простых чисел. Ясно, что после 50 нам понадобятся не более 20 следующих простых чисел, поэтому перебирать числа имеет смысл только до 150 (ну или какое там простое число перед ним). Теперь осталось заметить, что когда мы перебираем значение очередного числа (пусть оно сейчас равно X), то если X не противоречит маске, X — простое и оно строго больше максимального из изначальных чисел, то после того как мы его рассмотрим, можно делать break. Выходит, все простые числа, которые больше 50, будут в нашей маске всегда идти подряд, т.е. мы никогда не используем большее, если в маске еще нет меньшего. Значит, возможных масок будет не более 2^15 * 20.
большое спасибо! буду разбираться!
Альтернативный вариант: написать перебор с отсечением по ответу. Мысли:
На тестах жюри пережёвывает все кейсы за секунду. Однако у меня есть несколько очевидных тестов, которые заставляют это работать порядка десяти-пятнадцати секунд. Мой код.
Еще немного упростим.
Перейдем к k=1 и отсортируем.
Случай с 0 разбираем отдельно: 0 может быть в ответе только тогда, когда в начальном массиве все <=1. И даже в таком случае нулей не больше одного.
Отбросив случай с 0, переходим к простому перебору, начиная с пустого вектора. Обычный dfs по всем возможным векторам натуральных чисел. Нам нужен подходящий вектор с минимальной суммой, тогда ответ — это сумма этого вектора минус сума инпута. Добавляем по очереди все возможные числа. GCD проверяем прямо после проверки. Сумму можно там же. Для того, чтобы работало быстро — добавляем очевидное отсечение "если сумма не меньше текущего ответа — дальше не перебирать".
Локально худшее, что нашел рандом-стресс — 4 секунды. На тестах Facebook в общей сложности работало две с половиной. Можно пример "очевидного теста", на котором будет медленно? Хочу оценить, насколько все плохо.
классное решение, совсем не сложное!))
Вот все мои тесты с ответами, логами (содержат последовательности, количество итераций и время работы) и решением: D.tar.gz
Кому неохота качать, вот пример жёсткого теста (из файла 04):
iters — количество рекурсивных вызовов, что более-менее то же самое, что количество состояний в твоём dfs'е.
Значит у вас как-то неоптимально написан перебор, потому что моё решение на этом тесте работает 6.625 с за 7 991 195 итераций
Вот полный лог по всем тестам. Ни на одном из файлов программа не работала больше 1.5 минут. Хотя тесты хороши) особенно тесты в файле 07. Сразу видно, что я забыл сделать в своём решении и почему оно на инпуте от фейсбука работал 30 секунд. Но дело в том, что это решение было вспомогательным, только для того, чтобы убедиться, что ДП работает. Только потом оказалось, что оно работает вполне себе быстро на всех тестах
Мы, вероятно, разные вещи называем словом "итерация", потому что у меня их 250 миллионов и 14 секунд, а у вас — 8 миллионов и 6 секунд. Да и не факт, что у меня ноут не медленнее, чем у вас.
У нас отличие в двух вещах: я оцениваю ответ за линию, тогда как вы чуть хуже оцениваете, но за O(1). Ну и вы явно gcd считаете, может это и быстрее. Хотя мне это кажется странным.
Похоже, что вы правы. Запустил ваш код и свой код на кодефорсе, работают 8 и 7.5 секунд соответственно. Кстати у вас такое большое количество итераций потому что вы для выхода из forа используете не то же условие, которым проверяете, что ответ лучше предыдущего. Получается, что кучу итераций forа проходит вхолостую. Если занести эту саму проверку в for по v целиком, то ваша программа работает значительно лучше: этот тест сверху у меня на компьютере проходит меньше чем за секунду, итераций 8 миллионов , все ваши тесты обрабатывает где-то за 9 секунд.
Классные у них тесты, что тут сказать... Спасибо... Мое решение у меня на этом тесте 3.5 минут работает) То самое, которое на контесте все 20 тестов за 2.5 секунд решило)
Scoreboard updated. Lots of B failed. (Mine too). Can anyone give a brief description of algorithm?
If you can assign q = ceil(c / n) coins to each bucket, then you just do that and the answer is c. If you cannot, assign q to as many buckets as you can (to floor(k / q)), and distribute the remaining part (k % q) among the remaining buckets in any way. Then the strategy is to try to get q coins from each bucket. In the worst case you will try n — k / q buckets that don't have q coins first, so the answer is c + n — k / q.
Why is this construction optimal?
Results are up. Everyone with 40p get through although it was close — the first 40p is only 492th.
Does 40p going further?
Yes. People with 40 points advance. :D
Total 935 people advance.
Hope they have the same scoring system in the next round.
Let's agree we will all solve problem A only.
This suggestion does not go well with your avatar :P
Итоговая таблица, мягко говоря, не впечатляет процентом АС.
ААА!!!! 506й!!!! Ненавижу это 24-часовые контесты.
В 4й не рассмотрел, что можно ставить два числа 1 и 1.
Во 2й как все, видимо, написал, упало.
Да там же проходят все, у кого очков как у 500-го, не переживай.
Тебе может быть интересно узнать, что 506 место проходящее :о)
Ура!)))
506 — проходящее место если что
UPD: Опередили :)
вообще, вроде до 950 места у всех 1 и 3 сдано
What is the answer for "4 5 5" in B and why?
7 is enough and the distribution is 2 2 1 0 Now I get why those simple solutions work
Could anybody whose 40-pt is OK post the answer for this input: http://pastie.org/8538734 ?
UPD. Oops, I forgot that the sources are available.