### Egor's blog

By Egor, 9 years ago, translation, ,

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.

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.

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.

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

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.

• +24

 9 years ago, # |   0 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
•  9 years ago, # ^ |   0 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...
•  9 years ago, # ^ |   0 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.
•  8 years ago, # ^ |   0 " for (int count=1;count<=30;count++) " why do you use count here?
 9 years ago, # |   0 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 functiondouble 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; }
•  9 years ago, # ^ |   0 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)
•  9 years ago, # ^ |   0 Насколько корректна будет замена условия типа while() на выполнение log2(1e18) итераций бинарного поиска?
•  9 years ago, # ^ |   0 я думаю, что пройдет
•  9 years ago, # ^ |   +3 Видел реализации, в которых сделали ~200 итераций и они прошли
•  17 months ago, # ^ | ← Rev. 3 →   0 what should be the output for this test case for problem A ? ~~~~~ 5 1 2 1 5 4 4 2 3 2 3 4 3 5 1 5
•  9 years ago, # ^ |   +1 Replace any cin's with scanf's, if you have any.
•  9 years ago, # ^ |   0 In problem E, I got TLE on test case #18. However, when I replace cin>>x>>v; with scanf("%d", &x); scanf("%d", &v); I got accepted. It's incredible.... What's the problem with cin?
•  9 years ago, # ^ |   0
•  9 years ago, # ^ |   0
•  9 years ago, # ^ |   0
•  9 years ago, # ^ |   0
•  9 years ago, # ^ |   0
•  9 years ago, # ^ |   0 see this post, there is a tutorial of reading/writing times
 9 years ago, # |   +3 Earlier i didnot know that u are the winner of GOOGLE CODE JAM 2010Congrats egor !!!
•  9 years ago, # ^ |   +4 Earlier I was not winner of GCJ :)Thanks
 9 years ago, # |   0 congrats egor!!...nice tutorial :)
 » 7 years ago, # |   0 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