Всем привет!!!
Осталось меньше 11 часов до начала Codeforces Beta Round #98 (Div. 2). Этот раунд для вас подготовил я, идеи задач мне подкинул MikeMirzayanov. По традиции RAD проследил за тем, чтобы я не посадил багов и написал нормальные условия, а Delinur перевела условия на английский язык. За что им всем спасибо!
Если вы решите поучаствовать в раунде вам придётся помочь мальчику Поликарпу и его однокласснику Иннокентию во всех трудностях с которыми они сталкиваются. Чем лучше вы им поможете, тем более высокое место займёте.
Надеюсь задачи окажутся интересными не только участникам из Div. 2, но и участникам с рейтингом больше 1699.
Продолжу небольшое повествование о себе (начало в предыдущей записи в блоге). Кроме программирования я очень люблю спорт. В течении нескольких лет до того как я начал писать код, я достаточно серьёзно занимался академической греблей. А до этого я занимался практически всеми видами спорта :-): каратэ, футбол, хоккей, борьба самбо и ещё много всего интересного. Сейчас очень люблю (особенно на сборах) играть в волейбол и настольный теннис. Я решил подготовить этот раунд несмотря на то, что в течении последних двух недель Codeforces заметно менялся внутри и я принимал в этом участие.
Следуя модным тенденциям скоро поменяю аватарку.
Всем удачи на раунде и высокого рейтинга!
UPD:
Соревнование закончено, результаты окончательные, рейтинги пересчитаны.
Top 10 (Div. 2)
Поздравляем победителей!!!
неудачное время контеста
Да и посидеть наверное удастся недолго. Однако всё равно будет оч. приятно поучаствовать - надеюсь, и своих силёнок хоть на первую задачку мне хватит! Спасибо за организацию мероприятия!
Даёш Anonymous - в группу антидоппингового контроля!
Если попытаться открыть страницы без логина, кидает на all your bugs. До начала со старыми контестами так не было
UPD: уже пофиксили
Меня и под логином выбросило туда же (на контест не зарегистрирован, естественно). Проверил на другой машине без логина - та же картинка.
Я думаю что это скорее всего превентивные меры администрации на обсуждение задач во время контеста теми, кто в них не участвует - называется, дообсуждались... :)
Рядом сидят 4 залогиненых ученика - всё видят и решают - так что скорее всего это именно так, как я написал выше.
Видно наше обсуждение этого явления обратило на себя внимание соответсвующих исполнителей - уже задачки видны как из-под логина так и для незалогиненных.
Generator is not determinate [the verification run produces different output, cmd =test].
Объясните, пожалуйста, в чём проблема
How can I use generator??
сделав задачу, отправил ее, вердикт - "решение зависло на тесте 4". Отправил еще раз - "решение зависло на тесте 1", отправил еще пару раз - уже на тесте №8, отправил еще раз - претесты пройдены. При этом менял я в исходнике только комментарии, ибо не позволяет отправлять один и тот же файл более 1 раза.
Так вот, это я что-то дико делаю не так или это распространенная проблема?
А если в последующем будут подобные "зависшие" решения - то как поступать? Ждать пока перетестируют? Но ведь надо быть уверенным, что решение прошло все тесты, а время идет...
Liked the problem set, but I cant understand how to prove binsearch in E, can anyone help?
Binary search is incorrect, can anyone explain right sol?
1. Convert the string into an integer array A. convert a vowel to -1 and a consonant to +2.
2. Calculate a sum array, where sum[i] is the summation of A[0] to A[i].
3. Now for each i, we need to find the minimum index j<=i, such that sum[j]<=sum[i]. For this I used a binary indexed tree. So for i we found the longest good substring which starts at j.
4. Thus longest good substring can be easily calculated in O(nlogn).
5. The number of times can be easily calculated in O(n).
epic fail... проспал контест на час,
за 10 минут решил Е и около получаса возился с В =)и лучше бы спал дальше...Как минимум поменять ее с Е местами...Не, она на своем месте)I agree, E was much easier to code, D took me much timeI was wrong, my sol. is wrong for E
Назовем балансом позиции в строке удвоенное число согласных минус число гласных в префиксе до этой позиции. Тогда для данной позиции самая длинная хорошая строка заканчивается в самой дальней позиции, где баланс такой же или больше. Посчитаем для каждого баланса самую дальнюю позицию, где он достигается, затем посчитаем для каждого баланса самую дальнюю позицию, где достигается он или больший, затем заново пройдем по строке и для каждой позиции узнаем самую длинную хорошую, начинающуюся тут
Сообщения выводятся в порядке их появления. Это сделано именно для того, чтобы дискуссии сильно не углублялись.
Когда разумные желания пользователей ограничены техническими возможностями — это нормально.
Но вот когда разработчики социального ресурса исходят из того, что технические возможности первичны, а желания пользователей вторичны — это, на мой взгляд, большая ошибка.
Эээ... А разве нет? По-моему, заменить гласные на -1, согласные на +2 - очевидно. Сумма на префиксах - очевидно. Единственное над чем стоило подумать - то что для каждой позиции можно итератором поддерживать последнюю позицию, где подстрока все еще не отрицательна. Значит, после сортировки будет тупо один проход.
Ну а дальше наступает "моя любимая" реализация...
my C is Denial of judgement
Anyway char tab[100] would not necessarily yield error with 100 Cs - it is possible that 101-th '\0' was placed in spare memory after the end of the array without error...
To make sure that my hack is correct , I tested it on my computer, and it caused Seg. Fault.
And unluckily enough, got -50 During hack. :(
char a[100];
char b = 5;
int func() {
return;
}
Suppose, user made writing into a[100] - what then?
If code is not optimized and data are not aligned, he will write actually into b.
If code is aligned at 4 bytes border, he will writing between end of a and beginning of b - no problem at all.
If code is optimized, b may become register variable and disappear, if code is not aligned, he will erase beginning of "return" instruction (this may lead to funny bugs).
However this depends on actual placement of data and code, architecture etc.
Thank You.
When I click on Hack, it did not do anything .
int x=1;
cout<<100000<<endl;
for(int i=1;i<=100000;i++)
{
if(x+1>1000000000) break;
printf("%d %d\n",x,x+1);
x+=2;
}
I have hacked some n*n solutions with this today.
ну когда я не умел это, я сдавал простецкие задачи на ифы, массивы и прочие стандартные вещи...
ну и как бы, даже если не знаешь сколько итераций можно успеть сделать, после 1 взлома можно понять, что гнать 2 цикла по 105 не заходит по времени
(c) Egor
Let B[i] "Balance" of the position i - doubled amount of consostants minus amount of vowels in i-th prefix. Then the longest "good" substring, which begins at i'th position ends at the farest position j, such that B[j] >= B[i]. Count for each balance the farest poisition, where we can achieve it, then for each balance count the farest position, where we can achive equal or greater than it. Finally, iterate threw a string and for each position count the longest "good" string, which ends here.
Expected solution was O(nlogn) .
One of the solution I saw, used Binary search . (Don't ask on what ;-) )
Other used some kind of tree. Binary Indexed one. (I was never able to fully remember this thing. :( )
we need to keep track of the first position in the string that has a cumulative sum less than the or equal to any given cumulative sum the first time it comes up.
Hmm, for non-negative sums, the first position is always zero.
Haha, the joke is on me: I only needed to keep track of the first position of negative cumulative sums! the array only needs to be 200,000 elements long; the length for any non-negative cumulative sum after N characters is always N.
I said: for any position let's find the string with the most length which started at this position. What is it hard to understand? I can explain it in another variants, but I can't understand what's the trouble.
UPD: I'm understand
thank you for the contest... :)
waiting for the next contest and expecting a better performance next time..