### Nedy88's blog

By Nedy88, 12 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

• +58

 12 years ago, # |   0 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++ ?
•  12 years ago, # ^ |   0 Oh..In GNU C++ you can use %I64d...%lld sometimes doesn't work...
•  12 years ago, # ^ |   +11 FAQ really should be easily accessible from the main page
•  12 years ago, # ^ |   0 thank you~
 12 years ago, # |   0 please can anyone describe the solution of the third problem ?
•  12 years ago, # ^ |   +6 M[k + 1] = 2 * A[k % n] - M[k]. It is easy to check that M[2 * n] = M[0]. So you can calculate M[j % {2 *n)] instead of M[j]
•  12 years ago, # ^ |   0 Если не сложно, то поясните, каким образом получается M[2 * n] = M[0].
•  12 years ago, # ^ |   0 M[1] = 2 * A[0] - M[0],M[2] = 2 * A[1] - 2 * A[0] + M[0],M[3] = 2 * A[2] - 2 * A[1] + 2 * A[0] - M[0],...M[n] = 2 * A[n] - 2 * A[n - 1] + ... + 2 * A[0] - M[0] (т.к. по условию n нечетно),...M[2 * n] = 2 * A[n] - 2 * A[n - 1] + ... + 2 * A[0] - M[n] = M[0].
•  12 years ago, # ^ |   +1 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.
•  12 years ago, # ^ |   0 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.
•  12 years ago, # ^ |   0 I checked it, there is no test with j = 0. (please delete my previous post in wrong place)
 12 years ago, # |   0 I checked it, there is no test with j = 0.
 12 years ago, # |   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.
•  12 years ago, # ^ |   +17 Topcoder SRM often starts at 5AM MSK. That is our revenge :)
 12 years ago, # |   0 Please tell me the sollution of problem d, my algorithm is too slow , does someone has a fast algorithm ,  like O(n^2) ?
•  12 years ago, # ^ |   0 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.
 12 years ago, # |   0 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?
•  12 years ago, # ^ |   0 The key is to use binary search.
 12 years ago, # |   0 Excuse me,could you please tell me how to solve problem D?
•  12 years ago, # ^ |   0 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.
•  12 years ago, # ^ |   0 Thank you very much!!!I have learnt some useful knowledge with your help!Sorry for my poor English:)