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:
DifAlice = 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:
DifBia = B - (A ∩ B)
Se |DifBia| < |DifAlice|, então o resultado é |DifBia|. Caso contrário, o resultado é |DifAlice|. 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.
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.
Um comentário:
Como seria a resolucao em C do problema "ir e vir" da Maratona de Programação da SBC 2010?
Postar um comentário