otero1991's blog

By otero1991, 12 years ago, In English

I'm trying to find an algorithm for computing a minimum diameter spanning tree of a graph or just the length of the diameter of a minimum diameter spanning tree. There is a problem on SPOJ related with this:(http://www.spoj.com/problems/MDST) . I wonder if somebody could help me to find some information about this.

Full text and comments »

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

By otero1991, 12 years ago, In English

Recently I was trying to solve 266D - БерДональдс from Codeforces Round 163 (Div. 2), and I tried to understand the tutorial posted by the author. But then I realized that the tutorial for this problem was impossible(at least for me) to understand and that the first solution for this problem was wrong or incomplete!! So I think that this is still a problem here on CF!! Tutorials sometimes can be very weak!! Authors should take care of Tutorials as they do with the problems of the rounds!!!

If somebody could help me to understand 266D - БерДональдс I will appreciate it!! Thanks!!!

Full text and comments »

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

By otero1991, 12 years ago, In English

After removing some elements from a geometric sequence (with not necessary integer ratio), I wonder how can I recover this ratio, and if there are some possibles ratios the one with the greatest absolute value. The solution should be linear or nlogn. The numbers are not greater than 10^18

This problem is from the contest Waterloo Local Contest 24 September (Gym)

Full text and comments »

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

By otero1991, 12 years ago, In English

I have found this problem at the Gym:

Two counterfeiters each made a coin: one of these coins has the probability of getting heads p%, and another one  q%. For some reason the counterfeiters bet that if one chooses the random of these two coins, he gets heads two times in a row. They do so: choose the random coin and throw it. At the 1rst throw they really got heads. Now they want to know: what is the probability to getting heads at the second throw of the chosen coin?

Sample Test:

Input: 50 50 Output: 0.500000000000000

Input: 33 66 Output: 0.550000000000000

Input: 80 40 Output: 0.666666666666667

Does anyone could help me with this problem??

How can I find solutions ans codes for problems from the gym????

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By otero1991, 12 years ago, In English

I have spent some days thinking this problem but I couldn't found the solution!! I think it's greedy!! The problem is: There are some tasks of four different types: AB,BA,A and B. This tasks must be solved using two machines MA and MB. Tasks of type A must be solved on machine MA and tasks of type B must be solved on machine MB. Tasks of type AB, have two parts, part A must be solved on machine MA and part B must be solved in machine MB, but part B can't start until the part A is completed, and similar with tasks of type BA. Each task has its processing time in each machine, and each machine can run at most one task at the same time. Compute the minimal time to finish all the tasks

Full text and comments »

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

By otero1991, 12 years ago, In English

Why are the Codeforces rounds always at the same time and the same days, I think that they should be for example on weekends when people doesn't have to work or to go to school. For me and some friends is very difficult to participate on CodeForces rounds becouse we have to miss some lessons!!!! I think this should be considered!!

Full text and comments »

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

By otero1991, 12 years ago, In English

I have another geometry problem: N points on the plane are given and Q querys must be answered. Each query is about computing how many of those points lay inside a circunference. N,Q<=10^4

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By otero1991, 12 years ago, In English

I wonder if somebody can help me to solve this problem: There is a set X of N point on the plane not two sharing the same x-coordinate, and a set Y of S points. The task is to compute for each point on X the distance to its closest point on Y with a precision of 10^-2 N,S<=10^5 and the coordinates of the points x,y <=10^6

UPD: Sorry for my English I corrected a mistake in the first line

Full text and comments »

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

By otero1991, 12 years ago, In English

When are the authors of CodeForce Round #134 or anybody going to write the Editorial, I couldn't make Div2 D and I want to read the solution, but nobody has post it

Full text and comments »

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

By otero1991, 12 years ago, In English
  • Vote: I like it
  • -22
  • Vote: I do not like it