Assume that you are the manager of a security company tasked with assigning security officers $($n$)$ to a group of companies $($m$)$ in a certain month with $30$ days numbered D$0,$ D$1,...,$ D$29.$ As$-$ sume that security officers are denoted by SO$0,$ SO$1,...$ SOn$1$ and the companies are represented by C$0,$C$1,...$Cm$1.$ There are three $8-$hour shifts per day: S$0($midnight$-8$am$),$ S$1(8$am$-4$pm$),$ and S$2(4$pm$-$midnight$).$ For each pair company$/$shift $($Cj$,$Sk$),$ the company Cj has a different number of security officers required for the shift Sk$,$ however, this is constant for each day of the month.

The security officers specify the shifts they are interested in working on$,$ and they have the opportunity to indicate more than one $(1)$ preferred shift. However, they cannot be allocated to more than one $(1)$ shift per day. Further, the shift preference of each security officer should be the same for all the days of the month $($and therefore specified only once per security officer$).$

Your task is to provide a plan for assigning officers to the companies for the coming month according to the requirement of the number of security officers per shift by each company. For each day of the month, and for each shift, each company should be allocated exactly the same number of security officers it requests. There are $2$ integer parameters, $0<=$min$\_$shifts$<=30($minimum number of shifts$)$ and $0<=$max$\_$shifts $<=30($maximum number of shifts$),$ and the total number of shifts allocated to each security officer in a month should be within these two integer parameters $($closed interval$).$

As long as you comply with the constraints above, you are free to allocate the security officers any way you want.

The input to your function allocate consists of a list of preferred shifts provided by each security officer and the number of security officers requested by the companies for each shift: preferences is a list of lists, where preferences$[$i$][$k$],$ is a binary value $(0$ or $1),$ indicating whether security officer SOi is interested in working on shift Sk in that month $(1$ indicates that the officer is interested$).$ officers$\_$per$\_$org is a list of lists, where officers$\_$per$\_$org$[$j$][$k$]$ is a non$-$negative number that specifies how many security officers company Cj needs for shift Sk on each day of that month.

Yourtaskistoimplementafunctionallocate$($preferences$,$ officers$\_$per$\_$org, min$\_$shifts, max$\_$shifts$)$ which returns:

$$ None $($i$.$e$.,$ Python NoneType$),$ if no allocation satisfying all constraints exists.

$$ Otherwise, it returns a list of lists allocation, where allocation$[$i$][$j$][$d$][$k$]$ is equal

to $1$ if security officer SOi is allocated to work for company Cj during shift Sk on day Dd$.$

Complexity requirement: The worst$-$case time complexity of your solution should be O$($m$$n$$n$).$

Thank you for your implementation. It passes most test cases except these ones:

result $=$ allocate$([[0,1,0],[1,0,1]],[[3,2,1]],8,26)$

assert result is None

result $=$ allocate$($

$[$

$[1,0,0],$

$[0,1,0],$

$[0,0,1],$

$[0,1,1],$

$[1,0,1],$

$[1,0,0],$

$[1,0,0],$

$[0,0,0],$

$],$

$[[9,1,9]],$

$7,$

$20,$

$)$

assert result is None

result $=$ allocate$($

$[$

$[1,1,0],$

$[1,1,0],$

$[0,1,0],$

$[0,0,0],$

$[0,1,0],$

$[1,0,1],$

$[0,0,1],$

$[1,0,1],$

$[1,1,1],$

$[1,0,0],$

$],$

$[[4,5,10]],$

$22,$

$27,$

$)$

result $=$ allocate$($

$[$

$[1,0,0],$

$[0,0,1],$

$[1,0,0],$

$[1,1,0],$

$[0,0,1],$

$[0,1,1],$

$[0,0,0],$

$[1,1,0],$

$[0,0,0],$

$[0,0,1],$

$[0,0,0],$

$[1,0,1],$

$[0,1,1],$

$[1,0,1],$

$[1,1,1],$

$[1,0,1],$

$[1,0,0],$

$[0,1,0],$

$[0,1,1],$

$],$

$[[4,9,2]],$

$20,$

$27,$

$)$

assert result is None

result $=$ allocate$($

$[[1,0,1],[0,0,1],[0,1,0],[1,0,1],[1,0,0],[0,0,0]],$

$[[7,7,10]],$

$28,$

$28,$

$)$

assert result is None

result $=$ allocate$($

$[$

$[0,1,0],$

$[1,0,0],$

$[0,1,0],$

$[1,1,0],$

$[0,0,1],$

$[0,1,0],$

$[0,1,1],$

$[0,1,0],$

$[1,1,0],$

$[1,1,1],$

$[1,0,0],$

$[0,1,1],$

$[1,1,0],$

$[1,1,0],$

$[1,0,1],$

$[1,0,0],$

$[1,0,1],$

$[0,1,0],$

$[1,0,1],$

$[0,1,1],$

$],$

$[[1,3,2],[4,1,1]],$

$16,$

$24,$

$)$

assert result is not None

result $=$ allocate$($

$[$

$[1,0,1],$

$[0,1,1],$

$[0,1,1],$

$[0,1,1],$

$[0,1,0],$

$[0,1,1],$

$[1,1,0],$

$[1,0,0],$

$[0,0,1],$

$[1,0,1],$

$[1,1,0],$

$[1,0,1],$

$[1,0,0],$

$[0,1,0],$

$],$

$[[2,1,2],[4,3,2]],$

$30,$

$30,$

$)$

assert result is not None

result $=$ allocate$([[1,1,0],[1,0,1],[1,1,1]],[[10,6,5]],3,25)$

assert result is None