Всем привет!
До Codeforces Round #135 (Div. 2) осталось всего несколько часов. Вся подготовка раунда сосредоточена в городе Петрозаводске, где проходят традиционные сборы по подготовке к ACM-ICPC. Сегодня здесь выходной, многие поехали на экскурсию в Кижи, а я с Gerald-ом готовим для вас контест. Виталик Aksenov239 Аксенов не остался равнодушен и предложил свою помощь, за что ему большое спасибо. Спасибо Маше Delinur Беловой за перевод условий.
Задачи будут отсортированы по предполагаемой сложности, стоимость задач — динамическая.
Всем удачи и удовольствия от раунда!
С нетерпением жду начала раунда. :о
Будет интересно. А на вопросы вы же будете отвечать?
Люблю число 239 в нике. Оно говорит о порядочности и уме.
По моему, оно говорит о том ,что человек учился(тся) в 239 и вроде как все=/(кэп)
Это одно и то же, нет?:)
будут ли интерактивные задачи? :)
I got report on my email about this round and there was writen that contest was held by rules of codeforces not dynamic scoring.
Good luck everybody! May the best will win! Let's hope for an interesting problem set and a lot of hacks!
Посоны не ездите в Кижи там на комете укачивает сильно а в порту вода горизонтально на тебя летит я зонт поломал ноги промочил завтра заболею сдохну в финал не пройду
Мой желудок сегодня открыл счёт среди участвовавших в поездке. Чтоб я ещё раз на этой корыт^W комете катался в шторм.
Скажите пожалуйста , а разбор задач после раунда будет?
Спасибо за интересный раунд, хотя задачи показались в среднем легче, чем обычно.
А мне понравилось
hints for problem D needed :D please help :)
Dfs from any vertex, then ansver for vertex is number of edges goes up in path from root to it + all other edges, that goes down
1) At start find the result for the first node using bfs. 2) Again, using bfs for all neighbor nodes result differs always in 1 (+ or — depending on direction of the edge) -> count result 3) After you counted result for all nodes I believe it's obvious
How to solve E?
Use a heap to maintain all the gap each time we pop the longest gap
You are so clever ... I use segment tree to update the longest gap ...
STL is a better choice for C++.The maintain of segment tree is very complex.
+1
Отличный раунд, спасибо :)
Hi all , I have solved 4 problems (A,B,C,D), but i have spent about an hour for task B ,so couldn't get enough points: It will be fine ,that for counting points we use the time participant has spent ( counting from his/her first opening that task) , and not to use the time counted from begining the contest : Sorry for bad English :D
It's not good for system because now you can read the task and not solve it, and return to this task later.
Не подскажете, почему взлом генератором на C# возвращает вердикт "Неизвестный вердикт:GENERATOR_CRASHED" ?
Пытался взломать задачу C, параметрами 500000 2 AAAAA... (500000 раз)
А чем, кроме отсутствия необходимости отвечать на довольно простой запрос, задача Е отличается от задачи D c 68го раунда?
может быть я ошибаюсь, но если у нас будут машины стоять на парковке так: ....XX.....X.. и приедет новая машина, то мы должны выбрать не самый длинный.
Ну, то, что мелкими деталями реализации — это понятно. Еще в задаче этого раунда первые 2 машины по краям встают. Я имею ввиду в принципе
Одними из распространенных взломов по задаче С были:
3 2 AAB
или
4 2 AABB
I think systest is so slow today. Maybe it causes from to many testcase on problem B
I think the problem E should solve via Interval Tree. For each node in the tree, we store min parked space, max parked space, max interval length without parking and that maximum interval.
Slow system :(
Indeed..
Now we must wait for rating. .
не успел отослать С.
Вот моя идея:
если k=2 тогда найдём первую пару, которая стоит неправильно.
и рассмотрим два случая:
Выберем наименьший а если k>=3 то допустим нашли неправильную пару например ABB, то среднюю букву мы всегда можем поменять на третий цвет.
я прав?
на счёт k = 2, мне кажется проще проверить, что лучше ABAB... или BABA...
так я тоже самое и делаю)
Если во вопрос случае менять дальнюю букву, то верно
для k>=3 и строки ABBB такой алгоритм даст неправильный ответ
почему? он даст ABAB
Значит ты непонятно его объяснил ибо я тоже понял что он вернет acab или что то подобное
ну если под "средней буквой" в "неправильной паре ABB" понимается последняя, тогда да :)
да извиняюсь) под средней понимается последняя)
Как решать A ?
Считаешь количество различных букв, если количество какой-то буквы не делится на K, то выводишь -1, иначе пробегаешь и добавляешь в строку все буквы N раз, где N = целочисленное деление количество буквы на K. И эту строку повторяешь K раз
Посчитаем count[ch] — количество символов ch в строке. Если для каждого ch count[ch] кратно k, то выводим k раз строку, состоящую из букв, каждая из которых выписана count[ch] / k раз.
первый и самый разумный посмотреть чей-нибудь код, на которым пишешь или посчитать кол-во для каждого символова, проверить делимость на k, вывести ответ.
Считаем кол-во букв. Если кол-во какой-то буквы не делится на K, то выводим -1. Иначе k раз выводим все буквы от 'A' до 'Z' кол-во этой буквы деленная на k раз.
I used abs() function in my C++ code in problem B where it should get the absolute value between to long longs, but actually this caused a Wrong Answer in the final tests. When I removed the abs() and made it manually, it got accepted in the practice! How come something like this happen?
BTW, labs() don't work too.
There no abs function for long longs in c++ start, but as far as I remember one of msvc++ and g++ support it
I used abs() function in my C++ code in problem B where it should get the absolute value between to long longs, but actually this caused a Wrong Answer in the final tests. When I removed the abs() and made it manually, it got accepted in the practice! How come something like this happen?
BTW, labs() don’t work too.
according to this site: http://www.cplusplus.com/reference/clibrary/cstdlib/labs/ labs takes a long int as a parameter, while you use long long ints. So does abs
long ints are 32 bits long, while long long ints are 64 bits
That is correct only for a certain set of compilers (including both compilers supported by codeforces), but in general this statement is not always true. 64-bit g++, for instance, has 64 bit long
longs.When you submit C++, write in C++: 2060835
Oh I see, thanks a lot! :)
Опять я потерял один знак равенства! :-( WALL
Будет ли разбор???
Давно уж http://codeforces.com/blog/entry/5158 ;)
Here is my submission to problem B: 2054290. It gives correct output on my system as well as ideone (8JSXv). But it fails on codeforces judge (for test case 11). Is there some problem with my code ? Comments are welcomed!!
Here is my submission to problem B: 2054290. It gives correct output on my system as well as ideone (8JSXv). But it fails on codeforces judge (for test case 11). Is there some problem with my code ? Comments are welcomed!!
The problem is in using of pow() with integers. Try the following code in custom test:
long long int a=10, t=1; while(t<3) { long long int test=(long long int) (pow((long long int)10,t)); cout<<test<<endl ; t++; }Выпендривайся перед контестом @ Получай -84 к рейту после контеста
Все потому, что ты DNIWE.
http://s.pikabu.ru/images/big_size_comm/2012-05_3/13367338583921.gif
классная картинка)
а мне понравилось про 239
in problem B, it says--
what does that mean??
output should >= (p-d) and <= p
or >= (p-d) and <p
confusing!!
>= (p-d) and <= p
i am getting TLE for Problem C.
here is my try: http://codeforces.com/contest/219/submission/2067867
i am trying to solve it with DP..
any suggestions to optimize it ???
The problem is your DP complexity. It is 100000 * 26 * 26 ~= 10^8 in the worst case. One good point to think is "Do you really need a DP for all testcases?"
Add this to the start of your code. Here is my submission which ran on 1934ms : 78488193