Блог пользователя determinism

Автор determinism, 9 лет назад, По-английски

I could't solve this problem, then I've read the editorial; but, I still can't understand how we convert dp states into matrices. Can someone, who knows the solution, elaborate?

PS: I know how to compute Nth power of matrix (size M*M) in O(M^3 * log N). I couldn't understand the values we are storing in the matrix and how kth matrix is used to get (k+1)th matrix.

UPD: I've coded the solution as terribleimposter told me, but I think that my implementation is awful. How can I improve it (especially initialising adjacency matrix) ?

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Consider a state (x1, x2,.. , xn).

Here xi denotes the number of times crime i is committed % its multiplicity.

So there are a maximum of 123 states.

Now, create a graph where there is an edge from (x1,.. xi,.. xn) to (x1,.. (xi + 1) % mi,.. xn), for each i. (Basically from each state there are n edges, each edge means committing a particular crime).

Now, you can see that committing k number of crimes means traversing k edges.

So, the question now basically reduces to finding out the number of n length paths in this graph from node (0, 0,... 0) to (0, 0, .., 0).

This is a pretty standard problem whose answer is simply [0][0] element in the adjacency matrix of this graph exponentiated to n-1.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How can I hash (x1,x2,x3...,xn) into an integer?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      You can generate all the required vectors, sort them and then use a map. But this is a very bad way. :P

      I hope someone else gives you a better answer.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      An alternative form is to treat it like a number base, i.e. hash it as

      x_1 + mult[1] * (x_2 + mult[2] * (x_3 + ... mult[n-1] * x_n)))))))

      or

      x_1 + x_2 * mult[1] + x_3 * mult[1] * mult[2] + x_4 * mult[1] * mult[2] * mult[3] + ...

      I don't know if it's strictly better than what was suggested, but it's an alternative way: 9453430