ಚಿತ್ರಕಲೆ ಬೇಲಿ ಅಲ್ಗಾರಿದಮ್


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಕೋಡ್‌ನೇಷನ್ ಫೇಸ್ಬುಕ್ ಗೂಗಲ್ ಪ್ರತ್ಯಕ್ಷ JP ಮೋರ್ಗಾನ್ ಮಾರ್ಗನ್ ಸ್ಟಾನ್ಲಿ
ಅರೇ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಲೀಟ್‌ಕೋಡ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಪೇಂಟಿಂಗ್ ಫೆನ್ಸ್ ಅಲ್ಗಾರಿದಮ್” ನಿಮಗೆ ಕೆಲವು ಪೋಸ್ಟ್‌ಗಳನ್ನು (ಕೆಲವು ಮರದ ತುಂಡುಗಳು ಅಥವಾ ಕೆಲವು ಇತರ ತುಣುಕುಗಳು) ಮತ್ತು ಕೆಲವು ಬಣ್ಣಗಳನ್ನು ಹೊಂದಿರುವ ಬೇಲಿಯನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಬೇಲಿಯನ್ನು ಚಿತ್ರಿಸಲು ಎಷ್ಟು ಮಾರ್ಗಗಳಿವೆ ಎಂಬುದನ್ನು ಕಂಡುಕೊಳ್ಳಿ, ಅಂದರೆ ಕೇವಲ 2 ಪಕ್ಕದ ಬೇಲಿಗಳು ಒಂದೇ ಬಣ್ಣವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಈ ಸಂಖ್ಯೆ ದೊಡ್ಡದಾಗಿರುವುದರಿಂದ, ಉತ್ತರ ಮಾಡ್ಯುಲೋ 1000000007 ಅನ್ನು ಹಿಂತಿರುಗಿಸಿ.

ಉದಾಹರಣೆ

ಚಿತ್ರಕಲೆ ಬೇಲಿ ಅಲ್ಗಾರಿದಮ್

Number of posts/wooden sticks = 2
Number of colors = 2
4

ವಿವರಣೆ
ನೀವು ಎರಡೂ ಪೋಸ್ಟ್‌ಗಳನ್ನು ವಿಭಿನ್ನ ಬಣ್ಣಗಳೊಂದಿಗೆ 2 ರೀತಿಯಲ್ಲಿ ಚಿತ್ರಿಸಬಹುದು. ಮತ್ತು ಒಂದೇ ಬಣ್ಣದಿಂದ ಪೋಸ್ಟ್‌ಗಳನ್ನು ಚಿತ್ರಿಸಲು ನಿಮಗೆ 2 ಮಾರ್ಗಗಳಿವೆ. ಆದ್ದರಿಂದ ಒಟ್ಟು ನಿಮಗೆ 4 ಮಾರ್ಗಗಳಿವೆ.

ಬೇಲಿ ಅಲ್ಗಾರಿದಮ್ ಚಿತ್ರಕಲೆಗೆ ಅನುಸಂಧಾನ

ನಿಷ್ಕಪಟ ವಿಧಾನದಿಂದ ಪ್ರಾರಂಭಿಸೋಣ. ನಮಗೆ n ಪೋಸ್ಟ್‌ಗಳು ಮತ್ತು ಕೆ ಬಣ್ಣಗಳಿವೆ ಎಂದು ನಮಗೆ ನೀಡಲಾಗಿದೆ. ಪೋಸ್ಟ್‌ಗಳನ್ನು ಬಣ್ಣ ಮಾಡುವ ವಿಧಾನಗಳ ಸಂಖ್ಯೆಯನ್ನು ಈಗ ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ, ಅಂದರೆ ಒಂದೇ ಬಣ್ಣವನ್ನು ಹೊಂದಿರುವ 2 ಪಕ್ಕದ ಪೋಸ್ಟ್‌ಗಳು ಮಾತ್ರ ಇವೆ. ನಾವು ಒಂದು ನಿಷ್ಕಪಟ ವಿಧಾನವಾಗಬಹುದು ಎಲ್ಲಾ ಅನುಕ್ರಮಗಳನ್ನು ರಚಿಸಿ ಪ್ರತಿ ಪೋಸ್ಟ್ ಪಡೆದ ಬಣ್ಣವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಆದರೆ ಈ ವಿಧಾನವು ಹೆಚ್ಚು ಅಸಮರ್ಥವಾಗಿದೆ ಮತ್ತು ಖಂಡಿತವಾಗಿಯೂ ಸಮಯದ ಮಿತಿಯನ್ನು ಮೀರುತ್ತದೆ.

ಆದ್ದರಿಂದ, ಉತ್ತಮ ವಿಧಾನ ಯಾವುದು? ಒಂದು ವಿಧಾನ ನಾವು ಸಮಸ್ಯೆಯನ್ನು ಸಣ್ಣ ಸಮಸ್ಯೆಗಳಾಗಿ ಮುರಿದರೆ ಆಗಿರಬಹುದು. ಪೋಸ್ಟ್‌ಗಳ ಸಂಖ್ಯೆಗೆ ಉತ್ತರ ನಮಗೆ ತಿಳಿದಿದೆ ಎಂದು ಪರಿಗಣಿಸಿ = n-2 ಮತ್ತು n-1. ಈ ಮೌಲ್ಯಗಳನ್ನು ಕ್ರಮವಾಗಿ ಎಫ್ (ಎನ್ -2) ಮತ್ತು ಎಫ್ (ಎನ್ -1) ಬಳಸಿ ಸೂಚಿಸೋಣ. ಆದ್ದರಿಂದ ಎಫ್ (ಎನ್ -1) ಕೇವಲ 2 ಪಕ್ಕದ ಪೋಸ್ಟ್‌ಗಳು ಒಂದೇ ಬಣ್ಣವನ್ನು ಹೊಂದುವ ವಿಧಾನಗಳ ಸಂಖ್ಯೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ ಮತ್ತು ಎಫ್ (ಎನ್ -2) ಗೆ ಇದು ನಿಜವಾಗಿದೆ ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ. ಈಗ ನಾವು (n-1) ನೇ ಮತ್ತು n ನೇ ಸ್ಥಾನದಲ್ಲಿ ಒಂದೇ ಬಣ್ಣದೊಂದಿಗೆ ಪೋಸ್ಟ್‌ಗಳನ್ನು ಬಣ್ಣ ಮಾಡಿದರೆ, (n-1) ನೇ ಪೋಸ್ಟ್‌ಗೆ (n-2) nd ಪೋಸ್ಟ್‌ನಂತೆಯೇ ಒಂದೇ ಬಣ್ಣ ಇರಬಾರದು ಎಂದು ನಾವು ಬಯಸುತ್ತೇವೆ. ಈ ಮೌಲ್ಯವನ್ನು ಎಫ್ (ಎನ್ -2) ಬಳಸಿ ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ ನಮ್ಮ ಎನ್ ಟಿ ಪೋಸ್ಟ್ ಕೊನೆಯ ಪೋಸ್ಟ್ನಂತೆಯೇ ಒಂದೇ ಬಣ್ಣವನ್ನು ಹೊಂದಿರುವ ಪ್ರಕರಣವನ್ನು ನಾವು ಪರಿಗಣಿಸಿದ್ದೇವೆ. ಪ್ರಸ್ತುತ ಪೋಸ್ಟ್ ಮತ್ತು ಕೊನೆಯ ಪೋಸ್ಟ್ ಒಂದೇ ಬಣ್ಣವನ್ನು ಹೊಂದಿರದ ವಿಧಾನಗಳನ್ನು ಸಹ ನಾವು ಪರಿಗಣಿಸಬೇಕು. ಈ ಮೌಲ್ಯವನ್ನು ಎಫ್ (ಎನ್ -1) ಬಳಸಿ ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಈಗ ನಾವು n ನೇ ಪೋಸ್ಟ್ ಅನ್ನು ಬಣ್ಣ ಮಾಡಲು (k-1) ಮಾರ್ಗಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಹೀಗೆ ಒಟ್ಟು ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆ (F (n-1) + F (n-2)) * (k-1) ಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ.

ಕೋಡ್

ಚಿತ್ರಕಲೆ ಬೇಲಿ ಅಲ್ಗಾರಿದಮ್‌ಗಾಗಿ ಸಿ ++ ಕೋಡ್

#include <bits/stdc++.h>
using namespace std;

int main(){
  // number of posts
  int n;cin>>n;
  // number of available colors
  int k;cin>>k;
  int mod = 1000000007;
  int ways = 0;
  if(n == 1)cout<<k;
  else if(n == 2)cout<<k*k;
  else {
    int last = k*k; int lastTolast = k;
    for(int i=3;i<=n;i++){
      ways = ((last + lastTolast)*(k-1))%mod;
      lastTolast = last;
      last = ways;
    }
    cout<<ways;
  }
}
4 2
10

ಚಿತ್ರಕಲೆ ಬೇಲಿ ಅಲ್ಗಾರಿದಮ್‌ಗಾಗಿ ಜಾವಾ ಕೋಡ್

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// number of posts
    int n = sc.nextInt();
    // number of available colors
    int k = sc.nextInt();
    int mod = 1000000007;
    int ways = 0;
    if(n == 1)System.out.print(k);
    else if(n == 2)System.out.print(k*k);
    else {
      int last = k*k; int lastTolast = k;
      for(int i=3;i<=n;i++){
        ways = ((last + lastTolast)*(k-1))%mod;
        lastTolast = last;
        last = ways;
      }
      System.out.print(ways);
    }
    }
}
4 2
10

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯದ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ನಾವು ಅಲ್ಗಾರಿದಮ್ನಿಂದ ನೋಡಬಹುದು. ನಾನು ಒಂದೇ ಲೂಪ್ ಅನ್ನು ಬಳಸಿದ್ದೇನೆ ಅದು ನಾನು n ಗೆ ಸಮಾನವಾಗುವವರೆಗೆ ಚಲಿಸುತ್ತದೆ. ಹೀಗೆ n ಪುನರಾವರ್ತನೆಗಳನ್ನು ಮಾಡುವುದು, ಅಂದರೆ ನಮಗೆ ರೇಖೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆ ಇದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1),  ನಾವು ಡಿಪಿ ಅರೇ ಮಾಡುವ ಬದಲು ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸಿದ್ದೇವೆ. ಈ ವಿಧಾನವು ಹೆಚ್ಚು ಕಾರ್ಯಸಾಧ್ಯವಾದ ಕಾರಣ ಸಮಸ್ಯೆಯ ಪರಿಹಾರವು ಕೊನೆಯ ಎರಡು ಸಣ್ಣ ಸಮಸ್ಯೆಗಳ ಮೇಲೆ ಮಾತ್ರ ಅವಲಂಬಿತವಾಗಿರುತ್ತದೆ.