Всем привет!
Вот и опять пришло время раунда, в этот раз это Codeforces Beta Round #91! Автором задач являюсь я, Герасимов Виталий (witua). Большое спасибо Артему Рахову (RAD) за помощь в подготовке раунда и Марии Беловой за перевод условий. Надеюсь задачи всем понравятся.
Приятного раунда!
Спасибо всем за участие! А вот и победители:
Дивизион 1:
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Тег 77+7+7 говорит о том, что нас опять ждет встреча со счастливыми числами. Я угадал? :)
Удачи всем; и после опыта нескольких последних матчей - пожелаю, чтобы матч был рейтинговым, а так же чтобы автору не пришлось прямо во время матча исправлять какие-то проблемы или баги.
Все эти тэги смахивают на некую временную меру которую прикрутили при разработке сайта, надеясь в будущем нормальный поиск добавить... Ну и подзабыли... ;-)
Помню, что, помимо семерок, автор любит еще и четверки, есть еще такое представление:
I hope I will increase my rating as well by positive "lucky" number.
bug comment
Да, наверное, тебе одному.
Is there any place here, where noobs can ask stupid questions?
May be your blog is a such place, but if care about your "contribution" you'd better to ask Google first :)
What IDE/OS do you use?
I am using Visual Studio on Windows. It would be fun to write such a tool, I am up to it, unless it is not implemented yet (which would surprise me actually).
You're welcome to implement and share it :)
Отличный контест.
Немного резкий переход между "простыми" и "сложными" задачами, ну и многовато пользователей, которые решили все. Хотя последнее, думаю, поправят систесты:)
Зато удобные понятные короткие условия, отсутствие лагов, понятные сэмплы, ну и + за тему счастливых чисел!
Сгенерируешь перестановки для 4 и 7 размером <=9
После чего находишь наиближайшие индексы к значениям для left и right.
Потом в цикле подсчитываешь все суммы (happy[i+1]-happ[i])*happy[i+1].
Или ограничения до 10^12.
А то люди пишут за O(10^9) и...
01:18:36 A Неудачная попытка взлома участником atetubou
01:26:09 A Неудачная попытка взлома участником dalex
01:28:57 A Неудачная попытка взлома участником hogeover30
01:40:22 A Неудачная попытка взлома участником flowlight
А в остальном очень хороший контест!
Partly because I'm very sleepy, I don't like those `lucky number' problems, by the way. I shouldn't have participated :-(
The idea of four being a lucky number sounds a bit odd to me, because where I live the number four (in fact even numbers in general) is considered to be very unlucky.
This is tradition from Lviv, Ukraine.
upd:
о_О оптимистично... Я хоть и знаю, что сервак быстрый, но M*sqrt(N)*С отбросил сразу...
А действительно, может пройти?
Прочитал комментарий ниже - вопрос отменяется.
После исправления бага — хранения ответа в short :Z. Ну это надо было умудриться.
Заметим, что суммарно добавлений не более 109. Поэтому втупую реализованная операция add работает довольно быстро (а после loop unrolling-а руками — ещё чуть быстрее).
Напротив, count может в сумме пройти по 1010 элементам. Чтобы с этим бороться, кэшируем последние 128 запросов на count. При запросе add инвалидируем все закэшированные запросы, с которыми этот add имеет общие точки. При очередном запросе среди всех валидных закэшированных запросов выбираем тот, от которого быстрее всего считать до нового (оценка — сумма модулей разностей левых и правых границ отрезка). Если нашли, считаем от него. Если не нашли, считаем просто в лоб.
Решение вот. Свалить его, вероятно, можно тестом, который поочерёдно делает add точкам вблизи середины и count на почти всём отрезке.
Я решал следующим образом.
Сгенерил все счастливые числа, отсортил. Далее перебираю самое левое счастливое число и бинпоиском ищу правое. А затем в этот получившийся отрезок подгоняю входные отрезки. За O(1) не придумал как подгонять. Придумал за logN с суммой левых границ, но 10^18*10^5 в худшем случае в long не помещается, поэтому пришлось использовать Бигинты.
Ну почему никто не поломал мой шедевр в C?
if (n <= 3) {
out.println(0);
return;
}
Исправил и получил Accepted :(
И у себя проглядел - упало на тесте "1 2"
Я получил на претестах WA 6, исправил про -1 в основной проге, а в этом if-е забыл. Не всегда их полезно писать...
Кстати, даже фиолетовым не стал. Все-таки сложно вылететь из Div-1, надо штук 5 подряд контестов сливать.
Ну вот, наконец, и в B дурацкий баг нашел. Как так можно писать...
задача B.НЕНАВИСТЬ
P.S. а в целом задачи отличные
а я так надеялся, что Гена отловит все мои тупые баги...
P.S. видимо, в этот раз ему было лень ломать )
Я круче, в В сначала ищу последнее вхождение тройки, которая зацикливает, а после этого использую его, как первое.
-25, снова в оранжевые, вместо плюсика...
1. When you find the a 4-7 in a odd position
>>If there is only one 7 in front of it than just replace the 7 with 4 and continue searching.
>> If there are more than one 7 like(124777) you'll stuck in a loop(124777-->124477-->124777)
2. When you find the a 4-7 in a even position
>>If there is a 4 behind the 47(like 6447) you'll stuck in a loop.(6447-->6477->6447)
>>other wise you can just replace and continue searching.
in case of "replace and continue" i increment "step" by 1. When i stuck in a loop i just check how many steps left and determine the final string from it. The complexity is just o(n).
Hope this helps.
I assume you mean div 2 problem D. The idea is, that once you encounter the string "447", where the second 4 is at an even position it will keep looping with 447 -> 477 -> 447.
If a such string is not present the amount of operations that can be done is O(n).
You thus run through the string and when encountering a 47 you check if it's in odd or even spot. If it's in an even spot you check for the terminal condition (above). If this isn't a terminal 47 we can just do the operation and either move one step forward or one step backwards depending on odd/even.
А бывало и наоборот. На Делфи - TL, на FPC - Accepted. Раз на раз не приходится.
Can anyone share idea of div1 C?
Can you please explain how do you generate the k-th permutation of SIZE numbers using O(SIZE) memory and O(SIZE * SIZE) time?
Notice that 10^9-th permutation can shift no more than 13 last numbers.
First, count number of happy numbers that could not be shifted - they all stay on their places, happy places.
After that, generate K-th permutation, apply this permutation to last numbers and find indices of happy numbers among last numbers.
upd: so many replies)
Nice problemset!
But what's the point of having hacks if there are trick/corner cases on pretests?
Not only on pretests but also on the examples. However it depends on the author which corner cases he decides to reveal. Sometimes the difficulty of the problem can vary a lot depending on the pretests and the examples.
UNFORTUNATELY , i had a stupid mistake and got wrong answer on 30th test . I have never written any contest with no silly mistakes thats why i am in 2nd division again :(((
Правда, оранжевый цвет мне нравился больше :)
Это очень просто
1) Регистрируемся на любой контест
2) На первой минуте сабмитим int main(){} на любую задачу
3) Достаем пиво и два часа наслаждаемся монитором на контесте
4)
??????system tests5) PROFIT
После того, как dalex получил +2050 на взломах, мне кажется, что это может привести к увеличению рейтинга.
For problem E in div 1, is block-array solution expected to pass? My code in the contest had some minor bugs, however I modified and it worked in practice (for example, 809913)
Right after the contest, I submit my code with O(nlogn) for adding and O(logn) for counting (using BIT) and get AC, that's really surprising!
5' ago, I resubmitted the same code and got TLE on test 62.. :(
The complexity of block-array solution seems to be O(m*sqrt(n)*log(sqrt(n)*2^10)? I don't know whether it can solve this problem without enumerate every lucky number
I am wrong， I didn't see the condition
Отличные задачи :)
С интересом решал.
Можно глупый вопрос? Как вы генерировали последовательности счастливых чисел? Мне ничего умного в голову не пришло :(
vector<int> lucky;
void gen(int num, int l) {
if (l > 0)
lucky.push_back(num);
if (l < 9) {
gen(num * 10 + 4, l + 1);
gen(num * 10 + 7, l + 1);
}
}
Запустить надо от параметров (0, 0), результатом будут все счастливые числа длиной не более 9 цифр.
void gen() {
for (int len = 1; len <= 10; len++) {
for (int mask = 0; mask < (1 << len); mask++) {
long res = 0;
for (int i = 0; i < len; i++) {
if (((1 << i) & mask) != 0) {
res = 10 * res + 4;
} else {
res = 10 * res + 7;
}
}
list.add(res);
}
}
Collections.sort(list);
}
Подсветка синтаксиса тупит и вставляет лишние переводы строк
Why is 799 almost lucky? (122A)
Cause it can be divided by 47.