Всем привет!
Совсем скоро, 16 декабря в 19:30 MSK состоится Codeforces Round #156, автором которого являюсь я. Это мой второй раунд на Codeforces и я надеюсь, что не последний.
Спасибо Steps09, Seyaua и sdya за помощь в тестировании задач, а также Gerald за помощь в подготовке раунда. Отдельное спасибо Delinur за перевод условий на английский.
Разбалловка в первом и во втором дивизионе стандартная: 500-1000-1500-2000-2500.
Настоятельно рекомендую прочитать условия ВСЕХ задач.
Gl & hf ! :)
Контест окончен, надеюсь вам понравилось :)
Поздравляю победителей див1:
1). YuukaKazami
2). al13n
3). rng_58
4). Bigsophie
5). KADR
И победителей див2:
1). ShadowSong
2). ynbpdy072
3). jiaobu
Настоятельно рекомендую прочитать условия ВСЕХ задач. Это значит, что они не обязательно расположены по уровню сложности??
Это значит, что автор рекомендует прочитать условия всех задач.
Это значит, что "сложность" — субъективная штука
Если задачи не расположены по уровню сложности, то разбалловка должна быть нестандартная, на мой взгляд.
Да ладно
Это значит что скорей всего будет весело
More like "lack of lag and luck" — when you say it with the right accent it sounds really hilarious, but still makes sense :D
Seyaua и sdya теперь официальные тестеры на CodeForces? :)
Does this contest require any file input or output ?
I don't think so.
Thanks :) !
Usually, we don't need to get input from files. The two last contest were exceptionnal, because it was for a local stage in Saratov. If it isn't indicated, the input and output are standard.
Moreover we can write code that will check if such file exist and then read and write here, otherwise use standard IO.
Usually we don't have permissions to read files :P
Thanks ! I will have that in mind from now on ! :)
Задачи наверно будут интересные...Желаю всем ++color.
Нагин — автор задач? Ну всё, прощай, мой фиолетовый ранг :(
Почему ? :)
Твои задачи на ДП очень трудные.. Я в этой теме итак не профи, и до решений задач C и D твоего прошлого контеста сам бы не додумался.
Да не парься, больше 100 рейтинга нельзя потерять за один раунд)
Will the scoring be dynamic or standart?
No dynamic scoring, I promise.
And will it be 500-1000-1500-2000-2500, as usual?
I don't know, temporary.
If problems will not be sorted by difficulty, I don't think that scoring will be 500-1000-1500-2000-2500 as usual.
I strongly recommend you to read ALL the problems.
You see :D i don't think the score will be the same as usual :D
As a matter of fact we have contest in both divisions and as each contester can see the others' problem so it is hard to separate problems . :D
Пусть контест будет интересным и запомнится всем на долго! Желаю всем удачи! P.S. С Днем Независимости Казахстан!
Спасибо!
Всем желаю удовлетворительных результатов, особенно HKL)
It's not the first time lots of solutions are in queue =(
Очередь на десять страниц... :(
I need a clarification, the integer 'q' in div2-C is always an positive integer ?
I think it can be negative.
thank u! :)
But... in proper solution it doesn't matter
In Div2C does q need to be positive, because if no then in the second test case:10 20 10 30 the example can be 4 or I am missing something?
yes, q can be -
On problems page (dashboard) there is [ASK QUESTION] button !!! ( So you should not ask questions in blogs during contest) =)
I didn't know this man. Take it easy, relax.
I didn't know that. I am sorry if I disturbed someone.
hi can help me about problem c? i dont know what is say
given a sequence b, find longest sequence q in the form of
a,b,a,b,a..... where a and b are integers.
Well the server is tottaly trolling me. I submit on problem D and it cost more than a minute to running on test 8. I though it will TLE. Then I decided to resubmit it, When I resubmit it my last submission got passed. Now I get -50 for my submission and penalty minute.
Sorry, but it was your choice. Lag is to be expected, you should've waited for the result.
Кто нибудь знает, из за чего D Div 2 может падать на 15 тесте?
Из-за переполнения.
How solve problem C ???
Maintain a list of indices for each different value. I missed just a couple of characters in my code, and I got WA :(
Я, к сожалению, даже после 3 кларов не знаю, правильно ли я понимаю условие задачи D...
каких кларов?о_О
Моих вопросов жюри и ответов на них
Не успел доломать решение из-за очереди в конце. А контест кайфовый.
Почему в задаче С для интервала от 16 до 81 число Шпрага-Гранди равно 1, а не 2?
Оно равно 2
упс, кажется я нашла ошибку, вопрос отпадает...
Предвижу, что почти у всех Е(div 2) упадет, либо тесты будут фиговые.
Респект за задачу Е. Даёшь нетрадиционные деревья отрезков! :-)
У меня вполне традиционное (только для подсчета ответа), что я делаю не так?
Ну, её можно очень коротко и красиво написать со следующей идеей.
Давайте в вершине дерева отрезков хранить значения динамики по маске (т. е. D[a][b] = количество способов заполнить отрезок, где в левом конце лежит значение a, а в после правого конца лежит значение b). Фишка в том, что мы такие динамики можно "подцеплять" одну к другой.
По мне так очень красиво. У тебя такое же?
Я предподсчитал для всех возможных (длина, что слева, что справа) отрезков ответ, а потом в дереве отрезков просто хранил ответ в вершине для отрезка, который в ней начинается (или 1, если в ней не начинается отрезка). Тогда ответ в каждый момент времени — произведение всех значений в дереве. Остается только с помощью трисета находить самый ближний не 0 справа и слева от точки запроса и все аккуратно расставлять
Ну вот, нечто подобное было первое про что я подумал. Но меня конкретно заломало аккуратно разбираться с тем, что куда ставить, и искать ближайшие слева/справа значения. А в таком дереве отрезков как у меня, все запросы делаются единообразно — один раз написал функцию merge(A, B, y), которая слепляет две матрички с динамиками, соответствующие отрезкам [l; y) и [y; r) и используешь её везде — и в изменении, и в запросе ответа.
2781042. Остаётся надеяться, что это моё добро не упадёт :-)
UPD: Прошло!
What's the trick in D? Why counting a number of sequences in which number (n-k) appears exacly (n-k) times and there isn't any other number q that appears exacly q times is wrong?
I guess number of i such that a[i] appears exactly a[i] times should be equal to n — k.
There may be some numbers s_i such that each number s_i occurs exactly s_i times and the sum of all s_i is n-k.
Let's assume n = 4 and k = 1. Does the sequence 1, 2, 2, 4 is good? There are 2 possibilities: either first person always tell the truth or second and third does. We can't know anything for sure.
For the fourth person we are sure that he is lying. Each of the first three people may be telling the truth. So the sequence is correct.
I have some trouble understanding Div1D. If 0<k<n, then nobody can answer 0. How can Serge with such answers find out that not everybody is a liar (if everybody is a liar, then everybody can answer anything)?
If X people tell the truth then exactly X people must answer X.
I had the same trouble for a while.
For example, suppose that there are two people A and B, and they answered 1 and 2, respectively. Then there are two possibilities: {A honest B liar} or {A liar B liar}. You can conclude that B is a liar, but you have no information about A. You concluded that k = 1 people (B) is a definitely liar.
do you have an algorithm that does not require to make a table beforehand?
I can only figure out a solution with time complexity n^4 :(
Author solution is n^4 dynamic programming. And precalc (n is power of 2).
umm...so why not just make n<=50?I don't know the intention of force competitors to make a table :(
My solution is O(n^4) too.
OK, thank you! I thought Serge would be able to say that there are exactly k people lying (no matter which), not that there are exactly k people for which he knows that they are lying.
Понравился контест, второй дивизион. Жаль стал разрываться сразу между двумя задачами, и с и д были клевыми. Как в Е писать теорию игр на таких ограничениях не совсем понял.
funny!! couldn't understand div2-C in contest time. :(. i could solve it... :(
please explain your algorithm
you can see solution of others within a very short time :)
where can see solution?
(you can filter status page using 'status filter' portion in the right side)
Thank you very much :)
u wc :)
Did anybody use binary search in div2-D, or it's bad idea to do it?
I think many people would have done it using binary search on the number of steps.
I could count numbers until this wave will reach any wall, but what to do then?
You can find out the number of cells filled in T steps in O(1). It is easier if you consider the simpler problem where we start filling an A*B (A<B) box starting with the bottom left cell filled.
Then you should count cells switched on which are outside of board.
These cells formulate a triangle. There are at most four triangles (one for each side). And some of them can overlap.
Thx for clear explanation, I'll try)
count how much of them out of the field using arithmetic progression
border1, border2, cap1, cap2 is distance to border and top from start. if cell on edge, then here coord are abs(bx — x) + abs(by — y) = step, step is current number of step, x, y from input. After we have line of fill edge cell on each side, we can calculate square with (a-1) * b /2, a-how mach cell if fill on this edge, b — is height step out borber, (step — distance to this side)
I think so.
Interval is 0..2n-2
This problem was similar with last COCI exam !! Isn't it ??
UPD: I mean solution of them were similar.
I must learn to read problems really. I have misunderstood DIV2-E :@ :@ Complicated it for nothing :@
дурацкая Б — какие-то шизофренические формулы
Можно было не писать шизофренические формулы, а чуть больше подумать и накодить решение вообще без разбора случаев.
посмотрел ваш код, однако, у вас есть некий разбор случаев, у меня же его нет, но формулы дурацкие, они так-то несложные, но можно ошибиться, я думаю, у многих подобное решение
У меня не разбор случаев. Я просто запихиваю все возможные вершины многоугольника в вектор, затем выбрасываю лишние и потом для него ищу количество целочисленных точек внутри.
Очень интересный подход :) Мое решение тоже вроде как без формул (2781504): поделил ромб на четыре треугольника, а потом считал, сколько из каждого треугольника попадает в заданную область.
У меня тоже в таком стиле — делил всю область на четыре прямоугольника, затем считал для каждого по отдельности.
Да, пока пишешь на ум приходит — зачем так жить? А потом ещё и претесты не проходит.
So slow
So obvious :P
There are two reasons to try to solve a problem faster .
UPD: Now I can sleep and relax. No problems with my solutions. I prefer sleeping than waiting for rating change and be late for school tomorrow.
Thanks for the advice, but actually I meant slow system testing phase
It seems the systest will take a big amount of time... a previous round written by me also have this problem... It is because put so much big test in problem A or B, that kind of easy problem has many submissions, so if one submit need 50 seconds, then the whole judging will last for hours :(... so I hope the later writers can take care of it :)....
радует сдача участником Bigsophie задачи Е на 13 минуте
Какой то таргет балуется.
and one thing....who is Bigsophie ?
maybe there will come someone like Petr2 or ACRush2 ? (just joking :) )
may be WJMZBMR2 !!!!
I found who he is by his code....
a hint: he use lemon() a lot :)
And what does it mean?
>>see<<
I think, he meaned "who uses lemon() besides tourist2" :D
And I was thinking why I have negative votes (=
By the way, his solution of todays div1-B (2777959) includes many useless procedures and functions, it seems that he's trying to make his code difficult to read, and it's a bit unfair because, I think, CF rules include some prohibitions like that.
this is not the case.... that code is an solution for a another problem, which is the same as today's B but has many point at the start not one. this is very difficult indeed and require tons of code.. he just use that big weapon to shoot at this easy problem.. this is ok bcz CF allow you to use previous code written by you.
But his solve2(), slove3() .... etc are equal to each other! :D
read carefully...they're not equal and every one work for some case... but indeed it can be replaced by 4 rotation ...
oh, my mistake, they are different))
I know who you talking about. :)
I got TLE when I sent Prob B div 2. I think this solution does not spend more than 2 second running. I lost 50 point in that.
strlen() function works in O(n) time
Thanks
The rate of comments in this blog is more than the rate of system testing !!!
из примечания задачи Б: В первом тесте изначально закрашена одна клетка, по этому ответ 0.
может, все-таки, "поэтому"?
в задаче С: Ваша задача — узнать, кто выиграет в данной игре, если и Фурло и Рубло играют оптимально.
может нужна запятая после "и Фурло"?
в задаче С: Другими словами после описанного хода игрока в выбранной кучке останется y монет.
может нужна запятая после "Другими словами"?
в задаче Д: Выведите m целых чисел — i-тое число, должно быть равно...
видимо, запятая не нужна?
Главное что смысл задач понятен :)
не спорю, но когда ошибок нет — вдвойне хорошо
На мой взгляд отличный контест, спасибо за это Sereja
Спасибо :)
Да, контест реально крут, задачи классные). Спасибо Sereja
Sereja, спасибо! :)
Самое суровое решение задачи Div1 — D : 2777535
Это и планировалось. :)
Problem A turns out to be harder than expected
Yes, I think many people tried an optimized O(n^3) solution.
Div 1 or Div 2??
Div1
this systest need one codeforces contest time
Обожаю концепцию расстановки сложности задач на Codeforces.
да ладно, все-таки не так много Е решило, да и когда раунд готовишь, тяжело вот так объективно оценить: кому-то будет проще, кому-то сложнее
А никто и не говорит, что легко оценить. Я даже больше тебе скажу — от автора контеста особо-то разбалловка не зависит. Я, когда давал контест, хотел сделать все задачи одной стоимости, но мне не разрешили. А хотел я дать все задачи одной стоимости именно вот из-за таких случаев.
Ага, а более сложные задачи будут в итоге стоить меньше ибо их пишут позже и дольше.
Гыгы, а многие не заметили, что в задаче B c <= 10^9, и можно решать без бинпоиска?
Есть тест с ответом 999999999
Как там может быть такой тест? У нас же поле не прямоугольное, а квадратное.
Да, что-то меня сегодня глючит
Я заметил, но вы наверное имеете в виду линейное решение, а у меня О(1): 2782985
Суть в том, что количество включенных клеток изменяется с некоторой начальной скоростью (клеток за секунду) и ускорением. А ускорение изменяется только при достижении сторон и углов. То-есть мы имеем 8 контрольных точек, в которых можем сразу посчитать количество включенных клеток. И найдя из 8 интервалов времени, тот, на котором получим необходимое количество клеток, мы решаем для него квадратное уравнение, и получаем точный ответ.
Жаль, во время контеста не успел сдать из-за багов=) Ещё и в С в одной цифре опечатался, и как результат, WA на 72-ом тесте=)
Copy. Delete.
I passed Div2 C with O(N^3). I even had prepared a test case where I fail because of time limit. I was lucky this test was not in the systest. I just fixed the two starting numbers — O(N^2) and then greedily find the longest sequence — O(N). So totally O(N^3).
I have added this: if (many[A] + many[B] <= ans) continue; and fooled the systest. But the test 1 2 2 3 3 4 4 5 5 6 6 7 7 ..... breaks my solution with time limit exceeded.
It's your luck no one hacked you. But in this case of course it's fair
And my solution of O(N^2+ Hashtable search) gets TLE :(
EDIT -> Used Hashtables to map a particular element to one of the index in between [0,4000) and then called every reference with arrays and the code gets Accepted
Your solution can be easily changed to O(n^2). When you are finding the longest sequence, you can only go through the elements that are equal to the one of those two fixed (not through the whole sequence like in your submission).
Как повезло мне однако. Если бы ещё не пожарная тревога...
Интересные задачи, спасибо! :)
For Div 2 E , please tell whether my grundy number calculation is correct or not ??
In each step we should try to make y as large as possible. So we should try to make y to x^(1/2) in each step. We can keep doing this until we can make a move ie. 0<=y<x. finally grundy number will be the number of steps taken in this part.
please verify findXor function to calculate xor . link : http://www.codeforces.com/contest/255/submission/2782916
No, we shouldn't try to make y as large is possible. Actually, if n=1 and x=25, it's better to take y=3 and win (Rublo can't change the number, because 1<3^(1/2)<2 and 1<3^(1/2)<2, there is no integer in this interval). Sprague-Grundy number of some state of the game is the minimum non-negative integer, that is not equal to Sprague-Grundy numbers of any state, which we can achieve from current state.
Thank you for your reply, Now I have understood it. Actually I thought of taking sqrt(x) because I wanted to make state less. But I forgot the nice thing that I only needed to have grundy numbers upto sqrt(77777..... 12 times ) which was not so large.
EDIT : solved the problem.
rating?
probably having coffee around a corner of RAM with "paging system"....
Ratings have been updated:)
And this is the 101st comment!
Editorial in Russian available here @ http://codeforces.com/blog/entry/6161
google translate makes a good translation for this editorial .... thanks for being google-translate friendly.....
It would be really helpful if anyone could provide a dynamic programming solution to Div-2 C problem.( not the code, only the idea)
Well there are only N different numbers so we can sort them and lower them to the range [0, N — 1] instead of [1, 10 ^ 6]. Now we can build a matrix DP[MaxN][MaxN] where DP[i][Numbers[j]] would be equal to the maximum length of some progression that has the last two elements Numbers[j] and Numbers[i]. Since we know the last two elements we know the last three since it equals (a, b, a, b, a, b, ... ) are Numbers[i], Numbers[j], Numbers[i] so we can use something of a very simple knapsack solution. Try to update DP[i][Numbers[j]] with DP[j][Numbers[i]] + 1 and in the end write maximum of the matrix + 1.
Code for this idea: 2775826
Thanx a lot :)
My dp solution: take all pairs (these pairs will end of our subsequence, subsequence must be like this: x y x y x y x) and try to find answers for them. Say, pairs are : a[i] and a[j], which i > j. So d[i][j] = d[j][k] + 1, which (k < j) and (a[k] = a[i]), of course we must know answer of d[j][k]. I tried to explain to you my solution, sorry for my bad english.
thank you for the contest , I think that these problems have fresh ideas
the first and second questions of div 2 was very awful :|
I cant believe it. My submission number 2812603 passes the test case 11 (458754) for which it gives the answer 667496909 on my computer.
is there any english editorial of round 156???? I'm thirsty of it