Если вы не спите в час ночи и не знаете чем заняться, то у меня есть для вас хорошие новости. В час ночи 17-го января 2014 г. состоится Testing Round 9, цель которого протестировать хорошенько платформу перед завтрашним раундом. Мы порелизили большое количество внутренних изменений, которые не видны пользователям, но влияют на всевозможную функциональность системы.
Раунд будет неофициальным, нерейтинговым. Мы постараемся дать вам новые задачи, уверен, многие из вас получат удовольствие от их решения.
Если вы видите какие-то изменения в функциональности, то пишите о них в комментариях.
Спасибо.
UPD. Контест закончен. Спасибо всем, кто принял участие.
А интерактивки когда в раундах появятся?
А как их взламывать?
Существуют интерактивки, где это можно реализовать. Например, игра "Угадай число с logN попыток". В инпуте (для интерактора) хранится число, которое надо угадать, это же и будет взломом.
При этом в полигоне, судя по всему, даже менять ничего не придется — инпут для интерактора находится ровно там же, где инпут для обычных задач.
Может быть, 17 хомячков расскажут, что же я не так написал?
Забавно, сразу же плюсанули.
У меня одного рейтинг перестал отображаться ?
АПД. Спасибо :)
Сейчас починим.Он вернулся.а куда делась строка отображения рейтинга?
При регистрации: "Вы регистрируетесь "вне конкурса", причина: рейтинг должен быть от 0 до 1,699 для возможности регистрации на это соревнование".
Хм...?
Я может раньше не замечал, но, кажется, страница обновляется сама онлайн
it's allowed to know the type of these improvements ? :D
All improvements are relatively deep inside Codeforces system and are mainly made to improve performance. So you won't see anything, except, maybe, faster page loading.
Why always Testing rounds are at a very very unusual time?!
Я заблокировал в домашней сети vk.com и теперь кодефорсес стал заметно медленнее грузится, в левом нижнем углу отображается надпись ожидание от vk.com, но через некоторое время страница загружается. Не знаю было ли это раньше
the duration changed?
No, but the starting time yes.
Originally durations was 1 hour.
Yes sorry, didn't saw time when the comment was written :/
Что и старт отложили?
Не дождемся...
Момент номер раз: Не появилось всплывающее окошко, сообщающее о начале раунда. Chrome
Странно, у меня было.
Подтверждаю, Chrome (Win7).
В комнате, если открыть информацию о чьей-нибудь посылке, а конкретно о взломанной посылке, то сначала написано "Полное решение", потом "Решение взломано". Не помню было ли так раньше, но логичней писать "Претесты пройдены", а не "Полное решение".
UPD: Ну в принципе в общей таблице так же.
Первая задача элементарная
Как ее решать, ковбой?
Для каждого покупателя запоминаешь цену, которую он предлагает, и его порядковый номер. Сортируешь всех по убыванию предлагаемой цены и выводишь индекс первого и цену второго покупателя.
Да, красиво, я так же решал. Ваше решение можно несколько упростить, если использовать pair<int, int> вместо структуры human. Тогда можно использовать стандартный компаратор, это делает код более лаконичным.
да, достаточно изящно, разобрался, спасибо.
Да, действительно, я просто не сразу додумался до использования пар, а потом уже не стал переписывать код. Эта задача года два назад у нас в Саратове на муниципальном этапе была.
Задача D : Я не умею писать bfs или там что-то другое?
Просто bfs.
А это нормально, что я все еще не могу просматривать решения других участников?
Will there be an editorial for this round ?
I am not sure if editorials are written for testing rounds.
A. 3 main approaches:
1) Select two indexes of the two biggest values with one loop.
2) Sort numbers in pairs with their indexes.
3) Select max index. Then find max value which is different from the previous found.
B. Sort all numbers and use one loop for l, other for r, then select max(r — l + 1), where a[r] — a[l] <= t. You can use "two pointers" too.
C. Find the number of substrings which have d <= i (not exactly i), for each i from 0 to 26. Then the exact answer for each i ([1; 26]) is res[i] — res[i — 1]. How to do that? Well, here you could use "two pointers". Keep the number of distinct letters (there are 26 of them, make a small array to keep their counters). Go through all l, then keep extending r if the number of distinct letters is not more than i.
Adding r: increases the number of distinct letters if the counter of this letter was 0.
Leaving l: decreases the number of distinct letters if the counter of this letter becomes 0.
D. Use BFS where the positions are defined as the indexes of taken vertices. For each member in the triple try to change its location (if the colors are the same as it is said in the statement). Let's remember which member we have changed as well as its old value. We break from BFS if we dequeue a triple which when it is sorted gives (1, 2, 3). We can restore the path from the end to the beginning recursively.
For details look into my solutions.
do you know any tutorials or examples for "two pointers" ? i heard about "two pointers" but don't know exactly what it is .
You can see this post for example
http://codeforces.com/blog/entry/4586
The are a lot of problems tagged as "two pointers" here in Codeforces for practice.
can any one explain how to solve problem C ? i don't think there will be tutorial for this 'Testing' round .
I have 26 counters (one for each possible k) and a vector with the last position for each c, updating this vector for each char of the string.
Example: For "abacd" at char "d" the vector will be:
(a, 3) (b, 1) (c, 2) (d, 4)
If you sort by the second element in decreasing order
(d, 4) (a, 3) (c, 2) (b, 1)
You are at char 4 right now. From the vector you know that the range from 4 to 3+1 belongs to k=1, from 3 to 2+1 to k=2, from 2 to 1+1 to k=3 and the rest to k=4.
The cost is O(26*size of the string)
My solution failed during the final tests because I was printing at the only up to K=25 :(
i read your solution ant got it :) thanks !
Wow, very nice, I unnecessarily complicated it.
When processing the ith character, I found the last occurence of that character(like you did) and had a list of prefix sums as to the number of occurences of each character upto that special character(these diversities do not change). And then, I modified the new diversities like you did. And to top it all, I had the long long bug. :D
If I'm not mistaken there was no typical window with text "Contest has started. Would you like to enter the contest area?".
I saw it. And used.
Like this round. It was sudden and pleasant. Unfortunately, my crooked hands didn't let me make workable my two-pointers-O(n) and really unsophisticated solution in C =__=
Извините, а как решать задачу C.
dp[i][j] — количество подстрок, заканчивающихся в позиции i и имеющих уникальность j. Пусть где-то в строке есть еще один символ s[i] (из всех таких рассмотрим крайний правый), тогда все подстроки, начинающиеся после этого символа, будут иметь уникальность больше на единицу. Если подстрока начинается до этого символа, то ее уникальность останется такой же. Так же нужно не забыть учесть новую подстроку (i; i). Для того чтобы пересчитывать быстро стоит заметить, что если мы рассмотрим подстроку (0; i), потом (1; i) и так далее, то уникальность будет неубывать. Поэтому если максимальная уникальность на отрезке 0..i-1 равна x, то подстрочки (0; i), (1; i) ..., (dp[x] — 1, i) имеют уникальность x. Следующий dp[x — 1] подстрочки имеют уникальность x — 1 и т.д. Тогда можно пройтись по их количеству за размер второго параметра и посчитать сколько из них начинаются до правой встречи s[i], сколько после. O(N*26). Если что-то не понятно можно взглянуть на мое решение.