### dalex's blog

By dalex, 7 years ago, translation,

Hi all,

I was honored to open the fourth hundred of Codeforces Rounds. Unfornunately, neither I nor my friends couldn't invent any hard problems, so it's only a Div. 2 Round. But we'll definitely prepare a full round in the future! As always, I thank Zlobober for his help in preparing the problems, Delinur for English translations and MikeMirzayanov for the Codeforces itself.

The problems must be pretty easy for Div. 1 guys, so let's start a challenge: reds should solve everything in 30 minutes, yellows — in 1 hour, and violets — in 1 hour and a half. How many people will be able to make a success?

The score distribution will be standard. Wish you accepted solutions and successful hacks!

UPD 1. Congratulations to the winners in Div. 2:

and in Div. 1:

UPD 2. This is the editorial: /blog/entry/17643.

• +351

 » 7 years ago, # |   0 Well experts, going by interpolation, you should be able to solve everything in 2 hours, set your bar no lower
 » 7 years ago, # |   +1 Needs to put in main page.Hope for high rating!
 » 7 years ago, # |   +10 And Div. 1 guys do not make new accounts
•  » » 7 years ago, # ^ |   +1 You are right
•  » » » 7 years ago, # ^ |   +12 11 upvotes for "you are right" :P
 » 7 years ago, # |   -25 You didn't deserve +1 for a 'quick' announcement, first I'll look at tasks :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Im sure he needs your +1 while he has +248
 » 7 years ago, # |   0 I think this post must be in home page...
•  » » 7 years ago, # ^ |   0 İt is.
 » 7 years ago, # |   -7 I Hope to find many hacks :D
•  » » 7 years ago, # ^ |   -8 Keep on hoping
 » 7 years ago, # | ← Rev. 2 →   -51 0100100001100001011100000111000001111001 0100100001100001011100000111000001111001 !!! P.S Hey people who put minus let brainstorm a little. I want to say "Happy Coding"...
•  » » 7 years ago, # ^ | ← Rev. 4 →   -44 I'm sorry if what I wrote has disturbed you.
•  » » » 7 years ago, # ^ |   -38 Konuşma lan! Konuşma lan! Paylaşımcılıksız bencil herif !!! (R.I)
•  » » 7 years ago, # ^ |   -6 why minus?
 » 7 years ago, # |   0 Such a interesting challenge...
 » 7 years ago, # |   +6 "How much people will be able to make a success?"I think "many people" is grammatically correct, not "much people".
•  » » 7 years ago, # ^ |   +5 Fixed
 » 7 years ago, # |   +4 I hope I can get a better score than before.
 » 7 years ago, # |   +59
 » 7 years ago, # |   +5 I Hope this contest will stop/break my declination !!
 » 7 years ago, # |   0 It's my First Round on CodeForces,Hope we will enjoy together ;)
•  » » 7 years ago, # ^ |   0 Good Luck & Have Fun my friends :)
 » 7 years ago, # |   +75
•  » » 7 years ago, # ^ |   0 Wishing you successful Challenges , and Accepteds :) pardon the wordplay.
 » 7 years ago, # |   +35 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.
 » 7 years ago, # |   0 I wish good contest for every one.
 » 7 years ago, # |   0 The score distribution will be standard.
 » 7 years ago, # |   -22 fourth hundred!!! isn't this the #301 Round
•  » » 7 years ago, # ^ | ← Rev. 2 →   +23 it's like centuries, 301 year belongs to 4 century. Century is 100 years
•  » » 7 years ago, # ^ |   -10 Maybe the author counts the non-regular rounds as welle.g. ZeptoLab Code Rush, Rockethon, etc.
•  » » 7 years ago, # ^ |   +9 and in which hundred the first round is? and 101st?
 » 7 years ago, # |   +6 I wish I could join Round #302 with div 1 :D
 » 7 years ago, # |   0 One day I was very good and then I tell you the same! :)
 » 7 years ago, # |   0 I have missed the Registration -_- :3
•  » » 7 years ago, # ^ |   -6 So what should we do?
•  » » » 7 years ago, # ^ |   -7 KEBAB just shut the f**k up. Don't make fun of other people it's rude.
•  » » » » 7 years ago, # ^ |   +1 And the man saying me shut the f**k up and KEBAP(whatever it means?!?!) saying "it is rude"?
 » 7 years ago, # | ← Rev. 2 →   +10 what was the hack on B and C ??
•  » » 7 years ago, # ^ |   +3 Tricky case for C: 2 2 .. X. 2 1 1 1 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: 9 8 10 90 2 1 1 1 1 1 1 1 1 
•  » » » 7 years ago, # ^ |   +2 Achievement Unlocked: Unsuccessful hacking attempt by * I_love_Tanya_Romanova :P
•  » » » » 7 years ago, # ^ |   +13 Moreover, you had a chance for a revenge — my solution for C seems to be wrong:)
 » 7 years ago, # |   +5 I guess I didn't understand D, or there are bug in my code :(
 » 7 years ago, # |   0 How to solve D ?
•  » » 7 years ago, # ^ |   0 Dynamic programming, by stepnumber/cur_r/cur_s. cur_p each time can be calculated from other values.
•  » » 7 years ago, # ^ | ← Rev. 5 →   0 Consider the dp[i][j][k], which denotes probability of having i rocks, j scissors and k papers remaining.From this we can calculate, dp[i-1][j][k] = dp[i][j][k] * ((i*k)/(i*j + j*k + k*i)); dp[i][j-1][k] = dp[i][j][k] * ((i*j)/(i*j + j*k + k*i)); dp[i][j][k-1] = dp[i][j][k] * ((j*k)/(i*j + j*k + k*i)); 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
•  » » » 7 years ago, # ^ |   0 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?
•  » » » » 7 years ago, # ^ |   0 I used the same but then you need to normalize probabilities. (because these sums miss when two of the same type are selected).
 » 7 years ago, # |   +7 How to solve the problem E. I think use set and binary indexed tree, but my code is bug.
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   +1 vector a; ... int dist = upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x); Distance between iterators is O(1) or O(N)?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 O(1) for iterators of vector.
•  » » 7 years ago, # ^ |   0 O(1) because they are random access iterators. In sets, it is O(N).
 » 7 years ago, # |   -18 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 ;)
•  » » 7 years ago, # ^ |   -46 I wish you luck anus <3 or uranus <3 or whatever is your name <3(xo dezle var boshyo)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -24 I have no idea,what you mean my friend,but anyway best wishes from me :)
•  » » » » 7 years ago, # ^ |   -110 it's good that u don't know
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   -19 Ok
•  » » » » » » 7 years ago, # ^ |   -26 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)
•  » » » » » » » 7 years ago, # ^ |   0 Wtf is kebap ?!?!!?
•  » » » » » » » 7 years ago, # ^ |   0 You talk too much for a person registered 48 minutes ago?!?!
 » 7 years ago, # |   0 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?
•  » » 7 years ago, # ^ |   0 I think it's a greedy problem, you must practice a lot of greedy problems to be able to solve it pretty fast :D
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # | ← Rev. 2 →   -16 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 =(
•  » » 7 years ago, # ^ |   +25 It does not count when you are participating unofficially:)
•  » » 7 years ago, # ^ |   0 Eh, I solved all with 1:47 but B failed systest :/
•  » » » 7 years ago, # ^ |   +13 LOL that's why B failed: if len(arr) > n: print "first" print -1 quit() 
 » 7 years ago, # |   0 For D, I was using the following recurrence to calculate the probability that rock wins. total = r + s + p // rock loses against paper rock(r, s, p) += ((r / total) * (p / (total - 1)) + (p / total) * (r / (total - 1))) * rock(r - 1, s, p) // scissor loses against rock rock(r, s, p) += (r / total) * (s / (total - 1)) + (s / total) * (r / (total - 1)) * rock(r, s - 1, p) // paper loses against scissor. rock(r, s, p) += (s / total) * (p / (total - 1)) + (p / total) * (s / (total - 1)) * rock(r, s, p - 1) And handled the base cases when r = 0, s = 0, p = 0 as r = 0 return 0 s = 0 return 0 p = 0 return 1 Where did I go wrong?
•  » » 7 years ago, # ^ |   0 why did you Added ((r / total) * (p / (total — 1)) ?
•  » » » 7 years ago, # ^ |   0 Rock loses against paper in two cases, if the people chosen are in the following orderRP PRThe probability for the first thing to happen is ((r / total) * (p / (total — 1)) and then we add the probability of the second thing happening, which is (p / total) * (r / (total - 1)))
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 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
•  » » » 7 years ago, # ^ |   0 Please check my reply to jibon_ebong_shomoy. Why is my reasoning incorrect?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +9 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
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 If we are in state rock(r, s, p) (this is winning probability for rock), and if we get RR, 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.
•  » » » » » » 7 years ago, # ^ |   0 so the recurrent is something likerock(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.
•  » » » » » » » 7 years ago, # ^ |   0 Isn't that an infinite loop? Using rock(r, s, p) to calculate rock(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?
•  » » » » » » » » 7 years ago, # ^ |   0 Well, in that equation you may move all rock(r,s,p) to the left and divide by adequate coefficient
•  » » » » » » » » » 7 years ago, # ^ |   0 Thanks, that was a stupid mistake :(In the second case, there are a total of total = r + s + p people. So there are pairs. Out of these, there are rp pairs in which rock loses to paper. So why isn't the equation
 » 7 years ago, # |   0 As you say : reds should solve everything in 30 minutes.But I can see : the person who finished first (only pretest pass, not Accepted) is 33 minutes (this is niyaznigmatul)
•  » » 7 years ago, # ^ |   0 Oh, niyaznigmatul get Accepted all 5 problems with 33 minutes.33 minutes > 30 minutes (failed challenge)
 » 7 years ago, # |   +107 " The problems must be pretty easy for Div. 1 " they said," reds should solve everything in 30 minutes " they said.
•  » » 7 years ago, # ^ |   +30 tourist , we need you)
•  » » 7 years ago, # ^ |   0 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. )
 » 7 years ago, # |   +8 yellows — in 1 hourzld3794955 managed to solve everything in 1:00:21, does it counts? :)
•  » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ |   -17 GUYS THERE IS SOME YELLOW GUY WHO FINISHED THE CONTEST IN 12 MINUTES!!!!
•  » » » 7 years ago, # ^ |   0 NO, it's a Virtual participation .
 » 7 years ago, # |   -11 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: else if(!cracked[r][c] >= 2) return false; instead of else if(!cracked[r][c] && visit_count[r][c] >= 2) return false; 
 » 7 years ago, # |   +4 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
•  » » 7 years ago, # ^ |   0 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 :)
•  » » » 7 years ago, # ^ |   0 Nice idea you can copy paste that easily but on the other hand my code... http://paste.ubuntu.com/10955206/
•  » » » 7 years ago, # ^ |   +6 You don't need 3 recursive functions, you can just rearrange your parameters. http://codeforces.com/contest/540/submission/10944961
•  » » » » 7 years ago, # ^ |   0 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;
•  » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » 7 years ago, # ^ |   0 thank you. this looks a lot simpler than the bottom up code.
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 I think my solution is quite concise: http://codeforces.com/contest/540/submission/10954948EDIT: yzyz's solution above my comment is simpler
 » 7 years ago, # |   -8 What was the catch for problem C?I wrote recursive DFS which obviously overflowed memory.
•  » » 7 years ago, # ^ |   +12 :|| 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
•  » » » 7 years ago, # ^ |   0 Oh shit! I screwed it for myself! Anyway a lot to learn.
•  » » » 7 years ago, # ^ |   0 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
•  » » » » 7 years ago, # ^ |   +1 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.
•  » » » » » 7 years ago, # ^ |   0 Oh you're right, didnt think about the order that the vertexes were visited, it was a bfs indeed
•  » » 7 years ago, # ^ |   0 Wrote a recursive DFS as well:See 10951361
•  » » » 7 years ago, # ^ |   0 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 :)
•  » » » » 7 years ago, # ^ |   0 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'.
•  » » » 7 years ago, # ^ |   0 I wrote recursive Dfs function for problem C but was getting segmentation fault. Any help will be appreciated code
 » 7 years ago, # |   0 I wrote recursive Dfs function for problem C but was getting segmentation fault. Any help will be appreciated code
•  » » 7 years ago, # ^ |   +5 don't go to dfs if visited is true?
•  » » » 7 years ago, # ^ |   0 Can you explain how ?
•  » » » » 7 years ago, # ^ |   0 you forgot to check the visited condition in the bool condition(int i,int j) function. so u are visitng visited nodes again and again which causes stack overflow (seg fault).
•  » » » » 7 years ago, # ^ |   0 write in ur dfs function if(visited[i][j]) return;
•  » » » » 7 years ago, # ^ |   0 http://codeforces.com/contest/540/submission/10955779 now u get wrong answer.
•  » » 7 years ago, # ^ |   0 if(grid[i][j-1]==c && condition(i,j-1)) DFS(i,j-1); you should let the condition() before checking the grid
•  » » » 7 years ago, # ^ |   0 Thanks now it's working, Can you explain?
•  » » » » 7 years ago, # ^ |   0 if(grid[i][j-1]==c && condition(i,j-1)) this line starts evaluation fro left so it first tries to access grid[i][j] without checking if i and j are valid. this will cause seg fault in situion like i = -1 or i > limit of ur array.
•  » » » » 7 years ago, # ^ |   0 Because first u check grid[i][j-1] == c where (j — 1) can ne negative.
•  » » » 7 years ago, # ^ |   0 Damn, what a silly mistake !! Thanks everyone.
 » 7 years ago, # |   0 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
 » 7 years ago, # |   0 Very ambiguous description of problem C. -_-The word 'down' should have been explained properly.
 » 7 years ago, # |   0 For problem C, what would be the answer for test case?3 3XXXXXXXXX1 32 2
•  » » 7 years ago, # ^ |   0 The answer is NO. You can move only between cells that share a common side (to the left, right, top or bottom).
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 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??
•  » » » » 7 years ago, # ^ |   0 (1 2) is already cracked, so when you move there, you will immediately fall.
•  » » » » » 7 years ago, # ^ |   0 yeah, so falling through (1,2) will make us fall through (2,2) which was our objective !!!
•  » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » 7 years ago, # ^ |   0 got it !!! thanks :)
 » 7 years ago, # |   0 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. 1 1 X 1 1 1 1 
•  » » 7 years ago, # ^ |   0 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.
•  » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   0 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
 » 7 years ago, # |   0 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
•  » » 7 years ago, # ^ |   0 Your code really has some bug. I tried to modify the code, and got ac now. you can see this code.10960015 good luck!
•  » » » 7 years ago, # ^ |   0 Thanks!
 » 7 years ago, # |   0 I have only solved two problems just now. but all of the problem is interesting, thanks for this interesting challenge!
 » 7 years ago, # |   0 Thank you for B and C — very nice problems.
 » 7 years ago, # |   +6 This Contest made me BLUE :D :D Will Remember #301 ......
 » 7 years ago, # |   0 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 1We 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/JS4OAUWhat's the flaw?
•  » » 7 years ago, # ^ |   0 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.