snacache's blog

Help with some fractions operations
By snacache, history, 9 years ago, In English

Hi everybody!

I recently was in a programming contest. There were 20 tasks, and one of them was as follows:

In resume, you have C chairs and P pairs of chairs are given. The pairs P(i, j) denote the probability of changing from chair i to chair j. You are sitting in one of these chairs, and every second you have to move to another one.

Then you have Q queries, each with two integers Ci, s , where Ci is the initial chair you are seated and you have to tell the chair that has the highest probability of being seated in after s seconds (after s changes).

1 ≤ Ci ≤ 50

1 ≤ s ≤ 100000000

At first, I thought this was a simple problem, solvable using matrix exponentiation. First creating a matrix M, where Mij = P(i, j). The answer should be in the Ci row of the resulting matrix MS, but the problem has the next important requirement:

You have to output the probability as an irreducible fraction. Worst of all, you have to output ONLY the very last digits of numerator and denominator...

For example: 15/23 -> 5/3, 19/33 -> 9/3

I tried using Java BigInteger, doing reductions with gcd, but it was way too slow.

This is a very interesting requirement (yet a very tough one too, at least for me). Any help will be very appreciated :)

(The contest has already ended, I'm not cheating, and I struggled a lot of hours with this task :( )

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by snacache (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I also participated and have the same question, here is the original problem: https://contest.tuenti.net/Challenges?id=15

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have an idea, I'm not sure it will work. Instead of using Big Integers, represent the number as an array of powers of primes since there are only 25 primes under 100 I think it can be done. I used the condition in the original problem that k890alex pointed out about the restriction on the probability being an integer/100.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Bad idea — does not handle max operation.

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

It seems it wasn't necessary to raise the matrix to the original power.

You can check the following solution: https://github.com/Landertxu/tuentichallenge6/blob/master/15.py

During the contest I also tried to do the same exponent = changes % cycleLength + cycleLength thing, but I don't understand the lcm stuff for example.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, how would matrix exponentiation satisfy time constraints though? Matrix multiplication is an $$$O(N^3)$$$ operation per step, so worst case would be $$$O(N^3 * S)$$$ which would be TLE right?

Furthermore, even a linear time $$$O(N * S)$$$ would also give TLE. Am I missing something?

Regards PS: sorry for the necropost, just wanted to clarify my question, and I think it may benefit others

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You can do the exponentiation in $$$O(log(S))$$$ time. Look for fast exponentiation for more details.

    However if I recall that wasn't enough because of what I mentioned about the fractions. But to answer your question, you can do matrix exponentiation in $$$O(N^3 \cdot log(S))$$$

    → Reply