Добрый день!
Завтра утром состоится Coder-Strike 2014: Раунд 2. Как обычно, для участия в нем нужно зарегистрироваться на странице.
Аналогично прошлому раунду, все желающие могут принять участие в раунде. Раунд будет рейтинговым для всех официальных участников раунда (лучшие 50 официальных участников первого раунда), а также для неофициальных участников из второго дивизиона. Рейтинг по официальным и неофициальным участникам будет считаться отдельно. Для неофициальных участников из первого дивизиона раунд будет нерейтинговым, но не расстраивайтесь, финальный раунд обязательно будет рейтинговым для первого дивизиона.
Если есть какие-то вопросы, не стесняйтесь, задавайте их в комментариях.
Удачи и до встречи на раунде!
UPD 1. Прошу прощение за небольшое опоздание, разбалловка стандартная.
UPD 2. Контест завершен, поздравляю победителей, надеюсь задачи вам понравились!
Количество задач и разбалловка как вчера?
Количество задач — да. Разбалловка, как обычно, будет перед началом раунда.
Will the finals be rated for both divisions or the first division only?
May be the finals problems will be too hard for div.2 participants. Now I cannot tell this for sure.
When will the finals be held?I hope it's also held at Russian morning(or afternoon) so it will be convenient for coders in China and other east asia countries.
I am very glad to tell you, that mostly it will be held in Russian morning. =)
for the rating of this round when you get a best rank between Div 2 participants but between both participants you get the higher rank like 20! wich one is count for your rating?( I got the answer after the end of the Contest THX btw;) )
can we get reward point from the game?
It coincides OpenCup. dafaq?
Назовите разбалловку раунда.
Отказ тестирования по E
Я ответил вам в личку.
I think problem A of Round 2 have an ambiguity .....the value of ti must be ,min<=ti<=max ... correct me if i am wrong ??
wrong you can see it by exp3
ur not wrong in terms of the answer.
but since the question doesnt specify these constraints, it means that u must print
Incorrect
in this case.Что за 9-ый тест в Е? Неужели обычный BFS не заходит? Мое решение работает так: обхожу по столбцам наше поле, если не посещал еще клетку, то пускаю BFS из нее. Ответы на запросы: если клетки в разных компонентах связности, то -1, иначе abs(dist[v] — dist[u]). Что неверного? Вот решение: 6427623
Если посмотреть на ограничения то можно понять что BFS ту будет долго работать (>2 sec). Также здесь есть уловка: "Считается, что клетки первой строки лабиринта нумеруются от 1 до n слева направо, а клетки второй строки от n + 1 до 2n слева направо.".
Ты каждую клетку переберешь максимум 1 раз.
bfs долго? Он посетит никак не больше чем все клетки, разве нет? По-моему хоть несколько раз его тут пускай (и больше, пока не надоест).
У меня было две ошибки в решении, главная появляется на этом тесте
Была мысль про 2 бфс, но это не помогает при
2 1
..
..
2 3
I don't know if it's why I've been awake for so long, but statements of problems C and D were a bit difficult to understand.
yes, the explanation of problem D just make me more confused
For the ones not knowing the games 2048, it would be much more difficult to understand
A bit!!!I couldn't understand C through out the entire contest. and still I don't know how the game continues!
I couldn't understand C either, I didn't realize that the questions can be selected in any order.
even i took about 10-15 minutes to realize this fact, because problem statement said:
since question was so confusing (especially about order), atleast explanation to example cases should have been included!
we have to take care of R2 company only.......
and they can choose any problem which is not taken already without considering any order......
for 1st test case, take 1st,2nd and 4th at first then take 3rd no question.....
The description of C could be more specified.... have no idea about D.
So fast systest. Very wow.
hope the rating changes will be that fast ! :D
aaaanddddd... the rating changes are slow lol
relevant comment
Nice problems
I don' t think there r much div 2 participants...
What is the solution to problem D?
hint: You can use dp with bitmask
You do a DP keeping an increasing sequence of powers of 2 by using a bitmask.
Ah, I get it now, thanks. I should have noticed that only the increasing powers of 2 matter :P Also, it is very nice that when we add the number 2 or 4 to the mask, it modifies the mask according to the rules of the game. :D
At first figure out what was the problem . weird statement, one more disgusting contest with poor statement.
Just played that game:)
Just realize that it can be solved using dp bitmask, anyway i have a different dp solution by considering that it is possible to get 2^{K} if there's 2^{K-2} consecutive 4 (two consecutive 2 can be merge into 4)
Кто-нибудь решил b на python? А то я оптимизировал как мог, но все равно не прошло. Может быть, есть способ лучше? Вот мое решение: 6426282 работает за O(n * m)
And also I have no idea why my first submission for Problem C got RE. I changed the size of arrays then I got AC later, but why?
I have the same situation, but with problem B :/
in problem B I have same situation too, but that's because i miscalculated array for n is 2000 not 20000 .. LOL
But I' m sure the size is big enough, for the number of auction problems is at most 30.
u have a statement
c[i] = a[b[i]]
, where1 <= i <= n
(not1 <= i <= m
). this is the reason for RE.change
35
to105
and u will get AC.Будьте осторожны, игра затягивает, а времени на контесте не так много!
Вот это в D надо было перед ссылкой на игру написать, а не после.
is it problem C can solved by greedy?
Yes! U can calculate the sum of the points of regular problems and the add the points of other problems
how can it be? can you explain a bit more?
well, I' m afraid my poor English can' t explain it clearly... U can view my code. that' s much clearer, I think.
Yes. Basic idea is to take all regular questions first (since you need to take them at some point anyway), then sort auction questions by decreasing order of price and, for each, either double your score or increase it by the auction question price (whichever is greater).
The point is that you want as high a score as possible when getting to a specific auction question, so you should always start with the highest values.
when will the ratings be updated???
Sorry, I' m wrong.
А свои ноутбуки на онсайте это нормально? Всегда так?
Если рядом с обычным компом — то нет, не нормально. Если из-за отсутствия обычных компов — тоже не нормально, но лучше чем отправить всех по домам.
Вообще, было бы круто писать не на своих компах. А то финал можно и дома написать, а победители потом приехали бы за своими призами.
Сделал в youtube 15-минутный скринкаст задания "A", на языке Perl. Если кому интересно — ссылка.
First Time to uncheck box "show unofficial" & didn't see any one all of us are unofficial :D
Why don't the problems of any Coder Strike round appear in the problemset?
They do. Look at 413 A, B,...
ya thanks i expected them at the top they appeared lower in the list :P my bad
What is the solution to E? Is there some approach using segment trees/BIT ?
I used DP in segments of length equal to a power of 2 and then merged them to solve the queries. You could also do that with a segment tree.
Code: 6427362
Yes, there is a solution using segment tree.
Consider the interval
[l; r]
.Cell of maze will be denoted a pair
(i, j)
— the index of row and column.For interval
[l; r]
we will store an arrayd[2][2]
.d[i][j]
— length of shortest path between(l, i)
and(r, j)
.For segments
[l; l]
is easy initialize the array d. We can easily merge two adjacent segmentss1 = [l; m]
ands2 = [m+1; r]
.d[i][j] = 1 + min(s1.d[i][0] + s2.d[0][j], s1.d[i][1] + s2.d[1][j])
My submision: 6425791
Why my solution on problem-B gets TIMELIMIT?
Complexity of your solution is
O(n*k)
. In worst casen*k = 4 * 10^9
There's some editorial for this contest?
Астрологи объявили неделю контестов и битмасок.
Прирост контестов увеличился в 10 раз. Прирост задач на битмаски увеличился в 20 раз.
Много улыбок и крови в мире Героев клавиатуры и магии.
Помоги решить задачу Е, пожалуйста! Моя идея решения: 1)строим граф, затем dfs-ом находим компоненты связности и в них находим минимальный путь от любой вершины (назовем её главной в этой компоненте) до всех остальных в этой компоненте. 2)Ответ будем искать с помощью LCA в оффлайне. Для этого сделаем списки запросов, затем во время dfs-а для поиска, будем искать предка и пытаться отвечать на запросы. Если главная вершина для u != главной вершине для v, то сразу -1, а иначе ответ будет = dist[u] — dist[lca] + dist[v] — dist[lca]; Вот мой код. Совсем не знаю, где ошибка! :( http://codeforces.me/contest/413/submission/6430904 Помогите, пожалуйста! UPD: я уже понял, что это не деревья
Если нужно, могу рассказать свое решение(Код). Разбор спрятал в предыдущую страницу правки
← Rev. 2: Problem C Spoiler Alert!