AlexErofeev's blog

By AlexErofeev, 8 years ago, translation, In English,

Meanwhile, David Eppstein has published his own chart of top algo results of 2011
In russian version I've tried to review some of them, but if you know english better, you should follow original post.
I found it very interesting that there are some red topcoders among authors :)

Read more »

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

By AlexErofeev, 9 years ago, translation, In English,
Today at uva.onlinejudge.org there's going to be held A Contest dedicated to Renat Mullakhanov (rem)
Start at 13:00 MSK.

Read more »

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

By AlexErofeev, 9 years ago, translation, In English,
Already first semifinal of TopCoder Open 2010 finished.
Round was won by bmerry, who was leading through all the round, also Louty (this guy became red just after TCO2010 Online Round5!) and Klinck passed to the Finals.
sys96, Vasyl[alphacom], dzhulgakov and grotomol got it to the wildcard round.
Unfortunately, Petr finished this year's TCO participation after spending too much time on 250.

About tasks:
250: Given a field 2^10+2 by 2^10+2. Squares are filled this style: first they fill (1,1), then leftmost lwermost point of those, which minimal distance to already filled are maximal. Problem is to find kth filled square.
500: Given an infinite field with Alice and 10 rabbits. Rabbits run across the field in given directions. You are to find minimal time for Alice to step into the square, which already contains rabbit, for each rabbit.
950: Given 25 participants of CodeTopper Open 2010. Everyone can get an integer point between worst[i] and best[i] with equal probability. Topmost k pass to the Finals. You are to find probability of each participant to pass into Finals.


How to solve:
250:quoting misof: "make 5 iterations by hand, then make 4 more by hand"
500: more or less standard dp: d[bitmask of catched rabbits][rabbit, that was catched last] = spent time.
1000: even bmerry had about an hour to solve it, but it could not help, so I can't tell you anything now.

Read more »

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