Thursday, February 25, 2010

Codeforces

My friends from Saratov are building a new system for hosting contests and beyond. They aim for everything there to be available both in English and in Russian. Today was its second beta-test, which was a contest under ACM ICPC rules for 2 hours with 3 problems. Results: http://codeforces.com/contest/2/standings. Problems: http://codeforces.com/contest/2.

Problem B is very nice. I scratched my head for a long time before getting it, yet the idea is very simple and beautiful. I won't spoil it yet - I hope you'll enjoy solving it as well :)

Problem C turned out to be a tough implementation problem for me (I solved a system of two quadratic equations on 2 variables by eliminating the squares to get a linear equation, substituting one variable from that linear equation into one of quadratic equations, and solving the result. This required a lot of care about precision issues and corner cases, and took an hour). However, I have a feeling that it is doable by some binary/ternary search. Any ideas?

12 comments:

  1. Can't you just use the traditional DP approach for problem B? Store each value as N(i, j) * 10 ^ Z(i, j), where N(i, j) and Z(i, j) are integers. Let M(i, j) be the minimum number of trailing zeros following any path to (i, j). If N(i, j) = 0, then C(i, j) = 1 (total product is 0, i.e. one trailing zero). The number of trailing zeros following any path to C(i - 1, j) and then to C(i, j) is the number of trailing zeros in N(i - 1, j) * N(i, j) + Z(i - 1, j) + Z(i, j). There is an analogous formula for the number of trailing zeros from C(i, j - 1) to C(i, j). Then you just fill the DP table, storing backtrack pointers.

    ReplyDelete
  2. Never mind, that isn't quite correct. Need to do something about the non-trailing-zero part of the product for partial paths...back to the drawing board.

    ReplyDelete
  3. hi..peter. can u give me clue about a problem
    how to find the first k digit of n^n
    where 0<n<10^9
    plz provide a clue...

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Hi Petr. Im a new member of TopCoder and I must say your work is very impressive. Can you pls tell me what you studied and any books you recommend. Thnks

    ReplyDelete
  7. non-negative - я так понимаю, что ноль может встретиться по дороге?

    ReplyDelete
  8. hi peter,
    i m new in technolgy of computer and also new to the tests conducted online. can u suggest some way how to increase the capability of coding.
    thnx

    ReplyDelete
  9. Que te focka, vete al instituto.

    ReplyDelete
  10. Hi Petr, Can u recommend me mathematics book for necessary for programming?

    ReplyDelete
  11. Hi Peter,

    I thought about Problem B, and I think I thought of a solution that I would like to check whether it is correct.

    For each number, we calculate the number of 2s and 5s that make up the number. Then, we know that for there to be K trailing zeroes, there must be at least K 2s and K 5s in prime factorisation of the number. Therefore, I use DP.

    DP(i,j) store the minimal 2 and 5 that I can get at (i,j). The number of trailing zeroes at (i,j) will be min(no. of 2s, no. of 5s). Then I recursively do this for DP(i+1,j) and DP(i,j+1) and then I will store the value such that when I add the 2s and 5s to dp(i,j), min(no. of 2s, no. of 5s) is minimal.

    Sorry, my English is not that good. I hope you can understand what I said. Hope for your favourable reply :).

    If it is wrong, is it okay if you give me a clue?

    ReplyDelete
  12. If we se the classic dp approach with a small tweak to have an array(from 1 to 9) for every cell(3d table) and store the number with the lest nmber of trailing zeroes that has the x nmber after the zeroes at A[i,j,x].
    Is this correct?If so are there any optimisations?

    ReplyDelete