



from collections import defaultdict







class       __lowerCAmelCase   :



   def __init__(						self       :  Dict			,		A       :  int			,		A       :  List[Any])       ->   Any:



      """simple docstring"""






      _UpperCAmelCase			=       total  # total no of tasks (N)

      # DP table will have a dimension of (2^M)*N
      # initially all values are set to -1
      _UpperCAmelCase			=       [
          [-1 for i in range(total + 1)] for j in range(2 ** len(__A))
      ]

      _UpperCAmelCase			=       defaultdict(__A)  # stores the list of persons for each task

      # final_mask is used to check if all persons are included by setting all bits
      # to 1
      _UpperCAmelCase			=       (1 << len(__A)) - 1



   def    _lowerCamelCase	(						self       :  Tuple			,		A       :  List[Any]			,		A       :  List[Any])       ->   List[str]:



      """simple docstring"""






      if mask == self.final_mask:
         return 1

      # if not everyone gets the task and no more tasks are available, return 0
      if task_no > self.total_tasks:
         return 0

      # if case already considered
      if self.dp[mask][task_no] != -1:
         return self.dp[mask][task_no]

      # Number of ways when we don't this task in the arrangement
      _UpperCAmelCase			=       self.count_ways_until(__A			,		task_no + 1)

      # now assign the tasks one by one to all possible persons and recursively
      # assign for the remaining tasks.
      if task_no in self.task:
         for p in self.task[task_no]:
            # if p is already given a task
            if mask & (1 << p):
               continue

            # assign this task to p and change the mask value. And recursively
            # assign tasks with the new mask value.
            total_ways_util += self.count_ways_until(mask | (1 << p)			,		task_no + 1)

          # save the value.
      _UpperCAmelCase			=       total_ways_util

      return self.dp[mask][task_no]



   def    _lowerCamelCase	(						self       :  Tuple			,		A       :  Union[str, Any])       ->   List[str]:



      """simple docstring"""






      for i in range(len(__A)):
         for j in task_performed[i]:
            self.task[j].append(__A)

          # call the function to fill the DP table, final answer is stored in dp[0][1]
      return self.count_ways_until(0			,		1)


if __name__ == "__main__":
       UpperCAmelCase__       =	5  # total no of tasks (the value of N)

       # the list of tasks that can be done by M persons.
       UpperCAmelCase__       =	[[1, 3, 4], [1, 2, 5], [3, 4]]
       print(
           AssignmentUsingBitmask(task_performed, total_tasks).count_no_of_ways(
               task_performed
           )
       )





from __future__ import annotations

from itertools import permutations
from random import randint
from timeit import repeat





def 							A     (					)    ->			tuple[list[int], int]:







			'''simple docstring'''
			_UpperCAmelCase			=       [randint(-1_000							,       1_000   ) for i in range(10   )]
			_UpperCAmelCase			=       randint(-5_000							,       5_000   )
			return (arr, r)


UpperCAmelCase__       =	make_dataset()





def 							A     (					_UpperCAmelCase    :       list[int]							,       _UpperCAmelCase    :       int   )    ->			tuple[int, ...]:







			'''simple docstring'''
			for triplet in permutations(_UpperCAmelCase							,       3   ):
						if sum(_UpperCAmelCase   ) == target:
									return tuple(sorted(_UpperCAmelCase   )   )
			return (0, 0, 0)





def 							A     (					_UpperCAmelCase    :       list[int]							,       _UpperCAmelCase    :       int   )    ->			tuple[int, int, int]:







			'''simple docstring'''
			arr.sort()
			_UpperCAmelCase			=       len(_UpperCAmelCase   )
			for i in range(n - 1   ):
						_UpperCAmelCase	,					_UpperCAmelCase			=       i + 1, n - 1
						while left < right:
									if arr[i] + arr[left] + arr[right] == target:
												return (arr[i], arr[left], arr[right])
									elif arr[i] + arr[left] + arr[right] < target:
												left += 1
									elif arr[i] + arr[left] + arr[right] > target:
												right -= 1
			return (0, 0, 0)





def 							A     (					)    ->			tuple[float, float]:







			'''simple docstring'''
			_UpperCAmelCase			=       '\nfrom __main__ import dataset, triplet_sum1, triplet_sum2\n'
			_UpperCAmelCase			=       '\ntriplet_sum1(*dataset)\n'
			_UpperCAmelCase			=       '\ntriplet_sum2(*dataset)\n'
			_UpperCAmelCase			=       repeat(setup=_UpperCAmelCase							,       stmt=_UpperCAmelCase							,       repeat=5							,       number=10_000   )
			_UpperCAmelCase			=       repeat(setup=_UpperCAmelCase							,       stmt=_UpperCAmelCase							,       repeat=5							,       number=10_000   )
			return (min(_UpperCAmelCase   ), min(_UpperCAmelCase   ))


if __name__ == "__main__":
							from doctest import testmod

							testmod()
							UpperCAmelCase__       =	solution_times()
							print(f"""The time for naive implementation is {times[0]}.""")
							print(f"""The time for optimized implementation is {times[1]}.""")
