Доброе время суток!
Через несколько часов начнется очередной Codeforces Round #147 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Игорь Кудряшов (Igor_Kudryashov), Павлик Холкин (HolkinPV), Геральд Агапов (Gerald), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).
Традиционно всем удачи, полных решений и удачных взломов!
В раунде будет использована стандарная разбалловка: 500-1000-1500-2000-2500
UPD: Соревнование завершено, поздравляем победителей:
UPD: Разбор уже опубликован тут.
:-W
Gerald always gives a hand to prepare the problems in recent contests :D
Надеюсь что контест будет решаемым для обоих дивизионов. Всем удачи!
Спасибо.И тебе удачи!
sorry for posting here but,My contribution is -69,I do not know what to do :(
Just be yourself, dude. Don't get upset about any negative numbers :)
choose picture of a pretty girl for your account !
And why don't you do so?
cause i don't care .
Rejoice?
Oh, Poor man, No one can stop me click +1 。。
Надеюсь сегодняшний контест будет не хуже предыдущего.
Have a good contest everyone! :)
в тот раз уже спрашивалось, почему разбаловку скрывают вплоть до начала раунда, но никто не ответил на этот вопрос, так все таки, почему?
PS. да почему этот вопрос игнорируют? или не царское это дело администрации отвечать на вопросы пользователей
Ничего себе "чуть позже" :)
Согласен.
"чуть позже", к сведению, значит "за 5 минут до начала".
Оказалось, что где-то за 15 минут
What advantages does the stardand scoring system have over the dynamic one?
I prefer dynamic one :D
Стандартная разбалловка, класс !
seems, there is huge change for me to be hacked today.... :P
I want to be in your room in this case.
yes..... after a long time.... none of my solution (A, C) hacked.... :D
Me too, so we can hack each other :) Let hack and find who is the better =]]
Заплывший мужчина
Заплывший такой
В заплывшей кровати
Лежит никакой.
Автор : Ионас Пакальнишкис
2730 -это случайно не рекорд !???
Не пойму, что надо курить, чтобы сделать задачу D? Ее тут кто-нибудь понял вообще?
Подвешиваем исходное дерево за лист, тогда вершины — пары (x, parent(x)), , тогда рёбра есть между (x,parent(x)), (parent(x),parent(parent(x))). Все баллы чисто за условие.
5, ведь решалась mincost-maxflow?
Работает, так как граф хороший.
Граф называется хорошим, если на нем всякая фигня работает.
А почему не проходит решение: 1) Построить весь граф 2) Запустить MaxFlow? Точнее, работает до первого max теста
Обычный, не mincost? Он же на всем подряд валится:
Что мешает ему выбрать вторую строку? (Ну, кроме порядка обхода вершин)
Отличная идея)
Возникли проблемы с окном (страницей) взломов. Вот скриншот. В лисе 16.0.1 под win7, если пытаешь проскролить до кнопки "Взломать", то скролл просто уменьшается и страница увеличивается. Получается можно только с помощью клавиши Tab изменить фокус на кнопку "Взломать" и потом нажать Enter.
Исправьте пожалуйста этот косяк.
Может у тебя ctrl запал? Бывало такое, постучал по ctrl, все стало ок
Нет, косяк в странице.
я на такие дела держу несколько браузеров)
тоже было, уменьшил шрифт страницы...
Такая же фигня. под Ubuntu, тестил на Chrome и Opera.
Thanks for the good contest
Хороший контест. Сложность задач порадовала.
Расскажите, что нужно было сделать в C. Условие замудренное (.__.)
Найти минимальное l, чтобы все подотрезки длины l содержали не менее k простых чисел
По-моему самая понятная задача контеста :-D Нужно было найти такую длину отрезка, что если идти им по участку от a до b, то в отрезке будет не менее k простых чисел
расскажите решение а то мои решето, дерево отрезков и бинпоиск не проходят по времени.
Решето Эратосфена + бинпоиск + 2 указателя. Upd. Всего 78 мс на макс.тесте.
Расскажите, как вы два указателя использовали? Я не могу понять, куда их воткнуть :( Я считал количество простых на префиксе, потом для отрезка совсем легко пересчитывать.
Вместо префиксных сумм(двигаем отрезок, если (left — 1) — простое, то уменьшаем сумму, если right — простое, то увеличиваем(отрезок [left..right]).
Спасибо
Решение С за решето + О(n) — без бинпоиска: Соберем все простые числа из нашего отрезка в массив р. Найдем максимальную разность (p[i+k]-p[i]) — это наименьшее L, покрывающее k подряд идущих простых чисел. Очевидно, ответ будет не меньше. Это L по сути подходит для любого внутреннего подотрезка. Значит, осталось проверить только "слева" и "справа". Найдем наименьшее x такое, что x>=a+L-1 и на отрезке [a,x] не менее k простых. Заменяем L на x-a, если нужно. Аналогично с другой стороны. Код, 46 мс.
Хороший подход)
Правда с бинпоиском тоже 46 мс)
У тебя правильная идея, только надо было просто заменить дерево отрезков частичными суммами.
check out my output here http://ideone.com/aCIGH7
when i run it as a custom test here i get this output instead
if I change the 2d arrays to maps instead i get the desired output. Any idea why this happens?
array nums is very small. we can have up to 2500 numbers.
Как ломали А7
У меня четверо(!) на:
3 10 15 10 15 10 15
Многие писали что-то такое:
Что приводило к грустным для них последствиям :)
кроме перечисленных, был один написавший А за квадрат.
Wow , very fast judging :D
System test is really fast !!!
But rating update so slow!!!
Как решать E?
Wow, what a fast judge!
Отличный контест! :)
Really enjoyed the contest. And it also helped me identify a bug in our ACM team's notebook. Many thanks to the author :D
скажите а почему в задаче С нельзя было хранить минимальную длину для каждого х между a,b такую что в этом отрезке k простых чисел? и потом просто идя от начала до n- l обновлять наш l как максимум из t[x] и l?
мда( обидно крайний случай не учёл когда а = в и упала таска :(
Кто нибудь сдавал С за n*log^2 ?
Такая асимптотика не должна заходить, так что сомневаюсь.
у меня зашла с такой асимптотикой)
Значит, можно было спокойно писать обычное решето Эратосфена?
Не понял. Ассимптотике решета ой как далеко до n * log^2(n)
Разве его асимптотика не O(n* log (log n) )?
Именно. Только теперь я не вижу связи в ваших комментариях. При чем было это?
Я увидел, что у людей заходит O (n* log^2(n)), и мне стало интересно, можно ли было писать обычое решето вмето решета за O(n), ведь O(n* log(log n) + n * log^2(n) ) = O(n*log^2(n)).
Откуда N*log^2(N) то?
Находим обычным решетом все простые числа, сохраняем их в массиве prime. Потом бинпоиском подбираем l. внутри бинпоиска пробегаемся по числам, смотрим, сколько простых чисел умещается на текущем отрезке (x, x+l-1). для этого, аккуратно используя в моем случае upper_bound и lower_bound над массивом prime, ставим первое и последнее простые числа в отрезке. ну и находим между ними расстояние. итого асимптотика получается n*log^2(n).
А что, окном пробегаться трудно?
не самый лучший раунд:
А и Б можно было сделать поинтеллектуальнее,С — в некоторых раундах это 4мерная дп или бешеные хэши (раунд 141), а в некоторых вот такая халявка, Д — не понимаю, зачем такие задачи давать, просто надо понять укуренное условие, и она сразу переходит в разряд уровня B/C, Е — безыдейная, знаешь потоки (таких в див2 мало) — сдаешь, нет — без шансовA и B, по-моему, были нормальными для A и B.
ну да, я погорячился А и B правда норм...
Насчёт Д согласен:)
Спасибо, отличный раунд, очень все понравилось )
i am from China i am sorry i can't use English well i only wrote A problem and C problem The B problem can make a right answer and check with read by computer i don‘t know how to do D AND E who can help me
Problem D was difficult to understand even for those who know English. Can someone explain Problem D with an example.
I think the question had it well explained. The reason for not putting a bit complicated example is that it would be too easy to guess the answer, rather than getting the information from the problem itself :)
Yes, the description was quite clear. The main thing here to understand is the the minimum weight will always be 2. Now just try to think of a way to connect the nodes.
Problem E is Standard Min Cost Max Flow problem.
Тест 11 к задаче А корректен??? 10 человек приходят в один момент и их обслужит одна касса? По-моему, нужно 10 касс =)
Ответ как раз 10, а Ваша программа выводит 1.
С чего вы взяли что там одна?
Спасибо, неправильно протокол понял.
Today is my unlucky day I save my solution for problem C in file B.cpp but I upload C.cpp to judge
i did the same mistake in a round last month..... :(
I always use the same file to code, after pass the pretest I clear the code and only use my macro.
I don't knw why I am getting "Idleness limit exceeded on test 8"....... for Problem B. Seems mysterious for me..... plz help...
http://www.codeforces.com/contest/237/submission/2434517
Maybe its because the declaration
co place[mo];where mo is only 101. But it should be 100² + 1 because the number s can be at most 100²Oh thx..... now it is accepted...... I thought I would get RTE for these.... anyway good experience without any penalties...... thx again....
There is no reason to vote negative at this comment, he has the good answer. place[i] is used for store the position on the array of the cell who has number i on it. So, 1<=i<=s, 1<=s<=n*max(ci), 1<=n<=50 and 1<=ci<=50.
Edit: oups, too late: the comment has received new positives votes before I post my comment
You are right cup_of_tea....... this definately help me in future contest.... Thx god it was not rated for me... gdisastery really deserves positive feedback... But I cannot vote twice... maybe I have to try from different ID..... :D
Omg, really fast judge!
Ожидается ли разбор? А то моё решение B, абсолютно наивное и лобовое (бегаем по строкам снизу вверх, каждый раз ищем максимум всего нерассмотренного, кладём в конец строки, укорачиваем строку) как ни странно, зашло, но я видел чьи-то решения, судя по количеству вложенных циклов, куда более быстрые; было бы полезно увидеть их в текстовой форме.
Разбор уже выложили: http://codeforces.com/blog/entry/5648
I am facing a strange problem in the practice session . My solution for problem C is returning -1 for the first test case when i submit my .cpp file but it returns the correct value ( 3 ) when running in my pc.
Try Custom Test :-)
Did you set all the variables to zero?
Контест классный!!!!!!!!!!!!!!
I'm looking to be on top10 contributors, could you help me ? =/
Post funny comments with memes (or not) will not suffice for become top contributor. If you really want to progress, you should make interesting posts on your blog, or give interesting answers.
Anyway, Good Luck!
I'm kidding man.
No one could find it out, even when looking at kiddy-kiddy Po on your ava:)
Is it rated?
Why not? There was no mistakes on statements/examples, the server was stable, the contest has not an odd name, so I will be very surprised if it isn't rated...
i think yes
All contests are rated!
I think it's not rated yet!!
Be patient
Testing is fast — very good.
Rating update is slow — not very good.
Just joking
Sucks that I kept getting WA on C because I put == as opposed to >=. On the bright side, you can do C in linear time as opposed to using a binary search.
Really? Remember that the sieve of Eratosthenes is O(n log log n) ;)
In fact sieve of Eratosthenes can be done in O(n) Linear_sieve
Yeah I wasn't taking into account the sieve at the beginning.
I saw a lot of binary searches and I thought maybe my algorithm wrong. Good thing that wasn't the case.
Judging was too fast but rating dont provide yet...I thing something is going WA...:D
it's so slow...
yap...But i just get d rating...:)
Here is a screencast of me solving this round: youtube To watch comfortably (and see clear text), choose 1080p and watch full-screen on a 1920x1080 resolution or higher. I will also provide a file in 1680x1050 for download later if you prefer.
Good, very useful video! thanks
Can you upload your "Hightail" program? It may be useful
It's not yet ready to be called even pre-alpha or something (most of the buttons just outright don't work), but if you're interested: github IF you want to help with development, that would be very very welcome. There is a ready list of tasks (issues) on the github page.
And the file download is ready.
Dude, just keep doing it! I think it would be great to have some alternative on Egor Youtube channel.
Here are the cheaters! wangyedong CHFB_oXbT 389804652 jionghehe Their E Codes are the same!
Registered: 22 minutes ago And you're registered just to say that they're cheaters ?
They pretend to be Japanese, But their function names are in Chinese :(.
waiting for editorial! thanks already
in problem E. Build String , we should write min cost flow algorithm , but what will be in the role of nodes ? From which node to which are we finding flow ?
As I see it, you need n+26+2 nodes: a node for each given string, a node for each distinct letter in t and source and sink. The edges will be:
a) source -> string i, with capacity ai and cost i (no more than ai characters can be erased from the i-th string and each operation costs i).
b) string i -> letter c, with capacity [the number of times c occurs in the i-th string] and cost 0 (to erase at most as many letters as there are in the i-th string).
c) letter c -> sink, with capacity [the number of times c occurs in t] and cost 0 (we shouldn't erase more c-s than there are in t overall).
thanks , i found out now . Firstly i thought flow was going from each string to the main source. :)
Problem E is Standard Min Cost Max Flow problem. China's NOIP don't test it, I think i need not do it now; i also want to know what the problem 4 mear
We are waiting for the editorial.
In the problem C I am using binary search to find the minimum value of l.prime[i] stores the number of prime numbers upto i.I am using the following code to return true or false.
bool check(int l) { for(int x=a;x<=b-l+1;x++) { if(prime[x+l-1]-prime[x-1]>=k) return true; }
return false; } and I am getting the wrong answer. Please tell what is wrong in my approach.
It should be this :
bool check(int l) { for(int x=a;x<=b-l+1;x++) { if(prime[x+l-1]-prime[x-1]<k) return false; } return true; }@problem setter : Editorial ??
Hi NALP,is there any editorial for this round?
UPD:Could anyone tell me how to solve prob D T-decomposition?
can anbody plzz tell me wats wrong with the following code..its giving wrong ans on pretext 10
include
using namespace std;
define MAX 11111
int a[MAX][2]; int main() { int t; cin>>t; for(int i=0;i<t;i++) cin>>a[i][0]>>a[i][1]; int cash=1; int maxcash=1; for(int i=0;i<(t-1);i++) { if(a[i+1][0]==a[i][0]) { if(a[i+1][1]==a[i][1]) cash++; else { if(maxcash<cash) maxcash=cash; cash=1; } } else { if(maxcash<cash) maxcash=cash; cash=1; } } if(maxcash<cash) maxcash=cash; cout<<maxcash<<endl; return 0; }
plz reply
You are not getting Wrong Answer but Run Time Error. Increase the size of your array : change
#define MAX 11111to#define MAX 111111.will we have an editorial for this round?I am not able to solve the young table problem,could someone give a hint?
My approach:sorting
for any young table,like
a1 a2 a3 a4 a5 a6
a7 a8 a9 a10
a11 a12 a13 a14
a15 a16
the following satisified: a(i)>a(i+1)