Nickolas's blog

Codeforces Round #105 (Div. 2)
By Nickolas, 12 years ago, translation, In English

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!

  • Vote: I like it
  • +166
  • Vote: I do not like it

Comments Comments (65)
| Write comment?
»
12 years ago, # |
← Rev. 3   Vote: I like it +54 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

are these problems just in Russian?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    No. Only the fairy tales are in russian :)

    → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem E: Porcelain is contributed by MikeMirzayanov's

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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)

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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;

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    if(a==n-1 && a > 0) return -1;
    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Very interesting. Thanks.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not 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

→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How much time approximate it takes to update the new ratings

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    3 after 2 causes "Wow" :)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    3 ---> "wow"

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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)

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

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; i++){
	    	princessHaveRun += princeseSpeed; 
	    	draconHaveRun += DraconSpeed;
	    	if(discoverEscape != 0 ){	draconHaveRun =0; discoverEscape--; }
	    	if(numberOfDeley != 0 ){	draconHaveRun =0; numberOfDeley--; }
	    	if(princessHaveRun >= 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);
	}
}
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      dragon and princess run at same time

      princessHaveRun += princeseSpeed; draconHaveRun += DraconSpeed;

      if you mean this

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Ratings?

→ Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Anyone noticed how similar Top 3 finishers codes are?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I think they were just disqualified.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Ratings up

→ Reply