We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
From the Problem explanation for Sample 0: "With probability 0.25 there will be three dances (the course will end in one day or two days but we don't care about it)."
This is false. There is no way that exactly three dances can occur with the class ending on the second day. To see this, notice that no day can finish with fewer than two dances, so all three would have to occur on the same day. Therefore, the probability of exactly three dances is (1/2)(1-r)(1/2)=(1-r)/4 (i.e. 1/2 for second matching the first, 1-r for not quitting, and 1/2 for the third not matching the first two).
This sort of subtlety will only increase with the the total number of dances, so I am suspicious that any particularly nice closed form solution is possible without some pretty serious combinatorial reasoning.
In the editorial, I fear I do not grasp the "formal definition" of ev[i][j][k]. In my mind, the number of dances associated with a valid (i,j,k) state is unlimited (even in a single day), since we can pick up the same pairs over and over again (with probability 1-r to continue).
Is the underlying infinite sum somehow simplified ?
No more comments
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
From the Problem explanation for Sample 0: "With probability 0.25 there will be three dances (the course will end in one day or two days but we don't care about it)."
This is false. There is no way that exactly three dances can occur with the class ending on the second day. To see this, notice that no day can finish with fewer than two dances, so all three would have to occur on the same day. Therefore, the probability of exactly three dances is (1/2)(1-r)(1/2)=(1-r)/4 (i.e. 1/2 for second matching the first, 1-r for not quitting, and 1/2 for the third not matching the first two).
This sort of subtlety will only increase with the the total number of dances, so I am suspicious that any particularly nice closed form solution is possible without some pretty serious combinatorial reasoning.
In the editorial, I fear I do not grasp the "formal definition" of
ev[i][j][k]. In my mind, the number of dances associated with a valid (i,j,k) state is unlimited (even in a single day), since we can pick up the same pairs over and over again (with probability1-rto continue).Is the underlying infinite sum somehow simplified ?