CHEFWORD - Editorial

general
, , ,
21

Oh my God, this is why I kept getting wa :frowning:

22

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

3 Likes
23

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

1 Like
24

Great excercise, thank you for that :wink:

Try with K=1000 and input:

0.99999 0.00001
0.00001 0.99999
25

@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ā€¦

26

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ā€¦

27

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

28

@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!!!

29

Just for the record this branch of probability is known as
markov chain.

2 Likes
30

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

31

This problem is basically this one http://en.wikipedia.org/wiki/Stochastic_matrix

32

Itā€™s not working for sample input - http://ideone.com/9ZFwtm (I just copied our code)

33

Hey Guys ,can anybody tell me what is wrong with my solution:
http://www.codechef.com/viewsolution/5438749

34

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!

35

@khitish The max value of ā€˜hash_stringā€™ would be 26 * 26 * 26 + 26 * 26 + 26, not 26 * 26 * 26

36

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])

37

@zentropy ā€¦still getting WA ā€¦http://www.codechef.com/viewsolution/5440351

38

Please add the setter and testerā€™s soutions.

39

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.

40

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