- 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!
Nenhum comentário:
Postar um comentário