Facebook Hacker Cup. Round 1

11 лет назад, # ^ |

+33

It should work, so sorry for the silly question: have you solved at least one problem in qualification round about 2 weeks ago?

→ Ответить

HASP

11 лет назад, # ^ |

No, I don't know, sorry.

→ Ответить

misafir

11 лет назад, # |

-6

Can anyone explain me third case in "Coins Game". Of course if it isn't illegal.

→ Ответить

riadwaw

11 лет назад, # ^ |

I believe any discussion is illegal. Solution on specific test case can help you to solve problem.

→ Ответить

11 лет назад, # ^ |

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.

→ Ответить

misafir

11 лет назад, # ^ |

Yeah you are right. I thought a little bit , then i found optimal arrangement.

→ Ответить

King-Kong

11 лет назад, # |

мне кажется, или первая задача (Labelmaker) почти тоже самое, что [problem:http://mirror.codeforces.com/contest/1/problem/B]?

ПС я говорю, про похожесть условий и никого не призываю обговаривать решение до конца контеста

→ Ответить

Sereja

11 лет назад, # ^ |

Если это считать "похожими", то тут 50% задач баяны...

→ Ответить

Krasnokutskiy

11 лет назад, # |

← Rev. 2 →

Что должно выдавать в D(40) на тесте N = 20, K = 1, A[i] = 50 (для всех i = {0, ..., 19})? А еще спешу огорчить тех, у кого в B(20), на тесте 3 7 7, выдает 9:(

→ Ответить

11 лет назад, # ^ |

← Rev. 4 →

-16

У меня 647.

О, а как тогда B решать?

→ Ответить

I_love_Tanya_Romanova

11 лет назад, # ^ |

+18

У меня 643. Мне это уже не нравится)

→ Ответить

11 лет назад, # ^ |

Вот теперь это уже не нравится мне :D

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

-8

А, фух, не ту задачу посмотрел, 643, всё ок.

→ Ответить

Rubanenko

11 лет назад, # ^ |

+14

Case #1: 643

51 53 58 59 61 65 67 71 73 77 79 83 89 97 101 103 107 109 113 127

→ Ответить

kostya_by

11 лет назад, # ^ |

+16

643.

→ Ответить

misafir

11 лет назад, # |

When will results be announced ?

→ Ответить

xennygrimmato

11 лет назад, # |

Can someone explain their solution to the 40pt question?

→ Ответить

hex539

11 лет назад, # ^ |

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.

→ Ответить

caustique

11 лет назад, # ^ |

-8

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?

→ Ответить

hex539

11 лет назад, # ^ |

← Rev. 2 →

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).

→ Ответить

11 лет назад, # ^ |

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 :)

→ Ответить

11 лет назад, # ^ |

Should not this case be caught by the last example?

→ Ответить

11 лет назад, # ^ |

← Rev. 3 →

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.

→ Ответить

11 лет назад, # ^ |

It's 18, because you need just 18 ones, one zero and one 2.

→ Ответить

11 лет назад, # ^ |

+16

Yeap, but gcd(0,2) = 2, and 2 > 1.

→ Ответить

11 лет назад, # ^ |

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).

→ Ответить

11 лет назад, # ^ |

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

→ Ответить

hex539

11 лет назад, # ^ |

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].

→ Ответить

11 лет назад, # ^ |

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.

→ Ответить

11 лет назад, # ^ |

+27

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.

→ Ответить

11 лет назад, # ^ |

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.

→ Ответить

11 лет назад, # ^ |

Not true. Maybe we can get somthing smaller than the first unused prime >50 later with combination of first 15 primes.

→ Ответить

11 лет назад, # ^ |

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.

→ Ответить

11 лет назад, # ^ |

Ok, indeed, thank you.

→ Ответить

pllk

11 лет назад, # ^ |

I just implemented a brute force search with pruning and it was efficient enough. However, I didn't consider some special cases with zeros. :/

→ Ответить

PetarV

11 лет назад, # ^ |

← Rev. 3 →

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.

→ Ответить

niklasb

11 лет назад, # ^ |

← Rev. 2 →

Hmm, did you consider cases like 4 1, 1 1 2 3, where you might need to select a 1 twice? The answer will be 0 for this case.

→ Ответить

PetarV

11 лет назад, # ^ |

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).

→ Ответить

franc

11 лет назад, # ^ |

Here is my solution based on backtracking, it corrected after considering the case 12.

→ Ответить

stas_sl

11 лет назад, # |

А что с Preventing Alzheimer's делать? Кроме перебора, что-то ничего не придумалось (( Но это долго...

→ Ответить

Rubanenko

11 лет назад, # ^ |

-20

Не долго!

→ Ответить

11 лет назад, # |

+12

Думаю, очень много 2-х попадает и часть 3-х. У многих вторая падает на тесте "3 7 7". Если что, ответ 8.

→ Ответить

11 лет назад, # ^ |

-8

у меня такого инпута нет)) есть 3 4 4 так и должно быть?

→ Ответить

11 лет назад, # ^ |

Да ни у кого такого инпута нет, зато есть аналогичные. Если на этом падает, то и на них тоже упадет.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

+13

А как решалась задача правильно?

Большинство (как и я), насколько я понял, засылали фигню, типа оставим m свободных, по остальным равномерно распихаем и попробуем обновить ответ.

→ Ответить

11 лет назад, # ^ |

← Rev. 5 →

-16

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)

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

-28

буду счастлив, если я решил правильно, а красненький нет))

счастья не произошло у меня задача упала((

→ Ответить

Anarivu

11 лет назад, # ^ |

← Rev. 6 →

Их не обязательно оставлять свободными, можно в них класть k % (n-m) монет (если при этом ни в одной из m стопок не выйдет больше чем k / (n-m) монет)
По крайней мере это проходит тест 3 7 7
P.S.: и это прошло =)

→ Ответить

rob.kh

11 лет назад, # ^ |

← Rev. 3 →

Я написал динамику F(n,k,c) представлял через F(n-1, k — full*i, c-full*i) где full — число монет в банке N, при этом считая что в банках 0..N-1 монет не меньше. Изначально работает медленно, но если full пускать по уменьшению, и отдельно обработать случай k<n, то быстро.

P.S. прошло

→ Ответить

qwerty787788

11 лет назад, # ^ |

Правильно вроде бы так. Переберем максимальное количество монеток, которые положим в одну емкость. Тогда в некоторых емкостях будет ровно столько и (возможно) еще в одной емкости оставшиеся монеты.

→ Ответить

caustique

11 лет назад, # ^ |

-12

Решалась очень просто — напишем несколько решений, сравним их с полным перебором и то, которое проходит, зашлем. http://pastie.org/8537897

→ Ответить

11 лет назад, # ^ |

Мне показали решение в одну строку: return c + max(0, n - k / ((c + n - 1) / n));.

Я сам перебирал размер максимальной кучки, а также их количество. Тогда среди оставшихся кучек нам выгодно разделить монетки поровну, причем надо следить чтобы размер всех остальных кучек был меньше максимального, который мы перебираем. И отдельно рассмотрел случай, когда во всех кучках одинаковое количество монет, а оставшиеся монеты мы выкинули вообще.

→ Ответить

NKolotey

11 лет назад, # ^ |

А как нужно разложить в кучки, чтобы ответ получился 8? До меня пока что не доходит :(

→ Ответить

Anarivu

11 лет назад, # ^ |

3 3 1
тогда если ты попробуешь взять вторую монетку из кучи и она есть, то в кучке точно 3, а если нет — то в остальных точно 3

→ Ответить

NKolotey

11 лет назад, # ^ |

Спасибо, теперь понятно

→ Ответить

NKolotey

11 лет назад, # ^ |

← Rev. 2 →

-удалено-

→ Ответить

rob.kh

11 лет назад, # ^ |

3 3 1

→ Ответить

AlexSkidanov

11 лет назад, # ^ |

← Rev. 2 →

1 3 3

UPD ниче я слоупок, три человека опередили пока я три числа писал О.о

→ Ответить

11 лет назад, # |

может кто-то подробно написать, как четвертую (Preventing Alzheimer's) решать?

→ Ответить

11 лет назад, # ^ |

Можно динамикой за 2^15*20*20*150. На самом деле, там гораздо быстрее выходит.

Задача понятно как сводится к такой: дан набор целых положительных чисел, требуется некоторые числа увеличить так, чтобы они все стали попарно взаимнопростыми. Нужно минимизировать суммарное увеличение.

Отсортируем все числа по неубыванию. Теперь запустим динамику, где состояние — это номер текущего числа и маска простых чисел, которые были использованы хотя бы в одном из рассмотреных чисел. Тогда для текущего числа мы можем просто перебрать его новое (увеличенное) значение и если набор простых в его разложении не пересекается с маской, обновить динамику. До 50 есть 15 простых чисел. Ясно, что после 50 нам понадобятся не более 20 следующих простых чисел, поэтому перебирать числа имеет смысл только до 150 (ну или какое там простое число перед ним). Теперь осталось заметить, что когда мы перебираем значение очередного числа (пусть оно сейчас равно X), то если X не противоречит маске, X — простое и оно строго больше максимального из изначальных чисел, то после того как мы его рассмотрим, можно делать break. Выходит, все простые числа, которые больше 50, будут в нашей маске всегда идти подряд, т.е. мы никогда не используем большее, если в маске еще нет меньшего. Значит, возможных масок будет не более 2^15 * 20.

→ Ответить

11 лет назад, # ^ |

большое спасибо! буду разбираться!

→ Ответить

Zlobober

11 лет назад, # ^ |

← Rev. 3 →

Альтернативный вариант: написать перебор с отсечением по ответу. Мысли:

Сведём задачу к случаю k = 1, округлив все числа до ближайшего кратного k сверху и поделив на k.
Упорядочим числа по неубыванию. Будем считать, что итоговая последовательность тоже упорядочена по неубыванию, при этом i-е число получилось именно из A[i], где A[i] — исходный возраст i-го ребёнка (нетрудно понять, что это корректно — любой ответ можно привести к такому виду).
Числа в наборе попарно взаимно просты, если ни одно простое число не встречается в разложении двух различных чисел.
Предподсчитаем все простые, участвующие в разложении всех чисел до 10000.
Делаем перебор: передаём на следующий уровень позицию, флаг, был ли ноль, значение предыдущего числа и на сколько мы уже суммарно увеличили числа. Глобально держим массив пометок для каждого простого числа, было ли оно и лучший найденный к текущему моменту ответ.
Перебираем очередное число от max(prev, A[i]) вверх, проверяя, не зацепляет ли оно какие-то уже использованные простые числа (с небольшими оговорками для нулей). Если подходит, то ставим его и рекурсивно вызываемся от следующей позиции.
На каждой итерации оцениваем, какой мы получим ответ (как если, например, мы бы поставили текущее число во все оставшиеся позиции), и отсекаемся, если мы уже получим заведомо хуже, чем оптимальный.

На тестах жюри пережёвывает все кейсы за секунду. Однако у меня есть несколько очевидных тестов, которые заставляют это работать порядка десяти-пятнадцати секунд. Мой код.

→ Ответить

I_love_Tanya_Romanova

11 лет назад, # ^ |

← Rev. 2 →

-8

Еще немного упростим.

Перейдем к k=1 и отсортируем.

Случай с 0 разбираем отдельно: 0 может быть в ответе только тогда, когда в начальном массиве все <=1. И даже в таком случае нулей не больше одного.

Отбросив случай с 0, переходим к простому перебору, начиная с пустого вектора. Обычный dfs по всем возможным векторам натуральных чисел. Нам нужен подходящий вектор с минимальной суммой, тогда ответ — это сумма этого вектора минус сума инпута. Добавляем по очереди все возможные числа. GCD проверяем прямо после проверки. Сумму можно там же. Для того, чтобы работало быстро — добавляем очевидное отсечение "если сумма не меньше текущего ответа — дальше не перебирать".

Локально худшее, что нашел рандом-стресс — 4 секунды. На тестах Facebook в общей сложности работало две с половиной. Можно пример "очевидного теста", на котором будет медленно? Хочу оценить, насколько все плохо.

→ Ответить