Contest da semana #1

Revision en17, by Sazzon, 2016-11-26 18:19:20

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.

Sorry for the lack of translation, we are from Brazil and the group is closed. Don't downvote this post just because you don't understand the language. We are using the platform to communicate internally. Please be nice ! :-)

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, lower_bound

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)