natalia's blog

Codeforces Beta Round #60
By natalia, 14 years ago, translation, In English
I'm glad to invite everybody to take part in the current round.

Today the problems' author is me. I with Artem Rakhov, Maria Belova and Dmitry Matov have tried  to do everything possible to make problems more reliable.

I hope that the problems will be interesing for you, the contest will be dinamical, and stronger competitors will cope with the problems quickly to help newcomers to catch all bugs by their hacks :)

Good luck!

P.S. The phrase "stronger competitors will cope with the problems quickly" in no way means that all the problems will be easy. Don't forget to read statements and to test your solutions!

UPD. The contest is over. Congratulations to the winner - Kenny_HORROR! 

UPD2. Tutorial is added. In spite of the record number of participants the system has been working stable during the round. Thanks to Codeforces team! Also thanks to everyone who took part in the round.
Announcement of Codeforces Beta Round 60
  • Vote: I like it
  • +134
  • Vote: I do not like it

Comments Comments (48)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Translated Version:
==============

Is pleased to invite all to take part in the next round.·

The author of the challenges I am today. We Artem Rakhiv, Maria Belova and 
Dmitry Matt tried to make every effort to make the problem as soon as more
reliable.·

I hope the problem will be interesting for you, the competition is a dynamic and 
fast powerful members cope with the challenges and help newcomers to catch all 
the bugs by their hacking:)·

Good luck!·

P.S. The phrase "strong parties quickly deal with problems" in any case does not 
mean that all problems will be simple. Do not forget to read the conditions and 
test their solutions!

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    Execute installer by tray icon and insert ms windows binaries or another os with custom mouse driver support in current boot drive.
    → Reply
14 years ago, # |
  Vote: I like it +9 Vote: I do not like it
getting a bad feeling......seems this time probs will be more tough :)
→ Reply
14 years ago, # |
← Rev. 10   Vote: I like it 0 Vote: I do not like it
Hoping that the problems will be easier so that i can solve :D
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
@Natalia: How did you get this rating? 1999 rocks!!
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Good Luck!!
→ Reply
14 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Hacking Festival!
→ Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Can the contest be a little earlier ? Because for most chinese students, the contest time is between 0 and 2 o'clock midnight, which is not so good for us, for we have to go to have class early in the morning.
→ Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
What is the logic to solve problem A? I understood the problem well but couldnot think of how to proceed. How you guys interpreted this question. Being 1st problem, i thought it must be based on "if else" condition....but...no success..
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I hope you'll understand my code:
    if(d==0)
            cout<<H;
        else
            if(c==0)
                cout<<R;
            else
                if(b==0)
                    cout<<H;
                else
                    if(a==0)
                        cout<<R;
                    else
                        if(f==0)
                            cout<<H;
                        else
                            if(e==0)
                                cout<<R;
                            else
                                if(a*c*e<b*d*f)
                                    cout<<R;
                                else
                                    cout<<H;
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
       if(a*c*e<b*d*f) //what is this part  calculating
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it
        When I try to post explanation my message becomes empty.
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        this means that when a,b,c,d,e,f!=0, and you have x sand,
        you get x*(b/a)*(d/c)*(e/f) sand after a loop.
        if b*d*e>a*c*f , the sand will become more and more,and we can get infinite gold.

        → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Please use cycles while programming! This code with 6 'if' was really pure =(
          int ron = -1;
          int val[] = {e, f, a, b, c, d};
          for (int i = 5; ron == -1 && i >= 0; i--)
            if (val[i] == 0)
              ron = (i & 1) == 0;
          if (ron == -1)
            ron = b * d * f > a * c * e;
          printf("%s\n", ron ? "Ron" : "Hermione");
      → Reply
  • 14 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I don't know if it is easy,but my last idea (which got accepted) was just to simulate the process of transformations:

    double process(double x,int a,int b)
    {
    if(a==0 && b==0)return 0;
    if(a!=0 && b!=0)return x*b/a;
    if(a==0 && b!=0)return 1e+100;
    if(a!=0 && b==0)return 0;
    }

    t0=c,c>0

    then t1=process(t0,a,b);t2=process(t1,c,d);t3=process(t2,e,f).

    if we have a lot of gold after 2-nd step(t2>1e+50),or more sand then it was before after the 3-rd step(t3>t0),then Output=Ron

    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    mine was simple brute force using doubles
    double p=1e20,ng,pg;
        for(i=0;i<5;i++) {
            j=i%3;
            if(fm[j]==0) {
                if(to[j]) {p=pow(10,k);k+=20;}
                else p=0;
            }
            else p=(p*to[j])/fm[j];
            if(i==1) pg=p;
            else if(i==4) ng=p;
        }
        if(ng>(pg+1e-6)) puts("Ron");
        else puts("Hermione");
    → Reply
14 years ago, # |
  Vote: I like it +12 Vote: I do not like it
It was a nice background of problems. I appreciate it. Thank you :) However, I failed in this contest. Maybe the next time... ;)
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
During the first half of the contest, clicking on "ROOM" always brings me to room 9, while my room is room 1. Thus it takes me quite long time to understand why I can NOT read other's solutions. I would like to report it as a bug.

This is the first time I participate in a codeforces-ruled contest. :)
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it
1. Solve A.
2. Submit A.
3. Lock A.
4. Realize A is wrong.
5. Hack all the wrong submissions of A.
6. Don't be able to write even B!
7. Solve 0 probs, make some hacks, ... +24 to global rating. o_O
8. ????????
9. PROFIT
→ Reply
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Seems that the precision issue in C is quite serious. What I mean is that, the test data are sensitive to numerical precision error. After chaning the EPSILON in my code, I got ACCEPTED. By randomly looking at others codes and judge results, I find that quite many give an "incorrect" answers which differ from the judge's data by 1 or 2 digits.

(P.S. My algorithm is a little bit different; I employed equation-solving approach whereas many others used binary search.)
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    I think avoiding precision problem is really difficult in this problem.

    If (length of polyline) / (speed of snitch) is just smaller than (distance between last point of polyline and Nimbus' start position) / (speed of Nimbus), it's really difficult to detect that it's impossible.

    I thought about these cases, and - just gave up to think and submitted.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      So, can someone explain what was the difference between correct and wrong solutions here? Such precision problems are very annoying.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Firstly, it is necessary to use a small positive value - EPSILON - to distinguish between < and <=. And in this problem, differences between < and <= matter.

        To my understanding, the point is that, different quantities (e.g., parameter in segment, time, angle in radiance, length, area, ...etc) have DIFFERENT ORDER of magnitudes. If the test data are sensitive to precision, making a "correct" choice of EPSILON could be difficult. (Or even, I would say, it requires luck.)

        Some problems (in various contests) will state explicitly that, you may assume that small precision problem will not affect the solution. But it seems not the case here...

        I guess (and I hope) problem setters do not intend to include estimating good values of EPSILON as a part in Problem C. I am not blaming the problem/test setters, and in fact this problem is well set and interesting. But I hope that next time they could take care of this issue.

        Please share with us if you have any insights. I suspect quite many algorithm coders, including me, find precision problem annoying before...
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hope  in srm 500 there will  be the task like that.
→ Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
I really wanted Dumbledore's help when i read problem statement A
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
The Problem Statement is nice, although I don't know Harry Potter so much.
And the problem A is real interesting!
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
I got rank 118 and my rating rises by 137,
while in the previous contest I got rank 89 but my rating fell by 19.

Is this caused by more competitors?

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Of course. There was a vote after round 58, and rating was calculated only within voted participants.
    → Reply
14 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it
Meanwhile advantage of Gennady over second place increased.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    And Petr advanced to the third place
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +50 Vote: I do not like it
      Petr is so cool that he rises in the ranking even without taking part in competitions
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problem A is good brain-storming problem. It made me hane no mood in solving other problems. :P    After spending a little time thinking, I finally got the logic. What an idiot I am when the contest was running!

First examine the second rule, then the first and the third ones.
If c is 0 but d isn't, it means you can gain gold by no cost.   =>  R
If d is 0, no matter what c is, it means you can never gain gold.   =>  H
If c and d aren't 0, in the same way to think about first and third rules.
If a is 0 but b isn't / e is 0 but f isn't, it means we have infinite resource.  =>  R
If b / f is 0, no matter what a / e is, it means that our resource will be exhausted.  =>  H

Finally, if no number is 0, it's just an easy math problem.

It seems that many people gain lots of hacking score by problem A.
It contains some basic consideration in our daily life.
We should just calm down to think about it, instead of  being nervous or careless and then promiscuously guessing the answer.

→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Can anyone explain this test (#11) for me (problem B)?
Input  Mine Answer
5
1901   1001 
1166   1066 
1308   1108 
1037   1137 
1808   1208 

Correct Output:
No solution
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    My AC solution outputs the same. And checker says that it's okay.

    You confused your output and jury answer.
    → Reply
14 years ago, # |
  Vote: I like it +20 Vote: I do not like it
It has been a while since I last competed in a Codeforces contest, and I was pleasantly surprised by yesterday's round.  Not only was the problem set interesting and well-balanced in terms of difficulty, but the English translations were greatly improved as well, which was a real obstacle for me in the past.

tl;dr: great job, organizers!  I definitely look forward to the next match.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It seems hacking is worth too much in some contest rounds. How about reducing the point value of each successful hack on the same problem? For example: 1st successful hack = 100 pts, 2nd hack = 95 pts, etc.
→ Reply