### Nedy88's blog

By Nedy88, 9 years ago, , Hey everybody,

Wellcome to Codeforces Beta Round #24. I'm author to most of the problems today. Something about me: My name is Nedyalko Prisadnikov and I'm a student from Sofia University in Bulgaria. Here are some pictures of me. Many thanks to Mike Myrzayanov and to Artem Rakhov for organizing the contest, writing alternative solutions and some of the problems.

Good luck and have fun!

UPD: Announcement of Codeforces Beta Round #24  Comments (22)
 In the problem C, i submit a solution in GNU C++ which contains/*    long long id;    int n;    scanf("%d %lld",&n, &id);*/and got wrong answer on test 3, but when  i changed to Ms C++ with the same code, i got yes. Can anyone tell me the reason ? can not i use %lld in GNU C++ ?
•  Oh..In GNU C++ you can use %I64d...%lld sometimes doesn't work...
•  FAQ really should be easily accessible from the main page
•  thank you~
 please can anyone describe the solution of the third problem ?
•  M[k + 1] = 2 * A[k % n] - M[k]. It is easy to check that M[2 * n] = M. So you can calculate M[j % {2 *n)] instead of M[j]
•  Если не сложно, то поясните, каким образом получается M[2 * n] = M.
•  M = 2 * A - M,M = 2 * A - 2 * A + M,M = 2 * A - 2 * A + 2 * A - M,...M[n] = 2 * A[n] - 2 * A[n - 1] + ... + 2 * A - M (т.к. по условию n нечетно),...M[2 * n] = 2 * A[n] - 2 * A[n - 1] + ... + 2 * A - M[n] = M.
•  A point that is symmetric to (x, y) with respect to (x0, y0) is (x + 2· (x0 - x), y + 2· (y0 - y)), that is, (2· x0 - x, 2· y0 - y). This gives us the O(j) method of solving the problem.To speed it up notice that the first ⌊ j / n⌋ "cycles" can be processed faster with a sort of parity trick. In particular, any even number of cycles can be dismissed and the rest can be processed with the naive algorithm.
•  there is a small notification about the constraints. it is said that 1<=j<=10^18 and it gave me wrong answer becaues i assumed that j will not less than 1 but i got accepted when i handled the case j = 0.
•  I checked it, there is no test with j = 0. (please delete my previous post in wrong place)
 I checked it, there is no test with j = 0.
 Fun contest :) The timing really killed me though... had to get up at 5AM PST (I live in the USA, on the west coast)! That was nasty. I wish there was a possibility to bump the time back a few hours to help out all of us over in North/South America.
•  Topcoder SRM often starts at 5AM MSK. That is our revenge :)
 Please tell me the sollution of problem d, my algorithm is too slow , does someone has a fast algorithm ,  like O(n^2) ?
•  If you solve the problem row by row starting from the last one, then for every row you'll have tridiagonal matrix which can be solved much faster then standard Gauss elimination.
 I have wrote a brute-force solution (O(n^2)) for problem E. Of course, I got TLE. I have no idea how to prune the search space, any hint?
•  The key is to use binary search.
 Excuse me,could you please tell me how to solve problem D?
•  Let d[i][j] be the expected number of steps to reach the bottommost row from the cell (i, j). Calculate d[i][j] for rows N, N-1, ..., 1 in this order. To get d[i][j], j = 1, ..., m from d[i-1][j] you have to solve a linear system with tridiagonal matrix which can be solved in O(n) operations.
•  Thank you very much!!!I have learnt some useful knowledge with your help!Sorry for my poor English:)