Geral de Vinhos

Eu ia fazer uma postagem individual de cada vinho, mas como foi acumulando ao longo dos últimos meses e eu ia acabar não falando deles em detalhes (até por faltarem descrições mais detalhadas de olfato e paladar), vai um apanhado dos vinhos diferentes que tomei recentemente. Para começar dois Shiraz tomados na sua terra de produção, a Austrália. Esses eu tomei quando fui ao IJCNN com dois colegas, o Luiz Oliveira e o Alessandro Köeirich.

Começamos com o shiraz 2010 Promised Land da Taylors, um vinho do qual não tínhamos ouvido falar nada. Mas arriscamos a compra por causa das medalhas na etiqueta e, surpresa, foi o melhor vinho que tomei na viagem. O defeito desse vinho é que não achei ele fora da Austrália, está fora do catálogo da SAQ. Custou 13 paus Australianos e valeu centavo por centavo o valor pago. Um vinho excelente para se tomar numa boa conversa, mesmo sem acompanhar um prato.

 

O segundo  vinho do dia foi outro shiraz, um 2009 do sudeste australiano, mas de uma vinícola mais conhecida, a Jacob's Creek. Apesar de bem conhecido como o vinho que representa o país, na Austrália esse é vinho de quitanda, custou 12 dólares Australianos e alguns centavos (aqui no Canadá custa na base do 14 dólares, é um preço razoável). A expectativa da reputação e a boa surpresa com o Promised Land fizeram com que o Jacob's Creek decepcionasse. Pelo menos o ano de 2009 não é um vinho tão bom assim para justificar o preço cobrado, já que por um dólar a mais compramos um vinho bem melhor, nem desce tão bem sem nenhum acompanhamento. Talvez com a harmonização ideal dê para revelar mais do seu potencial, mas como apenas um vinho para se tomar num bate papo, com certeza deve muito. Quem sabe um Jacob's Creek produzido em Barossa Valley (aqui no Canadá na base dos 19 dólares) caia melhor, mas esse ficou a dever.

O próximo foi um que o Rafael Menelau trouxe num dia que eu fiz uma pizza aqui em casa, um Chianti 2010 da Antolini Maza (italiano), um vinho DOCG (denominação de origem controlada e garantida, traduzindo para o bom português). Como todo vinho italiano, o preço é convidativo (acho que 15 dólares canadenses) e o sabor é excepcional, combinando perfeitamente com massas a base de tomate. Tomamos a garrafa como se fosse refrigerante, não sobrou nada para contar a história. Não só recomendo como compraria ele.

Para não ficar só nos vinhos tintos, também tomei com meus pais um Vigna di Gabri 2010 da vinícola Donnafugatta, um DOP italiano (denominação de origem protegida, outro sistema de nomenclatura italiano). Custou 19 dólares canadenses, mas o benefício dele é excepcional, ainda se levar em consideração que ele harmoniza com comidas a base de alho (no dia comi um filé de linguado com molho de alho), algo que me dizem que é difícil de se conseguir. Ele é uma mistura predominante de uva chadornnay e parte uva ansonica.

Já que falei de um vinho branco, falo de outro que tomei na sequência, um chadornnay 2011 da Citra Terre de Chieti (outro italiano). Como um bom chadornnay ele harmoniza bem com frutos do mar (comi salmão no dia), como todo italiano o vinho bom não custa muito caro e desce bem. Foram 9,95 dólares por uma garrafa de litro, achar um custo benefício melhor é complicado. Não abriria ele numa ocasião especial, mas para uma refeição quotidiana é um excelente vinho de acompanhamento.

Pra fechar, um shiraz californiano que tomei hoje, um Barefoot (sem indicação de ano de produção, deve ser um 2012, no máximo um 2011). Confesso que esse eu peguei olhando o preço, 9,95 dólares canadenses (só perdeu para um italiano que tomei com meus pais), para acompanhar uma lasanha que eu fiz no almoço. Tomando ele sozinho, não é nem de longe o melhor shiraz que eu tomei (fica abaixo do Jacob's Creek, por exemplo). Porém esse é um excelente vinho de mesa, bateu perfeitamente com o  molho de tomate da lasanha. Tão bom que tomei 2/3 da garrafa só no almoço (o resto foi fechado a vácuo e tomado durante a janta). Ele é um vinho com cheiro e fundo de madeira, como muitos shiraz. Compraria sem medo para fazer outra refeição.

XIV Maratona de Programação da SBC - Problema G

Esse problema eu fiquei "sentado em cima da solução" por um bom tempo (desde o dia da maratona), então vamos, sem mais rodeios, à solução do Problema H - Escultura a Laser. Esse problema tem uma solução quadrática simples, tanto que dos times que resolveram ele em Curitiba, boa parte sofreu com tempo limite excedido. Porém, a solução linear dele não é tão óbvia, tanto que algumas equipes não conseguiram resolvê-lo. A pergunta é simples, dado um histograma de alturas de uma peça recortada com um laser, quantas vezes é preciso ligar o laser para que o corte seja feito?

Vamos estabalecer as regras do jogo. Primeiro, o laser percorre na horizontal a peça, retirando uma camada de material por passada. Toda vez que o laser acaba uma passada ele é desligado, volta à posição inicial e, se for o caso, é ligado novamente. Não tem nenhuma pegadinha de otimização com o laser indo e vindo. Assim, caso exista uma protuberância no caminho, o único jeito de fazê-la é desligando o laser para que o material não seja cortado.

A solução ingênua é simular o funcionamento do laser, removendo as camadas em um for aninhado de altura A e largura C. Ingênua porque ela é quadrática e estoura o tempo de processamento. Os limites são de 10000 para cada dimensão, assim, são 100 milhões de comparações que devem ser realizadas. Como o juiz online é draconiano e tem uma entrada dessas, não precisa ser gênio para entender porque essa solução não serve.



A solução linear, por sua vez, requer um pouco de insight, já que devemos pensar "verticalmente". O fato do laser ir do começo ao final é traiçoeiro neste problema, já que ele nos induz ao uso de uma repetição para percorrer o bloco de material do início ao fim, de cima para baixo. Porém tal fato é irrelevante: Não precisamos saber quantas viagens o laser faz do início ao fim, mas sim quantas vezes ele é ligado no processo. Assim, basta considerar, para cada degrau descendente no objeto, que o laser foi ativado uma vez para cada unidade de altura, como na figura abaixo! Quando subimos, o laser é desligado, então não conta. Idem para quando mantém-se a altura, o laser vem ligado e pronto.



A solução deste problema usando apenas uma repetição simples usa uma variável auxiliar que marca a altura atual do objeto, inicialmente a altura máxima da peça (dado no problema), além de um contador de vezes em que o laser foi ligado (que começa com zero). Com uma repetição do começo ao final do histograma fornecido, observamos a variação da altura do bloco com a altura atual. Se ela permanece a mesma não fazemos nada. Se ela mudar, além de alterarmos a altura atual verificamos a diferença de altura: se subiu, ignoramos, mas se desceu, adicionamos ao contador o módulo da diferença. Ao encerrar a repetição, o contador tem o número de vezes em que o laser foi ligado.

O fonte do programa C que faz a solução linear encontra-se aqui. Agora é começar a implementar o resto que já tem esquematizado, mas nunca tive inspiração de codificar :).

XIV Maratona de Programação da SBC - Problema C

Como hoje estou com paciência e tempo para escrever, vamos à solução do terceiro problema da XIV Maratona de Programação da SBC. O problema escolhido é o Problema C - Troca de Cartas. Este problema não exige nenhuma conta complexa. Ele é até bastante simples nesse quesito. Só que ele trabalha com conjuntos, coisa que os alunos não andam lá tão acostumados a trabalhar. Tanto que quase metade dos competidores de Curitiba não fez. Representar o conjunto de maneira adequada é o primeiro passo para se resolver o problema.

Como representamos o conjunto também influencia a solução, então vou descrever inicialmente a primeira solução que encontrei, bastante simples, e que funcionou nos quesitos de tempo do juiz online. Como isso é o que interessa na maratona, esta solução seria tão boa quanto qualquer outra 20 vezes mais elegante. No final eu discuto como poderia ser uma solução alternativa ao problema. Uma solução mais rápida, usando menos memória, porém bem mais complexa.

Pontos em Comum

Não importa qual método você escolha para resolver este problema, um fato que deve se tomar cuidado é que o interesse é na quantidade máxima de figuras que a Beatriz e a Alice podem trocar. Em nenhum momento menciona-se a quantidade máxima de cartas duplas que podem ser trocadas, que é o que pessoas normais fariam com suas coleções. Quando li a prova no dia da maratona esse foi o ponto que mais me intrigou quando fui ver as entradas exemplo e que possivelmente causou alguma dúvida. Tem que avisar quem fez este problema qual o comportamento padrão de colecionadores, o que seria um problema bem mais interessante do que o apresentado na maratona.

O problema no final consiste em verificar quantas cartas podem ser trocadas. Isto é, determinar quantas cartas a Alice tem que a Beatriz não tem, e vice-versa. O menor dos valores é o número de cartas que podem ser trocadas. Matematicamente, sendo A o conjunto de cartaz da Alice, B o conjunto de cartas da Beatriz, calculamos o conjunto de cartas que a Alice tem e que a Beatriz não tem como:

Dif_Alice = A - (A ∩ B)

Com a mesma lógica, determinamos o conjunto de cartas que a Beatriz tem e que a Alice não tem como:

Dif_Bia = B - (A ∩ B)

Se |Dif_Bia| < |Dif_Alice|, então o resultado é |Dif_Bia|. Caso contrário, o resultado é |Dif_Alice|. Lembrando que |i| é o número de elementos no conjunto i e que não há repetições em i (provavelmente disso saiu a idéia de não considerar figuras repetidas, o que denuncia que foi um matemático que fez o problema).

Primeira Solução

A primeira solução, nem de longe a mais eficiente em velocidade e uso de memória considera um "álbum virtual" a completar. Cada menina possui um vetor booleano com tamanho 100.000, sendo que verdade indica que ela possui a carta (quantas cópias é irrelevante) e falso que ela não possui. Como usamos inteiros na solução e a pilha é bem menor que a memória RAM, os vetores estáticos beatriz e alice são declarados como globais, já que cada um deles usa 400.000 bytes (lembrete: tem jeito melhor sim, discuto isso no segundo método).

Lembre-se que variáveis locais (dentro da main) são criadas na pilha, que tem um tamanho definido pelo linker. No caso do Visual Studio, por exemplo, esses dois vetores dariam stack overflow na pilha padrão. Por segurança, usamos alocação dinâmica, ou variáveis globais. Como sabemos o tamanho máximo dos conjuntos, dane-se, vamos de global mesmo.

Inicialmente, zeramos ambos os vetores com memset, para que nenhuma menina tenha cartas. Em seguida, lemos o número de cartas de cada menina, seguido da leitura das cartas em si. A cada número de carta lida (variável carta), associamos a posição equivalente do vetor (carta-1) o valor verdade (-1). Lembrete 1: as cartas vão de 1 a 100.000. O vetor vai de 0 a 99.999, então tem que subtrair 1. Lembrete 2: falso é zero e diferente de zero é verdade, converta -1 para bonário para entender porque usei ele como verdade.

Para contar quantas cartas cada menina tem que a outra não tem, usamos duas variáveis, m_bia e m_alice, ambas iniciadas com zero a cada caso testado. Como o álbum tem 100.000 figuras para ambas as meninas, basta fazer uma repetição e, para cada posição dos vetores, testamos se ela é verdade para apenas um deles. Se for verdade apenas em beatriz, incrementamos m_bia. Se for verdade apenas em alice, incrementamos m_alice. Se for verdade ou falso em ambos, não fazemos nada. No final do processo, imprimimos o menor valor, que é o número de cartas que podem ser trocadas.

O programa C que faz esta solução do problema está aqui.

Segunda solução

Essa eu não testei, então dou as linhas gerais. Ela só funciona bem (e rápido) porque as "caras estão em ordem não decrescente", jeito complicado de dizer que as cartas estão em ordem crescente, exceto as cartas iguais, que aparecem em sequência.

Um dos dados do problema é que as meninas possuem um limite de 10.000 cartas. Assim, dá pra resolver o problema com um vetor de 10.000 inteiros, lendo nele todas as cartas de acordo como o apresentado na entrada. Em seguida, lemos as posições dos vetores usando dois indexadores, de forma a avançar no vetor quando encontramos cartas iguais, parando o avanço em um deles quando temos uma carta diferente maior que a do segundo. A cada carta diferente encontrada, incrementamos um contador similar ao m_bia e m_alice da solução anterior.

Essa solução é mais chata porque usa dois indexadores, é uma repetição enquanto ambos valores forem menores que 10.000 e a atualização dos indexadores é uma chatice só. Ela é mais eficiente do ponto de vista uso de memória por usar vetores com 1/10 do tamanho, o que é óbvio. Já a repetição é bem mais enxuta porque ela é proporcional ao tamanho da entrada, enquanto no outro caso é sempre 100.000. Mas vale lembrar que a complexidade é bem mais alta e, francamente, por mais que eu ache essa solução computacionalmente mais interessante, não é o caso da maratona. O que vale é resolver em menos tempo e a primeira é bem mais fácil de imaginar e implementar.

Como dito inicialmente, esta solução não foi testada, mas quem a seguir conseguirá resolver o problema também.

XIV Maratona de Programação da SBC - Problema D

Continuando a postagem das soluções da maratona de programação de 2009. Vamos ao Problema D - Subprime, outro problema de contas bem simples, mas com um enunciado um pouco mais complexo. No problema anterior (o B, do alarme, escolhido como primeiro), tínhamos apenas 4 valores para manipular e a lógica era um pouco chata. Neste problema, a lógica é menos chata (já chegamos nela), mas a quantidade de valores é maior e não são diretamente os valores que nos interessam. Isso pode assustar os mais desavisados, ou os pressionados pelo tempo na competição.

No universo do problema proposto, um sistema financeiro saudável é aquele que se resolve por si só. Isto é, se para cada um dos bancos a soma das suas reservas e os seus créditos forem maiores ou iguais às suas dívidas, não será necessária uma intervenção. Neste caso, imprimimos S na saída. Caso contrário, se para ao menos um dos bancos a dívida for maior que a soma das reservas e dos créditos, será necessária a intervenção do governo e devemos imprimir N.

Uma característica que confunde o competidor neste problema é como os dados são apresentados e como eles devem ser analisados. A pergunta que devemos responder é:

reservas+créditos >= dívidas

Porém, o problema não dá isso para cada banco, à exceção das reservas. Sabemos que os bancos tem créditos e que eles tem dívidas, mas as informações tem que ser extraídas das debêntures do sistema financeiro da nLogônia. Esse é o ponto principal do problema, passada essa etapa, o resto é ladeira. Assim, precisamos armazenar três valores para cada banco, reservas, creditos e dividas. Como são até 20 bancos no sistema financeiro, podemos usar vetores alocados estaticamente, em que posições de mesmo índice representam uma informação de um banco específico. Não são vetores que podem estourar a pilha se declarados localmente, mas por costume declarei os vetores como globais.

Para resolver o problema, usamos duas variáveis, nbancos e ndeben, que indicam o número de bancos (o número de posições usadas do vetor) e quantas debêntures devemos ler. Primeiramente, lemos no vetor reservas o quanto cada banco tem no caixa. Isso é simples e direto. Em seguida, devemos determinar indiretamente as o conteúdo dos vetores creditos e dividas. Em geral, aqui eu vejo o maior problema de interpretação para os novatos na competição, porque o próximo dado da entrada são as debêntures emitidas. O que devemos fazer aqui é o seguinte, a cada debênture lida, associamos o valor da debênture ao crédito do banco credor e o mesmo valor à dívida do banco devedor. Tal processo é feito cumulativamente, a cada debênture encontrada, somamos o valor dela ao crédito de um banco e à dívida de outro.

Assim, zeramos todas as posições dos vetores creditos e dividas usando memset (se você programa C e não sabe como isso é feito, tome vergonha e volte pra faculdade). A cada debênture lida, guardamos o montante na variável valor, o banco que cedeu o dinheiro em credor (um número inteiro de 1 a nbancos) e o banco que emprestou em deve (também um valor de 1 a nbancos). Agora, adicionamos valor à posição credor-1 do vetor creditos e à posição deve-1 do vetor dividas. Como os vetores em C começam em 0 e os bancos em 1, devemos subtrair um de credor e de deve para manter o acesso coerente aos vetores. Pergunta inocente do leitor incauto: perdemos os debêntures originais, oh céus, o que fazer? Não precisa, os debêntures não precisam ser guardados em memória ou analisados mais tarde. Precisamos deles apenas para extrair os créditos e dívidas. Feito isto, os debêntures em si são irrelevantes ao problema.

A etapa final faz o seguinte, para cada banco i, de 0 a i<nbancos, testamos se isso é verade:

reservas[i]+créditos[i] >= dívidas[i]

Se para ao menos um dos bancos isso for falso, o sistema bancário é inviável. Se para todos os bancos isso for verdade, o sistema é viável. O problema é que o computador não tem comando mágico para comparar simultaneamente conjuntos condições de tamanho variável. Assim, devemos testar, individualmente, cada um dos nbancos para dizer isso. Para isso, usamos uma variável booleana pode, que diz isso pra gente. Lembre-se: em C, 0 (zero) é falso, qualquer valor diferente de 0 (zero) é verdade. Inicialmente partimos do pressuposto de que o sistema é viável e associamos -1 ao valor de pode (por que -1? Converta pra binário e descubra, oras!). em seguida, para cada banco testamos se ele é inviável:

reservas[i]+créditos[i] < dividas[i]

Caso um dos bancos for inviável, associamos 0 à variável pode e encerramos a repetição. Se todos os bancos forem viáveis, a variável pode continua com -1. Ao encerrar a repetição (normalmente ou pelo break), testamos o valor de pode. Se for verdade, imprimimos S. Caso contrário, imprimimos N.

O programa C que faz o proposto e atende aos requisitos de tempo da maratona de programação está disponível aqui.

XIV Maratona de Programação da SBC - Problema B

Vamos começar pelo problema mais fácil, o Problema B - Alarme Despertador. Primeiro, porque esse problema é o mais fácil de todos? Vamos aos detalhes: dada a hora atual e a hora que o despertador da Daniela vai tocar, temos que dizer quantos minutos ela dorme. Resolve isso com continha básica de multiplicação e soma, além de uma condicional para quando vira a data.

O problema apresenta uma entrada simples: a hora atual e a do despertador, dividida em quatro inteiros. Os dois primeiros para a hora atual (horas e minutos, respectivamente), repetindo a estrutura para a hora do despertador. Como nos interessa o número de minutos dormidos, a solução passa por um passo obrigatório: converter o valor de horas e minutos para o número de minutos corridos do dia (de um total de 1440, isto é, 24*60). Tal conta é feita da seguinte forma:

m_dia=hora*60+minutos

Se calcularmos a diferença desse valor em minutos da hora do despertador com a hora atual, temos os minutos que a Daniela vai conseguir dormir. Porém, temos um caso omisso: e se o despertador for tocar no dia seguinte? Por exemplo, se a Daniela dormir às 22:00 e acordar às 6:00, temos que a hora inicial em minutos é 1320, sendo a hora do despertador é 360. Se fizermos a diferença do final para o início, temos um valor negativo (360-1320=-960).

Aí entra o jogo de cintura do aluno, porquê ao fazer essa diferença, o valor negativo indica o número de minutos entre o horário do despertador e o horário do início do sono, ou seja, o complemento do valor que nós queremos em um dia (faz um círculo que é mais fácil de entender). Oras, se temos o complemento, basta somar a este valor o número de minutos total de um dia (1440) que temos o valor correto:

1440+(360-1320)=1440-960=480

Assim, a lógica tem que considerar o seguinte: se o resultado da conta em minutos for positivo, esse é o valor correto e é só imprimir. Se for negativo, basta somar 1440. E voilà, temos aqui o programa em C que resolve em tempo linear O(n) o prolema do alarme despertador. Q.E.D..