Existe uma solução mais rápida para o problema da Grande Muralha do Google Code Jam

16

Considere a seguinte pergunta da rodada 1C do Google Code Jam :

A Grande Muralha da China começa como uma linha infinita, onde a altura em todos os locais é .0 0

Algum número de tribos , atacará a parede a parede de acordo com os seguintes parâmetros - um dia de início, , uma força de partida , uma coordenada oeste de início, e uma coordenada leste de início, . Este primeiro ataque ocorre no dia , no intervalo , a força . Se houver qualquer parte da Grande Muralha dentro de com altura , o ataque será bem-sucedido e, no final do dia, a parede será construída de modo que qualquer segmento dela dentro de de altura estaria então em alturaN 1,000 D S W E D [ W , E ] S [ W , E ] < S [ W , E ] < S SNN1000DSWED[W,E]S[W,E]<S[W,E]<SS (ou maior, se algum outro ataque naquele dia atingir o mesmo segmento com força )S>S

Cada tribo executará até ataques antes de recuar e cada ataque será determinado iterativamente do anterior. Toda tribo tem alguns , e que determinam sua sequência de ataques: eles esperarão dia entre os ataques, eles moverão seu alcance de ataque unidades para cada ataque (negativo = oeste, positivo = leste), embora o tamanho do alcance permaneça o mesmo e sua força também aumente / diminua em um valor constante após cada ataque.δ D δ X δ S δ D1 δ X1000δDδXδSδD1δX

O objetivo do problema é, dada uma descrição completa das tribos atacantes, determinar quantos de seus ataques serão bem-sucedidos.

Consegui codificar uma solução que funciona, executando em cerca de 20 segundos: acredito que a solução que implementei leva o tempo , em que o número total de ataques em uma simulação (máximo de ) e o número total de pontos de borda exclusivos nos intervalos de ataque (máximo de ).A = 1000000 X = 2000000O(AlogUMA+(UMA+X)registroX)UMA=1000000X=2000000

Em um nível alto, minha solução:

  • Lê todas as informações da Tribo
  • Calcula todas as coordenadas exclusivas para os intervalos de ataque -O ( A )XO(UMA)
  • Representa a parede como uma árvore binária atualizada preguiçosamente sobre os intervalos que rastreiam os valores mínimos de altura. Uma folha é a extensão de duas coordenadas sem nada no meio e todos os nós pais representam o intervalo contínuo coberto por seus filhos. -X O ( X log X )XXO(XregistroX)
  • Gera todos os ataques que toda tribo executará e os classifica por dia -O(UMAregistroUMA)
  • Para cada ataque, veja se seria bem-sucedido ( tempo de consulta). Quando o dia mudar, percorra todos os ataques bem-sucedidos não processados ​​e atualize o mural de acordo ( hora de atualização para cada ataque). -log X O ( A log X )registroXregistroXO(UMAregistroX)

Minha pergunta é a seguinte: Existe uma maneira de fazer melhor que ? Talvez haja alguma maneira estratégica de tirar proveito da natureza linear dos sucessivos ataques do Tribes? 20 segundos parecem muito longos para uma solução pretendida (embora o Java possa ser o culpado por isso).O(UMAregistroUMA+(UMA+X)registroX)

torquestomp
fonte
3
Por favor, não feche. É uma pergunta válida. Uma resposta seria uma prova de limite inferior, mostrando que não podemos fazer melhor, se é realmente o melhor que podemos fazer. Por exemplo, acho que podemos usar o Problema de Distinção de Elemento aqui, mas ainda não encontramos tempo para pensar nisso.
Aryabhata 16/05
Eu vou mantê-lo aberto então :)
torquestomp

Respostas:

2

O espaço óbvio para melhorias é este passo:

Gera todos os ataques que toda tribo executará e os classifica por dia -O(UMAregistroUMA)

Sabemos que as tribos atacarão a partir de um dia específico, em intervalos regulares. Isso significa que devemos essencialmente mesclar várias listas pré-classificadas. Além disso, a declaração do problema nos diz que nunca haverá mais de 1.000 tribos (ou seja, 1.000 listas para mesclar); um pequeno número comparado aos 1.000.000 de ataques máximos! Dependendo dos tempos relativos da sua implementação, alternar isso pode reduzir o tempo de processamento pela metade.

Isso é realmente tudo o que posso sugerir para otimizar a complexidade teórica, mas não tenho provas de que seria ótimo após essa alteração.


Eu mesmo experimentei o quebra-cabeça, mas usei uma representação muito mais burra da parede: uma árvore de pesquisa binária (C ++, std::mappara ser mais preciso) armazenando locais onde a altura da parede muda. Com isso, fui capaz de adicionar e remover nós, conforme necessário (ou seja, se uma seção complicada estivesse sujeita a um ataque grande e esmagador, ou vários ataques da mesma força tocados, o número de nós reduziria significativamente). Isso resolveu a grande entrada em 3,9 segundos (no meu laptop de desenvolvimento para especificações médias). Eu suspeito que existem várias razões para a melhoria:

  • Como você apontou, o boxe e o unboxing podem ficar caros, mas os contêineres baseados em modelo do C ++ evitam isso completamente.
  • Embora a representação de parede que usei seja teoricamente pior, na grande maioria dos casos, a capacidade de reduzir dinamicamente o número de nós tornou-a super-rápida (a maioria dos casos de teste atingiu o máximo de menos de 1k nós e todos, exceto 2, menos de 10k) . De fato, o único caso que levou algum tempo significativo foi o nº 7, que parece estar testando vários intervalos sem interseção.
  • Não usei nenhum pré-processamento (os estágios são determinados acompanhando quando cada tribo atacará em seguida e procurando a menor articulação a cada turno). Novamente, isso é teoricamente pior, mas para a maioria dos casos, suspeito que a sobrecarga mais baixa signifique que foi mais rápido (testarei isso e retornarei a você). Atualização : eu adicionei uma fila de prioridade para ataques, semelhante ao método descrito acima (embora, em vez de criar a grande matriz, eu a tenha calculado em tempo real), vi o tempo diminuir para 3,0 segundos para a entrada grande.

Resumindo, embora eu ache que seu algoritmo seja quase ideal no caso geral, existem várias maneiras de acelerar esse processo para entradas típicas .

Dave
fonte
1

O seguinte foi removido da pergunta, pois é uma resposta.

Examinar outras discussões e soluções bem-sucedidas parece indicar que a solução que descrevi é praticamente o algoritmo esperado. A desaceleração da minha solução possivelmente se deve apenas ao uso preguiçoso do boxe automático e de uma estrutura em árvore baseada em ponteiro, em vez de em uma matriz - então eu suspeito que, se existe uma solução, provavelmente não é um todo muito melhor do que o que está aqui.

A solução pode ser encontrada aqui . É muito parecido com o que eu publiquei aqui; então, estou muito mais inclinado a acreditar que não existe uma solução mais eficiente.

Juho
fonte