Este é um acompanhamento de matrizes de contagem que fazem conjuntos exclusivos . A diferença significativa é a definição de exclusividade.

Considere uma matriz Ade comprimento n. A matriz contém apenas números inteiros positivos. Por exemplo A = (1,1,2,2). Vamos definir f(A)como o conjunto de somas de todos os sub-arranjos contíguos não vazios de A. Nesse caso f(A) = {1,2,3,4,5,6}. As etapas a f(A) serem produzidas são as seguintes:

Os sub-arranjos de Asão (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Suas respectivas somas são 1,1,2,2,2,3,4,4,5,6. O conjunto que você obtém dessa lista é, portanto {1,2,3,4,5,6}.

Chamamos uma matriz de A única se não houver outra matriz Bdo mesmo comprimento, de modo que f(A) = f(B), exceto a matriz Ainvertida. Como exemplo, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6}mas não há outra matriz de comprimento 3que produz o mesmo conjunto de somas.

Tarefa

A tarefa, para um dado ne, sé contar o número de matrizes exclusivas desse comprimento. Você pode assumir que sestá entre 1e 9. Você só precisa contar matrizes onde os elementos são um número inteiro sou s+1. Por exemplo, se s=1as matrizes que você está contando contêm apenas 1e 2. No entanto, a definição de exclusividade refere-se a qualquer outra matriz do mesmo comprimento. Como exemplo concreto, não[1, 2, 2, 2] é único, pois fornece o mesmo conjunto de somas que .[1, 1, 2, 3]

Você deve contar o reverso de uma matriz, bem como a própria matriz (desde que a matriz não seja um palíndromo, é claro).

Exemplos

s = 1, as respostas para n = 2,3,4,5,6,7,8,9 são:

4, 3, 3, 4, 4, 5, 5, 6

Pois s = 1, as matrizes únicas de comprimento 4 são

(1, 1, 1, 1)
(2, 1, 1, 2)
(2, 2, 2, 2)

s = 2, as respostas para n = 2,3,4,5,6,7,8,9 são:

4, 8, 16, 32, 46, 69, 121, 177

Um exemplo de uma matriz que não é exclusiva s = 2é:

(3, 2, 2, 3, 3, 3). 

Isso tem o mesmo conjunto de somas que ambos: (3, 2, 2, 2, 4, 3)e (3, 2, 2, 4, 2, 3).

s = 8, as respostas para n = 2,3,4,5,6,7,8,9 são:

4, 8, 16, 32, 64, 120, 244, 472

Ponto

Para um dado n, seu código deve gerar a resposta para todos os valores de sfrom 1a 9. Sua pontuação é o valor mais alto npara o qual isso termina em um minuto.

Teste

Vou precisar executar o seu código na minha máquina ubuntu, portanto, inclua as instruções mais detalhadas possíveis sobre como compilar e executar seu código.

Entre os melhores

• n = 13 por Christian Sievers em Haskell (42 segundos)

Haskell

import Control.Monad (replicateM)
import Data.List (tails)
import qualified Data.IntSet as S
import qualified Data.Map.Strict as M
import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed.Mutable (write)
import System.Environment (getArgs)
import Control.Parallel.Strategies

orig:: Int -> Int -> M.Map S.IntSet (Maybe Int)
orig n s = M.fromListWith (\ _ _ -> Nothing) 
               [(sums l, Just $! head l) | 
                   l <- replicateM n [s, s+1],
                   l <= reverse l ]

sums :: [Int] -> S.IntSet
sums l = S.fromList [ hi-lo | (lo:r) <- tails $ scanl (+) 0 l, hi <- r ]

construct :: Int -> Int -> S.IntSet -> [Int]
construct n start set =
   setmax `seq` setmin `seq` setv `seq`
   [ weight r | r <- map (start:) $ constr (del start setlist)
                                           (V.singleton start)
                                           (n-1)
                                           (setmax - start),
                r <= reverse r ]
  where
    setlist = S.toList set
    setmin = S.findMin set
    setmax = S.findMax set
    setv = V.modify (\v -> mapM_ (\p -> write v p True) setlist)
                    (V.replicate (1+setmax) False)

    constr :: [Int] -> V.Vector Int -> Int -> Int -> [[Int]]
    constr m _ 0 _ | null m    = [[]]
                   | otherwise = []
    constr m a i x =
         [ v:r | v <- takeWhile (x-(i-1)*setmin >=) setlist,
                 V.all (V.unsafeIndex setv . (v+)) a,
                 let new = V.cons v $ V.map (v+) a,
                 r <- (constr (m \\\ new) $! new) (i-1) $! (x-v) ]

del x [] = []
del x yl@(y:ys) = if x==y then ys else if y<x then y : del x ys else yl

(\\\) = V.foldl (flip del)

weight l = if l==reverse l then 1 else 2

count n s = sum ( map value [ x | x@(_, Just _) <- M.toList $ orig n s]
                      `using` parBuffer 128 rseq )
  where 
    value (sms, Just st) = uniqueval $ construct n st sms
    uniqueval [w] = w
    uniqueval _   = 0


main = do
  [ n ] <- getArgs
  mapM_ print ( map (count (read n)) [1..9]
                    `using` parBuffer 2 r0 )

A origfunção cria todas as listas de comprimento ncom entradas sou s+1, guarda-as se vierem antes do reverso, calcula sua sub sums- lista e as coloca em um mapa que também lembra o primeiro elemento da lista. Quando o mesmo conjunto de somas é encontrado mais de uma vez, o primeiro elemento é substituído por Nothing, então sabemos que não precisamos procurar outras maneiras de obter essas somas.

A constructfunção procura por listas de determinado comprimento e determinado valor inicial que possuem um determinado conjunto de somas de sub-listas. Sua parte recursiva constrsegue essencialmente a mesma lógica que essa , mas possui um argumento adicional que fornece a soma que as entradas restantes da lista precisam ter. Isso permite que você pare mais cedo, mesmo que os menores valores possíveis sejam grandes demais para obter essa soma, o que proporcionou uma enorme melhoria de desempenho. Grandes melhorias adicionais foram obtidas movendo esse teste para um local anterior (versão 2) e substituindo a lista de somas atuais por a Vector(versão 3 (quebrada) e 4 (com rigor adicional)). A versão mais recente faz o teste de associação ao conjunto com uma tabela de pesquisa e adiciona um pouco mais de rigor e paralelização.

Quando constructencontrar uma lista que forneça as somas da sub-lista e seja menor que o contrário, ela poderá devolvê-la, mas não estamos realmente interessados ​​nela. Seria quase o suficiente apenas retornar ()para indicar sua existência, mas precisamos saber se precisamos contar duas vezes (porque não é um palíndromo e nunca lidaremos com o contrário). Então, colocamos 1 ou 2 como weightna lista de resultados.

A função countreúne essas partes. Para cada conjunto de somas da sub-lista (provenientes de orig) exclusivo entre as listas que contêm apenas se s+1, ele chama value, que chama constructe, via uniqueval, verifica se há apenas um resultado. Nesse caso, esse é o peso que precisamos contar, caso contrário, o conjunto de somas não era exclusivo e zero é retornado. Observe que, devido à preguiça, constructirá parar quando encontrar dois resultados.

A mainfunção lida com IO e o loop de s1 a 9.

Compilando e executando

No debian, isso precisa dos pacotes ghc, libghc-vector-deve libghc-parallel-dev. Salve o programa em um arquivo prog.hse compile-o com ghc -threaded -feager-blackholing -O2 -o prog prog.hs. Execute com ./prog <n> +RTS -Nwhere <n>é o comprimento do array para o qual queremos contar os arrays exclusivos.