Click here to edit contents of this page.
Click here to toggle editing of individual sections of the page (if possible). Watch headings for an "edit" link when available.
Append content without editing the whole page source.
Check out how this page has evolved in the past.
If you want to discuss contents of this page - this is the easiest way to do it.
View and manage file attachments for this page.
A few useful tools to manage this Site.
See pages that link to and include this page.
Change the name (also URL address, possibly the category) of the page.
View wiki source for this page without editing.
View/set parent page (used for creating breadcrumbs and structured layout).
Notify administrators if there is objectionable content in this page.
Something does not work as expected? Find out what you can do.
General Wikidot.com documentation and help section.
Wikidot.com Terms of Service - what you can, what you should not etc.
Wikidot.com Privacy Policy.
Discuta o problema
estou tomando TLE nele com a implementacao mais simples de pra cada configuracao ver quem ela gera e (ou entao por quem ela pode ser gerada) olhando para cada um dos $$n \cdot m$$ os 8 vizinhos e decidir o que fara (se nascera, ou morrera ou nao alterara)
nem uso matrizes, soh bits…
Tome cuidado mais com muitas operações de módulo, elas estavam fazendo estourar meu tempo.
Só um detalhe, não são 8 vizinhos, mas 4.
Não, são 8 mesmo.
Então o exemplo do enunciado está errado, não?
Agora lendo o enunciado com atenção eu vi que são 8 vizinhos mesmo. Está escrito explicitamente no enunciado.
Também acabo de entender o exemplo, para variar eu tinha entendido errado aquele negócio de contar uma célula mais de uma vez.
A aposentadoria forçada acabou comigo, estou enferrujado até para entender enunciados.
Eu fiz um backtrack convencional em cima da matriz mesmo.
Conto quantos vizinhos tem cada célula e não usei módulo, só ifs igual o tiago.
Eu tava com o mesmo problema durante o treino, também cheguei a implementar ele sem nenhuma matriz e tomei TLE.
Eu resolvi e diminui o meu tempo só o suficiente pra passar aplicando essa otimização: Em vez de olhar para cada quadrado e contar quantos vizinhos vivos eu tenho, eu olho para cada celula viva, e adiciono 1 em todos os seus vizinhos em uma matriz.
Outra possibilidade é esquecer completamente os bits, e só mexer com matrizes. O pessoal que passou ele com menores tempos ontem fez assim. Eu não entendo porque, mas…
Eu fiz com matriz, sem módulo (fiz ifs) e passou de primeira (no entanto, segundo o GTreino, foi o maior tempo :D)
Eu fiz com matrizes e módulo. Passou até que bem.
Eu não sei ao certo, porque essas coisas tem que medir, mas acho que só compensa usar bitsets quando os dados não cabem no cache, porque se couberem os erros de cache não são comuns e assim não compensa fazer shifts e ands para evitá-los divindo a memória usada por 8.
E sobre o módulo, eu não sei se ajuda, mas meus tipos eram de 8 bits, e assim creio que o módulo seja mais rápido, mas realmente não sei.
Eu também tive problem com TLE. Acabei passando como uma otimização que usava máscara de bits e precomputava as mascaras que satisfaziam cada posição individualmente. Aí eu consiguia podar muitas configurações rapidamente. Descobri agora que foi devido ao try/catch que eu estava usando para sair do loop que validava uma configuração. Eu tirei isso e coloquei uma variável com um break que fazia o equivalente e ficou bem mais rápido. Moral da história, não use try/catch =P. Alguém usou try/catch tbm?
Eu nem sabia que C++ tinha try/catch :)
Tb to sofrendo com o TLE.
Quanto tempo mais ou menos o programa de vcs que passaram leva para essa entrada aqui???
2 3
2
0 0
0 1
3 3
4
0 0
0 1
0 2
1 1
3 3
5
0 0
1 0
1 2
2 1
2 2
4 4
3
0 3
2 2
1 3
4 4
0
0 0
abraços.
natan@bogardan:~/maratona/pku/codes/solved/efil$ time a.out < in
Case 1: 3 possible ancestors.
Case 2: 1 possible ancestors.
Case 3: Garden of Eden.
Case 4: 4 possible ancestors.
Case 5: 9628 possible ancestors.
real 0m0.198s
user 0m0.184s
sys 0m0.000s
Valeu pessoal!
Eu tinha interpretado "ancestrais" de forma diferente do esperado.
Pensava que podia ser em vários passos.
No fim o problema era muito mais fácil, apaguei uns tecos de código e passou hehe.
Obrigado pela ajuda!
bom, ifs sao mais rapidos que modulo.
eu estava fazendo com modulo e só de substituir por ifs, tomei AC.