JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Evaluating cyclic recurrences | Reply
Nice Article!
but one thing i want to know is, How do i eveluate a recurrence which is cyclic?

For example, in SchoolTrip, we need to evaluate
E[x1] = p1*E[a]+p2*E[x2]
which eventually ends up in
E[x2] = p3*E[b]+p4*E[x1]

here, pn is a known probablity as well as E[a], E[b] is known.

I could neither solve it using DFS nor using linear recurrences
Re: Evaluating cyclic recurrences (response to post by agsharath) | Reply
From what you have said:

E[x1] = ( p1*E[a] + p2*p3*E[b] ) / ( 1-p2*p4 )

Or I understood something wrong?
Re: Evaluating cyclic recurrences (response to post by agsharath) | Reply
SchoolTrip is a bit different, because it involves taking the minimum across a bunch of possibilities and min is a non-linear function. It's therefore not possible to directly model it as a linear recurrence.

If the strategy were fixed (i.e. you know ahead of time what each student will do depending on who's left in the game), then it would be a linear process. In that case, you end up with a bunch of linear equations (1 for each state). These can be solved with Gaussian Elimination. However, the time-complexity of this is not very good. If the number of states is N (187 in the case of SchoolTrip), then GE takes O(N^3) operations. This is the method of solution for EscapeTheJail for example.
Re: Evaluating cyclic recurrences (response to post by agsharath) | Reply
Other than EscapeJail for other similar problems where this kind of cycles exist, see

CoinGame

PartyGame

This one - simulation. Not sure if Gaussian Elimination would work
ChutesAndladders

CyclicGame

http://www.spoj.pl/problems/FAVDICE/
http://www.spoj.pl/problems/BPRED

All of them involve probability and observe that the number of turns/moves/steps is infinite.
(If the number of turns had been finite say N it would become a DP problem, as that becomes part of state and it reduces in each step)
Re: Evaluating cyclic recurrences (response to post by it4.kp) | Reply
Or I understood something wrong?

What u've said is correct, but consider a more general scenario where we need to traverse a graph to evaluate an expression and the graph is cyclic. ordinary DFS fails and we somehow need to "pass-forward" the coefficients in recursion
Re: Evaluating cyclic recurrences (response to post by StevieT) | Reply
In SchoolTrip you can decide each player's strategy for a given set of remaining players. This is because the probability of hitting is independent of the target and if you miss it doesn't matter who the target was, so you simply pick the target that you'd most like to hit - with the expected value in that case given by a smaller state already computed by DP.

In general for cyclic relationships you'd need to do some sort of Gaussian elimination, but for SchoolTrip you can just continually substitute each equation into the next one until you get an equation for one of the variables in terms of only itself.

CoinGame I think you'd need to use Gaussian elimination, but there are actually only about 20 states of interest (matching prefix length and which player it matches) so it's quite feasible.

PartyGame is only sort-of cyclic - each state is defined in terms of itself, but that can be factored out within each equation, and then a DP should finished it.
Re: Evaluating cyclic recurrences (response to post by bmerry) | Reply
Any hints on this BPRED problem please?

EDIT: I found the recurrence for the label I need to check, but I have still trouble in setting the first element in this recurrence and also reaching the end label from given target label after I iterate the recurrence.

EDIT2: Ok, my problem seems to be, that even though I can find the recurrence for say B in the example input of the BPRED problem with pen&paper, I have no idea how to solve the system of linear recurrences, to obtain the closed form formula within the program. I'm trying to force GJ elimination to solve the system, but it just does not work.

I know that having the recurrences, I can do matrix exponentiation and stuff, but that is not enough for this problem (TLE), so I need to find the closed formula.
I was also thinking about matrix decompositions that would allow me to exponentiate it faster, but I really hope that is an overkill here, because coding them is pure pain for me.
Re: Evaluating cyclic recurrences (response to post by supo) | Reply
Dont know about recurrence based solution. Here is one solution i saw in contest and was able to submit to AC later in judge using Gaussian elimination

Let e[i] : e[0] .. e[n-1] be expected number of times Target statement is executed if we start executing from statement i

e[i] = p* e[i1] + (1-p) e[i2]      // i1 and i2 are two branches,  i2 = i+1 , next statement as per problem 
     = 1 + p* e[i1] + (1-p) e[i2]  // if i is target statement, we add 1 times of execution.Even after reaching target, it again gets executed further,
     = 1.0 * e[i+1]                // if i is  start statement , next statement executes with 100% probability
     = 0                           // if i is End statement


Build a n x n set of equations and solve using Gaussian elimination. For eg above would become

1 e[i] - p  e[i1]  - (1-p)  e[i2]  = 0 
...


Then
e[start] is the answer.
Re: Evaluating cyclic recurrences (response to post by rrpai) | Reply
Can you please explain what is required for

http://www.spoj.pl/problems/FAVDICE/

I wasnt able to completely get it from the message.

Thanks for your help.
RSS