Thanks for the catch! :)

comment on cf

I've seen the same idea in a DPRK contest and a recent CCPC, so to me, the problem was just a quick-typing.

I've first seen the idea from the editorial in "A Practical Guide To Quantitative Finance Interviews" (aka green book). The Coin Sequence problem in chapter about martingales.

The recent CCPC problem is https://mirror.codeforces.com/gym/102832/problem/G. Kevin, Scott and I virtualled this contest recently on stream actually, and Scott told us the solution then.

For each $$$i$$$, find the expected number of steps until you get to the KMP state $$$i+1$$$ from the state $$$i$$$.

I ended up coding a Gauss elimination and it turned out to be fast enough to pass. I suspect it may have been because I chose the right order of traversal and it actually worked in O(N^2) but I didn't prove it on the contest. On the contest I also added some heuristic for the case when there were a lot of zeroes in each row, but I tried to submit it in the practice room without that optimization and it still passed.

At least in the applet the following works. Copy an entire string that looks like this:

{ 10, 20, 30, 40 }

paste it into the text box where you normally enter one element, and press the {} button.

Actually "Since t occurs at the end of s, completing s after the x-th occurrence of t is on average the same as the (x+1)-th occurence of t." part is a bit shaky. Is there a way to make this step cleaner?

I also don't understand how we get independent probability and how we used the fact that t is the largest border.

Consider $$$s=abaca$$$. It's largest border is $$$t=a$$$. Consider two subsequent occurrences of $$$a$$$, distance between which is two ($$$a?a????$$$). Completing $$$s$$$ after the first $$$a$$$ and after the second $$$a$$$ are dependent.

Could anyone elaborate this please?

How do you see which test a particular submission fails on? Also, if you are using BFS / Dijkstra, maybe your queue is overflowing somehow, BTW.

I got the verdict "uncaught exception" for problem div1A from this contest. I ran the failing test case locally and noticed that my BFS queue was growing indefinitely. I fixed the problem and the test cases passed. So "uncaught exception" can indeed be because of MLE.

Yes please! I had to read and re-read it multiple times, yet my understanding is shaky, in fact very weak. Someone kindly help.

Assume you already performed some dice rolls and got some string. What is the information you want to keep about it? Just the longest suffix of it which is also a prefix of our pattern. That single number (length of this suffix) contains everything that you want to know about it. If you know sth about regular languages you can think of things like this in kind of a Myhill-Nerode type where you distinguish two strings based on all possible futures. That "what information do I want to know about what I already processed?" is also very common in all types of dynamic programming.

Given that, you can represent current state as a single number and consider a graph of transitions and you are good to go

Not a closed form solution as mentioned in editorial but here is my approach — Starting with standard approach to this type of problems — $$$f(i)$$$ denotes expected turns to reach the goal given that we start with prefix of length $$$i$$$ Recurrence — $$$f(i)$$$ = $$$p(s[i+1]).(f(i+1) + 1)$$$ $$$+$$$ $$$sum_{ch!=s[i+1]}p(ch).(f(trans(i,ch)) + 1)$$$ where $$$p(ch)$$$ is probability to get the digit $$$ch$$$ and $$$trans(i,ch)$$$ is normal KMP failure function. Problem is we cannot use $$$DP$$$ to solve since recurrences are cyclic. We need Gauss but it is slow(Can we use some other kind of substitution trick to solve?). After that I thought if we can find the expected value to get from $$$trans(i,ch)$$$ to $$$i$$$ we can get the acyclic recurrence. Let's denote $$$DP[from][to] = EV$$$ to reach $$$to$$$ from $$$from$$$. Assume $$$from = to - 1$$$. We can write $$$DP[to-1][to] = p(s[to]).1 + sum_{ch!=s[to]}p(ch).(DP[trans(to-1,ch)][to-1] + DP[to-1][to])$$$. Open the recurrence accumulate coefficients of $$$DP[to-1][to]$$$ to left side which is simply equal to $$$p(s[to])$$$. When $$$from < to - 1$$$ we need $$$DP$$$ values for $$$DP[from+1][to]$$$ and $$$DP[loc][from]$$$ where $$$loc < from$$$ so process $$$DP[i][j]$$$ in increasing order of $$$j$$$ and decreasing order of $$$i$$$ you have acyclic recurrence now you can use $$$DP$$$ to solve it. Proof from the editorial of the formula is very good.

With,

$$$dp[i]$$$ = expected rolls to reach $$$i^{th}$$$ place in $$$goal$$$. ($$$dp[0] = 0$$$, 1 based indexing)

$$$f(i, d)$$$ = fallback position for digit $$$d$$$ at the $$$i^{th}$$$ place

$$$p_d$$$ = probability of getting the digit $$$d$$$

Now you can easily get the following recurrence,

Answer is obviously $$$dp[len(goal)]$$$.

This is a linear $$$dp$$$, with the overhead of $$$f(i, d)$$$.

$$$f(i, d)$$$ can be calculated using the KMP array (can be pre-calculated), or do a linear search with Hashing.

The time complexity will vary with the method used to calculate $$$f(i, d)$$$.

The best time complexity I can think of is $$$O(len(goal) \cdot len(die)) \equiv O(len(goal))$$$, with pre-calculated KMP array.

Hash h;
// linear search with hashing
int fall(int pos, char d, string & s) {
    int ans = -2 + (s[0] == d);
    for (int i = 0; i < pos; ++i) {
       if (h.subhash(0, i) == h.subhash(pos - i - 1, pos - 1) && s[i + 1] == d) {
         ans = i;
       }
    }
    return ans + 2;
}

int solve(vector <int> die, string goal) {
    h.build(goal);
    int n = sz(die);
    int tot = accumulate(all(die), 0);
    vector<int> dp(sz(goal) + 1);
    for (int i = 1; i <= sz(goal); ++i) {
       int p = die[goal[i - 1] - '0'];
       dp[i] = 1 + dp[i - 1];
       if (dp[i] >= MOD) { dp[i] -= MOD; }
       for (char d = '0'; d < n + '0'; ++d) {
         if (goal[i - 1] != d) {
          int f = fall(i - 1, d, goal);
          dp[i] -= mul(dp[f], mul(die[d - '0'], inv(tot)));
          if (dp[i] < 0) {
              dp[i] = dp[i] + MOD;
          }
         }
       }
       dp[i] = mul(dp[i], mul(tot, inv(p)));
    }
    return dp[sz(goal)];
}