Привет всем!
Рад приветствовать вас на очередном раунде Codeforces. Надеюсь, что недавняя цветовая революция и несколько более позднее время проведения раунда внесут некоторое разнообразие в процесс решения задач:)
Автором задач сегодняшнего раунда являюсь я. Раунд помогал готовить RAD, на английский язык задачи перевела Delinur.
Всем удачи.
UPD.
Раунд окончен, рейтинги пересчитаны.
Победители div1:
1. Egor
2. tourist
3. unicef
4. sevenkplus
Победители div2:
1. RainbowDash
2. cjtoribio
3. miraliv
5. majia5
Ура!
У нас в Казахстане в Атырау контест будет до 00:00 o_o в некоторых других регионах страны будут до 01:00 писать.
Не усните там =)
По-моему, тех, кому удобно писать в будний день в 10.00 МСК (как 15.11) должно быть очень мало.
mind it, he is no professional, but an (international) master :)
Just a reminder, a contest starting at 1:00am or 2:00am local time is really inconvenient for the people live in East Asia.
what's worse!!
for an Australian...the contest start at 3:00 am local time ><!
That's why I like when the contest time vary a lot, like TopCoder. If it's not a good time for you today, it will probably be a good time in the next round.
But this is an international site right where most participant are outside russian. I think CF must anticipate contest time. most in Indonesia CF contest start at 10 PM and now it start on 12 AM.
О, контест Ripatti, сразу вспоминается задача про химические элементы :)
When trying to hack I'm being put on standard bug page
думаю что у вас где то ошибка в округлении...
я убил себе мозг поиском ошибки в задаче (C div. 2/A div.1)...
уже 9 неверных отправок
не нравится мне 8 претест
похоже на то
но я ещё кроме целочисленного посылал с double решение но оно тоже падало на 8 претесте
Скорее тест 1 1 1 1 1
Хотя нет, на нем же хакать можно
C div 2(A div 1) и D div 2(B div 1) imho надо было местами поменять
Да и A с B в div 2 тоже
В целом контест неплохой :)
Я тоже бинпоиском досдал. Сначала находим за один проход все такие подстроки, которые являются и префиксом, и суффиксом, запихиваем их в массив. А дальше бинпоиск по длине ответа.
Простите, не заметил, что ниже то же самое уже написано. =)
BECEJIb4AK_U, а у тебя линейный поиск зашел по длинам, если я правильно прочитал твое решение? Там строки такие замечательные, что ответ быстро находится?
==================
Блин, я тоже так делал, только по возрастанию делал и получил тл51, поменял на убывание и сразу прошло((
ну просто раунд #91 и #93 вообще в сравнение никак не идут...
P.S. да и не все любят такие математические задачи
P.S.S и как бы A(div2)-1130человек, В(div2)- 1078человек, С(div2)-152человека, ниче себе так разрывчик
Что надо написать в параметрах генератора. Из за этого я не смог взломать ( .
1 1000000 1 1 999999
I would like to see the solution without hashing that fits the time limit.
Edit. Especially I don't understand why KMR algorithm got TLE?
Egor
How do you make your own library in java
It is solvable by KMP. You must count the length of the maximal prefix that is also a suffix for each position, let's say in table p. Then you are interested in checking if p[n-1] is also somewhere in the middle (if p[n-1] = 0 the answer is NO). To check this, it's enough to count the number of positions where p[i] = p[n-1]. If there is more than one such position it means that we have found substring somwhere in the middle. If not, then you must use the fact that another maximal prefix that is also a suffix is p[p[n-1]-1]. You check if it's greater than 0, if yes than you have your substring otherwise, the answer is NO.
как решалась C(div2)?
а ну да действительно
но бинпоиском по времени тоже должно проходить если правильно все написать))
Я указателями двигался, с учетом монотонности функции - вроде правильно.
Можно готовую формулу?
Посчитаем для каждого возможного количества воды из первого крана, какое минимальное количество воды надо взять из второго, чтобы при смешивании получилась температура, которая нам подходит. Если нельзя взять столько воды (например, краны 10 и 20 градусов, надо температуру 20, а из первого что-то взяли), то определим функцию как x2+1.
За исключением варианта, когда ничего не берем из первого крана - функция будет монотонной. Логично - ведь если подкрутим первый, то смесь станет холоднее, и надо подкрутить так же и второй, чтобы снова стало не ниже требуемого. Поэтому весь миллион значений можно посчитать двумя указателями (подкрутили на 1 первый - подкрутили на сколько надо второй, если второй еще не переполнен).
Дальше просмотрим все варианты (для каждого варианта из первого крана мы ведь уже знаем, есть ли уже подходящий вариант из второго, и если есть, то какой именно) и выберем тот, который дает минимальную температуру, запомним ее.
Дальше еще раз просмотрим все, и среди всех вариантов, которые по температуре в пределах эпсилона от оптимального, выберем тот, где максимальный суммарный напор воды.
y2 = y1 * (t0 - t1) / (t2 - t0)
Не факт. У меня на 6 претесте падало, когда я неправильно обрабатывал случай t1 == t0 == t2.
PS. Я не прав.
Сдал на последней секунде задачу D (div.2), не знаю правильно или нет... Но условие там сформулировано не очень. Не беря в расчет опечатки ("Суффикс считал, что строки t должна быть"), там написано "Обеликс же посчитал, что t должна ..., то есть не являться ни ее началом, ни ее концом" - если чисто логически/математически подумать, то в таком случае всегда ответ "Just a legend", потому что нельзя удовлетворить всех.
Потому что t - результатирующая строка, по условию "должна" "не являться ни ее началом, ни ее концом".
P.S. Конечно из тестов видно, что это не так... но в целом условие получается противоречивое.
Из условия: "Астерикс выбрал подстроку t так, чтобы угодить всем своим спутникам", т.е. t должна удовлетворять мнению Обеликса.
Из того же условия: "Выведите строку t", т.е. t - есть сам ответ.
Из условия: "Астерикс выбрал подстроку t так, чтобы угодить всем своим спутникам.", т.е. t - это одна строка, а не несколько.
P.S. t - это набор символов и не более. ;)
Жду не дождусь увидеть этот коварный 6 претест в C(div 2) ;D
UPD: P.S Сегодня определенно не мой день, надо было D делать а не бессмысленно париться с C, спасибо за отличный раунд, буду делать выводы.
Хотя немного обидно, что D есть в OEIS. Кстати, это помогает? Я что-то не пойму.
Никак не пойму, почему в C (Div2) (3 претест) ответ будет не "114 81"
Потому что на 114+81 надо делить, а не умножать. Хотя с этим претестом все равно что-то не так. Если считать всё целочисленно (умножить обе части неравенства на y1+y2), то получается, что при y1=38, y2=27 t ближе к t0, чем при y1=76, y2=54.
Ой, затупил, так считать нельзя :(
дабл
Потом все проверят... У меня лично их было вроде штуки 3...
Нормально ли то, что контест тестится в режиме "эмуляция контеста" - посылки тестируются не подряд, а в моменты посылки?
Вроде такое уже когда-то было.
Хоть семеро меня минусуйте, но для 11 вечера задачи слишком сложные...когда не очень соображаешь и находишься в полусне, хочется решать задачи на подумал-написал, а не думал-думал-думал-ни фига не придумал и бросил (сугубо личное мнение)
В результате получился такой код:
- if (prefixHash1 * p1[n-len] != suffixHash1 && prefixHash2 * p2[n-len] != suffixHash2) {
- return -1;
- }
Моя невнимательность в два раза повысила шансы коллизий (правильно || вместо &&). К счастью, авторы не валили хеши, и я жив)А... ну тогда надо делать не break/return из цикла при не прохождении проверки на четкое соответствие, а continue.
P.S. Просто с хешами всегда проще и лучше перепроверять ответ.
Автору минус за вторую задачу. Спасибо конечно, что я не получил по ней минус из-за своей невнимательности, но автору все равно минус за задачу)
Точнее, за тесты. У меня прошло неверное решение, в котором классический баг (забыл забрать с этапа дебага) - слишком маленькое основание хэша.
У меня вместо 47 оставлено 17. Это меньше размерности алфавита, и очень легко поймать коллизию.
Т.е. строки типа 18-1 (18ая буква и 1ая буква) и 1-2 (первая буква алфавита и вторая буква алфавита) считаются равными.
Если вы выбираете случайные элементы, то контртеста нет. Может случиться, что возникнет ошибка, но только если рандом сойдется очень неудачно. Но такого на наборе из 100-200 тестов не случится. То есть, упадет не из-за того что составители тестов молодцы, а из-за неудачного стечения обстоятельств.
В прошлом комментарии ошибка.
Как уже выше говорили, функция ответа от длины не монотонна. А n log n с хешами и так заходило.
P.S. А я затолкал А-шку, но мне это не дало абсолютно ничего...
generated here
for(int i = 0; i < 1000000; ++i)
s[i] = (i%2 ? 25-i%26 : (i%26))+'a';
for(int i = 0; i < 1000000; ++i)
s[i] = (i%100 ? 25-i%26 : (i%26))+'a';
i think is really hard to optimise it, probably imposible :/
if (t2 == t0) {
out.println(0 + " " + t2);
return;
}
Вам изначально дали 1500 очков рейтинга и теперь отняли 55)
Вот
хуже, оптимизатор. при добавлении левой строчки выдаёт верно и проходит тесты.
странно, до этого был обнаружен код, где mvc в отличие от gnu коряво работает с double, теперь вот наоборот...
Удивительно. Я сталкивался только с сильно разным временем работы.
продолжение
ещё один код, работа с double, mvc - ac, gnu - fail.
По задаче С:
Походу перебор всех состояний холодной воды О(х1) и нахождение для каждого состояние количество теплой воды за О(1) не катит.
Does it have anything to do with optimizers ?
подскажите по задаче С(2див)
Там можно было просто посчитать (t2-t0)/(t0-t1) и перебирать y2
а y1=y2*(t2-t0)/(t0-t1)
и потом считать какое меньше всех отличаеться после округления.
AFAIK на наших контестерах пробовали внедрить 2008-й вижак, но в итоге оказалось, что в нём всё только гораздо медленнее - видимо, т.к. STL стала тормознее. И в итоге откатились обратно к 2005-й. Не знаю, возможно, с этой тормознутостью можно бороться какими-то флагами компилятора...
(Правда, есть вариант сделать доступными обе версии на выбор - как с G++ поступили)
Все достаточно просто - есть стандартная динамика a[i][j], где i - номер позиции в системе счисления, j - разница между записанным в 1..i числом и тем, что надо получить. В этой задаче можно заметить, что получаемые j в фибоначчиевой системе счисления записываются как a_1*fib[i] + a_2*fib[i+1] + a_3*fib[i+2] + a_4*fib[i+3], 0 <= a_k <= 1.
Дело в том, что fib[i+4] и больше разницы будет иметь ответ 0.
how can we recognize that the bath is going to be fulled? there is no data about bath size :?
vector<int>v[2000]
as you said... but the case is the same.
actually i was intended to have a map of the positions of the certain character that appears in the string. and whren i get char x at position i in the given string i do the followings:
v[x]<--i ; so i should need actually v[] of size 124. think problem is some where else.....
А студенты и работающие люди типа ой как свободны в 10 часов.
Да-да, конечно, дискриминация. Из Владивостока, например, писать в 17:00 школьникам намного удобнее, чем в 02:00, всем не угодишь. Радует хоть какое-то разнообразие.
Thanks. :)