मान लीजिए हमारे पास एक ऐरे colors है, जो एक नियमित n-gon के लिए रंगों का प्रतिनिधित्व करता है। यहां इस n-gon के प्रत्येक शीर्ष को दिए गए ऐरे में मौजूद n अलग-अलग रंगों में से एक के साथ रैंडमली रंगा गया था। हमें बहुभुज शीर्षों के विशेष उपसमुच्चयों की संख्या ढूंढनी है, जैसे कि ये उपसमुच्चय इन शर्तों को पूरा करते हैं:
- उपसमुच्चय का आकार कम से कम दो होना चाहिए।
- यदि हम उपसमुच्चय में मौजूद शीर्षों को बहुभुज से हटा दें (उन शीर्षों के आसन्न किनारे भी हट जाएंगे), तो शेष शीर्ष और किनारे कुछ सतत पथ बनाते हैं।
- उन पथों में से कोई भी दो शीर्ष नहीं होने चाहिए जिनका रंग समान हो।
हमें गिनना है कि ऐसे कितने उपसमुच्चय मौजूद हैं। यदि उत्तर बहुत बड़ा है, तो परिणाम mod 10^9 + 7 वापस करें।
तो, यदि इनपुट colors = [1,2,3,4] है, तो आउटपुट 11 होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- count := एक खाली मैप जहां सभी मान खाली सूची होंगे।
- n := colors का आकार
- i के लिए range 0 से colors के आकार - 1 तक, करें
- i को count[colors[i]] के अंत में डालें
- answer := 0
- i के लिए range 2 से n तक, करें
- answer := answer + nCr(n, i)
- count की सभी कुंजियों की सूची में प्रत्येक i के लिए, करें
- l0 := count[i]
- n0 := l0 का आकार
- यदि n0 > 1, तो
- i के लिए range 0 से n0-2 तक, करें
- j के लिए range i+1 से n0 - 1 तक, करें
- d1 := l0[j] -l0[i]
- d2 := l0[i] -l0[j] + n
- यदि d1 <= n-3 या d2 <= n-3, तो
- answer := answer - 1
- j के लिए range i+1 से n0 - 1 तक, करें
- i के लिए range 0 से n0-2 तक, करें
- answer वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
from collections import defaultdict from math import factorial def nCr(n, i): if n==1: return 1 return factorial(n)//factorial(i)//factorial(n-i) def solve(colors): count = defaultdict(list) n = len(colors) for i in range(len(colors)): count[colors[i]].append(i) answer = 0 for i in range(2, n+1): answer += nCr(n, i) for i in count.keys(): l0 = count[i] n0 = len(l0) if n0 > 1: for i in range(n0-1): for j in range(i+1, n0): d1 = l0[j] -l0[i] d2 = l0[i] -l0[j] + n if d1 <= n-3 or d2 <= n-3: answer -=1 return answer colors = [1,2,3,4] print(solve(colors))
इनपुट
[1,2,3,4]
आउटपुट
11