Editorial for Encryption by Reversal

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: jsumabat

Time complexity: $\mathcal O(N)$ ~\mathcal O(N)~.

To solve this, we can use dynamic programming.

Let us consider a dp array $dp[i][j] = dp[\text{index}][\text{reversed or not reversed}] = \text{ minimum number of reversals for the elements of the array up to index } i$ , assuming we are 1-indexed.

Therefore, we know the solution at $dp[1][0]$ ~dp[1][0]~ will be $0$ ~0~, because we do not have to flip any integer to find are solution only for the range $1 \le i \le 1$ ~1 \le i \le 1~. This also means that the solution at $dp[1][1]$ ~dp[1][1]~ will be $1$ ~1~ because at $j=1$ ~j=1~, this signifies we have flipped the integer at index $i=1$ ~i=1~.

Now that we have clarified the state, let us move onto the transition.

We run into 4 cases, where we store 4 variables.

If the current integer is greater than the previous, then this means $dp[i][0] = min(dp[i][0], dp[i-1][0])$ ~dp[i][0] = min(dp[i][0], dp[i-1][0])~ as we do not flip any integers.

If the current integer is greater than the previous reversed integer, then this means $dp[i][0] = min(dp[i][0], dp[i-1][1])$ ~dp[i][0] = min(dp[i][0], dp[i-1][1])~.

If the current integer reversed is greater than the previous, then this means $dp[i][1] = min(dp[i][1], dp[i-1][0]+1)$ .

If the current integer reversed is greater than the previous reversed integer, then this means $dp[i][1] = min(dp[i][1], dp[i-1][1]+1)$ .

Therefore our solution, after running this for $1 \le i \le N$ ~1 \le i \le N~, is $min(dp[N][0], dp[N][1])$ ~min(dp[N][0], dp[N][1])~.

Comments

There are no comments at the moment.