Contest UF(RN, MG) #3 - ICPC Latin America Regional 2012

Como eu e Zailton ja haviamos terminado todos os problemas do contest passado, resolvi criar esse antes com os problemas da final latinoamericana da Maratona de 2012. Os problemas estao novamente no URI, com os IDs do 1282 ao 1285 e tambem do 1297 ao 1302. Seguem abaixo os links para os problemas e, quando terminar a competicao, edito com as solucoes:

• Arranging Heaps (URI1282): ???

• Boxes and Stones (URI1283): ???

• Cellphone Typing (URI1284): ???

• Different Digits (URI1285): ???

• Environment Protection (URI1297): ???

• Fix the Maze (URI1298): ???

• Game of Tiles (URI1299): ???

• Hours and Minutes (URI1300): ???

• Interval Product (URI1301): ???

• Joining Couples (URI1302): ???

Comentem com suas duvidas e, quando terminar o contest, com as solucoes alcancadas!

Contest UF(RN, MG) #2 - Primeira fase da Maratona 2013

Outra competicao criada para o treinamento da UFRN e UFMG. Dessa vez foram usados os problemas do URI do ID 1467 ao 1476, correspondentes aos problemas da primeira fase da Maratona de Programacao 2013. Segue abaixo o link para os problemas e, quando terminar a competicao, edito com as solucoes:

• Zero or One (URI1467): Apenas testa se A é diferente de B e de C, ou se B é diferente de A e de C, ou se C é diferente de A e de B. Caso algum seja verdade, retorna o valor que é diferente. Se nenhum desses casos for verdade, retorna "*".

• Balloon (URI1468): Para montar o line sweep, irao existir 3 eventos distintos, os quais serao ordenados pelo X e o desempate sera feito pelo tipo do evento. 1o: comeca um segmento nessa posicao; 2o: é feita uma consulta de balao nessa posicao; 3o: termina um segmento nessa posicao. Assume-se, ainda, que, para todo o segmento, p1.x < p2.x. Ao chegar em um evento do tipo 1, insere-se o segmento em um set e, caso o p1.y > p2.y, preenche como nextSeg o indice do segmento logo acima no set (esse set estara ordenado dos segmentos mais abaixo para os mais acima). Ao chegar em um evento do tipo 2, preenche a posicao firstSeg com o indice do primeiro segmento do set. Ao chegar em um evento do tipo 3, caso p1.y < p2.y, preenche o nextSeg com o valor do segmento logo acima e retira o segmento do set. Logo apos, faz uma PD que, dado o segmento inicial, retorna qual o segmento final (ou se escapou) e o X final. A resposta da query sera a PD para o firstSeg do X dado.

• Boss (URI1469): Monta o grafo ao contrario do que é indicado, ou seja, insira uma aresta do vertice do empregado para o vertice do chefe. Realiza-se uma busca no grafo para montar uma matriz de antecedencia, em que a posicao (i, j) indica que o vertice j é antecessor de i no grafo. Como os limites sao baixos, para cada operacao de troca entre vertices A e B realiza-se uma troca das posicoes (i, A) pelas (i, B) e das (A, i) pelas (B, i), tratando de forma especial apenas no caso de A ser antecessor de B ou vice-versa. Para a consulta, precisa-se apenas iterar o vetor de idades e pegar o minimo das posicoes em que (A, i) sejam verdadeiras.

• Folding Machine (URI1470): Como os limites sao muito baixos, entao da para realizar um backtracking simulando todas as possiveis dobraduras a serem realizadas na fita. O backtracking pode receber os indices de inicio e fim do intervalo e fazer a operacao de dobradura em cada posicao possivel, ate que o intervalo chegue ao tamanho M. Quando chegar ao tamanho M, pode-se testar se ele ou o inverso sao iguais ao output dado. Como corte no backtracking foi preciso apenas calcular qual era o maximo do output e qual o maximo do vetor atual, caso o maximo do vetor atual seja maior do que o do output, entao ja pode retornar falso, porque os valores so irao aumentar.

• Dangerous Dive (URI1471): Cria um vetor com N posicoes e define todas como false. Para cada valor X lido, coloca a X-esima posicao para verdadeiro. Ao final, itera sobre o vetor de 1 ate N e imprime aqueles que estao como false. Caso N == R, imprime "*".

• Triangles (URI1472): Insira em um set a posicao absoluta de cada ponto em relacao ao inicio do circulo (va acumulando um total e somando pontos[i] a cada leitura). Ao final, defina dif = total / 3 e para cada elemento X do set, procure se (X + dif) % 3 e (X + 2*dif) % 3 estao tambem no set. Caso positivo, some na resposta final. O resultado deve ser ainda dividido por 3.

• Lines of Containers (URI1473): Inicialmente, para cada linha I descubra qual a linha que esta na sua posicao, ou seja, caso existam 3 colunas e na linha 2 estejam os elementos (em qualquer ordem) 1 2 3, marque lines[2] = 1, pois os elementos 1, 2 e 3 deveriam estar na linha 1. Faca o mesmo com as colunas. Ao mesmo tempo, verifique se nao ha nenhuma incompatilidade, como uma linha com 1, 2 e 7 no exemplo anterior. Ao final, apenas percorra os vetores lines e cols e faca a troca com a posicao em que a linha certa esta.

• Buses (URI1474): Pode-se modelar a funcao de contagem de possibilidades para uma recursao do tipo f(n) = k * f(n-1) + l * f(n-2), em que n ja é o tamanho da linha de onibus e micro-onibus dividido por 5. Uma das formas de computar eficientemente uma funcao recursiva, ja que o expoente por chegar a 10^5 é modela-la como uma exponenciacao de matrizes e faze-la com exponenciacao rapida. Pode-se pensar em um vetor que armazena [ f(n) f(n-1) ] e ao multiplica-lo pela matriz com linhas [ K 1 ] e [ L 0 ], ele se torna [ f(n+1) f(n) ].

• Patches (URI1475): Crie uma PD simples, que para cada indice idx retorna o menor tamanho de remendos a serem utilizados. Como pre-processamento, calcule para cada buraco, qual seria o proximo buraco a ser processado no caso de usar o remendo 1 e no caso de usar o 2. Alem disso, como trata-se de algo circular, é preciso zerar todos os dados e recalcula-los considerando que agora o ultimo buraco sera o inicial (alguem sabe justificar/provar porque sao necessarios apenas o buraco 1 e n-1 como iniciais?).

• Trucks (URI1476): O problema quer descobrir qual é a menor aresta do caminho entre cada 2 vertices. Para isso, cria-se a arvore geradora maxima por conjuntos disjuntos (sem compressao de caminhos), armazenando para cada vertice qual o peso da aresta que o liga ao seu pai. Alem disso, as arestas irao ser processadas em ordem decrescente de peso. Para cada consulta, descobre-se o LCA entre os vertices e a resposta sera o menor peso existente no caminho.

Comentem com suas duvidas e, quando terminar o contest, com as solucoes alcancadas!

Contest UF(RN, MG) #1 - Primeira Fase da Maratona 2012

Esses problemas estao sendo usados em conjunto para o treinamento da UFRN e da UFMG, e toda semana sera criado um contest novo e um novo topico para comentarem suas duvidas e sugestoes.

Os problemas foram todos retirados do URI Online Judge, do ID 1222 ao 1233, e correspondem aos problemas utilizados na primeira fase da Maratona de Programacao 2012. Segue abaixo uma breve descricao da solucao de cada problema:

• Short Story Competition (URI1222): [ Iniciante / Guloso ] Seja current o numero atual de caracteres na linha. Para cada word[i], se (current + word[i].size() + 1) for maior do que o maximo de caracteres por linha, voce incrementa lines, o numero de linhas atual, e current se torna igual a word[i].size(). Se for menor ou igual, voce somente soma (word[i].size() + 1) ao numero atual de caracteres. Ao final, o numero de paginas pode ser computado como (lines / L) + (lines % L ? 1 : 0).

• Toboggan of Marbles (URI1223): [ Intermediario / Geometria ] Para um problema de geometria, pode ser considerado ate facil. Voce precisa apenas computar as distancias de cada aleta para a haste oposta e tambem do ponto final de cada aleta para a proxima aleta. O resultado é o mínimo dessas distancias.

• Cards (URI1224): [ Intermediario / PD ] Crie uma PD com estado [ size ][ i ], em que size é o tamanho de um intervalo de cartas e i é o indice do elemento inicial para o intervalo. Para cada estado, voce simula dois rounds, ou seja, se voce pegar o i-esimo elemento, entao seu oponente tentara minimizar entre os estados [size-2][i+1] e [size-2][i+2]. Caso contrario, pegando o j-esimo elemento (j = i + size - 1), seu inimigo ira minimizar entre [size-2][i] e [size-2][i+1]. Para o URI, é preciso fazer uma PD bottom-up e utilizando apenas 2 linhas da matriz por vez.

• Perfect Choir (URI1225): [ Iniciante / Ad Hoc ] Calcule a soma de todas as notas. A reposta sera -1 somente se a soma nao for divisivel por N. Se for divisivel, entao defina uma variavel X e, para cada nota[i], some em X a distancia da nota[i] para a media de todas as notas. A resposta final sera (x / 2) + 1, porque para cada rodada é possivel diminuir a diferenca em 2.

• Space Elevator (URI1226): [ Intermediario / PD + Busca Binaria ] Crie uma PD com 2 parametros, em que o primeiro é a quantidade de digitos e o segundo é um bool dizendo se anteriormente teve um numero 1 ou não. Essa PD ira armazenar quantos numeros validos existem da forma xxx...xxx ou 1xx...xxx Depois disso, crie uma funcao que recebe um numero N e diga quantos numeros validos (sem 13 nem 4) existem entre 1 e N. Para cada digito digit[i] de N, itere sobre cada X entre 0 e digit[i],  pulando o 4 e,  em caso do digito anterior ter sido 1, o 3, e compute a quantidade de numeros validos pd[ total_digitos(n) - i - 1 ][ X == 1 ]. Agora voce sabe calcular quantos numeros validos existem entre 1 e N, porem quer saber qual o numero N que receber o andar K, i. e., para qual N, temos que f(N) = K. Isso pode ser resolvido por uma busca binaria no valor de N.

• Midnight Cowboy (URI1227): [ Intermediario / Grafos ] Como as arestas do grafo da cidade sao descritas como probabilidades, voce pode modelar o problema com uma cadeia de Markov. O vetor de probabilidades iniciais é 1.0 no local de A e 0.0 em todos os outros. Ainda, se o viajante estiver na cidade B ou C, havera apenas uma aresta de loop com probabilidade 1.0. Eleve ao quadrado a matriz de probabilidades ate que ela nao mude mais, o resultado estara em matrix[ a ][ b ].

• Start Grid (URI1228): [ Iniciante / Ad Hoc ] Como o numero de competidores é bem pequeno, é possivel resolver o problema com uma solucao O(N^2) para o problema de contar flips entre dois vetores. Voce pode manter a posicao inicial do grid (seja o vetor starts) e para a posicao final voce mantem em um vetor qual a posicao do competidor de numero K (como um indice invertido, chamado de posEnd). Entao, voce itera sobre os pares de posicoes iniciais (i, j) tal que i < j, e se posEnd[ starts[i] ] > posEnd[ starts[j] ], voce incrementa o valor da resposta.

• Combating Cancer (URI1229): [ Avancado / Grafos ] Testa se as duas arvores sao isomorfas. Primeiramente, calcula-se o(s) centro(s) das arvores, pois sera feito um teste de isomorfismo para arvores enraizadas em cada um dos centros. Para testar isomorfismo de arvores enraizadas é bem mais facil, pois voce tem uma definicao de pais e filhos, entao pode-se calcular um hash para o pai dependendo dos hashes ordenados dos filhos (use um funcao de hash razoavelmente boa e o problema passa).

• Integral (URI1230): [ Intermediario / Matematica ] Para o intervalo que existe entre dois valores pre-conhecidos s[i] e s[i+1], os valores de cada parte inteira do intervalo devera estar obrigatoriamente entre s[i] e s[i+1]. Dessa forma, primeiramente coloca-se todos os valores para o minimo possivel e tambem para o maximo e verifica se Y esta entre as integrais calculadas. Se nao for possivel, voce tem o caso em que a resposta é N. No caso positivo, coloca-se todos os valores para o maximo e vai analisando cada intervalo entre s[i] e s[i+1]. Se a integral atual estiver igual a Y, entao nao faz nada. Se a diminuicao por colocar todos os valores agora para o minimo ainda nao for suficiente para chegar a Y, entao coloca-se tudo para o minimo e vai para o proximo intervalo. Se a diminuicao fizer a integral ficar menor do que Y, entao esse é o ultimo intervalo a ser alterado e voce consegue os valores dos elementos dependendo se ele sera crescente ou decrescente.

• Words (URI1231): [ Intermediario / Strings ] Simule um automato sobre os dicionarios com uma BFS. O estado da BFS sera a diferenca entre as palavras sendo criadas por cada um dos dicionarios, bem como indicando qual o dicionario esta com a maior palavra. Para cada estado que esta sendo processado, voce ira tentar usar cada uma das palavras do dicionario que estiver com a menor e adicionar , e.g., se a diferenca entre as palavras é "aab" e o dicionario 1 esta com a menor palavra, eu posso usar a palavra "aa" dele e tornar a diferenca apenas "b", ou ainda usar "aabba" e a diferenca passar para "ba", sendo que a menor palavra agora é do dicionario 2.

• Rubik Cycle (URI1232): [ Intermediario / Matematica ] A pior parte do problema é implementar as operacoes do cubo magico. Para cada celula do cubo, realize as operacoes descritas e guarde em um map qual é a posicao resultante. Entao, para cada celula voce ira iterar pelos rounds ate que voce volte a posicao inicial, calculando o numero de rounds que demora. O resultado sera o MMC entre o numero de rounds de cada celula.

• Star (URI1233): [ Intermediario / Matematica ] É possivel ver que se um numero K tem algum fator comum com N, entao ele ira voltar para a posicao inicial em alguma rodada. Alem disso, para cada coprimo X de N, as estrelas formadas por X e N - X sao iguais. Dessa forma, o resultado final é phi(N) / 2.

Comentem as solucoes que eu apresentei, tirem duvidas e tambem postem suas solucoes (se diferentes das ja apresentadas).

Etapa 3 - Resultados e Dicas

Olá pessoal,

Nesse sábado 22/06 foi realizada a terceira e última etapa da seletiva UFRN para a Maratona de Programação. Infelizmente, não tivemos mais competidores entrando no ranking, fazendo com que terminássemos com 11 pessoas classificadas para as equipes da UFRN (uma das equipes terá o direito de escolher o terceiro competidor). Essa foi a competição em que mais problemas foram resolvidos, tendo Álvaro novamente em primeiro, com 6 problemas; em seguida, Charles, Argus e Lucas Tomé com 5 problemas cada.

Esses problemas acabaram por ser escolhidos meio nas pressas, resultando em uma competição um pouco mais fácil do que as demais, todavia ainda teve problemas complexos. Os arquivos de entrada/saída, as soluções para cada problema e a prova em PDF podem ser baixados aqui. Ainda, para os que preferirem testar usando juízes online, seguem abaixo os links para os problemas originais, bem como dicas de como resolvê-los.

A - Figuras Recursivas: calcular a forma para encontrar o lado do quadrado inscrito em um círculo e o raio de um círculo inscrito em um quadrado. Depois iterar sobre a quantidade de círculos.
B - Pontos de Amizade: questão simples de grafos, apenas sendo necessário iterar sobre cada par de vértices e verificar a condição apresentada no enunciado.
C - Soma de Raízes Ímpares: talvez o problema mais difícil da prova, considerando que os limites são bem altos e seria preciso encontrar uma fórmula para a soma.
D - Divisão da Pizza: como os limites são baixos, podem ser tentadas todas as direções possíveis para vetores entre pares de vértices.
E - Composição de Jingles: para evitar a utilização de ponto flutuante, multiplique cada valor por 64 e teste se a soma é igual a 64. Apesar de que sem esse truque a questão também passa.
F - Irmãos: simulação direta do que é descrito no problema. É necessário somente tomar cuidado com os casos de borda.
G - Par ou Ímpar: armazene apenas a quantidade de pares e ímpares para cada lado. Lembre das funções min e max, pois elas podem ser úteis.
H - Feynman: faça os cálculos para os exemplos menores e facilmente virá um padrão na resposta.

Etapa 2 - Resultados e Dicas

Olá pessoal,

Nessa sexta 21/06 ocorreu a segunda etapa da seletiva UFRN para a Maratona de Programação. Tivemos mais um competidor entrando no ranking e, assim, temos 11 pessoas para as equipes da UFRN. Ao final da competição, tivemos Argus em primeiro lugar, porém ele não está competindo pelas vagas. Contando apenas os concorrentes, temos Álvaro em primeiro, com 3 questões resolvidas e todos os demais (8 pessoas) com 2 questões resolvidas.

Novamente, os problemas foram escolhidas dentre diversas competições e, para aqueles que desejarem, os arquivos de entrada/saída, bem como as soluções para cada um deles e o PDF da prova podem ser baixados aqui (o arquivo de solução do Oráculo de Alexandria não está presente). Para aqueles que querem testar diretamente em um juiz online, veja os links abaixo, juntamente com uma dica sobre cada problema.

A - Arcade Manao: busca em largura em que cada estado é a célula em que se encontra e o tamanho da escada necessário para chegar até ela.
B - Cerca Engraçada: testa todas as possíveis substrings e verifica se é uma cerca válida.
C - Mova a Água: busca em largura em que cada estado é a situação atual dos jarros.
D - Triângulo Minimal: como existem poucas formas de dividir, é fácil chegar a uma fórmula fechada para o resultado.
E - WiFi: busca binária na resposta.
F - Oráculo de Alexandria: questão bem direta, precisando apenas calcular a fórmula da mesma maneira que é apresentada na questão.
G - Validador de Números de Nascimento: lembrar de verificar os anos bissextos e a quantidade de dias em cada mês.
H - Galou está de volta!: busca no grafo, marcando quem já foi visitado no sentido horário, anti-horário e nos dois.

Etapa 1 - Resultados e Dicas

Olá pessoal,

Nesse sábado dia 15/06 ocorreu a primeira etapa da Seletiva UFRN para a Maratona de Programação. Infelizmente, dos 29 inscritos para a seletiva apenas 12 compareceram, além de um competidor que não está concorrendo às vagas, porém a competição foi bem aproveitada por aqueles que lá estiveram. Como resultado final, tivemos Charles em primeiro lugar com 3 problemas resolvidos, Lucas Tomé em segundo com 2 problemas resolvidos e outros 8 com apenas 1 problema resolvido, diferenciando-se apenas pela penalidade de tempo (considerando que Argus não está concorrendo as vagas).
 

 

Os problemas da competição foram escolhidos dentre diversas competições passadas ao redor do mundo, tanto de fases regionais do ICPC quanto de outras competições como TopCoder e Google Code Jam. Os arquivos de entrada e saída de cada problema, bem como a nossa solução para eles podem ser baixados aqui (o código do Roleta Turca não está presente). Para aqueles que querem testar diretamente em juiz online, veja os links abaixo, bem como uma dica simples sobre cada problema.

A - Emoticons: pense em cada emoticon como um intervalo, então o que é preciso descobrir é o menor número de pontos que irão cobrir todos os intervalos.

B - Fraude Eleitoral: com os números dados, veja qual a menor e a maior soma que pode ter acontecido antes do arredondamento.

C - Recomposição de Pontuação Simples: podem ser testadas todas as permutações de pontuações possíveis.

D - Reorganização do Reino: árvore geradora mínima com os pesos das arestas existentes como negativos.

E - Roleta Turca: Programação Dinâmic.

F - Saudações Seguras: números de catalão (também pode ser feito recursivamente).

G - Tesouro: PD com bitmask, em que o estado é o bitmask dos baús já abertos.

H - TriFibonacci: ad hoc, porém precisa ser tomado cuidado com o fato de que o número a ser resposto tem que ser positivo.

Seletiva UFRN - Horários Definidos

Olá pessoal,

Finalmente foram definidas as datas para as provas da Seletiva UFRN 2013. A primeira etapa ocorrerá no sábado dia 15/06, a segunda irá ocorrer na sexta-feira 21/06 e a terceira acontecerá no sábado dia 22/06, todas as etapas acontecendo no período da tarde, das 14h às 17h, na sala 3E1.

Para mais informações, consulte o blog http://maratonaufrn.blogspot.com.br/.

Enquanto isso, vá treinando nos juízes online disponíveis, como SPOJ Brasil, URI Online Judge ou ainda no Top Coder, resolvendo problemas no Practice Room e lendo os tutoriais disponíveis.