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

XIV Maratona de Programação da SBC

Foi no sábado passado, mas segue aqui, além dos próximos posts, comentários e soluções dos problemas da XIV Maratona de Programação da SBC. Para quem ainda não conhece a competição, é só visitar o site aqui. Um resumo geral: ganha quem resolve mais problemas no computador, em menos tempo. Note, quem resolve mais problemas, não quem fica de discurso vazio das 1001 técnicas que diz saber dominar.

É a segunda vez que eu me envolvo diretamente, tanto no treinamento de alunos como no julgamento das soluções. Esse ano a regional de Curitiba teve 12 times concorrendo por duas vagas na final brasileira, um número legal. Nessa vez a sede foi na PUCPR, com o Emerson Paraíso e o Vidal Martins tocando o barco com a ajuda do Lucas Galete e do Jonathan "não sei o sobrenome" :).

A prova desse ano teve um ponto marcante na minha opinião: a divisão da prova em dois tipos de problemas, fáceis e bastante difíceis. Ano passado teve um equilíbrio melhor, com problemas de nível intermediário. Assim, o resultado da regional de Curitiba foi praticamente uma prova de velocidade, ganhando a maratona a equipe que conseguiu resolver 4 problemas em menos tempos. De velocidade porque metade das equipes fez os mesmos quatro problemas, a barreira foi chegar no quinto. Os outros 4 ninguém conseguiu fazer, o que mostra algumas deficiências dos alunos em relação aos conhecimentos necessários, além de uma escolha de problemas não tão bem acertada como no ano anterior.

Ano que vem espero conseguir levar alguns alunos do setor de educação tecnológica da UFPR, já que esse ano ficou em cima da hora com a minha posse tardia. Nesse ano, fica os parabéns para os alunos da UTFPR (equipe sudo make a sandwich, leitores de xkcd) e da Ciência da Computação da UFPR (equipe untitled).

Para quem quiser ver fotos do evento, deixei algumas no ar nesse site. Como estou resolvendo os problemas da maratona, vou colocar nos próximos posts as soluções. Tanto as que eu já tenho, como as que eu resolver no caminho. Claro, na ordem correta de solução da prova: do mais fácil para o mais difícil :).

Padronização, por favor!

Kuki, Librix, Satux, Kurumim, Fedora, Ubuntu, Debian, Yellow Dog, Gentoo, Mandriva, etc. O que todos esses nomes tem em comum? São distribuições Linux. Algumas delas, as Librix e Satux, você encontra ao ligar alguns notebooks à venda no mercado Brasileiro. O problema? É tudo Linux, mas não é tudo a mesma coisa.

Vamos passar ao largo da discussão da liberdade de se montar a sua distribuição, com a sua cara e adaptada as suas necessidades, porque isso é bom de se discutir de maneira acadêmica, mas no mundo real (e no mercado) isso não diz muita coisa. O fato é que o Linux não é um padrão de fato e isso influencia direto na sua adoção.

Mas, afinal, porque devemos ter um padrão de fato? Pelo mesmo motivo que devemos ter bocais de lâmpada e lâmpadas rosqueáveis padronizadas. Facilita a vida de todo mundo, fabricante, comerciante e usuário. Nos velhos tempos não havia padrão, cada fabricante criava o seu e o resultado era uma catástrofe, fabricante tinha que ganhar o cliente na obra, o comerciante tinha que diversificar muito o estoque para ter uma venda mínima e, enfim, o cliente, podia ficar na mão de um fabricante que podia desaparecer por um baixo volume de vendas. Ou seja, não era bom pra ninguém ter a liberdade de se desenvolver o seu próprio padrão proprietário, adaptado para certas situações e métodos de fabricação. O mercado deseja um padrão que, por mais que não seja perfeito, resolva a vida da maioria sem maiores sobressaltos.

Eu, como usuário, vejo o Linux hoje da mesma maneira: cada distribuição segue o seu padrão, adaptadas para certas necessidades específicas, definidas de acordo com a filosofia do distribuidor (não do usuário) e os usuários comuns ficam confusos entre as múltiplas escolhas e as diferenças encontradas entre elas.

Tenta explicar para um usuário comum o porque do Librix e que ele poderia trocar para outro Linux. Na certa quando ele ouvir "trocar", ele não vai pensar em outro Linux que ele não consegue entender. O problema hoje é não haver um comitê ou força equivalente na indústria para definir uma distribuição Linux "padrão" para o mercado. O mais próximo disto é a Canonical com o Ubuntu, que praticamente hoje tem o nome Ubuntu tão forte como o nome Linux, além de uma boa aceitação com os usuários por tornar o sistema fácil de usar. Discorda? Configura o Debian para montar pendrive automaticamente com link na área de trabalho. Isso é coisa pra hardcore, não pra usuário doméstico.

Resta a esperança de que, nas conjecturas atuais, a Canonical consiga um bom marketing com os montadores de hardware para incluir o Ubuntu, ou uma de suas variantes, em computadores novos. Não adianta a gente espernear, querer ser purista, ou então empunhar bandeiras de diversidade: o fato é que um padrão é necessário e isso deveria ser a bandeira dos usuários Linux hoje. Só assim teremos aplicações mais interessantes (e até mesmo jogos) migrando para o sistema do Pinguim.

3D Dot Game Heroes

O vídeo diz tudo, muito 10 :).

Virtualização Manda

Como todo professor de computação, sempre tive problemas de configuração de software em laboratório de aula. Sempre falta alguma coisa que não foi instalada ou, pior, foi mal configurada. Resolvi dessa vez uma abordagem diferente: fazer uma imagem para máquina virtual (a VirtualBox) com tudo o que precisa e passar para os alunos.

O pior de tudo é imaginar que muita coisa poderia ser facilitada com isso. Me lembro de ter instalado, na máquina que usava no dia-a-dia, uma pancada de servidor (web, banco de dados, etc), ambiente disso e daquilo, etc. Seria muito mais prático colocar tudo isso numa imagem e deixar o sistema do dia-a-dia o mais limpo possível. Assim o dia que precisasse reformatar (em especial no Windows) o ambiente de trabalho estaria preservado, sem precisar ligar/desligar uma penca de serviços na mão para deixar o sistema mais leve.