Nedy88's blog

Codeforces Beta Round #24
By Nedy88, 14 years ago, In English
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
  • Vote: I like it
  • +58
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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++ ?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
please can anyone describe the solution of the third problem ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    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]
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Если не сложно, то поясните, каким образом получается M[2 * n] = M[0].
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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].
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    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.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I checked it, there is no test with j = 0. (please delete my previous post in wrong place)
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I checked it, there is no test with j = 0.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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. 
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Please tell me the sollution of problem d, my algorithm is too slow , does someone has a fast algorithm ,  like O(n^2) ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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? 
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Excuse me,could you please tell me how to solve problem D?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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. 
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thank you very much!!!I have learnt some useful knowledge with your help!Sorry for my poor English:)
      → Reply