Painting Fence Algorithm in C++
In this article, we will discuss the Painting Fence Algorithm in C++ with its algorithm and multiple examples.
Problem Statement:
If a fence has n posts and k colors, determine how many methods there are to paint it so that no more than two posts next to each other have the same color. Return the value modulo 10^9 + 7, as the answer may be huge.
Examples:
Input: n = 2 k = 4. Output: 16 Explanation: There are 2 posts and 4 colors. Methods where the colors of the two posts match: 4 Methods in which the two posts differ in color:4 (first post selections) * 3 (second post choices) = 12 Input: n = 3 k = 2 Output: 6
The six alternative ways to paint three posts with two colors are shown in the following image:
Examine the following image: i, i-1, and i -2 are represented by the colors c, c', and c" respectively.
The problem constraint is that c = c' = c" cannot occur simultaneously, so either c'!= c or c"!= c, or both. For the case of c'!= c and c"!= c, there are k – 1 possibilities.
Algorithm:
diff = number of ways when the color of the last two posts are different same = number of times in which the color of the previous two postings is the same Total ways = diff + same for n = 1 diff = k, same = 0 total = k for n = 2 diff = k * (k-1) //k choices for first post, k-1 for next same = k/k choices for common color of two posts total = k + k * (k-1) for n = 3 diff = (all previous ways) * (k - 1) (k+1) * (k-1) * (k-1) same = previous diff ways k * (k-1) Hence, we deduce that, total[i] = same[i] + diff[i] same[i] = diff[i-1] diff[i] = total[i-1] * (k-1)
Example 1:
Let us take an example to illustrate the Painting Fence Algorithm in C++.
#include <bits/stdc++.h> using namespace std; // Returns count of ways to color k posts long countWays(int n, int k) { long dp[n + 1]; memset(dp, 0, sizeof(dp)); long long mod = 1000000007; dp[1] = k; dp[2] = k * k; for (int i = 3; i <= n; i++) { dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod; } return dp[n]; } // Driver code int main() { int n = 3, k = 2; cout << countWays(n, k) << endl; return 0; }
Output:
6
Example 2:
Let us take another example to illustrate the Painting Fence Algorithm in C++.
#include <bits/stdc++.h> using namespace std; // yields the number of methods to color k posts. // Using K colors long countWays(int m, int l) { // The first post can be colored in k ways. long total = l; int mod = 1000000007; // One post can be made in 0 ways to // both (same color) and k methods to // not violate (different color) int same = 0, diff = l; // Fill for the next two posts. for (int o = 2; o <= m; o++) { same = diff; // The current differs from the previous one. // For the next post, we always have k-1 alternatives. diff = (total * (l - 1)) % 1000000007; // total options up until I. total = (same + diff) % mod; } return total; } // Code for the driver int main() { int m = 3, l = 2; cout << countWays(m, l) << endl; return 0; }
Output:
6
Example 3:
Let us take an example to illustrate the Painting Fence Algorithm in C++.
#include <iostream> using namespace std; int minHeight(int *arr, int cnt) { int minValue = arr[0]; for (int i = 1; i < cnt; i++) if (minValue > arr[i]) minValue = arr[i]; return minValue; } int recursive(int *arr, int cnt) { if (cnt == 1) return 1; int minValue = minHeight(arr, cnt); int rest = 0; int count = 0; int start = 0; for (int i = 0; i < cnt; i++) { arr[i] -= minValue; if (arr[i] == 0) { if (count == 0) { start = i + 1; continue; } else { rest += recursive(arr + start, count); start = i + 1; count = 0; } } else count++; } if (count != 0) rest += recursive(arr + start, count); if (minValue + rest < cnt) return minValue + rest; else return cnt; } int main(void) { int n; cin >> n; int *a = new int[n]; for (int i = 0; i < n; i++) cin >> a[i]; cout << recursive(a, n) << endl; delete[] a; return 0; }
Output:
1 2 1