Hello,

Codeforces Round #105 will take place on February 2nd, 20:00 Moscow time.

This is a themed round, based on the fairy tales I write in Russian.

In this round we decided to conduct an experiment on smoothing the effects of problem setters misestimating the complexities of the problems: all problems have point values of 1000. We tried to order the problems by increasing difficulty, but this is a subjective opinion, so surprises are possible.

Thanks to MikeMirzayanov for the problem contributed to the round (who can guess which one of the five is not mine?) and to RAD for his help in preparing the problems.

Good luck at the round!

I prefer if the problems are not sorted, just randomly shuffled.

I think sorting the problems will ruin the experiment, just tell us after the contest what was your estimated difficulties, and see how correct is it.

How many points will be deducted after each minute passed for each problem?

I think it will be 4 points per minute, and the minimum score will be 300.

Thank you brother.

All problems with same value, were you guys inspired by the current Facebook Hacker Cup? ;)

I think that is a bad idea wich all problems with same value because no incentive make problems with more complexity and this is the award for greater ingenuity.

This timing (20:00 Moscow Time) for contest is very good for me. If it is possible to continue this timing in next contests I will be grateful. (Hope that this timing does not delay the Dinner for Russian people. )

You wrote fairy tales? Cool!!! Can you tell me some of yours? I really like fairy tale.

The link is in the post.

only in russian version of the post

According to the number of votes I got in the first comment, will you take it into considerations?

are these problems just in Russian?

No. Only the fairy tales are in russian :)

Problem E: Porcelain is contributed by MikeMirzayanov's

As for me, this problem is second by it's difficulty.

hmm, I have 22 failed hacks. It's due to my browser was non responding, can you remove wrong hacks? You can see, they are all at same time(almost all);

Very interesting. I support your plea. May be codeforces should put a check in place to see if the same exact test has been tried as hack by the same user, and not allow it. Just like resubmission of the exact same solution to a problem is rejected.

I think this accident was my fault(my netbook isn't that good, and firefox can kill it easily), but Mike said, they will be removed.

Actually, your idea is great.

Was I the only one who found the wording for problem D a bit confusing?

I think it was a DP problem. What was the recurrence, anyone?

I believe it's something like this:

Call pp(w,b) the probability that the princess wins when it's her turn to pick and there are w white and b black mice in the bag, and pd(w,b) the same probability when it's the dragon's turn to pick. Then:

pp(w,b) = w/(w+b) + b/(w+b) * pd(w,b-1)

and

pd(w,b) = b/(w+b) * (w/(w+b-1) * pp(w-1,b-1) + (b-1)/(w+b-1) * pp(w,b-2))

Base cases: pp(0,0) = pp(0,1) = 0, pp(1,0) = 1 pd(0,0) = pd(0,1) = pd(1,0) = pd(1,1) = pd(2,0) = pd(0,2) = 0

(EDIT: actually pp(0,x) = pd(0,x) = 0 for all x, since without white mice the princess will always lose)

Thanks

p(w,b) = w/(w+b) + b*/(w+b)*(1-d(w-b))

d(w,b) = w/(w+b) + b/(w+b)*(1-(w/(w+b-1)*p(w-1,b-1)+(b-1)/(w+b-1)*p(w,b-2))

Was E , a dp + a knapsack (which is also a dp) ?

i solved it that way and it passed, so i guess it was

First of all congrats to the author for such a logical and thinking contest. My C algorithm gives me wrong answer.Please tell me where am I wrong.Here's the algorithm:

`if(a=n-1) return -1;`

`a[0]=2;`

`if(b==0)`

`a[1]=1;`

`else a[1]=3;`

`for the left number of wows-> a[i]=2*a[i-1];`

`for the left oh's-> a[i]=a[i-1]+1`

`for the left places-> a[i]=1;`

Seams like you fail on n=1 like I did. (Test case 6)

Oh,yes.Corrected that and it got accepted.Silly mistake :( Thanks anyways for pointing that out

Once again python failed me on a simple O(n^2) dp, n around 1000. When will I learn... Or Codeforces give me a little more time..

Really liked the problem statements! Also, the problems were interesting (however, for me C was way harder than D and E, which were rather standard). Also, my opinion is that giving the same points to all problems (especially if their value is 1000) is TERRIBLE idea. Imagine that a person solves all 5 problems (and nobody else does, the fifth one is quite hard). Then he is beaten by a person with 8 or 9 successful hacks, who just was in a lucky room where nobody else tried hacking. I don't believe this would represent the best coder in the contest at all.

All problems with same value doesn't make any sense. Problem A (loop with % operation) can't have the same value as E which is a DP with caching. A guy who solved A can outweigh another solved E(obviously) in less time.

Anyone want to share recurrence for E as well please...

You should consider two things a) At which row you are b) How many remaining cracks you have

At each step you should try all possible ways to break some porcelain (which is about 100 * 100 possibilities, considering all possible from the left and all possible from the right). Since this becomes O(N * M * 100 * 100) algorithm, which is rather heavy, you should pre-calculate the best possible answer for breaking K dishes at row R. Now all operations at a given row and given remaining cracks can be calculated in O(100), giving overall complexity of O(N * M * 100), which is okay.

Very interesting. Thanks.

I was stuck on how to calculate the best possible answer for breaking K dishes at row R. Could you tell more about it? It just came to my mind that a greedy approach would be enough.

just check all possible I and J, such that we take I books from left, and J books from right. Look at my solution

Oh, I got it. Thanks! :-)

Greedy will not work. Do as Alias said -- just try all possibilities :)

Hello! I have got a accepted at E. My solution is pre-calculate and dp. And the complexity is O(n*m*100). But I have a question that n<=100, m<=10000, so the most complexity is 10000*10000. while it not return a TLE.

I saw the data is not strong enough.

sorry for my bad English. Thanks very much.

Although M is up to 10000, there is an extra constraint: "The next n lines contain the values of the items on the shelves: the first number gives the number of items on this shelf (**an integer between 1 and 100, inclusive**)" So, at each row you have at most 100 items, not 10000 -- i.e. you will never use all breaks in the same row if m is greater than 100. That's how the algorithm runs in time, and I don't think the input data is weak.

Thank you for your patient guide. But I have to ask again. my code have three 'for': first: for (i=1,i<=n,++i) read(); pre_cal() // O(...) second : for(j=m;j>0;--j) // knapsack third: for(k=1;k<=cnt;++k){} so I think the complexity is n*m*cnt: n<= 100, m<= 10000, cnt<=100, so the most is : 100*10000*100. how can you explain this? Thanks again. I beg you guide, please.

Well, 100 million is not THAT much, especially if it is integer operations. Apparently the time limit is large enough to run in time :)

P.S.: Apparently I'm an idiot, because my algorithm also uses about 100,000,000 operations in the worst case. My previous comment explains why the algorithm is 100 * 10000 * 100 and not 100 * 10000 * 10000, which is not what you asked in the first place :)

Oh, yes. 100,000,000 is not THAT much. sorry for my ignorance. I find that your English is so excellent.

Nickolas , thank you for the contest. I like it.

omg, I was typing inclusing/exclusing formula for A for 3-4 minutes and was stunned, when saw that someone wrote simple 1..d loop for 1 minute :D

AntiChernega got 48 wrong hacks! in my room. Though he solve 3 problems, he ended up with 200 points approximately.

poor guy :(

How much time approximate it takes to update the new ratings

Really long time

Can some please explain me why for task C, these test case 10 9 0 gives -1. I thought that solution for this could be 2 3 4 5 6 7 8 9 10 11.

3 after 2 causes "Wow" :)

3 ---> "wow"

Oh, yes. So silly, thank you very much !

Actually the princess would exclaim a wow when she see's a[1]=3.In fact if b=0 and a=n-1 and n>1 then always it is -1 beacuase a[1] has to be a value <= a[0] (to avoid a wow)

i spend like hour on this simulation every time it gets wrong answer on test 4 my answer is 21 and correct answer 22

can't figure out whats wrong with this code :( can anyone help?

Please dont write the whole code in a comment .You can give its link here. Secondly please mention the problem number although it seems obvious after reading the code

I am not sure about this . But looking into your code it seems that for the first time when the princess is running ,,, the dragon will only run after spending time t ,,,

You have made it to run immediately . I am not good at english but I think that you understood me ,,if not I will retry

dragon and princess run at same time

princessHaveRun += princeseSpeed; draconHaveRun += DraconSpeed;

if you mean this

yes , dragon and princess don't run at same time , there is time gap of t seconds

i clear gap in this statement i think there is another problem ~~~~~ if(discoverEscape != 0 ){draconHaveRun =0; discoverEscape--; } ~~~~~

Ratings?

Anyone noticed how similar Top 3 finishers codes are?

I think they were just disqualified.

Only the first and the third places were. Their codes were almost identical. The second finisher's (the winner now) codes seemed to have slight modifications but this is not for me to judge. It is up to administration.

For problem B, when i was accumulating the total time, i am getting WA, but when i am accumulating the total distance, and then calculating time from that it is getting accepted, can anyone reason out the problem ? Precision issues should be in both cases. :-o

Ratings up

... or down

well.