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).
