ОПЛ на Долгопруден

долгопруден

Хм . Аз ли съм единственият, който не се появява в таблото.

  • ko_osaga
  • Преди 2 години
  • 55

И тук така. Само хората, участвали в лагера на MIPT, са показани на таблото?

Виждаме грешка в генератора на класирането на Yandex.Contest, която няма да ни позволи да генерираме правилно класиране за състезания с голям брой регистрирани потребители (aounr 6000 за opencup кръгове поради секторната система). Проучваме проблема, ще направим всичко възможно да го отстраним до следващия кръг на отваряне. Много съжалявам за неприятностите.

Тази грешка е на поне няколко месеца =)

не точно, генерирането на дневник на състезанията за предишния кръг на отборния отбор отне около 5 минути и позволи на отборите да се появят в официалното класиране на отворен турнир (въпреки че определено далеч не е добро)

Важното за B:
НЕ ТРЯБВА да извеждате отговора като
! 2 2
11.
00

"Правилният" отговор е:
!
11.
00

Как да решим C.Array и D.Modular Knapsack?

C: Нека М = мин(A). Ако М настъпва през A веднъж, тогава отговорът е М . В противен случай помислете за първата поява на М .

Имайте предвид, че всеки а j такъв, че а j > а i, j > i са безполезни. По този начин можем да заключим, че "модулната верига" преди първото появяване строго намалява. Също така, след преминаване на първата поява, стойността х i никога няма да намалее, освен ако не е така М . Ще намерим набор от числа, които могат да бъдат резултат от х i след преминаване на първата поява.

След това трябва да намерим всички числа н такъв, че н може да се представи като. кога а i > а j > а к . Това може да стане с DP. Вид A и премахване на дубликати. Позволявам DP[i] [j] = (вярно iff j е възможен резултат след преминаване на някаква подмножина по модулна верига за дължина- i префикс). Това може лесно да се изчисли в О(н 2) и с малко битова работа можете да го намалите до О(н 2/64) .

D: Нека вместо това решим проблема за минимизиране. Изглежда, че този с голямо тегло е предимно безполезен, тъй като изглежда, че може да бъде заменен с по-малък. Тестовете са умишлено прекъснати, така че това е достатъчно. Добавете елемента в реда на тежестите, стартирайте програмата за 1,45 секунди и излезте. Можете лесно да трансформирате мин. решение на проблема в макс. проблем.