### Nickolas's blog

By Nickolas, 11 years ago, translation,

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!

• +166

 » 11 years ago, # | ← Rev. 3 →   +54 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.
 » 11 years ago, # |   +3 How many points will be deducted after each minute passed for each problem?
•  » » 11 years ago, # ^ |   +7 I think it will be 4 points per minute, and the minimum score will be 300.
•  » » » 11 years ago, # ^ |   +1 Thank you brother.
 » 11 years ago, # |   +18 All problems with same value, were you guys inspired by the current Facebook Hacker Cup? ;)
•  » » 11 years ago, # ^ |   0 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.
 » 11 years ago, # |   0 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. )
 » 11 years ago, # |   -7 You wrote fairy tales? Cool!!! Can you tell me some of yours? I really like fairy tale.
•  » » 11 years ago, # ^ |   -13 The link is in the post.
•  » » » 11 years ago, # ^ |   +8 only in russian version of the post
 » 11 years ago, # |   +5 According to the number of votes I got in the first comment, will you take it into considerations?
 » 11 years ago, # |   0 are these problems just in Russian?
•  » » 11 years ago, # ^ |   +12 No. Only the fairy tales are in russian :)
 » 11 years ago, # |   +2 Problem E: Porcelain is contributed by MikeMirzayanov's
•  » » 11 years ago, # ^ |   -15 As for me, this problem is second by it's difficulty.
 » 11 years ago, # |   +5 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);
•  » » 11 years ago, # ^ |   +9 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.
•  » » » 11 years ago, # ^ |   +10 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.
 » 11 years ago, # |   +7 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?
•  » » 11 years ago, # ^ | ← Rev. 2 →   +8 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)andpd(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)
•  » » » 11 years ago, # ^ |   0 Thanks
•  » » 11 years ago, # ^ | ← Rev. 2 →   0 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))
 » 11 years ago, # |   +2 Was E , a dp + a knapsack (which is also a dp) ?
•  » » 11 years ago, # ^ |   0 i solved it that way and it passed, so i guess it was
 » 11 years ago, # |   +2 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;
•  » » 11 years ago, # ^ |   +4 Seams like you fail on n=1 like I did. (Test case 6)
•  » » » 11 years ago, # ^ |   0 Oh,yes.Corrected that and it got accepted.Silly mistake :( Thanks anyways for pointing that out
•  » » 11 years ago, # ^ |   0 if(a==n-1 && a > 0) return -1; 
 » 11 years ago, # |   0 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..
 » 11 years ago, # |   +14 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.
 » 11 years ago, # | ← Rev. 2 →   +12 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.
 » 11 years ago, # |   +1 Anyone want to share recurrence for E as well please...
•  » » 11 years ago, # ^ | ← Rev. 2 →   +2 You should consider two things a) At which row you are b) How many remaining cracks you haveAt 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.
•  » » » 11 years ago, # ^ |   +1 Very interesting. Thanks.
•  » » » 11 years ago, # ^ |   0 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.
•  » » » » 11 years ago, # ^ | ← Rev. 2 →   +1 just check all possible I and J, such that we take I books from left, and J books from right. Look at my solution
•  » » » » » 11 years ago, # ^ |   0 Oh, I got it. Thanks! :-)
•  » » » » 11 years ago, # ^ |   0 Greedy will not work. Do as Alias said -- just try all possibilities :)
•  » » » 10 years ago, # ^ |   0 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.
•  » » » » 10 years ago, # ^ |   +1 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.
•  » » » » » 10 years ago, # ^ |   0 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.
•  » » » » » » 10 years ago, # ^ |   +1 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 :)
•  » » » » » » » 10 years ago, # ^ |   0 Oh, yes. 100,000,000 is not THAT much. sorry for my ignorance. I find that your English is so excellent.
 » 11 years ago, # |   +9 Nickolas , thank you for the contest. I like it.
 » 11 years ago, # |   +5 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
 » 11 years ago, # |   +7 AntiChernega got 48 wrong hacks! in my room. Though he solve 3 problems, he ended up with 200 points approximately.
•  » » 11 years ago, # ^ |   0 poor guy :(
 » 11 years ago, # |   +3 How much time approximate it takes to update the new ratings
•  » » 11 years ago, # ^ |   0 Really long time
 » 11 years ago, # |   0 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.
•  » » 11 years ago, # ^ |   +1 3 after 2 causes "Wow" :)
•  » » 11 years ago, # ^ |   +1 3 ---> "wow"
•  » » » 11 years ago, # ^ |   0 Oh, yes. So silly, thank you very much !
•  » » 11 years ago, # ^ |   +2 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)
 » 11 years ago, # | ← Rev. 2 →   -10 i spend like hour on this simulation every time it gets wrong answer on test 4 my answer is 21 and correct answer 22 100 10 10 739 can't figure out whats wrong with this code :( can anyone help? import java.util.Scanner; public class Test { public static void main(String[] args) { Scanner in = new Scanner(System.in); int princeseSpeed= in.nextInt(); int DraconSpeed = in.nextInt(); int discoverEscape = in.nextInt(); int fixTreasureTime = in.nextInt(); int wholeTime = in.nextInt(); int numberOfbijous = 0; int princessHaveRun=0; int draconHaveRun=0; int numberOfDeley = 0; for(int i=0; i= wholeTime) break; if(princessHaveRun <= draconHaveRun){ numberOfbijous++; numberOfDeley += fixTreasureTime; if((draconHaveRun)%DraconSpeed == 0){ numberOfDeley += ((draconHaveRun)/DraconSpeed); }else{ numberOfDeley +=(draconHaveRun/DraconSpeed + 1); } draconHaveRun = 0; } } System.out.println(numberOfbijous); } } 
•  » » 11 years ago, # ^ |   0 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
•  » » 11 years ago, # ^ |   0 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
•  » » » 11 years ago, # ^ |   0 dragon and princess run at same time princessHaveRun += princeseSpeed; draconHaveRun += DraconSpeed;if you mean this
•  » » » » 11 years ago, # ^ |   0 yes , dragon and princess don't run at same time , there is time gap of t seconds
•  » » » » » 11 years ago, # ^ |   0 i clear gap in this statement i think there is another problem ~~~~~ if(discoverEscape != 0 ){draconHaveRun =0; discoverEscape--; } ~~~~~
 » 11 years ago, # |   +12 Ratings?
 » 11 years ago, # |   +12 Anyone noticed how similar Top 3 finishers codes are?
•  » » 11 years ago, # ^ |   +5 I think they were just disqualified.
•  » » » 11 years ago, # ^ | ← Rev. 2 →   +5 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.
 » 11 years ago, # |   +8 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
 » 11 years ago, # |   -18 Ratings up
•  » » 11 years ago, # ^ |   +9 ... or down
 » 11 years ago, # |   -13 well.
 » 3 years ago, # |   0