Всем привет!
Мне выпала честь открыть четвертую сотню раундов на Codeforces. К сожалению, мы с друзьями пока что не смогли придумать сложных задач, так это всего лишь Div. 2 раунд. Но мы обязательно сделаем общий раунд когда-нибудь в будущем! Как всегда, благодарю Zlobober за помощь в подготовке задач, Delinur за перевод и MikeMirzayanov за сам Codeforces.
Для участников из первого дивизиона задачи должны быть совсем простыми, поэтому давайте поставим челлендж: красные должны все решить за 30 минут, желтые — за час, а фиолетовые — за полтора часа. Интересно, как много народу сможет управиться?
Разбалловка будет стандартная. Всем полных решений и успешных взломов!
UPD 1. Поздравляю победителей в официальном зачете:
и в неофициальном:
UPD 2. Разбор лежит тут: /blog/entry/17643.
Needs to put in main page.
Hope for high rating!
Thanx
And Div. 1 guys do not make new accounts
You are right
11 upvotes for "you are right" :P
You didn't deserve +1 for a 'quick' announcement, first I'll look at tasks :)
Im sure he needs your +1 while he has +248
I think this post must be in home page...
İt is.
За выполнение челенджа, забустишь ммр в доте?)
Макс, ты пока синий. Основной челлендж для тебя — вернуться в див1.
I'm not prepared
P.S. Доту не удаляй мне плз
I Hope to find many hacks :D
Keep on hoping
0100100001100001011100000111000001111001 0100100001100001011100000111000001111001 !!!
P.S Hey people who put minus let brainstorm a little. I want to say "Happy Coding"...
I'm sorry if what I wrote has disturbed you.
Konuşma lan! Konuşma lan! Paylaşımcılıksız bencil herif !!! (R.I)
why minus?
А кто главный герой на этом контесте ? (персонаж)
Я некоторое время назад понял, что вводить общих персонажей или сеттинг для задач не очень хорошо. Потому что, как правило, некоторые задачи приходится подгонять под сеттинг, а это не всегда можно сделать. Так что никаких главных героев. Как задачу придумал — так на контест ее и дал.
С одной стороны скучно, с другой стороны не придется привыкать. Все еще ненавижу Таваса с его карафасами — 5 минут я просто пытался думать этими названиями.
Ну попробуем =)
Удачи всем. вперед
Ваш первый контест?)
Это первый контест с полностью моими задачами. Прошлые мои раунды я вместе с ACM-тиммейтами делал.
Поздравляю! Чтобы решить такой контест, надо думать как автор.)
Such a interesting challenge...
"How much people will be able to make a success?"
I think "many people" is grammatically correct, not "much people".
Fixed
I hope I can get a better score than before.
Еще припишите: черные должны все решить за 15 минут, думаю, около сотни управится
I Hope this contest will stop/break my declination !!
It's my First Round on CodeForces,Hope we will enjoy together ;)
Good Luck & Have Fun my friends :)
Wishing you successful Challenges , and Accepteds :) pardon the wordplay.
As you say :
violets solve everything in 1 hour and a half.But I think :
I will solve these problems in 2 hour.And more importantly :
Until the contest over, I still haven't finished all problems.Becausee :
I am Stupid-Dog.fourth hundred!!! isn't this the #301 Round
it's like centuries, 301 year belongs to 4 century. Century is 100 years
Maybe the author counts the non-regular rounds as well
e.g. ZeptoLab Code Rush, Rockethon, etc.
and in which hundred the first round is? and 101st?
Если задачи очень простые можно намеренно сделать слабые претесты (например, не рассматривать частные случаи), чтобы можно было взломами занять участников, которые всё решили.
I wish I could join Round #302 with div 1 :D
Как Delinur перевела, если :
Последнее посещение: 6 месяцев назад...
Баг с временем
Баг в Матрице
Good luck to all of you guys in Conetests_)
I have missed the Registration -_- :3
So what should we do?
KEBAB just shut the f**k up. Don't make fun of other people it's rude.
And the man saying me shut the f**k up and KEBAP(whatever it means?!?!) saying "it is rude"?
niyaznigmatul почти выполнил challenge :(
Срочно нужен челлендж "лох дня"!
присоединяюсь)
А на чем все ломали C?
Ответ же "YES"?
UPD: уже понял, на чем этот тест ловит. Видимо, надо сначала найти кратчайший путь до финиша, а не какой-нибудь.
У половины комнаты было NO; у меня так и осталось:) Проверки в стиле "если клетка с точкой, то должно быть хотя бы 2 соседа с точкой" падают на случае, когда начальная и конечная точка являются соседями.
Да вроде любой путь работает. Нужно только начальную клетку занулить
Просто моя прога тут пошла не сразу вверх, а вправо-вверх-влево, и потом вообще не нашла свободного соседа. А чем тут поможет точка в стартовой клетке?
Ну видимо зависит от решения.
Во многих решениях(втч моем) проверяется наличие какого-то пути по белым клеткам и то, что у конечной вершины есть хотя бы 2 соседа(если она сама белая) — чтобы мы могли прийти как-то — выйти по незанятой и вернуться назад.
типа стартовая клетка не учитывалась при подсчете кол-ва соседей?
Мое решение хакнули потому что я смотрел только соседей точек :(
what was the hack on B and C ??
Tricky case for C:
There were lot of possible mistakes in B, it seems that most common of them is not checking that median of final array is large enough:
Achievement Unlocked: Unsuccessful hacking attempt by * I_love_Tanya_Romanova :P
Moreover, you had a chance for a revenge — my solution for C seems to be wrong:)
I guess I didn't understand D, or there are bug in my code :(
How to solve D ?
Dynamic programming, by stepnumber/cur_r/cur_s. cur_p each time can be calculated from other values.
Consider the dp[i][j][k], which denotes probability of having i rocks, j scissors and k papers remaining.
From this we can calculate,
where i*j + j*k * k*i is the total number of ways to choose two different species, and each term from this sum denotes the number of ways to choose (r,s), (s,p) and (r,p)
The simply sum over, all dp[i][0][0] for all i = 1 to r for rocks, all dp[0][i][0] for scissors all i = 1 to s for scissors all dp[0][0][i] for paper for all i = 1 to p for papers
instead of ((i*k)/(i*j + j*k + k*i)) I tried to use , (i/(i+j+k))*(k/(i+j+k-1). I know its wrong , but can't really understand why?
I used the same but then you need to normalize probabilities. (because these sums miss when two of the same type are selected).
How to solve the
problem E.I think use
setandbinary indexed tree, but my code is bug.I calculated number of inversions in modified elements separately. Then for each modified element you calculate how many elements to the left of it are larger it, minus number of modified elements in the same interval plus similar thing for the right side. To calculate number of modified elements in range I used binary search on array of modified positions.
Distance between iterators is O(1) or O(N)?
O(1) for iterators of vector.
O(1) because they are random access iterators. In sets, it is O(N).
For me,it wasn't enough time to solve all problems,It's ok,I will practice and I will do my best in next rounds ;)
I wish you luck anus <3 or uranus <3 or whatever is your name <3
(xo dezle var boshyo)
I have no idea,what you mean my friend,but anyway best wishes from me :)
it's good that u don't know
Ok
I don't know about him, but i had a lot of experience with your sister. She was the best :D
(lol i'm just kidding kebabs are as ugly as fuck)
Wtf is kebap ?!?!!?
You talk too much for a person registered 48 minutes ago?!?!
Why so many people finish Problem B in Div2 quickly,while I spend a lot of time? Is there some tricks or I am stupid?
I think it's a greedy problem, you must practice a lot of greedy problems to be able to solve it pretty fast :D
Solved A, spent 20 mins on B, solved C in like 10 mins, read D realised it was dp so meh... read E realised it was bit with some normalization and map usage so I went back to B and after anthoner 20 mins I finally solved it . Hope you feel better.
I not accepted challenge: to D spent an hour. But I have included worse style in the past 5 minutes.
UPD: 7/10 (hacking by my) solutions not passed system tests. Why I did not choose the right test =(
It does not count when you are participating unofficially:)
Eh, I solved all with 1:47 but B failed systest :/
LOL that's why B failed:
For D, I was using the following recurrence to calculate the probability that rock wins.
And handled the base cases when
r = 0,s = 0,p = 0asWhere did I go wrong?
why did you Added ((r / total) * (p / (total — 1)) ?
I don't really understand your probabilities. I think it should be
r * p /(rp + rs + sp) for the first case and similar for others. (maybe its equivalent)
And note that you shouldn't divide integer by integer if you do. Cast to double one of them first
Please check my reply to jibon_ebong_shomoy. Why is my reasoning incorrect?
Aha, I understood your reasoning and it seems to be correct.UPD: you don't consider the cases RR, PP, SS, so all you probabilities are to low. One way to fix is to divide result by 1 — p(RR) — p(PP) — p(SS)
Note about integer division still stands, throught
If we are in state
rock(r, s, p)(this is winning probability forrock), and if we getRR, SS or PP, we are left in the same state, so I ignored it. Why can't we ignore that?Also I didn't understand your point about dividing result by 1 — p(RR) — p(PP) — p(SS). Could you please elaborate? Thanks.
so the recurrent is something like
rock(r, s, p ) = p(rp) * rock(r — 1. s, p) + p(rs) * rock(r,s — 1, p) + p(sp) * rock(r, s, p — 1) + p(rr) * rock(r, s, p ) + p(ss) * rock(r, s, p ) + p(pp) * rock(r, s, p )
Note, rock(r,s,p) is calculated using itself.
Isn't that an infinite loop? Using
rock(r, s, p)to calculaterock(r, s, p)?And when you used
, you find the fraction of times an rp battle takes place out of rp, rs, ps battles. But even in this, rr, ss, pp battles are ignored. Why does this work?
Well, in that equation you may move all rock(r,s,p) to the left and divide by adequate coefficient
На B можно было вроде ловить, не напрягаясь, ибо у меня прошел претесты код, который вообще выводит не то количество цифр, которое надо (Как итог: глупейшая ошибка, и дай Бог, хотя бы A решил)
Как решать Е?
Давайте разделим последовательность на две группы:
1. U — Те позиций a[x] = x
2. C — Те позиций a[x] != x
Теперь есть три случая (a[i] < a[j] && j < i).
Т.е когда мы находим инверсий, мы фиксируем две позиций:
1. CC (a[j] != j, a[i] != i)
2. UC (a[j] = j, a[i] != i)
3. CU (a[j] != j, a[i] = i)
Все C можно запихать в массив (найти их можно map'ом).
Сумма всех CC — кол-во инверсий в нашем массиве.
А для нахождения UC или CU перебираем C а U можно найти бинпоиском. Для этого надо реализовать функцию calcU(l, r) — количество позиций a[i] == i (l <= i <= r). calcU(l, r) = r — l + 1 — calcC(l, r). calcC(l, r) — количество позиций a[i] != i. (если у нас есть все позиций в массиве all, то calcC(l, r) = upper_bound(r) — lower_bound(l)).
As you say :
reds should solve everything in 30 minutes.But I can see : the person who finished first (only
pretest pass, notAccepted) is33 minutes(this is niyaznigmatul)Oh, niyaznigmatul get
Acceptedall 5 problems with33 minutes.33 minutes > 30 minutes(failedchallenge)" The problems must be pretty easy for Div. 1 " they said,
" reds should solve everything in 30 minutes " they said.
tourist , we need you)
reds should solve everithing in 30 minutes and then failed systests on 1-2 problems.
For example task B. The complexity of this task even can't be recalculated to Div1. )
zld3794955 managed to solve everything in 1:00:21, does it counts? :)
This one's so damn close. But I guess that there's no success in the challenge. Regardless the result of the challenge zld3794955 had solved all the problems, that's very good, imo.
GUYS THERE IS SOME YELLOW GUY WHO FINISHED THE CONTEST IN 12 MINUTES!!!!
NO, it's a Virtual participation .
Sad Story. I finished coding C at 11:45, and started debugging. I was using DFS so it was I kinda hard to find the bug. I found the bug at 11:59 and when I try to submit, contest is over :'(.
Later when I submitted that solution, it was Accepted. I could've been 15th instead of 49th.
The bug I was facing was that, I had written:
instead of
When rating will be updated
can someone write recursive dp+memoization solution for prolem D bad luck island. bottom up DP solution just looks like magic to me.i dont understand it. please provide some explanation also for the recursive code. pleaseeet
Here you go!
There are 3 recursive functions in my solution. recurse1 is for the rocks, recurse2 is for the scissors and recurse3 is for the papers :)
Nice idea you can copy paste that easily but on the other hand my code... http://paste.ubuntu.com/10955206/
You don't need 3 recursive functions, you can just rearrange your parameters. http://mirror.codeforces.com/contest/540/submission/10944961
please explain this part of ur code:
int rs = r*s;int pr = p*r;int sp = s*p;int tot = rs + pr + sp;if (s) dp[r][s][p] += getdp(r, s-1, p) * rs / tot;if (r) dp[r][s][p] += getdp(r-1, s, p) * pr / tot;if (p) dp[r][s][p] += getdp(r, s, p-1) * sp / tot;If we have r rocks and s scissors, then the number of possible rock-scissor pairs is r*s, and similarly for the paper-rock and scissor-paper pairs. The probability that a rock-scissor pair is chosen is rs / tot. In the rock-scissor pair, scissor always loses, so now we want the probability that rock wins if there is one less scissor, which is getdp(r, s-1, p), and we do the same thing for the other pairs.
I think my solution is quite concise: http://mirror.codeforces.com/contest/540/submission/10954948
EDIT: yzyz's solution above my comment is simpler
Классный контест, авторы молодцы.
У кого-то на Е зашло решение за O(n * log2(n))?
What was the catch for problem C?
I wrote recursive DFS which obviously overflowed memory.
:|| man you shouldn't pass a whole n*n matrix to some recursive function of course you will get MLE you should've used a global matrix
Oh shit! I screwed it for myself! Anyway a lot to learn.
I had problems with recursive DFS and I didn't think of not passing a n*n matrix and using a global one so I implemented a iterative DFS with a queue T_T worst time from all the passed solutions but it is the first time I've solved a problem C
If you used a queue, it's a BFS, which is better in this case because if there's a path you'll find the shortest one. By the way, time is not really important if your algorithm complexity is good enough.
Oh you're right, didnt think about the order that the vertexes were visited, it was a bfs indeed
Wrote a recursive DFS as well:
See 10951361
Thanks! I didn't use a global matrix because I had to pass the changed(updated) matrix every time to the recursive call. Couldn't think of way to do that with global matrix. Let me check out how you made that :)
You don't need a visited matrix,
Never really used that in any conditional statements.
You can reuse the string array my making '.' to 'X'.
I wrote recursive Dfs function for problem C but was getting segmentation fault. Any help will be appreciated code
don't go to dfs if visited is true?
Can you explain how ?
write in ur dfs function if(visited[i][j]) return;
you should let the condition() before checking the grid
Thanks now it's working, Can you explain?
Because first u check grid[i][j-1] == c where (j — 1) can ne negative.
Огромное спасибо вам dalex за этот замечательный контест я так счастлив потому что я стал экспертом вы даже не представляете сколько я этого ждал сколько я трудился чтобы достичь этой цели Я благодарю всех кто мне помогал учил
Solved A,B. I took WA in C for a small wrong,but now accepted too. Very nice contest,and second time I am blue :) Thank you dalex
Very ambiguous description of problem C. -_-
The word 'down' should have been explained properly.
For problem C, what would be the answer for test case?
3 3
XXX
XXX
XXX
1 3
2 2
The answer is NO. You can move only between cells that share a common side (to the left, right, top or bottom).
when we move from (1,3)-->(1,2) ,
(1,2) will open which in turn opens (2,2),
so wouldn't it be "YES"???
or I didn't understand question yet??
(1 2) is already cracked, so when you move there, you will immediately fall.
yeah, so falling through (1,2) will make us fall through (2,2) which was our objective !!!
Well, you misunderstood the statement. The map given in the input is the view of one level of the cave from above. The falling is not falling down to the next row of the input, it's falling out the level of the cave.
The statement says: "The level of the cave where you are is a rectangular square grid of n rows and m columns." I think it's clear that only one level of the cave is described by that grid.
got it !!!
thanks :)
красные должны все решить за 30 минут, желтые — за час, а фиолетовые — за полтора часа. Интересно, как много народу сможет управиться?
Из красных ближе всех был niyaznigmatul: 33 минуты.
Из жёлтых: zld3794955: 1:00, но это значит что отправка была уже после окончания первого часа.
Из остальных: PauGra: 1:30, тоже не хватило менее минуты до полутора часов. Притом это новый юзер.
Из остальных, исключая новых: tgehr: 1:41.
Я никого не пропустил? Может быть, всё же есть хоть один осиливший?
Кажется, что нет. Но все цвета были очень близки к цели!
Can someone please help me understand how the answer to this case(test 5) is NO for problem C. I think it should be a YES.
You are not allowed to jump on the tile to make it crack, so to that you have to leave the tile and come back to it. Since there's just one tile in this case, you cannot leave anywhere, which means you won't be able to advance.
I get your point, but in this case I think we need not move at all because the player is standing at the exit itself and can directly exit from there.
Please correct me if I am wrong.
Thanks.
Yeah, but if he just keeps standing, he won't fall down. You only fall down if you move to a cracked ice. You can sort of assume that the ice under you was OK (.) and then you magically appeared on it, causing it to crack (X). However, to proceed to the next level you sort of need to crack it again. The sequence is . -> X -> advance.
I first tried solving problem C using BFS: 10948640. However, I got memory limit exceeded on test 14. When I implemented the same exact code but switched to recursive DFS, it passed all the tests with no problem.
The problem limit is 500, and that doesn't come anywhere near 256MB, so I can't figure out what happened. Can someone take a look and give me a suggestion?
Thanks
I'm not able to figure out where the bug is in problem B. Please help! here's my solution to Codeforces Round 301 (B) School Marks: CF301_Prob_B
Your code really has some bug. I tried to modify the code, and got ac now. you can see this code.10960015 good luck!
Thanks!
Thank you for B and C — very nice problems.
This Contest made me BLUE :D :D Will Remember #301 ......
Umm i may have grossly misunderstood problem C here. Probably the word 'side adjacent' or 'fall down'. Help me out here. I used the BFS in a grid technique to get my answer. However, my code gives me 'YES' for example testcase 2. According to my logic, that should right.
Here is the case:
5 4 .X.. ...X X.X. .... .XX. 5 3 1 1
We can go to 1,1 from 5,3 as follows
(5,3)->(4,3)->(4,2)->(3,2)->(2,2)->(2,1)->(1,1)
Here is my code: http://ideone.com/JS4OAU
What's the flaw?
You need to fall down through the cell (r2, c2) since the exit to the next level is there.
The cell (1,1) is intact before you step on it,so you wouldn't fall down through that,and you can't jump on that cell to that cell to make yourself fall.