মান লিজিয়ে n (ইভেন) نفر বন্ধুর পছন্দের লিস্ট দেওয়া আছে। প্রতিটি ব্যক্তি i-এর জন্য preferences[i] হল বন্ধুদের পছন্দ অনুযায়ী সর্টেড লিস্ট। যেসব বন্ধু আগে আছে সে বেশি পছন্দ। বন্ধুদের নম্বর ০ থেকে n-1। সব বন্ধুদের জোড়া বানানো হয়েছে। pairs[i] = [xi, yi] মানে xi ও yi জোড়া। কিন্তু বন্ধু x অনহ্যাপি হবেন যদি x এর জোড়া y হয় এবং এমন একজন u থাকে যেও জোড়া v কিন্তু:
xপছন্দ করেu-কেy-এর চেয়ে বেশি, এবংuপছন্দ করেx-কেv-এর চেয়ে বেশি।
অনহ্যাপি বন্ধুদের সংখ্যা বের করতে হবে।
যেমন, ইনপুট হলে preferences = [[1,2,3],[3,2,0],[3,1,0],[1,2,0]], pairs = [[0,1],[2,3]], তবে আউটপুট হবে 2 কারণ প্রথম বন্ধু অনহ্যাপি: ১-র জোড়া ০ কিন্তু ১ পছন্দ করে ৩-কে ০-এর চেয়ে বেশি, এবং ৩ পছন্দ করে ১-কে ২-এর চেয়ে বেশি। ৩ নম্বর বন্ধুও অনহ্যাপি: ৩-র জোড়া ২ কিন্তু ৩ পছন্দ করে ১-কে ২-এর চেয়ে বেশি, এবং ১ পছন্দ করে ৩-কে ০-এর চেয়ে বেশি।
সমাধানের ধাপসমূহ
graph := ডিফল্টডিক্ট(dict)pairs-এ প্রতিটি(start,end)এর জন্য:preferences[start]-এ প্রতিটিprefএর জন্য: যদিpref == endহয় ব্রেক, অন্যথায়graph[start][pref] = 1preferences[end]-এ প্রতিটিprefএর জন্য: যদিpref == startহয় ব্রেক, অন্যথায়graph[end][pref] = 1
unhappy := 0pairs-এ প্রতিটি(start,end)এর জন্য:graph[start]-এ প্রতিটিprefএর জন্য: যদিgraph[pref].get(start)থাকে, তবেunhappy += 1, ব্রেক।graph[end]-এ প্রতিটিprefএর জন্য: যদিgraph[pref].get(end)থাকে, তবেunhappy += 1, ব্রেক।
unhappyরিটার্ন করুন।
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন:
from collections import defaultdict
def solve(preferences, pairs):
graph = defaultdict(dict)
for start, end in pairs:
for pref in preferences[start]:
if pref == end:
break
graph[start][pref] = 1
for pref in preferences[end]:
if pref == start:
break
graph[end][pref] = 1
unhappy = 0
for start, end in pairs:
for pref in graph[start]:
if graph[pref].get(start, None):
unhappy += 1
break
for pref in graph[end]:
if graph[pref].get(end, None):
unhappy += 1
break
return unhappy
preferences = [[1,2,3],[3,2,0],[3,1,0],[1,2,0]]
pairs = [[0,1],[2,3]]
print(solve(preferences, pairs))ইনপুট
[[1,2,3],[3,2,0],[3,1,0],[1,2,0]], [[0,1],[2,3]]
আউটপুট
2
