andryk's blog

Problem analysis: Codeforces Beta Round #69 Falling Anvils (Div. 1 - Problem B , Div. 2 - Problem D)
By andryk, 14 years ago, translation, In English
My solution for this task.

We need discriminant to be above zero, so we have:
p - 4q >= 0
p >= 4q

What is probability? It's relation of needed events to all. In this case needed events are all pairs (p,q) where p >= 4q
All events are all possible pairs (p,q) 
How we can count them?
All possible pairs is Cartasian product. We can draw it like rectangle.
Its area - number of all possible pairs.
Also we need to find area of polygon, where p >= 4q.
For this let's draw line y=4x and needed set of points is above this line.
Our answer is relation between this area and area of whole rectangle.
I think finding areas isn't problem.
There is one case that I draw on second image, when 4b < a
There are 2 cases - when a=0 and b=0
When a=0 we have only left part of image, so answer is 0.5
When b=0 we have vertical line, so answer is 1.0
Sorry for some mistakes in English.


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

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
GOOD 77B not ,
Codeforces Beta Round #69 (Div. 1 Only) Problem B
Codeforces Beta Round #69 (Div. 2 Only) Problem D
this is better :D
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Excellent clarification (albeit weak English ;) ). Thanks a tons though.

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I solved it differently.
It is really interesting to note , people think so differently yet do the same thing.
Feynman Rocks!
→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can't we solve this problem by following method ? for a given p we can have any q from -b to p/4. Therefore this length can be written as :- f(x) = b + x/4 we can integrate f(x) from 0 to a g(a)-g(0)=b*a-a*a/8 and the total number of ways to choose two numbers will be a*2b so probability is = ( g(a)-g(0) ) / 2ab But this is giving WA code

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

    Yes you can my dear :) if you wait another 4 years, there will be some sort of method named solve, which solves this problem without any code :)

    → Reply