Oh my God, this is why I kept getting wa

I donāt know why Markov chain is not there in this whole page O:-)

what the hellā¦!! will never forget in lifeā¦! almost entire day wasted1

Great excercise, thank you for that

Try with K=1000 and input:

```
0.99999 0.00001
0.00001 0.99999
```

@kunal361, can you try with

```
0.999995, 0.000005
0.000005, 0.999995
```

My tests show, that it differs for K = 160942 and K = 160943ā¦

I chacked (http://ideone.com/IkXjcg) and it seems, that precision in C/C++ is not as good as in Javaā¦ I also tried long doubleā¦

@himanshujaju I used @mugurelionutās solution - http://ideone.com/ypAUKH, your last link to ideone has some bugā¦

@betlista this is the link to my codeā¦http://ideone.com/MzC8Ex and i have tried your test cases with k=10^9 and have printed when the probs converge!!!

Are there anyone can give me some example?I always get WA ,but i get the same answer with arsh anandā AC solution for test case that i generated randomly

my solution:http://www.codechef.com/viewsolution/5368419

VS

arsh anandās solution:http://www.codechef.com/viewsolution/5420736

Hey Guys ,can anybody tell me what is wrong with my solution:

http://www.codechef.com/viewsolution/5438749

thanks very well,it seems ālong doubleā didnāt work on GCC like it work on VS,it should use ā%Lfā insteading of ā%fā.Felling so bad!

Can You explain why āLetās determine probability that character a will turn into character b after x claps. Itās enough to raise matrix A to power x-1, then print element from (A^(x-1))[a][b].ā but not (A^(x)[a][b])

Please add the setter and testerās soutions.

I used the matrix exponentiation in the contest as that was quite easy compared to a graph solution. I had a graph solution in mind as well. Here is my way of approaching the problem through graph theory -

There are maximum three components in this graph - depending on which alphabet you start from in the original word.

For each component, I have to find the probability of an alphabet occurring at the i th position in our string after k claps separately. So,

Find all the different paths from the root node of the selected component to the required alphabet.

Maintain probability of each path vs distance/claps on each path in say set 1.

In set 1, we reached the required alphabet from the root via all the paths. Now to reach this vertex again further down the graph, it has to be a part of a cycle.

Find all the cycles that the required alphabet lies on.

Maintain probability decrease per cycle vs no of vertices/claps in each cycle in say set 2.

find if given k can be obtained using

k = a+b.n

where a is any element in set 1, b is any element in set 2 and n is 0,1,2,ā¦

find all valid (a,b) and add probabilities for each pair (a,b)

for a pair prob = p(a).p(b)^n

Once we have the three (max 3 letters) tables ready - i.e probability of each alphabet of the starting string converting into some other, the problem is almost solved.

I think this should be right but didnt have the time to implement it due to the end sems. Would be glad if someone could point out any mistakes / correctness of the approach.

yes, I had studied this in my 12th class but still couldnāt solve it due the observation about repeated stringsā¦