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