CF1625C - Road Optimization

Problem : [Codeforces Round #765 (Div. 2) - C. Road Optimization](https://codeforces.com/contest/1625/problem/C)  let $dp[i][j]$ be the minimum time to move up to sign $i$ and $j$ signs where $j$ is $[1 .. i - 1]$ are removed. We can iterate all the stops, try all $k$ on each possible position $p$ where $p$ is the previous stops $1 .. p - 1$. For example, if we need to move from stop $p$ to sign $i$ directly, then all signs between these two stops has to be removed. The total time is simply $(d[i] - d[p]) * a[p]$. And we need to add the previous part $dp[p][j - (i - p - 1)]$. If we remove all signs from stop $p$ to $i$, so basically it is $i - p - 1$. There is a constraint that we cannot remove no more than $k$ signs, so we check if previous $j$ signs that have been removed is greater than $0$ or not. If so, then we can update take the minimum of $dp[i][j]$ and $dp[p][j - (i - p - 1)]$. ```cpp void solve() { long long n, l, k; cin >> n >> l >> k; vector<long long> d, a; for (int i = 0; i < n; i++) cin >> d[i]; for (int i = 0; i < n; i++) cin >> a[i]; d.push_back(l); vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 1e18)); dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { for (int p = i - 1; p >= 0; p--) { int old_j = j - (i - p - 1); if (old_j >= 0) { dp[i][j] = min(dp[i][j], dp[p][old_j] + (d[i] - d[p]) * a[p]); } } } } cout << *min_element(dp.back().begin(), dp.back().end()) << endl; } ```

E-Olymp Competition - Dynamic programming (Linear) - Unofficial Editorial

Contest Link: [https://www.e-olymp.com/en/contests/19775](https://www.e-olymp.com/en/contests/19775) Full Solution: [https://github.com/wingkwong/competitive-programming/tree/master/e-olymp/contests/19775-dynamic-programming-linear](https://github.com/wingkwong/competitive-programming/tree/master/e-olymp/contests/19775-dynamic-programming-linear) # [A - Decreasing Number](https://www.e-olymp.com/en/contests/19775/problems/213338) ## Problem Statement There are three types of operations you can perform on an integer: 1. If it's divisible by 3, divide it by 3. 2. If it's divisible by 2, divide it by 2. 3. Subtract 1. Given a positive integer n, find the minimal number of operations needed to produce the number 1. ## Analysis Let $ \texttt{dp[n]} $ be the smallest number of operations to convert the number $ n $ to $ 1 $. For the base case, we know that for $ n = 1 $, there is no operation. Hence, we can define $ dp[1] = 0 $. For $ n = 2 $, there is only one way to do it which is the third operation. For $ n = 5 $, we can convert it like $ 5 \to 4 \to 2 \to 1 $, therefore we got $ dp[5] = 3 $. Therefore, the transition functions $ dp[i] $ for $ i = 2 \ldots n $ would be $$\begin{equation}\begin{aligned} dp[i] = dp[\frac{i}{3}] + 1 \\\\ dp[i] = dp[\frac{i}{2}] + 1 \\\\ dp[i] = dp[i - 1] + 1 \end{aligned}\end{equation}$$ We can only apply the first two operations only when the number can be divisible by $ 3 $ and $ 2 $ respectively. For every number greater than 1, we can subtract 1. Therefore, we can take the minimum one from previous results and add 1 to form $ dp[i] $. ## Implementation ```cpp int dp[1000005]; int go(int n) { dp[1] = 0; FORN(i, 2, n) { dp[i] = dp[i - 1] + 1; if(i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1); if(i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1); } return dp[n]; } void solve() { int x; while(cin >> x) { OUT(go(x)); } } ``` # [B - House Robber](https://www.e-olymp.com/en/contests/19775/problems/213339) ## Problem Statement You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses are broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. ## Analysis Let $ dp[i] $ be the maximum amount of money you can rob up to house $ i $ (0-base). We can think about the base cases first. We can set $ dp[0] = a[0] $ as we can only rob this house and $ dp[1] = max(a[0], a[1]) $ as we can only rob either one. Since we cannot rob adjacent houses, that means we can rob the current house $ i $ only if the house $ i - 1 $ hasn't been robbed. If we rob the current house, the total amount would be $ dp[i - 2] + a_i $. If not, that would be $ dp[i - 1] + 0 $. We just need to take the maximum one. ## Implementation Notice that the sum can be large so we cannot use int. ```cpp ll dp[1000005]; void solve() { int n; cin >> n; vl a(n); READ(a); dp[0] = a[0]; dp[1] = max(a[0], a[1]); FOR(i, 2, n) dp[i] = max(dp[i - 1], dp[i - 2] + a[i]); OUT(dp[n - 1]); } ``` # [C - Dice Combinations](https://www.e-olymp.com/en/contests/19775/problems/213340) ## Problem Statement Your task is to count the number of ways to construct sum $ n $ by throwing a dice one or more times. Each throw produces an outcome between $ 1 $ and $ 6 $. ## Analysis This question is like a knapsack problem. We can see that as we have infinite numbers of items with weights from $ 1 $ to $ 6 $ and we need to find out how many possible ways to make the knapsack completely full. Let $dp[i]$ be the number of ways to make it to sum $ i $ using numbers from $ 1 $ to $ 6 $. There is only one way to make the sum zero. Hence, we got $ dp[0] = 1 $. Let's say if last item was a $ 1 $, then we know there are $ dp[i - 1] $ ways to make the sum to $i$. If the last item was a $ 2 $, that would be $dp[i - 2]$ ways. The same logic applies for all the number from $ 1 $ to $ 6 $. Therefore we know that $$ dp[i] = \sum\limits_{j = 1}^{6} {dp[i - j]} $$ ## Implementation ``` int dp[1000005]; void solve() { int n; cin >> n; dp[0] = 1; FORN(i, 1, n) { FORN(j, 1, 6) { if(i - j >= 0) { (dp[i] += dp[i - j]) %= 1000000007; } } } OUT(dp[n]); } ``` # [D - Nails](https://www.e-olymp.com/en/contests/19775/problems/213341) ## Problem Statement Some nails are hammered on a straight plank. Any two nails can be joined by a thread. Connect some pairs of nails with a thread, so that to each nail will be tied with at least one thread, and the total length of all threads will be minimal. ## Analysis We can sort the coordinates of all the nails first. Let $ dp[i] $ be the minimum total length of all threads from the first nail to the i-th one. For the base cases we have $ dp[0] = 0 $, $ dp[1] = a[1] - a[0] $ and $ dp[2] = a[2] - a[1] $. Starting from $ i = 3 $, we can either connect the first $ i - 2 $ nails to have $ dp[i - 2] + a[i] - a[i - 1]$ or the first $ i - 1 $ nails to have $ dp[i - 1] + a[i] - a[i - 1] $. Therefore, we have to take the minimum length for each $ i $ where $3 \leqslant i \leqslant n $ holds to have $$ dp[i] = min(dp[i - 1], dp[i - 2]) + a[i] - a[i - 1] $$ ## Implementation ``` int dp[1000005]; void solve() { int n; cin >> n; vi a(n); READ(a); SORT(a); dp[1] = a[1] - a[0], dp[2] = a[2] - a[0]; FOR(i, 3, n) dp[i] = min(dp[i - 1], dp[i - 2]) + a[i] - a[i - 1]; OUT(dp[n - 1]); } ``` # [E - Journey from west to east](https://www.e-olymp.com/en/contests/19775/problems/213342) ## Problem Statement There are n cities standing on a straight line from west to east. The cities are numbered from 1 to n, in order from west to east. Each point on the line has its own one-dimensional coordinate, and the point closer to the east has a large coordinate. The coordinate of the i-th city is xi. You are now in city 1, and want to visit all cities. You have two ways to travel: Walk in a straight line. At the same time, your level of fatigue will increase by a units each time you move a distance of 1, regardless of the direction. Teleport to any point you want. Your fatigue level will increase by b units, regardless of teleported distance.  ## Analysis Let $ dp[i] $ be the lowest possible level of fatigue accumulated from the first city to the $i-th$ city. We can walk in a straight line to make our level of fatigue increase by $ a * (x[i] - x[i - 1]) $ or teleport to a point to make that increase by b. Therefore, the transition is a bit obvious. $$ dp[i] = dp[i - 1] + min(a * (x[i] - x[i - 1], b) $$ ## Implementation ``` ll dp[1000005]; void solve() { ll n, a, b; cin >> n >> a >> b; vl x(n); READ(x); dp[0] = dp[1] = 0; FORN(i, 2, n) { dp[i] = dp[i - 1] + min(a * (x[i - 1] - x[i - 2]), b); } OUT(dp[n]); } ``` # [F - Grasshopper](https://www.e-olymp.com/en/contests/19775/problems/213343) ## Problem Statement Grasshopper lives in the teacher's room. It likes to jump on one dimensional checkerboard. The length of the board is n cells. To its regret, it can jump only on 1, 2, ..., k cells forward. Once teachers wondered in how many ways a grasshopper can reach the last cell from the first one. Help them to answer this question. ## Analysis Let $ dp[i] $ be the number of ways for grasshopper to leap from the first cell to the $i-th$ cell. We know that there is only one way to move for $ i = 1 $ and $ i = 2 $. For $ 3 \leqslant i \leqslant k $, we can reach $i$-th cell from the previous cells. Therefore we can have $$ dp[i] = dp[1] + dp[2] + \ldots + dp[i - 1] = \sum\limits_{j = 1}^{i - 1} {dp[j]} $$ This would work if k is small enough. For large $ k $, we need a better way to calculate $ dp[i] $. Based on the observation, the first five values are $1, 1, 2, 4, 8$. Starting from $ i = 2 $, $ dp[i] $ is doubled from the previous value $ dp[i - 1] $. Formally, it can be obtained as follows. $ \begin{equation} dp[i] = dp[1] + dp[2] + \ldots + dp[i - 2] + dp[i - 1] \end{equation}\tag{1} $ $ \begin{equation} dp[i - 1] = dp[1] + dp[2] + \ldots + dp[i - 2] \end{equation}\tag{2} $ Put $ (2) $ into $ (1) $ $$ dp[i] = dp[i - 1] + dp[i - 1] $$ For $ 3 \leqslant i \leqslant k $, now we know that $ dp[i] = 2 * dp[i - 1] $. For $ i \gt k $, it can be reached from previous cells starting from $ i - k $. $$ dp[i] = dp[i - k] + \ldots + dp[i - 1] = \sum\limits_{j = i - k}^{i - 1} {dp[j]} $$ Similarly, we can rewrite it as follows. $ \begin{equation} dp[i] = dp[i - k] + \ldots + dp[i - 2] + dp[i - 1] \end{equation}\tag{3} $ $ \begin{equation} dp[i - 1] = dp[i - k - 1] + dp[i - k] + \ldots + dp[i - 2] \end{equation}\tag{4} $ Put $ (3) $ into $ (4) $ $$ dp[i] = (dp[i - k - 1] + dp[i - k] + \ldots + dp[i - 2]) + dp[i - 1] - dp[i - k - 1] $$ $$ dp[i] = dp[i - 1] + dp[i - 1] - dp[i - k - 1] $$ Therefore, we can conclude that we have $ dp[i] = 2 * dp[i - 1] $ for $ 3 \leqslant i \leqslant k $ and $ dp[i] = 2 * dp[i - 1] - dp[i - 1 - k] $ for $ i \gt k $. ## Implementation ``` int dp[1000005]; void solve() { int n, k; cin >> n >> k; dp[1] = dp[2] = 1; FORN(i, 3, n) { dp[i] = 2 * dp[i - 1]; if(i > k) dp[i] -= dp[i - 1 - k]; } OUT(dp[n]); } ``` # [G - Platforms](https://www.e-olymp.com/en/contests/19775/problems/213344) ## Problem Statement In older games one can run into the next situation. The hero jumps along the platforms that hang in the air. He must move himself from one side of the screen to the other. When the hero jumps from one platform to the neighboring, he spends |y_2 - y_1| energy, where y1 and y2 are the heights where these platforms hang. The hero can make a super jump that allows him to skip one platform, but it takes him 3 * |y3 - y1| energy. You are given the heights of the platforms in order from the left side to the right. Find the minimum amount of energy to get from the 1-st (start) platform to the n-th (last). Print the list (sequence) of the platforms that the hero must pass. ## Analysis Let $ dp[i] $ be the minimum amount of energy to get from the 1-st platform to the $i$-th. Starting from the base cases, we know that we need zero energy to reach the first platform, i.e. $ dp[1] = 0 $ and we need $ |y2 - y1| $ energy for $ dp[2] $. Starting from the third platform, we can either reach from the previous platform $ p[i - 1] $ or use super jump from $ p[i - 1] $. Hence, the minimum energy for $ dp[i] $ would be $$ dp[i] = min(dp[i - 1] + |y_{i} - y_{i-1}|, dp[i - 2] + 3 * |y_{i} - y_{i - 2}|) $$ So now we solve the first subtask. The remaining subtasks are to find out the number of platforms to pass and the list of these platforms. We can use another vector to store the index for each choice so that we can perform a path restoring at the end. The size of this vector is the answer to the second subtask and we need to reverse the vector to build the answer to the third subtask. ## Implementation ``` int dp[1000005]; void solve() { int n; cin >> n; vi a(n + 1); REPN(i, n) cin >> a[i]; dp[1] = 0; dp[2] = abs(a[2] - a[1]); vi p = {0, -1, 1}, ans; FORN(i, 3, n) { int x = dp[i - 1] + abs(a[i] - a[i - 1]); int y = dp[i - 2] + 3 * abs(a[i] - a[i - 2]); dp[i] = x < y ? x : y; p.pb(x < y ? i - 1 : i - 2); } OUT(dp[n]); int v = n; while(v != -1) { ans.pb(v); v = p[v]; } REVERSE(ans); OUT(SIZE(ans)); EACH(x, ans) OUTH(x); OUT(""); } ``` # [H - Frog](https://www.e-olymp.com/en/contests/19775/problems/213345) ## Problem Statement There are n stones, numbered 1, 2, ..., n. For each i (1 ≤ i ≤ n), the height of stone i is hi. There is a frog who is initially on stone 1. It will repeat the following action some number of times to reach stone n: if the frog is currently on stone i, jump to stone i + 1 or stone i + 2. Here, a cost of |hi − hj| is incurred, where j is the stone to land on. Find the minimum possible total cost incurred before the frog reaches stone n. ## Analysis Let $ dp[i] $ be the minimum possible total cost for frog to reach stone $ i $. We can reach the first stone without any cost and there is only one way to jump to the second stone. Hence, we know the base cases are $dp[1] = 0$ and $dp[2] = |h_2 - h_1|$. Starting from the thrid stone, we can either jump it from the last $i - 1$ stone or $i - 2$ stone. Therefore, we can add the current cost to previous results and take the minimum one. $$ dp[i] = min(dp[i - 1] + |h_i - h_{i - 1}|, dp[i - 2] + |h_i - h_{i - 2}|) $$ ## Implementation ``` int dp[1000005], h[1000005]; void solve() { int n; cin >> n; REPN(i, n) cin >> h[i]; dp[1] = 0; dp[2] = abs(h[2] - h[1]); FORN(i, 3, n) { dp[i] = min( dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]) ); } OUT(dp[n]); } ``` # [I - Platforms - 3](https://www.e-olymp.com/en/contests/19775/problems/213346) ## Problem Statement In older games one can run into the next situation. The hero jumps along the platforms that hang in the air. He must move himself from one side of the screen to the other. When the hero jumps from one platform to the neighboring, he spends |y2 - y1|^2 energy, where y1 and y2 are the heights where these platforms hang. The hero can make a super jump that allows him to skip one platform, but it takes him 3 * |y3 - y1|^2 energy. Symbol ^ here indicated exponentiation. You are given the heights of the platforms in order from the left side to the right. Find the minimum amount of energy to get from the 1-st (start) platform to the n-th (last). ## Analysis It is similar to the previous problem. Sometimes it is optimal to make a step back and jump to other platform. For exmaple, let's say there are four platforms and we can jump in the this order: $1 -> 3 -> 2 -> 4$. Let $ dp[i] $ be the minimum amount of energy to get from the 1-st platform to the $i$-th. We know that we don't need any energy to reach the first platform so we have $dp[1] = 0$. For the second platform, there are two cases to consider: 1. If there are only two platforms, the only way to reach the second platform is from the first platform. Hence, the required energy is $|a_2 - a_1| ^ 2$. 2. We can first jump to the third platform and jump back to the second platform. The required energy is $3 * |a_1 - a_3| ^ 2 + |a_2 - a_3| ^ 2$ Similarily, for $3 \leqslant i \leqslant n$, we can either 1. jump from the $(i - 1)$-th platform 2. super jump from the $(i - 2)$-th platform 3. jump from $(i - 1)$-th platform to $(i + 1)$-th platform and jump back to $i$-th platform if the jump is valid ($i < n$) The required energy for each case would be $$ dp[i - 1] + |a_i - a_{i - 1}| ^ 2 \\ $$ $$ dp[i - 2] + 3 * |a_i - a_{i - 2}| ^ 2 \\ $$ $$ dp[i - 1] + 3 * |a_{i + 1} - a_{i - 1}| ^ 2 + |a_i - a_{i + 1}| ^ 2 $$ and $ dp[i] $ takes the minimum one. ## Implementation ``` ll dp[1000005], a[1000005]; ll exp2(ll x) { return x * x; } void solve() { int n; cin >> n; REPN(i, n) cin >> a[i]; dp[1] = 0; dp[2] = exp2(abs(a[2] - a[1])); if(n == 2) { OUT(dp[n]); return; } dp[2] = min( exp2(abs(a[1] - a[2])), // 1 -> 2 3 * exp2(abs(a[1] - a[3])) + exp2(abs(a[3] - a[2])) // 1 -> 3 -> 2 ); FORN(i, 3, n) { dp[i] = min( dp[i - 1] + exp2(abs(a[i - 1] - a[i])), dp[i - 2] + 3 * exp2(abs(a[i - 2] - a[i])) ); if(i < n) { dp[i] = min( dp[i], dp[i - 1] + 3 * exp2(abs(a[i - 1] - a[i + 1])) + exp2(abs(a[i] - a[i + 1])) ); } } OUT(dp[n]); } ``` # [J - Buying tickets](https://www.e-olymp.com/en/contests/19775/problems/213347) ## Problem Statement There is a queue of n people to buy tickets to a musical premiere. Each person wants to buy exactly one ticket. Only one ticket-office was working, therefore ticketing was very slowly, bringing "guests" to despair. The most smart people quickly noticed that, as a rule, the cashier sells several tickets in one hand faster than when those same tickets are sold one by one. So they proposed for a number of people standing in a row to give money to the first one of them, so that he would buy tickets for all. However to deal with speculators, the cashier decided to sell maximum of three tickets per person, so to agree with each other in such way can only two or three successive persons. It is known that to sell one ticket for the i-th person in the queue takes ai seconds, to sell two tickets takes bi seconds, to sell three tickets takes ci seconds. Write a program that calculates the minimum time to serve all the customers. Please note that tickets for a group of united people always buys the first one. Also, no one buys extra tickets for speeding up the process (i.e. the tickets that are not wanted). ## Analysis Let $dp[i]$ be the minimum time in seconds to serve from the first to $i$-th customer. We only need $a_1$ seconds to server the first one if there is only one customer. If there are two customers, it takes either $a_1 + a_2$ seconds or $b_1$ seconds. Therefore, we know that the base cases are $$ dp[1] = a_1 $$ $$ dp[2] = min(a_1 + a_2, b_1) $$ If there are three or more customers, we have three cases to consider: 1. If the $i$-th customer buys one ticket, it takes $dp[i - 1] + a_i$ seconds 2. If the $(i-1)$-th customer buy two tickets, it takes $dp[i - 2] + b_{i - 1}$ seconds 3. If the $(i-2)$-th customer buy two tickets, it takes $dp[i - 3] + b_{i - 2}$ seconds We take the minimum value from these three cases. $$ dp[i] = min(dp[i - 1] + a_i, dp[i - 2] + b_{i - 1}, dp[i - 3] + b_{i - 2}) $$ ## Implementation ``` int dp[1000005], a[1000005], b[1000005], c[1000005], d[1000005]; void solve() { int n; cin >> n; REPN(i, n) cin >> a[i] >> b[i] >> c[i]; dp[0] = 0; dp[1] = a[1]; dp[2] = min(a[1] + a[2], b[1]); FORN(i, 3, n) dp[i] = min({ dp[i - 1] + a[i], dp[i - 2] + b[i - 1], dp[i - 3] + c[i - 2] }); OUT(dp[n]); } ```

Finding Longest Palindrome in O(n) Using Manacher's Algorithm

You can practice the problem [here](https://cses.fi/problemset/task/1111/). Given a string, your task is to determine the longest palindromic substring of the string. For example, the longest palindrome in aybabtu is bab. A palindrome here is a string which reads the same backward as forward. We can use functions like ``reverse`` to check if the given string is a palindrome or not. ```cpp bool is_palindrome(string s) { string t = s; reverse(t.begin(), t.end()); return s == t; } ``` Or we can use two pointers. ```cpp bool is_palindrome(string s) { int l = 0, r = (int) s.size() - 1; while(l < r) { if(s[l] != s[r]) return false; else l++, r--; } return true; } ``` The first approach is brute force. ```cpp int n = (int) s.size(), start = 0, mx_len = 1; REP(i, n) { REP(j, i) { int ok = 1; REP(k, (j - i + 1) / 2) { if(s[i + k] != s[j - k]) ok = 0; } if(ok && (j - i + 1) > mx_len) { start = i; mx_len = j - i + 1; } } } OUT(s.substr(start, mx_len)); ``` However, the time complexity for this solution is O(n ^ 3) because we need three nested loops to find the longest palindromic substring. It only works when n is really small. The second approach is dynamic programming. The time complexity can be further reduced to O(n ^ 2). We use dp[i][j] to indicate if s[i] .. s[j] is a palindrome or not. Let's think about the transitions. 1. If i == j, that means s[i] == s[j], a single character is a palindrome. Example: a. 2. If i + 1 == j and s[i] == s[j], then s[i] .. s[j] is a palindrome. Example: aa. 3. If dp[i + 1][j - 1] and s[i] == s[j], then s[i] .. s[j] is a palindrome. Example: abba. As we can see, dp[i + 1][j] needs to be calculated before d[i][j]. Therefore, we iterate i from n - 1 to 0 and j from i + 1 to n. ```cpp int n = (int) s.size(); vvi dp(n, vi(n, 0)); string ans; int start = 0, len = 1; REP(i, n) dp[i][i] = 1; FORD(i, n - 1, 0) { FOR(j, i + 1, n) { if(s[i] == s[j]) { if(i + 1 == j || dp[i + 1][j - 1]) { dp[i][j] = 1; if(len < j - i + 1) { start = i; len = j - i + 1; } } } } } OUT(s.substr(start, len)); ``` With dynamic programming, the time cplexity and auxiliary space are O(n ^ 2). However, we can solve the problem in linear time using Manacher's algorithm. As a palindrome has a symmetric property at the center position, it could help us to reduce some unnecessary computations. If there is a palindrome of length N centered at position P, we can avoid the comparisions after position P as we already calculated longest palindromic substring at position before P. However, an even palidrome has two centers, which makes the calculate a little bit different than the one calculating for an odd palindrome. Here's the implementation in C++. ```cpp string manacher(string s) { int n = (int) s.size(); // d1[i]: the number of palindromes accordingly with odd lengths with centers in the position i. // d2[i]: the number of palindromes accordingly with even lengths with centers in the position i. vector d1(n), d2(n); int l1 = 0, r1 = -1, l2 = 0, r2 = -1, mx_len = 0, start = 0; for (int i = 0; i < n; i++) { // ---------------------- // calculate d1[i] // ---------------------- int k = (i > r1) ? 1 : min(d1[l1 + r1 - i], r1 - i + 1); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++; d1[i] = k--; if (i + k > r1) l1 = i - k, r1 = i + k; if(d1[i] * 2 > mx_len) start = i - k, mx_len = d1[i] * 2 - 1; // ---------------------- // calculate d2[i] // ---------------------- k = (i > r2) ? 0 : min(d2[l2 + r2 - i + 1], r2 - i + 1); while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) k++; d2[i] = k--; if (i + k > r2) l2 = i - k - 1, r2 = i + k; if(d2[i] * 2 > mx_len) start = i - k - 1, mx_len = d2[i] * 2; } // return the longest palindrome return s.substr(start, mx_len); } ``` If you want to count how many palindromic substrings in the given string, simply sum d1[i] and d2[i] where i = 0 .. n - 1. ```cpp int cnt = 0; for(int i = 0; i < n; i++) cnt += d1[i] + d2[i]; ``` This problem can also be solved using fast LCA in O(n) or String Hashing O(nlogn). These methods will not be discussed in this post. You can find the whole solution [here](https://github.com/wingkwong/competitive-programming/blob/09531f2fbfbf03393ba3e744cb77858134463e29/cses/string-algorithms/1111-longest-palindrome.cpp).

AtCoder - ABC185C. Duodecim Ferra

You can practice the problem Duodecim Ferra [here](https://atcoder.jp/contests/abc185/tasks/abc185_c). ## Problem Statement There is an iron bar of length ``L`` lying east-west. We will cut this bar at 11 positions to divide it into 12 bars. Here, each of the 12 resulting bars must have a positive integer length. Find the number of ways to do this division. Two ways to do the division are considered different if and only if there is a position cut in only one of those ways. Under the constraints of this problem, it can be proved that the answer is less than 2^63. ## Solutions This problem can be solved using Stars and Bars Theorem. Given the lenght ``L``, we have a Diophantine equation ``x[0] + x[1] + ... + x[11] = L`` where x[i] are the lengths of the bars after the division. We need to select 11 positions out of ``L - 1`` positions. For example, if ``L`` is 14, we will have the following possible points to cut. ``` 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 ``` Therefore, the answer is ``` C(n, r) = C(L - 1, r - 1) = C(14 - 1, 12 - 1) = C(13, 11) = 78 ``` We can solve it in O(r) time complexity and O(1) space complexity . nCr can be written as ``` (n)! / (r)!( / (n - r)! = (n * (n - 1) * (n - 2) * ... * 1 ) / (r * (r - 1) * (r - 2) * ... * 1) / ((n - r) * (n - r - 1) * (n - r - 2) * ... * 1) = n * (n - 1) * (n - 2) * ... * (n - (r - 1)) / (r * (r - 1) * (r - 2) * ... * 1) ``` ```cpp // AC - 3 ms void solve() { ll L; cin >> L; ll ans = 1; FOR(i, 1, 12) { ans *= L - i; // n * (n - 1) * (n - 2) * ... * (n - (r - 1)) ans /= i; // r * (r - 1) * (r - 2) * ... * 1 } OUT(ans); } ``` We can turn it to a template for similar problems ```cpp template< typename T > T comb(int64_t N, int64_t K) { if(K < 0 || N < K) return 0; T ret = 1; for(T i = 1; i <= K; ++i) { ret *= N--; ret /= i; } return ret; } // AC - 7 ms void solve() { ll L; cin >> L; OUT(comb<ll>(L - 1, 11)); } ``` We can also use dynamic programming to solve this problem. The recursive formula is ``` C(n, r) = C(n - 1, r - 1) + C(n - 1, r) ``` For ``r == 0`` and ``n == r``, the result would be 1. ```cpp // AC - 10 ms const int mxN = 205; ll c[mxN][mxN]; void solve() { ll L; cin >> L; REP(i, l) { c[i][0] = c[i][i] = 1; FOR(j, 1, i) { c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; } } OUT(c[L - 1][11]); } ```

Finding All Pairs Shortest Path Using Floyd–Warshall Algorithm

Floyd–Warshall Algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). Let's say we have 4 nodes and given the 2D array ``edges`` containing three values - {from, to, weight} representing a bidirectional and weighted edges between nodes ``from`` and ``to``. Supposing we have a distance threshold ``k`` and we would like to find out the smallest number of nodes that are reachable through some path whose the distance is at most ``k``.  The pseudocode for Floyd–Warshall algorithm is ``` let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for each edge (u, v) do dist[u][v] ← w(u, v) // The weight of the edge (u, v) for each vertex v do dist[v][v] ← 0 for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if ``` To implement in C++, we first define ``dist``. As dist[i][j] stores the distance between two points, we can initialised the maximum value of ``k``. Let's say the constraint is ``1 <= k <= 10^4``. We can initialise any values which is greater than 10^4. ``` vector<vector<int>> dist(n, vector<int>(n, 10005)); ``` Then we need to reset the left diagonal to zero ``` for(int i = 0; i < n; i++) dist[i][i] = 0; ``` so that we can build the dist[i][j]. Let's say the edge is bidirectional. ``` for(auto e : edges) dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2]; ``` Calculate the distance for each pair with Time Complexity: O(n ^ 3) ``` for(int k = 0; k < n; k++) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } ``` If dist[i][j] is storing a boolean value, we can use ``` dist[i][j] = dist[i][j] || dist[i][k] && dist[k][j]; ``` Once we got dist[i][j], we can easily find out the answer. ``` int ans = 0, mi = n; for(int i = 0; i < n; i++) { int cnt = 0; for(int j = 0; j < n; j++) { cnt += dist[i][j] <= k; } if(cnt <= mi) { mi = cnt; ans = i; } } ``` Here are some practice problems. - [743. Network Delay Time](https://leetcode.com/problems/network-delay-time/) - [1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) - [1462. Course Schedule IV](https://leetcode.com/problems/course-schedule-iv/)

Unbounded Knapsack

Given an array of integers and a target sum, determine the sum nearest to but not exceeding the target that can be created. To create the sum, use any element of your array zero or more times. For example, if arr=[2,3,4] and your target sum is 10, you might select [2,2,2,2,2], [2,2,2,3] or [3,3,3,1] . In this case, you can arrive at exactly the target. Sample Input ``` 2 3 12 1 6 9 5 9 3 4 4 4 8 ``` Sample Output ``` 12 9 ``` Explanation In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}. This is a unbounded knapsack so we cannot use the classic way to solve this problem. To solve it, we can break the problem into smaller problems first. If we put the first item into the knapsack, then the remaining capacity would be ``W-w1``. So we can break it down to find out the maximum value ``max1`` if we pack the same item ``N`` times in a knapsack of capacity ``W-w1``. For the second item, we do the same thing to get ``max2`` so that it has a remaining capacity of ``W-w2``, and so on. Each item has a own value now but we have to add the original value to it. ``` itemMax1 = max1 + v1 ``` The maximum value is ``` W = max(itemMax1,itemMax2,...,itemMaxN) ``` where ``W`` is the maximum value packed in the knapsack of capacity. Psuedo code ```cpp f(v[], w[], c) { // v: array of values // w: array of weights // c: capacity // n: length of the array // base case // if it is full, the total value of a 0 capacity knapsack is 0 if(c==0) return 0; int[] m; // break it down to smaller problem // ---------------------------------------- for(int i=0;i<n;i++){ // if we can put item 1 if(w[i]<c) m[i]=f(v,w,c-w[i]); // not enough space else m[i]=0; } // add back the original value // ---------------------------------------- for(int i=0;i<n;i++){ // if we can put item 1 if(w[i]<c) mm[i]=m[i] + v[i]; // not enough space else mm[i]=0; } // find the maximum value // ---------------------------------------- int ans=mm[0]; for(int i=1;i<n;i++){ if(mm[i]>ans) ans=mm[i]; } return ans; } ``` However, we can use bottom-up dynamic programming solution for this problem to improve the above solution. As we may see that we only have one parameter ``c`` for the recursive method where ``c`` ranges from ``W`` to ``0`` and ``v[]`` and ``w[]`` remain unchanged. Therefore, we can store the results computed by the recursive function in a 1d array. ```cpp int dp[W+1]; ``` We can set our base case to 0. ```cpp dp[0] = 0; ``` We can turn ```cpp f(v,w,c-w[i]); ``` to ```cpp dp[c-w[i]] ``` and also from ```cpp int ans=mm[0]; for(int i=1;i<n;i++){ if(mm[i]>ans) ans=mm[i]; } return ans; ``` to ```cpp dp[c]=mm[0]; for(int i=1;i<n;i++){ if(mm[i]>dp[c]) dp[c]=mm[i]; } ``` and the result would be ```cpp return dp[c]; ``` So we have the following structure ```cpp dp[0] = 0 for C=0 ... W: for i=0 .. N: if w[i]<=C: dp[i] = max ( dp[i], ( dp[C-w[i]] + v[i] ) ) else dp[i] = 0 ```

The Longest Increasing Subsequence Problem

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in strictly ascending order. For example, the length of the LIS for [15,27,14,38,26,55,46,65,85] is 6 since the longest increasing subsequence is [15,27,38,55,65,85] Sample Input ``` 5 2 7 4 3 8 ``` Sample Output ``` 3 ``` Explanation In the array [2,7,4,3,8], the longest increasing subsequence is [2,7,8]. It has a length of 3. Given that an array with a length of `n`, we can create two vectors with the same size - one called ``l`` for holding the length, another one ``s`` for holding the sub-sequence index. ``` arr [2,7,4,3,8] n [1,1,1,1,1] s [0,0,0,0,0] ``` If we list out the index, we should see ``` idx 0,1,2,3,4 arr [2,7,4,3,8] ``` let's say we have ``i`` and ``j`` where ``i`` starts from ``1..n-1`` and j starts from ``0..i``. ``` j,i idx 0,1,2,3,4 arr [2,7,4,3,8] ``` we check if ``arr[j]`` is lesser than ``arr[i]``. If so, check if ``l[j]+1`` is greater than ``l[i]`` In this case, ``arr[j]`` is 2 which is lesser than ``arr[i]`` which is 7. So we add ``l[j]`` by 1 to see if it is greater than ``l[i]``. It is. So we set ``l[j]+1`` to ``l[i]`` and set the index ``j`` to ``s[i]``. Repeat the above steps till ``i`` reaches ``n-1``. Find out the maximum value of ``l``. That is the length of the LIS. ```cpp int lis(vi a, int n){ vi l(n); vi s(n); int max=0; l[0]=1; FOR(i, 1, n){ l[i] = 1; REP(j,i){ if(a[j] < a[i]){ if(l[j]+1>l[i]){ l[i]=l[j]+1; s[i]=j; if(l[i]>max) max=l[i]; } } } } return max; } int main() { // SKIPPED } ``` However, this approach is ``O(N^2)`` which gives you Terminated due to timeout (TLE) Error. We need a faster approach to resolve this problem. Supposing there is a vector called ``vi``. The strategy is - If ``vi`` is empty, set the input ``a`` to ``vi[0]``. - If ``vi`` is not empty and the input ``a`` is the largest value of ``vi``, append ``a`` at the end - If ``vi`` is not empty and the input ``a`` is in between, find the correct index and replace the existing value. We can implement a binary search function to look for the correct index or we can just use STL. The answer is the size of ``vi``. Final Solution ```cpp int main() { FAST_INP; int n,a; cin >> n; vi v; REP(i,n){ vi::iterator it; cin >> a; if(i==0) v.push_back(a); else { it=lower_bound(v.begin(),v.end(),a); int k=it-v.begin(); if(k==v.size()) v.push_back(a); else v[k]=a; } } cout << v.size(); return 0; } ```