### GrandLisboa's blog

By GrandLisboa, history, 3 months ago,

Why there are so few contests in the coming days? I want to compete and gamble more.

• +207

By GrandLisboa, history, 4 months ago,

Bug or feature?

• +51

By GrandLisboa, history, 6 months ago,

Submission: Link $O(n)$, 93ms!

Part1: Hint

By looking at the $4$ test cases, we find that answers for $b[i] = 1$ are the same.

Part2: The greedy strategy (for each index $i$)

First, we define some macros for convenience:

The previous index of $x$: #define pr(x) ((x) == 1 ? n : (x) - 1)

The next index of $x$: #define ne(x) ((x) == n ? 1 : (x) + 1)

If $b[x]==1$, rt(x) denotes the place of the next $1$ in the loop: rt(x). For example, let $b$ be an $1$-indexed array $[2, 1, 2, 1]$, then $rt(2)==4$ and $rt(4)==2$. Note that $rt(i)==i$ could happen, for example, $b==[2, 1, 2]$, then $rt(2)==2$. rt could be pre-calculated using a stack.

get(i, j): The liters of gas we need to go from $i$ to $j$, both inclusive and $1$-indexed. $j<i$ might happen since our trip is a circle. For example, if $a=[1, 2, 3, 4]$, then $get(1, 2)==a[1]+a[2]==1+2==3$ and $get(4, 2)==a[4]+a[1]+a[2]==4+1+2==7$. The $get$ function could be pre-calculated using the prefix sum.

We need to maintain an array $c$ in the algorithm. $c[i]$ denotes the minimum burbles we need to pay from the previous place $j$ where $b[j]==1$ to $i$. $j$ may be equal to $1$. For example, if $b==[1, 2, 1]$, then $c[3]$ denotes the minimum burbles we need to pay from $3$ to $3$, which is $a[3]$. $c[2]$ denotes the minimum burbles we need to pay from $1$ to $2$. Note that this $c$ is well-defined iff there's at least one $i$ such that $b[i]==1$. So we just need to output the case where all $b[i]$ equal to $2$.

//The Initialpoint
int i = initialpoint;
while(true){
(1) If you are at the destination, which is the same as the initialpoint, goto finish.

(2) When you stay at i where b[i]==2, just pay 2a[i] for a[i] liters that enables you to move from i to ne(i). let i = ne(i);

(3) When you stay at i where b[i]==1, set initialized2 = true and curi = i, and do the following inner while loop. Also, we need to calculate the array c.
while(initialized2 || curi != rt(i)){
//rt(i): The next i in this trip with b[i]==1
//Why do we need this initialized2? Because curi before the loop is i, which may be equal to rt(i) at the beginning, in this case we still need to go into this loop!
if(curi == initialpoint) goto finish;
initialized2 = false;
if(get(i, curi) <= k) c[curi] = get(i, curi);
else c[curi] = k + 2*(get(i, curi) - k); //Buy k liters at i using k burbles and the left get(i, curi) - k liters using 2*(get(i, curi) - k) burbles.
curi = ne(curi);
}
}
finish:


You may worry about the line if(get(i, curi) <= k) c[curi] = get(i, curi);. In this line, if get(i, curi) <= k, we just buy get(i, curi) instead of filling all $k$ liters into the tank. You may think it would be better if we grasp the chance (that we are at some good place that $b[i]==1$) to make our tank full. But, our algorithm is correct. Whenever our algorithm is forced to buy one liter using two burbles, every other strategy needs to. If we have not met an $i$ such that $b[i]==1$ in our trip, then we can only buy one liter using two burbles, no matter what our strategy is. Otherwise, if we are forced to buy one liter using two burbles at some place $i$ where $b[i]==2$, let $j$ be the last $1$ we meet ($b[j]==1$). According to our algorithm, $get(j, i) > k$, which means our algorithm already makes the tank full at place $j$. Even if that, it still faces the lack of fuel issue at $i$ and has to pay for more expensive liter. For other strategies, the fuel amount is at most $k$ at place $j$, so it must also face the lack of liter issue at $i$, and has to pay for more expensive liter also!

When there is at least one $b[i]==1$ in the array, it would be beneficial to decompose our trip into 1222222 blocks. There is at least one block. We would discover that when our trip starts at the leading 1 of the block, it always has $0$ liter! We can prove by induction that each block only buys the fuel it needs for this block. If there is a partial incomplete block before that leading 1, e.g., it starts at 2, goes like 22212222, and now we are at the fourth place 1. According to our algorithm, when it does not meet one 1, you only pay for the fuel that is sufficient for you to go to the next place. Therefore, you won't have any fuel left. Blocks are independent of each other, and if you start at $1$, the answer would be the sum of these blocks, which is the same for each $i$ where $b[i]==1$.

Part3: The overall algorithm

First, we need to special judge the case where all $b[i]==2$. In this case, the answer for each $i$ is

$2\sum\limits_{i=1}^n a[i]$.

We need this special judge, otherwise, the array $c$ in Part 2 would be ill-defined, and the blocks in the last paragraph of Part 2 would be ambiguous.

We denote the answer for each $1$ as answer1.

What is the answer when you start at $i$ (we call the block to which $i$ is affiliated the troublesome block)? It would be:

$ans1 - c[j] + 2get(i, j) + c[pr(i)]$.

Since we don't go through the troublesome block, we need to discount the contribution of this block, which is $c[j]$ from $ans1$. To travel from $i$ to $j$, we need $2get(i, j)$ burbles for $get(i, j)$ liters of fuel. And $c[pr(i)]$ is the burbles we need to pay from the start of this block (which we don't need to know) to $pr(i)$, since we need to finish our trip at $pr(i)$.

• +20

By GrandLisboa, history, 6 months ago,

Part 1: Calculate the Prefix function (next array) in $O(n)$

We can calculate the prefix function (next array) in linear time using the following code:

//next is a 0-indexed array that is initialized to zero.
//s is a 0-indexed string
for(int i = 1, j = 0; i < n; ++i){
while(j && s[i] != s[j]) j = next[j-1];
if(s[i] == s[j]) j++;
next[i] = j;
}


Why is it $O(n)$? The key idea is the amortized analysis. $j$ increases $n$ times, each times increase at most $1$ (in fact $0$ or $1$, $0$ if s[i] != s[j] and $1$ if s[i] == s[j]). Therefore, $j$ increases at most $n$. Since $j$ is never a negative number (you can prove it by induction on the next array), the amount $j$ decreases $\leq$ the amount $j$ increases $\leq n$. Each times $j$ decreases at least $1$ (as $next[j-1] \leq j-1$), so $j$ decreases at most $n$ times. To sum all, $j$ increases and decreases at most $2n$ times, which is $O(n)$.

But there is a trap! We can calculate the whole next array in $O(n)$, but for a suffix of length $k$, calculating the items of the next array that corresponds with that suffix is not $O(k)$!!! In fact, the worst complexity for every suffix, even a single character, could also be $O(n)$! In fact the example is very easy to construct: aaaaa....az, the next array is:

$[0, 1, ..., num(a)-1, 0]$.

For $0 \leq i \leq num(a)$, the line j = next[j-1] executes $0$ times, and when the index comes to $z$, j = next[j-1] would execute $num(a)$ times! That means, the computational burden on the suffix could also be $O(n)$!

The GrandLisboa earns $100$ million from $10$ gamblers, it may earn $90$ million from you and $10$ million from another $9$ gamblers, that is amortization! Let's come back to this problem. When you append each suffix $t$ to the original string $s$, the complexity to handle the suffix is not $O(|t|)$, in fact the worst case is $O(|s|)$, and according to the analysis above, such suffix is very easy to construct!

Part 2: A fix

We note that most next transition is unnecessary. For example,the $0$-indexed string $s$ is ababcababa and we are now checking the last character, which is a. it is not necessary to scan abab (length=$4$) at all, because the prefix abab (s[0:4]) is followed by c while the prefix abab (s[5:9]) is followed by a. So, scan the first two characters ab is enough! Inspired by this, we define the last array:

//last[i][c]: Among 0 <= k <= i such that [0...k] is a prefix of [0,...,i] and [i-k,...,i] is a suffix of [0,...,i], the max k such that s[k+1]==c
//For example, s = "abcabaabd", last[7]['d'] = 7, last[7][c] = 1.
//s[0:1] = "ab" is a prefix of s[0:7]("abcabaab").
//s[0:1] is also a suffix of s[0:7]
//and s[1+1] = s[2] = 'c'
//The transition function: last[i][c] = (c == s[i+1] ? (next[i] >= 1 ? last[next[i]-1][c] : -1) : i);


We can easily transfer to the proper place in $O(1)$ time. Deducing last[i][*] from last[i-1][*] costs $O(|\alpha|)$ time ($\alpha$ is the alphabet), and such transition only happens $O(n)$ times, so we can fix this issue in $O(n |\alpha|)$ time.

As a newbie, what do I learn from this problem?

(1) First, carefully thinks about why the naive algorithm fails. This has been carefully analyzed in the Part $1$.

(3) We should pay attention to the small constraints, they might be the breakthroughs. The "small constraints" are mostly explicit, but sometimes they are implicit and tricky. In this problem, the "lowercase Latin letters" is an implicit constraint that restricts the size of alphabet to $26$. When we work on some problems we may ignore this "implicit small constraints", which are the key factors. We may take the "lowercase Latin letters" for granted, but please note that the KMP algorithm never requires this! Here is another problem having "implicit small constraints": Diverse Substrings.
(1)The original $KMP$ algorithm is already linear and achieves the best theoretical complexity.
(2)The character set in the original $KMP$ algorithm is not restricted to the lower Latin letters. It can handle arbitrary character sets in linear time, not depending on the size of the character sets.