CHEFWORD - Editorial

Weak test cases, try for K = 41 and K = 40 for matrix

0.99 0.01
0.01 0.99

those are no so similar…

Hm, it’s not the same even for

0.9 0.1
0.1 0.9

lucky you :wink:

1 Like

ok I guess I didnt explain my approach completely. We are multiplying all the probabilities. A difference occurs only if one of them is pretty high, but then it will cause other probabilities to be low and their multiplication would result in an error <= 10^-6. Individually the probabilities maybe incorrect, but they correct themselves overall. There might be weak test cases, but I feel that my algo is right for <=10^-6 relative error.

I think the multiplication of probs of so many letters would lead to most answers being 0…suppose the average probability of a char in the string of length 100 is 0.5…mult value will be approx 10^(-31)…now even if u provide 10^6 such queries…addition of all would still be 0!!!

same for me here. after 2 WA, i thought to myself “noooooo ! omg i was so blind !” haha ! :slight_smile: then i submitted, and AC.

1 Like

If my matrix is the one above, and I ask you to print the probability of changing aaa to aaa in 41 klaps, your answer will be wrong (with respect to eps).

Of course for testing they can use “good” data = such that are no 0 at the end :wink:

Hmm. There must have been some bug by me in calculating the exact “k” value. But for k = 1000, it works! AV9g0U - Online C++ Compiler & Debugging Tool - Ideone.com .

1 Like

I was also getting WA and knew it was Matrix Multiplication, what I did is before printing answer I checked if it’s >1.0(don’t know why but came to mind), if it is I ran an infinite loop.I was given TLE. This way I knew I am counting some probabilities more than once. Then after thinking some time I got that strings can be same(what a realization!! ). Got AC afterwards:)

1 Like

Amazing tip again :wink:

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

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

3 Likes

what the hell…!! will never forget in life…! almost entire day wasted1 :frowning:

1 Like

Great excercise, thank you for that :wink:

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 (IkXjcg - Online C++ Compiler & Debugging Tool - Ideone.com) 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 - ypAUKH - Online C++ Compiler & Debugging Tool - Ideone.com, your last link to ideone has some bug…

@betlista this is the link to my code…MzC8Ex - Online C++ Compiler & Debugging Tool - Ideone.com and i have tried your test cases with k=10^9 and have printed when the probs converge!!!

It’s not working for sample input - 9ZFwtm - Online C++ Compiler & Debugging Tool - Ideone.com (I just copied our code)

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!

Please add the setter and tester’s soutions.