Contest da semana #1

Revision en10, by Sazzon, 2016-11-26 04:29:48

Olá todos!

Esse é o primeiro editorial feito pelos alunos da UECE no Codeforces. Esse contest foi criado como um treino do grupo de estudos da maratona. A seleção das questões do UVa, organização do contest foi feita com muito empenho pelo alissonrgs. Obrigado especial aos que ajudaram a fazer este editorial: wjoao, Lamartine e novamente ao alissonrgs.

Por favor, leiam as questões, tentem fazer, se não conseguirem leiam o editorial. Em último caso vejam o código.

Burguer Time?

Pré-requisitos: Nenhum

O problema é facilmente resolvido se pensarmos que se houver um restaurante e uma farmácia no mesmo local (se houver um caractere 'Z' na string) a distância mínima já vai ser 0. Se não houver, basta iterar por toda a string guardando a posição da última aparição de 'R' e 'D'. Quando uma nova posição aparecer, verificar se a distância entre os 2 atuais é menor do que a anteriormente calculada.

Code

Complexidade : O(n)

*n sendo o valor de L na questão.

Autor : Filipe Herculano Rocha

Anagram

Pré-requisitos: next_permutation

Para resolver essa questão vou usar dois métodos da biblioteca padrão: sort() e next_permutation(). O sort vai fazer a primeira string e o next_permutation vai gerar a próxima permutação da string inicial, na ordem lexicográfica. O problema é que a questão quer em ordem alfabética, então “Ba” virá antes de “aB”, dando resposta errada. Meu truque foi fazer um vetor com valores relativos aos caracteres, de modo que a string AaBbCc… vire o vetor {0,1,2,3,4,5...}. Daí, uso sort e next_permutation nesse vetor. Na hora de imprimir, verifico se o valor é par. Se for, então é maiúsculo. Senão, minúsculo.

Code

Complexidade : O(n!)

*n sendo o tamanho da string.

Autor : Lamartine Cabral

Euclid Problem

Pré-requisito: Algoritmo de Euclides extendido

Esse problema é a aplicação prática do algoritmo de Euclides extendido.

Code

Complexidade : O(log n)

Autor: Filipe Herculano Rocha

Laser Sculpture

Pré-requisitos: Nenhum

Com uma simples passada por todo o vetor com as alturas finais dos blocos, nós conseguimos o resultado. Dado uma altura de um bloco i (0 <= i < C) em um vetor v, se o bloco for o primeiro, deve-se somar ao contador abs(A-v[i]) . Caso i não seja o primeiro, deve-se verificar se ele é menor que o bloco anterior e se for soma-se ao contador abs(v[i]-v[i-1]) . O motivo é que raios são comuns em alturas superiores à direita, porém não são comuns quando a altura é menor.

Code

Complexidade : O(n)

*n sendo o valor de C na questão.

Autor : Filipe Herculano Rocha

Maximum Product

Pré-requisitos: Nenhum

Como o tamanho máximo do vetor é N = 18 (bem pequeno), uma solução possível era testar todos os conjuntos existentes. Com um loop para representar o tamanho do conjunto a ser testado (1 <= i <= N), bastava realizar mais dois loops com os valores do vetor, um de (0 <= j < N) e o outro com o tamanho do conjunto (j <= k < j + i), multiplicava os valores do conjunto e no final testava se o valor era maior.

Code

Complexidade: O(N^3)

Autor: Alisson Soares

Where is the Marble?

Pré-requisitos: Ordenação, busca binária

Para achar a solução da questão, tinha que receber os N elementos, e ordená-los. Após isso receber Q consultas, cada uma delas, tinha que retornar o índice do número e se existir mais de um número igual, pegar o menor índice, no vetor ordenado. Para se ordenar um vetor, pode-se usar a função sort. Ex: int vetor[n]; sort(vetor, vetor+n); Para realizar a busca binária em um vetor ordenado, você pode usar o lower_bound do cpp: Ex: int *p = lower_bound(vetor, vetor+n, valor_buscado); Obs: Detalhe que o lower_bound retorna um ponteiro para a posição do vetor, onde está o elemento encontrato, e caso ele não exista, ele retorna para algum número menor que o número buscado, e o mais próximo dele. Logo ao fazer o lower_bound, é necessário verificar se o valor de *p é igual ao valor da busca. Se for igual é porque foi achado e é necessário achar o indice e para isso é necessário apenas fazer uma operação de ponteiros, diminuindo p por vetor( A posição atual do ponteiro no meio do vetor, menos a posição do ponteiro inicial do vetor ) e o resultado disso é o indice, baseado em 0. Caso não fosse igual, o elemento não teria sido achado.

Complexidade : O(n*log n + q*log n)

Código com busca binária

Autor : Filipe Herculano Rocha

Código com lower_bound

Autor: João Vitor

Zeros and Ones

Pré-requisitos: Prefix Sum

Como a string tinha apenas 1s e 0s era possível aplicar a soma de prefixos, assim usando um vetor, bastava passar uma única vez por toda a string e ir somando o valor da posição da string com a posição anterior do vetor ( sum[ i ] = str[ i ] + sum[ i-1 ] ). Feito isso as consultas ficam O(1), pois para uma consulta de i até j com j > i, basta calcular ( sum[ j ]-sum[ i ] + s[ i ] ), se for igual a diferença dos índices ( j — i + 1 ) é porque todos os valores na string são 1s, e caso for 0 é porque todos os valores na string são 0s.

Esse problema também era possível com força bruta, a cada consulta bastava fazer um ‘for’ verificando se uma posição no vetor era diferente da anterior, caso fosse é porque a sequência não é de mesmos dígitos, caso contrário sim.

Code

Complexidade: O(n+q)

*n sendo o tamanho da string e q sendo a quantidade de queries

Autor: Alisson Soares

Pontentiometers

Pré-requisitos: Bit — Fenwick Tree

Utilização básica da bit. Usa-se o operador de Update em um ponto. e de Query para saber o resultado da soma entre intervalos.

Code

Complexidade: O(n*logn + q*logn)

*q sendo a quantidade de queries na BIT.

Autor: João vitor

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en17 English Sazzon 2016-11-26 18:19:20 53
en16 English Sazzon 2016-11-26 17:51:29 0 (published)
en15 English Sazzon 2016-11-26 16:55:52 13 (saved to drafts)
en14 English Sazzon 2016-11-26 16:54:49 222
en13 English Sazzon 2016-11-26 04:38:38 0 (published)
en12 English Sazzon 2016-11-26 04:37:20 66
en11 English Sazzon 2016-11-26 04:35:43 183
en10 English Sazzon 2016-11-26 04:29:48 5037
en9 English Sazzon 2016-11-26 04:08:17 1026 Tiny change: 'xidade :**\n\n**Auto' -
en8 English Sazzon 2016-11-26 03:55:53 1546 Tiny change: 'ade : O(n!)\n\n*_n' -
en7 English Sazzon 2016-11-26 03:26:24 161
en6 English Sazzon 2016-11-26 03:10:25 1802 Tiny change: ' sum[ j ] - sum[ i ] ' -
en5 English Sazzon 2016-11-26 02:56:47 1398 Tiny change: 'ade :** O(S.size())\n\n[Anag' -
en4 English Sazzon 2016-11-26 02:26:38 117
en3 English Sazzon 2016-11-26 02:19:53 2 Tiny change: ' todos! \nEsse é o' -> ' todos! \n\nEsse é o'
en2 English Sazzon 2016-11-26 02:19:27 18
en1 English Sazzon 2016-11-26 02:18:35 3701 Initial revision (saved to drafts)