Horje
Count ways to arrange integers in circle such that no two adjacent are same

Given 2 integers N and M, find the number of ways to arrange N integers in a circle such that every integer is in the range 0 to M-1, and no two adjacent integers are same. As the answer could be large, find the number, modulo 998244353.

Examples:

Input: N=3, M=3
Output: 6
Explanation: There are six ways as follows (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0).

Input: N =4, M=2
Output: 2
Explanation: There are two ways as follows (0, 1, 0, 1), (1, 0, 1, 0).

Approach: To solve the problem, follow the below idea:

The approach effectively uses dynamic programming to build up the count of valid arrangements.

State Representation:

  • dp[i][0]: stores the number of ways to arrange first i integers such that the ith integer is different from the first integer.
  • dp[i][1]: stores the number of ways to arrange first i integers such that the ith integer is same as the first integer.

Base Case:

  • dp[1][1] = m: There is only one element, so we can have numbers 0 to m-1 i.e. total m ways

Transitions:

  • dp[i][0] += (dp[i-1][0] * (m – 2) + dp[i-1][1] * (m – 1)): If the first and the ith integer are different, then we have to take the sum of both the cases:
    • The (i – 1)th integer is same as the first integer, so the number of ways will be dp[i-1][1] * (m – 1).
    • The (i – 1)th integer is different from the first integer, so the number of ways will be dp[i-1][0] * (m – 2)
  • dp[i][1] += dp[i – 1][0]: If the first and the ith integer are same, then the ith element should be same as the last element.

Step-by-step algorithm:

  • The dynamic programming array dp[N+1][2] is used to store the number of ways for each integer.
  • The base case dp[1][1] = m initializes the number of ways to assign integers to the first person.
  • Construct the dp array according to the above state transitions.
  • Return dp[N][0] as the final result.

Below is the implementation of the algorithm:

C++

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define MOD 998244353
 
int main()
{
    int n = 3, m = 3;
 
    vector<vector<long long>> dp(n + 1, vector<long long>(2, 0));
     
    dp[1][0] = 0;
    // Initialize base case
    dp[1][1] = m;
 
    // Bottom-up dynamic programming to fill DP table
    for (int i = 2; i <= n; i++) {
        // No consecutive numbers are the same
        dp[i][0] = (dp[i - 1][0] * (m - 2) + dp[i-1][1] * (m - 1));
        dp[i][1] = dp[i - 1][0];
        dp[i][0] %= MOD;
        dp[1][1] %= MOD;
    }
 
    // Output the result
    cout << dp[n][0];
 
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
 
public class Main {
    public static void main(String[] args) {
        int n = 3, m = 3;
 
        List<List<Long>> dp = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            dp.add(new ArrayList<>(List.of(0L, 0L)));
        }
 
        dp.get(1).set(0, 0L);
        // Initialize base case
        dp.get(1).set(1, (long) m);
 
        // Bottom-up dynamic programming to fill DP table
        for (int i = 2; i <= n; i++) {
            // No consecutive numbers are the same
            dp.get(i).set(0, (dp.get(i - 1).get(0) * (m - 2)
                    + dp.get(i - 1).get(1) * (m - 1))
                    % 998244353);
            dp.get(i).set(1, dp.get(i - 1).get(0) % 998244353);
            dp.get(1).set(1, dp.get(1).get(1) % 998244353);
        }
 
        // Output the result
        System.out.println(dp.get(n).get(0));
    }
}

Python3

MOD = 998244353
 
def main():
    n = 3
    m = 3
     
    # Initialize DP table
    dp = [[0 for _ in range(2)] for _ in range(n + 1)]
 
    # Initialize base case
    dp[1][0] = 0
    dp[1][1] = m
 
    # Bottom-up dynamic programming to fill DP table
    for i in range(2, n + 1):
        # No consecutive numbers are the same
        dp[i][0] = (dp[i - 1][0] * (m - 2) + dp[i - 1][1] * (m - 1)) % MOD
        dp[i][1] = dp[i - 1][0] % MOD
 
    # Output the result
    print(dp[n][0])
 
if __name__ == "__main__":
    main()

C#

using System;
using System.Collections.Generic;
 
class Program {
    static void Main()
    {
        int n = 3, m = 3;
 
        List<List<long> > dp = new List<List<long> >(n + 1);
        for (int i = 0; i <= n; i++) {
            dp.Add(new List<long>(new long[2]));
        }
 
        dp[1][0] = 0;
        // Initialize base case
        dp[1][1] = m;
 
        // Bottom-up dynamic programming to fill DP table
        for (int i = 2; i <= n; i++) {
            // No consecutive numbers are the same
            dp[i][0] = (dp[i - 1][0] * (m - 2)
                        + dp[i - 1][1] * (m - 1))
                       % 998244353;
            dp[i][1] = dp[i - 1][0] % 998244353;
            dp[1][1] %= 998244353;
        }
 
        // Output the result
        Console.WriteLine(dp[n][0]);
    }
}

Javascript

const MOD = 998244353;
 
function main() {
    const n = 3, m = 3;
 
    // Initialize dp array with dimensions (n+1) x 2 filled with 0s
    let dp = new Array(n + 1).fill(0).map(() => new Array(2).fill(0));
 
    dp[1][0] = 0;
    // Initialize base case
    dp[1][1] = m;
 
    // Bottom-up dynamic programming to fill DP table
    for (let i = 2; i <= n; i++) {
        // No consecutive numbers are the same
        dp[i][0] = (dp[i - 1][0] * (m - 2) + dp[i-1][1] * (m - 1)) % MOD;
        dp[i][1] = dp[i - 1][0];
        dp[i][0] %= MOD;
        dp[1][1] %= MOD;
    }
 
    // Output the result
    console.log(dp[n][0]);
}
 
main();

Output

6

Time complexity: O(N), where N is total number of integers in the input.
Space complexity: O(N)


 


Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Segment Tree for Range Bitwise OR and Range Minimum Queries Segment Tree for Range Bitwise OR and Range Minimum Queries
Longest strictly decreasing subsequence such that no two adjacent elements are coprime Longest strictly decreasing subsequence such that no two adjacent elements are coprime
3D Kadane&#039;s Algorithm 3D Kadane&#039;s Algorithm
Minimize operations to restore original string by permutation Minimize operations to restore original string by permutation
Optimization for Unordered Map O(1) operations Optimization for Unordered Map O(1) operations

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 15



 

Horje