Egor's blog

Codeforces Beta Round #24 solutions
By Egor, 14 years ago, translation, In English

Task A

This is pretty simple task - we have cycle and must direct all edges on it in one of 2 directions. We need to calculate cost of both orientation and print smallest of them.
There is a small trick - we can calculate cost of only one orientation and then cost of the other will be sum of costs of all edges minus cost of first orientation.

Task B

Also very simple - we need literary do what we asked. We put all data in a map where for each pilot we have number of points and array of 50 elements - number of times pilot finished at corresponding place. Then we just need to find maximum in this array according to 2 given criteria.

Task C

Reflection over 2 points is just a parallel shift for a doubled vector between them. So M2n = M0 because sequence of reflections may be replaced with sequence of shifts with doubled vectors A0A2, A2A4, ..., An - 2A0 - and their sum is 0. So we can replace j with j' = jmod2N. Now we can just perform j' reflections. Suppose we need to find M' (x', y') - reflection of M(x, y) witch center at A(x0, y0). Then x' = 2x0 - x, y' = 2y0 - y.

Task D

If robot is at last row then answer is 0. Suppose that for every cell of the next row we now expected number of steps to reach last row - zi. Let xi be expected value of steps to reach the last row from current row. Then we have following system of equations:
x1 = 1 + x1 / 3 + x2 / 3 + z1 / 3
xi = 1 + xi / 4 + xi - 1 / 4 + xi + 1 / 4 + zi / 4 for i from 2 to M - 1
xM = 1 + xM / 3 + xM - 1 / 3 + zM / 3
This is tridiagonal system, it can be solved using tridiagonal matrix algorithm in linear time.
So we just have to solve this for each row starting from N - 1 and ending at i and then take x[j].
For M = 1 the answer is 2(N - i) because expected number of steps to go down is 2 - on each turn we either go down or stay

Task E

At first we need to exclude answer -1. Answer is -1 if and only if first part of particles moves left and second part moves right (any of this parts may be empty)
Let's use binary search. Maximal answer is 1e9. Suppose we need to unserstand - whether answer is more then t or less then t. Let's itirate particles from left to right and maintain maximal coordinate that particle moving right would achive. Then of we will meet particle moving left that will move to the left of that coordinate in time t that we have 2 particles that will collide before time t. Otherwise we won't have such pair of particles.
  • Vote: I like it
  • +24
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Another solution for problem D:

Let's define function F(a,b) which returns X where X = 1 + X * a + (1-a) * b and e[i][j] is the expected number of steps that takes for robot to reach last row when robot is initially on cell(i,j).
Here is the whole code:

for (int i=1;i<=m;i++)
    e[n][i]=0;
 
for (int i=n-1;i>=1;i--){
    if (m == 1){
       e[i][1]=f(1.0/2,e[i+1][1]);
    }else{
      for (int count=1;count<=30;count++){
        e[i][1]=f(1.0/3,(e[i+1][1]+e[i][2])/2);
        e[i][m]=f(1.0/3,(e[i+1][m]+e[i][m-1])/2);
        for (int j=2;j<m;j++)
           e[i][j]=f(1.0/4,(e[i][j+1]+e[i][j-1]+e[i+1][j])/3);
      }
    }
  }
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Oh..There is no need to use F(a,b)
    Let the origin Array to be A[1..m]..represents the previous Floor..then first put all elements in B to be zero.
    then create Array C where C[i]=（B[i]+B[i-1]+B[i+1]+A[i])/4+1..then Let B=C and do it for many times can also calculate a new A...
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    are 30 iterations enough for achieving 1e-5 accuracy? Is there any reason why 30 are enough ? Ive tried 100 iterations before for around 500 variables, and I couldnt achieve 1e-9 accuracy.
    → Reply
  • 12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    " for (int count=1;count<=30;count++) " why do you use count here?

    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In problem E , althought I use binary search , it's also Time limited,
would you please tell why?    -_-!!!
my binary search code:

int judge(double t){
 double now = -1500000000;
 for(int i=1;i<=n;i++){
  if(node[i].type==1){
   double test = node[i].x + node[i].v * t;
   if(test > now) now = test;
  }
  else{
   double test = node[i].x - node[i].v*t;
   if(test<=now+epx) return 1;
  }
 }
 return 0;
}

// in main function
double left = 1e-10, right = (node[n].x - node[1].x)/2.0  + 1;
while(aabs(left-right)>epx){
     double mid = (left + right)/2;
     if(judge(mid)==1) right = mid;
     else  left =  mid;
 }

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    That's because left and right will never be within epx. But you only need to find ans within relative or absolute difference of 1e-9/ So you need to change condition to aabs(left-right)>epx * max(right, 1)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Насколько корректна будет замена условия типа while() на выполнение log2(1e18) итераций бинарного поиска?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        я думаю, что пройдет
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Видел реализации, в которых сделали ~200 итераций и они прошли
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Replace any cin's with scanf's, if you have any.
    → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Earlier i didnot know that u are the winner of GOOGLE CODE JAM 2010
Congrats egor !!!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Earlier I was not winner of GCJ :)
    Thanks
    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'v just found new solution for problem E and my code AC 2676662. We could use binary search on distance between two successive colliders that their sign of speed changes from positive to negative.Use this we could figure out the places that colliders could make a Big Bang. By dividing the speed of each collider into the distance from places that we calculate before , we could found the answer. another thing that this problem has very bad exact time limit so we must use printf. and sorry for my bad english :D

→ Reply