determinism's blog

By determinism, 6 years ago, In English

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 sandeepmohanty told me, but I think that my implementation is awful. How can I improve it (especially initialising adjacency matrix) ?

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nikhil ( pa.n.ik ) might be of some help, being a criminal himself. (Rapists like you should just eat poison and die. I'm providing you with link for cyanide.) https://www.amazon.com/Industrial-Test-Systems-486812-Cyanide/dp/B00DIJ9UEM/