X Открытый Кубок имени Е.В. Панкратьева по программированию Northern GP

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

-15

Может фишандра?;)

→ Ответить

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

← Rev. 5 →

+21

Наблюдение 1:

Сначала в суффиксном массиве идут позиции 0-ов, затем позиции 1-ек.

Наблюдение 2:

Если в конце нашего числа стоят k нулей, а потом единица, то в начале нашего суфф массива будут числа n, n-1, .., n-k+1, а число n-k будет первой позицией среди позиций, которые начинаются с 1, в суффиксном массиве. (потому что это строка 100..0 - это мин лекс строка, начинающаяся с 1)

Решение:

Смотрим сколько чисел вида n, n-1, .. идут в начале суффмаса, находим, где начинаются единицы. Получаем возможный ответ. Осталось его проверить. Это можно сделать либо построив суффиксный массив возможного ответа, либо посчитать частичные суммы хешей, а затем проверить, что каждые два суффикса в порядке суффиксного массива действительно упорядочены (делаем БП, чтобы найти на сколько элементов двух суффиксов совпадают, сравниваем хэшами, смотрим первые несовпадающие символы)

А:

1). Строим выпуклую оболочку. Добавляем к ответу кол.-во точек на ней * кол.-во точек не на ней. (Это если мы исключим любую точку не на оболочке)

2). Берем все четные точки оболочки + все не точки оболочки, строим выпуклую оболочку этого набора. Тогда получается, что мы исключили из оригинальной ВО каждую нечетную точку и заменили чем-то, что бы было если бы мы убрали ее. (Понятно, что наборы точек, которые добавяться в ВО если мы удалим 1,3,..,2х-1 точку оболочки не пересекаются, потому что они лежат соответственно в треугольниках 0-1-2, 2-3-4, 3-4-5,..

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

3). Делаем абсолютно ту же процедуру для четных точек вместо нечетных.

4). Если всего точек нечетное число, то надо проделать такую же процедуру еще для одной точки (мы сделали на 3 и 4 шагу для к/2 и к/2 точек оболочки соответственно, где к - ее размер).

→ Ответить

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

← Rev. 2 →

В A ещё можно вместо разбиения на чётные и нечётные честно выкидывать каждую точку из выпуклой оболочки и смотреть, сколько получится теперь точек на участке от предыдущей до следующей. Прикол в том, что каждая исходно внутренняя точка попадёт в не более чем два таких просмотра, и поэтому весь проход получится за то же самое линейное время. Ну, и отдельно обработать точку номер один.

→ Ответить

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

Кстати, а как определить, в какие просмотры попадает каждая точка?

→ Ответить

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

← Rev. 2 →

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

→ Ответить

tunyash

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

← Rev. 2 →

B можно было вообще без проверок. Рассмотрим пару соседних элементов суффиксного массива. Пусть это суффиксы длины l₀ и l₁. Тогда посмотрим на суффиксы длины l₀ - 1 и l₁ - 1. Если l₀ - 1 лежит в суффмассиве после l₁ - 1, то первый символ l₀ равен нулю, а первый символ второго - единице. Назовем такую позицию разбиением. Очевидно, что сначала в суффиксном массиве идут позиции нулей, потом - единиц. Тогда, найдем все разбиения. Если разбиение не единственно, то ответа нет. Но, если единственно, то ответ всегда есть. Вроде бы, понятно почему: нет противоречий. Строго доказательство сформулировать не могу. Те, кто еще так писал, можете объяснить?

→ Ответить

Urbanowicz

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

Пусть алгоритм нашел ровно одно разбиение. Тогда очевидно, что если есть какая-то бинарная строка, для которой данная перестановка П является суффиксным массивом, то эта строка единственна, и мы ее уже знаем. Теперь покажем, что условия, которые проверил алгоритм, являются достаточными для того, чтобы это П действительно было суффиксным массивом.

Рассмотрим первую часть перестановки П, где все суффиксы начинаются с нуля; в другой части все аналогично. Для всех этих суффиксов алгоритм проверил, что если мы откусим от каждого из них первый символ, то получится последовательность суффиксов, которая является некой подпоследовательностью исходной перестановки П. (Действительно, мы проверили, что каждая пара таких соседних суффиксов лежит в том же порядке, в каком они находятся в П.)

Так как это подпоследовательность исходной перестановки П, то первые символы суффиксов в ней тоже будут идти в пордке …0000111… Таким образом, по крайней мере по первым двум символам суффиксы отсортированы правильно.

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

Вот. Надеюсь понятно, как это превратить в строгое доказательство.

→ Ответить

igor.silin

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

Расскажите, пожалуйста, как решать задачу про простые числа, где их на две группы надо разбить, или ошибку объясните. Написали ДП + ДА, не зашло.
ДП :

a[1] = 1, b[1] = 2, a[2] = 2, b[2] = 3;
a[i] = min(a[i-2]*p[i], b[i-2]*p[i-1]);

b[i] = max(a[i-2]*p[i], b[i-2]*p[i-1]);
p - заранее посчитанный массив простых чисел.
Ответом будет a[n].

Заранее спасибо за помощь.

→ Ответить

sdryapko

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

← Rev. 2 →

Мы заранее просчитали все значения, а потом их просто выводили. Просчитывали за О(2^n), программа выполнялась где-то 10-15 минут.

→ Ответить

igor.silin

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

Аа, ну да, забыли мы про это. А длинку писали?

→ Ответить

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

За 2^n - это как-то по-умному в порядке кодов Грея чтобы каждый раз менять всего 1 бит или что? Потому что у меня было .. несколько дольше:)

→ Ответить

knightL

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

Я за 2^n написал обыкновенную рекурсию.
solve(id,mask,double a, double b)
id - номер простого, которое мы будем сейчас размещать.
mask - какие простые попали в первую группу
1) если id==n и a<b, то мы смотрим, улучшили ли мы результат, и если да, то запоминаем новое b-a и новую маску
2) Иначе пытаемся положить простое id-тое простое в первую группу и во вторую группу.
solve(id+1,mask|(1<<id),a*p[id],b);
solve(id+1,mask,a,b*p[id]);
При переборе можно спокойно забыть о длинке. Даблов хватает. А вот ответ по маске уже придется восстанавливать ею

→ Ответить

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

уверен что хватает? там вроде больше чем 18-20 знаков было, а даблы вроде больше и не хранят...

да и сложность получается не O(2^n), а O(2^n*n) ибо ты ещё углубляешься в рекурсию...

→ Ответить

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

А больше в этой задаче для нахождения правильного набора и не надо.

А сложность всё-таки O(2ⁿ) - от углубления в рекурсию лишнего n вроде не должно появиться :)

→ Ответить

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

специально залез посмотрел:

177792163538134124432895

24 символа, разве дабл возьмет столько?

а n всё таки думаю появляется, с делящей его константой, но появляется...

→ Ответить

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

Конечно возьмёт. Куда он денется?

Только отдаст он 177792163538134124429312, а не столько, сколько взял.

Но нам и этого хватит, чтобы максимум найти.

Про n: Ну откуда оно появляется?

→ Ответить

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

=============================================

т.е. ответ ищем в даблах, а уже в конце считаем длинкой точно?

по поводу n да, думал что угулублясь и возвращаюсь получится что-то... но нет...

→ Ответить

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

← Rev. 2 →

=======================================

Да, в даблах.

Я, чтобы не писать длинку, вывел сами числа через звёздочки и вставил это в виндовый калькулятор.

Там (в даблах) вроде только четыре последних числа неточно считаются.

→ Ответить

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

===================================

классные приемчик - "ручная длинка", правда применима только при небольших входных объемах информации

→ Ответить

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

======================================
Не проще ли вместо таких извращенств написать на Java с BigInteger ? :)

→ Ответить

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

============================================

Иногда, когда пишу что-то на Java с BigInteger, кажется, что вся Java - это одно большое "извращенство" :)

→ Ответить

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

================

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

→ Ответить

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

← Rev. 2 →

double

→ Ответить

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

А проблем с точностью не было?

→ Ответить

Kenny_HORROR

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

10-15 минут? Круто у нас под час генерилось...

→ Ответить

dalex

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

У нас в Петрозаводске 3 часа генерилось :)

→ Ответить

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

А в 64-битном компиляторе G++, если использовать 128-битные целые числа, то перебор за две с половиной секунды генерит все ответы.

→ Ответить

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

← Rev. 2 →

А с добавлением слова inline - меньше, чем за две...

→ Ответить

ifsmirnov

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

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

→ Ответить

ifsmirnov

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

← Rev. 2 →

повтор

→ Ответить

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

Я просто написал перебор всех подмасок (2^30 * 30 * BigInteger), запустил в районе 0:20 и сдал в районе 2:40 константы:Р

Но мне кажется, что тут надо было написать просто рюкзак + meet in the middle, разбив все на две части так, чтобы в каждой произведение простых не превышало 2^64, и решить где-то приблизительно за (2^10+2^20)log(2^20) рюкзаком и или константы или оно и вовсе проходит без них.

→ Ответить

ballon

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

← Rev. 5 →

у нас перекалк работал где-то 5 минут
ми искали первое число как максимальное число не больше квадратного корня с произведения первых N простых чисел, использовали даблом для произведений, поддерживая при етом маску использованых чисел
потом просто по маске искали ответ, длинкой

→ Ответить

Skird

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

Можно же вроде за $\text{[math]}$ , ведь одно из множеств меньше 15. А это уже совсем немного.

→ Ответить

steiner

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

← Rev. 2 →

Вообще-то там сумма цешек, равная примерно 2^n-1.

→ Ответить

Skird

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

Хм, да, логично.

→ Ответить

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

Я написал meet-in-the-middle + бинпоиск - все ответы сгенерились за пару секунд, однако на написание и придумывание потратилось не меньше часа, так что, наверное, оптимальнее было написать очевидный перебор.

Решение такое (рассмотрим сразу для случая n = 30).
Разбиваем на 2 части произвольным образом - например, берем первые 15 чисел в одну половину и остальные 15 в другую. Перебираем все возможные произведения в каждой половине и складываем в массив, а затем сортируем (2 * (2 ^ 15) * (1 + log(2 ^ 15)) ~= 2 ^ 20. Дальше перебираем все числа из первой половины и для каждого бин. поиском находим самое подходящее число во второй половине ((2 ^ 15) * log(2 ^ 15) ~= 2 ^ 19).

Итого решение работает 2^20 * скорость операций с BigInteger.

P. S. Не понял, как в этой задаче использовать рюкзак. Можно пояснить?

→ Ответить

tunyash

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

← Rev. 2 →

Хм. То есть, в оптимальном ответе кол-во сомножителей в обеих частях не превышает $\text{[math]}$ ? А почему?

→ Ответить

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

Мы как раз находим ту часть в которой сомножителей не больше n/2 . Смысла находить в одной части больше n/2 множителей нет, т.к. во второй части их будет меньше n/2 и оптимальнее искать будет вторую часть.

→ Ответить

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

Я немного накосячил в объяснении. Дело в том, что моя команда писала это Гран-При на сборах в Ижевске неделю назад, поэтому я забыл детали. Теперь вспомнил.

Нужно хранить в два раза больше информации.
Рассмотрим, как считаем числа для первой половины (первые 15 штук).
Пробегаемся по всем маскам (2 ^ 15): когда зафиксировали маску, перемножаем только те простые числа, которым в маске соответствует единица. Однако еще удобно посчитать другое число - произведение тех простых, которым в маске соответствует ноль.

Таким образом, есть два массива пар бигинтов - A[2^15] и B[2^15].
Отсортировали их по неубыванию по первому числу. Понятно, что в таком случае вторые числа будут отсортированы по невозрастанию.

Пусть зафиксировали индекс i в первом массиве.
Мы хотим найти такое j во втором массиве, что
F(j) = (A[i][0] * B[j][0] - A[i][1] * B[j][1])
принимает минимальное значение. Как мы уже знаем, если j возрастает, то B[j][0] тоже возрастает, а B[j][1] наоборот убывает. А[i][0] и A[i][1] фиксированы, поэтому с возрастанием j функция F(j) также возрастает. Раз функция монотонная, применим бинпоиск. В ответ мы запишем A[i][0] * B[j][0], такое что F(i, j) минимальна (тут уже i не фиксирована). В первом множителе перемножено до n/2 простых, во втором тоже, так что количество сомножителей в ответе может превышать n/2.

→ Ответить

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

Ну, это и есть задача о рюкзаке: нам же надо набрать величин как можно ближе по произведению к корню из произведения всех простых. А чтобы делать это не втупую за 2^30, используется М-и-М.

→ Ответить

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

Кто может пояснить причину таких малых ограничений в J? Там же вроде бы от порядка ничего не зависит? То есть можно для каждой територии посчитать минимальное число юнитов, необходимое для захвата, и получаемое количество очков, а затем просто перебрать все маски территорий с проверкой, что область связная и включает границу, нет?

→ Ответить

winger

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

← Rev. 2 →

Именно так. Только вот масок там C(30,10), повышать дальше уж некуда).

→ Ответить

igor.silin

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

-10

Динамическое-то решение кто-нибудь писал?

→ Ответить

PeaceDeath

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

мы писали

→ Ответить

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

Ребята рассказывали, что по B проходила проверка строки сортировкой суффиксов, обрезанные по 256 символов...

→ Ответить

agul	13 лет назад, # \| 0 Киньте ссылку на условия, пожалуйста. → Ответить

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

на сайте уже есть... выбрать этап и пошел...

→ Ответить

agul	13 лет назад, # ^ \| 0 Спасибо) → Ответить

BLIZZARD

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

Как G решалась?

→ Ответить

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

Обычная Дейкстра.

→ Ответить

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

-7

да вроде это потоки, насколько я понял поток + чуть динамики... честно говоря потоков не знаю, так что утверждать не могу

→ Ответить

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

Я её сдал в дорешивании обычной Дейкстрой.
Веса ребер - w[i]
Граф - неориентированный.
Ищем кратчайшее расстояние от 1 до n вершины. Если оно меньше C, то выводим Unfair и востанавливаем ответ, иначе - Fair.

→ Ответить

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

я один в шоке, что такое решение проходит?

→ Ответить

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

Теперь, похоже, я тоже)))

→ Ответить

http://mirror.codeforces.com/comments/2735#comment-56456

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

походу не в ту ветку отправил...

→ Ответить

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

+11

Гы-гы. Станкевич на разборе сказал, что на то и рассчитывал, что люди будут думать над задачей на потоки. Даже ограничения специально маленькие, чтобы пострашнее было. Ну, там, строго говоря, конечно, действительно надо найти поток минимального веса, но поток величины 1. Да, пожалуй, если бы в условии задачи была картинка *trollface*, её бы сдало больше народу :)

→ Ответить

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

← Rev. 2 →

Первая мысль которая возникает при прочтении задачи - макс. поток. И, вы правы, ограничения на это намекают. Немного подумав, я решил отправить в дорешивании Дейкстру не сильно надеясь на ОК. Я был очень удивлён:)

→ Ответить

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

-15

Первая мысль, которая возникает при чтении ЛЮБОЙ задачи - правильно понять условие.

→ Ответить

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

← Rev. 3 →

но разве там всегда выгоден поток величины 1 или просто этого условия достаточно ???!

→ Ответить

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

Вам ведь даже уже объяснили почему...

→ Ответить

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

спасибо, не заметил

→ Ответить

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

По идее стоимость каждого следующего увеличивающего пути будет не меньше предыдущего, поэтому смысла делать минкост нет.
У меня была другая проблема, не увидел в условии, что можно выбирать направление у трубы, поэтому не добавлял обратных ребер и хапнул 10 бревен. Даже писал минкост, но видимо для того чтобы убедиться в том, что поток не нужен.

→ Ответить

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

Кто-нибудь, расскажите, пожалуйста, как решалась задача I (про социальную сеть и френдлист).

→ Ответить

tunyash

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

Будем поддерживать кол-ва сообщений написанных к текущему моменту каждым из пользователей и set друзей каждого пользователя. Когда добавляем какого-нибудь пользователя A в друзья пользователю B отнимем от ответа для A текущее кол-во сообщений пользователя B. Когда будем удалять пользователя A из друзей пользователя B, прибавим к ответу для A текущее количество сообщений у пользователя B. В конце удалим всех друзей у всех пользователей и посчитаем ответы.

→ Ответить

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

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

→ Ответить

pva701

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

действительно классное решение, но думаю большинство решило, так, как описал yarrr или как-то подобно, до такого красивого решения, как у тебя, непросто додуматься сходу

→ Ответить

yarrr

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

Для каждого пользователя запишем действия, связанные с ним в вектор. Действия по добавлению и удалению разобьём на два, т.к. они, связаны с двумя пользователями.

Очевидно, что таких записей будет не больше 2m. Научимся их обрабатывать для каждого пользователя.

Заведем массивы when[n], pluses[2*m] и вектор добавленных.

Идём по действиям пользователя. В pluses[t] мы будем поддерживать количество сообщений, которые запостил пользователь:

pluses[t] = pluses[t - 1]

pluses[t] = pluses[t - 1] + 1, если тек. действие -- пост сообщения.

В when[p] будем поддерживать момент времени, когда мы добавили пользователя.

when[p] = curTime, если тек. действие -- добавление пользователя.

При удалении, нам нужно для этого пользователя добавить к ответу:

pluses[curTime] - pluses[when[p]].

Вот. Единственный момент -- остались пользователи, которых не удаляли. Именно для этого нам был нужен вектор добавленных, мы пройдемся по нему и для всех неудаленных юзеров увеличим ответ.

Код: http://pastie.org/2589935

→ Ответить

pva701

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

+1) точь-в-точь такое решение

→ Ответить

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

Понятно. Спасибо большое за столь понятный, содержательный ответ и код.
Решение довольно простое и понятное. Я же думал над какой-нибудь крутой структурой:)

→ Ответить

Vaness

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

Ага, мы не сильно задумываясь написали декартово дерево.

→ Ответить

pva701

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

я тоже хотел писать декартово дерево, но мой сокомандник меня переубедил, что он придумал что-то проще пищущееся

→ Ответить

ValenKof

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

Мы так же вычитали кол-во сообщений при добавлени и прибавляли при удалении. Но в конце, чтобы не было nlogn, прошли по списку в обратном порядке, заменяя + на - и наоборот. Потом ответы надо поделить на 2.

→ Ответить

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

надо проверить только тот случай когда поток равен 1... т.е. найти минимальный путь и его проверить, т.к. все последующие увеличения потока будут увеличивать стоимость в больше или столько же чем в первый раз, т.е. f(a) * c будет расти медленней чем сумма используемых w_i

→ Ответить

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

спасибо за объяснение, задача была расчитана на "лоха" ((( и я повелся(

→ Ответить

Sereja

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

← Rev. 2 →

Для ясности лучше написать, что для следующего потока нужно еще один путь из 1й в Ную вершину(те ребра что уже есть ничего не дадут), который будет больше-равен 1го, то есть только ухудшит ситуацию.

→ Ответить

map	13 лет назад, # \| 0 Обычное моделирование → Ответить

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

← Rev. 2 →

уже ответили

→ Ответить

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

Как решать F? Что-то не могу найти зацепку, чтобы написать динамику или оптимизированный брутфорс.

→ Ответить

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

при добавлении очередного 0/1 надо проверить что условие по прежнему выполняется, т.е. надо найти все позиции на которые добавленая 0/1 влияет и если она была ещё хорошей то превратить её в плохую... исходник пока не буду кидать, полезней будет...

→ Ответить

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

Т.е. перебор с начала? Просто я написал перебор с конца слова, но видимо отсечений больше, если перебирать с начала.

→ Ответить

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

← Rev. 4 →

Перебирай с начала без всяких отсечений.
Я написал на Java, складывал строки без всяких там стрингбилдеров, насоздавал кучу ArrayListов и все равно прога летает.

А причина в том, что таких строк всего 384 (всех возможных длин) и существуют они до длины 37.

→ Ответить

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

А я специально писал на С++, все строки и массивы заменил битовыми масками для максимальной быстроты. Но тупанул от усталости в концовке с перебором с конца :)

→ Ответить

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

хм, наверное и больше... но навен

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

→ Ответить

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

Для последних я могу, но сумма позиций будет постоянно меняться у последних чисел, в итоге там получается отсечение в стиле - "даже если все оставшиеся позиции я сделаю хорошими и мне все равно не хватит для ответа, то return"

→ Ответить

http://lurkmore.ru/%D0%A1%D0%BF%D0%B5%D1%80%D0%B2%D0%B0_%D0%B4%D0%BE%D0%B1%D0%B5%D0%B9%D1%81%D1%8F

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

+10

Полконтеста пытался понять, почему моя J получает WA4 - после контеста оказалось, что в слове "defence" была опечатка :)

→ Ответить

ivan.popelyshev

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

Мы в петрозаводске в команде со сборной солянкой умудрились 8 сдать :) В D вообще такой бред пропихнули...

→ Ответить

winger

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

В D правильное решение - на каждом шаге максимизировать максимальный суммарный размер обрабатываемых поддеревьев

→ Ответить

AlexErofeev

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

Интересно было услышать поподробнее :)
Как и про С и E :)

→ Ответить

Jacob

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

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

→ Ответить

Chmel_Tolstiy

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

А Вы сами много качественных контестов/задач сделали ?

Вообще всегда считал, что в Петрозаводске не самое главное супер качество тестов, ибо все равно потом команды могут написать и правильное решение, а того лучше добавить тест против неправильного. Другое дело, что теперь эти задачи ставятся на кубок, ну и понятно, что более полный набор тестов сюда поставить нельзя ибо нельзя будет переносить результаты команд со сборов.

Я не оправдываю автора, но и наезды делать думаю, что не стоит.

→ Ответить

AlexSkidanov

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

> А Вы сами много качественных контестов/задач сделали ?

→ Ответить

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

← Rev. 6 →

E. Elections (Division 1 Only!)

У нас решение вроде как правильно, но ВА12. Идея вроде как очевидная - динамическое программирование. Суть в том что можно перебрать значение A, оно будет не больше чем s + 50, так как сумма m_i ≤ 50. Затем считается динамика f_i, j, k, i - количество обработанных партий, j - сколько людей уже взяли, k - сумма выбранных людей по параметру a. Если писать динамику вперед, то получаем, что из f_i, j, k можем перейти в f_{i + 1, j + x, k + a(i, x)}, где 0 ≤ x и j + x ≤ s и k + a(i, x) ≤ A с увеличение на |a(i, x) / A - v_i / V| или в целых числах |a(i, x) * V - v_i * A| (a(i, x) это значение a_i если я выбрал из i партии x человек). Ответ для нашего A будет находится в f_n, s, A.

Вот мое решение (перебор значение A я делал как 4 параметр в дп)... ~~кто разобрался или решил её буду очень признателен, если сообщите (или лучше намекнете) мне в чем баг...~~

UPD.

Ответ для нашего A будет f_n, s, A / (A * V).

Также подправил своё решение, но по прежнему ва12...

UPD.

Сделал INF поменьше и условия в конце стали проще...

UPD

Немного не так понял условие, перефразировал по своему - в моем решение нельзя было выбрать a_i одним из тех, который отказывался из i-ой партии, а идея в принципе правильная. Решение подправил. Большое спасибо туристу.

→ Ответить

Chmel_Tolstiy

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

Леша, тебе не кажется, что ты ошибочно целевую функцию считаешь ?

→ Ответить