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.

Well experts, going by interpolation, you should be able to solve everything in 2 hours, set your bar no lower

Needs to put in main page.

Hope for high rating!

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.

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?

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.

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`

.I wish good contest for every one.

The score distribution will be standard.

fourth hundred!!! isn't this the

#301Roundit'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

One day I was very good and then I tell you the same! :)

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"?

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

`set`

and`binary 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 = 0`

asWhere did I go wrong?

why did you Added ((r / total) * (p / (total — 1)) ?

Rock loses against paper in two cases, if the people chosen are in the following order

`RP`

`PR`

The 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)))`

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 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.

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 calculate`rock(r, s, p)`

?And when you used , you find the fraction of times an

rpbattle takes place out ofrp,rs,psbattles. But even in this,rr,ss,ppbattles 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

Thanks, that was a stupid mistake :(

In the second case, there are a total of

total=r+s+ppeople. So there are pairs. Out of these, there arerppairs in which rock loses to paper. So why isn't the equationAs 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)Oh, niyaznigmatul get

`Accepted`

all 5 problems with`33 minutes`

.`33 minutes > 30 minutes`

(failed`challenge`

)"

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

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://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.

thank you. this looks a lot simpler than the bottom up code.

I think my solution is quite concise: http://codeforces.com/contest/540/submission/10954948

EDIT: yzyz's solution above my comment is simpler

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

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 ?

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).write in ur dfs function if(visited[i][j]) return;

http://codeforces.com/contest/540/submission/10955779 now u get wrong answer.

you should let the condition() before checking the grid

Thanks now it's working, Can you explain?

`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.Because first u check grid[i][j-1] == c where (j — 1) can ne negative.

Damn, what a silly mistake !! Thanks everyone.

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 :)

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!

I have only solved two problems just now. but all of the problem is interesting, thanks for this interesting challenge!

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.