#2 Exercícios Aleatórios

Continuando com minha nova série, vou escrever alguns comentários sobre alguns exercícios aleatórios. O exercício em deste post chamou tanto minha atenção que eu resolvi escrever bastante e unicamente a sobre ele:

Set – Paradigmas, Ad Hoc.

Eu recomendo que vocês tentem resolver o exercício acima antes de ler a solução abaixo. Assim suas teorias podem ser comparadas/contrastadas com as minhas, e isso pode ajudar no aprendizado.

Set – [uri]

Este exercício entrou pra minha lista de exercícios favoritos, graças à solução criativa que eu precisei usar para resolvê-lo. Pela primeira vez vi um exercício ser resolvido usando uma combinação dos paradigmas Guloso e Programação Dinâmica.

Os casos de teste apresentam alguns exemplos bem básicos do que o algoritmo deve ser capaz de resolver. Para cada conjunto existem inúmeras maneiras de se montar as combinações, e (1) testar todas recursivamente é inviável graças aos limites altos; (2) pensar em uma estratégia ótima de escolha de combinações me pareceu ser uma tarefa bem difícil (se é que é possível).

Para chegar à solução eu comecei a imaginar se não seria possível utilizar programação dinâmica. Minha linha de pensamento foi a seguinte: se eu for usar programação dinâmica, eu preciso ter alguns quesitos bem definidos, tal como (1) o que cada estado me diz (qual a pergunta); (2) como representar cada estado; (3) qual o relacionamento entre cada estado.

(1) O exercício em si nos pede: qual o maior número de sets que eu consigo formar com um determinado conjunto de cartas.
Por exemplo, qual o maior número de sets que eu consigo formar com 3 cartas de um quadrado.

(2) Quantas cartas de cada tipo eu tenho atualmente.
Por exemplo, no estado atual eu tenho 3 cartas de dois quadrados e 2 de três círculos.

(3) Se eu remover 3 cartas que correspondem a um tipo específico de set, eu caio no estado que corresponde às cartas que eu não removi (todas menos as 3).
Por exemplo, dado o estado atual acima, se eu remover as 3 cartas de dois quadrados eu cairia no estado onde eu tenho apenas 2 cartas de três círculos.

Tudo me pareceu ok, até eu tentar implementar a parte (2). Temos nove tipos de cartas diferentes, logo, se eu fosse montar um estado de programação dinâmica como geralmente faço, ele ficaria algo como: dp[qnt_a][qnt_b]…[qnt_i], sendo qnt_a = quantidade de um círculo, qnt_b = quantidade de dois círculos, etc. O porém está no fato de que podem haver até 3*10^4 cartas. Logo, o tamanho do meu vetor nono-dimensional (não sei se é esse o termo) seria algo em torno de (3*10^4)^9, ou seja, um número absurdo (pois seria int dp[3*10^4][3*10^4]…[3*10^4]).

Imagino então que eu deveria tentar diminuir o número de cartas, e é aí que entra a estratégia gulosa. Se eu tiver um número consideravelmente alto de cartas de cada tipo, talvez a escolha entre dois tipos diferentes de sets não faça tanta diferença, logo eu posso simplesmente escolher o primeiro set que me convém. Por exemplo, se eu tenho o seguinte conjunto de cartas:

4 cartas do tipo Um círculo
3 cartas do tipo Dois círculos
3 cartas do tipo Três círculos

Há duas maneiras de montar nossos sets que nos levam ao mesmo resultado: (1) posso montar três sets que consistem de cartas idênticas; (2) ou eu posso montar três sets idênticos que consistem de uma carta de cada tipo.

Isso não é necessariamente válido, porém, quando o número de cartas não é razoavelmente alto, como no caso:

3 cartas do tipo Um círculo
2 cartas do tipo Dois círculos
2 cartas do tipo Três círculos

A melhor estratégia é montar dois sets idênticos que consistem de uma carta de cada tipo, e não montar um set com três cartas idênticas.

Percebendo que minha estratégia de “equivalência” (escolher o primeiro set que me convém) só funciona quando o número de cartas de cada tipo envolvido é maior que 3, escrevi meu primeiro trecho de código Guloso:

// seja cont um vetor com o número de cartas de cada tipo.

// sejam a, b e c índices de três cartas distintas que podem formar um set.

// aqui vamos montar os sets mixos.
int resp = 0;
while(cont[a] > 3 and cont[b] > 3 and cont[c] > 3) {
    cont[a] -= 3; cont[b] -= 3; cont[c] -= 3;
    resp += 3;
}

// e aqui os sets de apenas um tipo de carta.
for(int i=0; i<9; i++) {
    while(cont[i] > 3) {
        cont[i] -= 3;
        resp++;
    }
}

Por mais que eu não tenha formado todos os possíveis sets, esse passo Guloso foi fundamental para que seja possível implementar a Programação Dinâmica que eu citei no início do post. Meu problema inicial era que eu podia ter até 3*10^4 cartas de cada tipo, porém após a redução acima, eu tenho certeza que posso ter no máximo 3 cartas de cada tipo. Logo, agora terei um total de 4^9 estados, que é um número consideravelmente menor e implementável. 🙂

Agora vou entrar em detalhes sobre a implementacão de todo o código, pois em diversos momentos eu usei “truques” que tornam a implementação mais fácil.

Implementação

O primeiro passo é fazer um mapeamento de cada tipo de carta para um inteiro único, para que possamos trabalhar de uma forma mais simplificada. O mapeamento usado vai ser o seguinte:

set_image_1

Para implementar isso, vou me aproveitar do fato de que os três números diferentes tem letras iniciais diferentes, e o mesmo vale para o nome das figuras. Logo, eu poderia atribuir um inteiro para cada letra inicial das palavras, e fazer o mapeamento através dessa soma:

int mapa[2][256];
char s[2][16];

int main() {
    // neste modelo, qualquer uma das possíveis somas resultam em inteiros únicos.
    mapa[0][(int)'u'] = 0; mapa[0][(int)'d'] = 3; mapa[0][(int)'t'] = 6;
    mapa[1][(int)'t'] = 0; mapa[1][(int)'q'] = 1; mapa[1][(int)'c'] = 2;
 
    while(scanf("%d", &n) and n) {
        memset(cont, 0, sizeof(cont));
 
        // input
        for(int i=0; i<n; i++) {
            scanf("%s %s", s[0], s[1]);

            // somo o valor da primeira letra de cada palavra para chegar a um identificador único.
            int ident = mapa[0][ (int)s[0][0] ] + mapa[1][ (int)s[1][0] ];

            cont[ident]++;
        }
    ...

Lembrando que esta não é a única, nem a mais eficiente forma de fazer essa conversão. É apenas, na minha opinião, a forma mais rápida e descomplicada (imagina fazer 9 if’s diferentes).

O segundo passo é implementar a parte gulosa citada acima. Se vocês notarem, os valores a, b e c do código guloso apareceram de forma mágica. Vou mostrar a maneira que usei para montá-los. Primeiro, levem em consideracão as possíveis combinações começando com a carta de um círculo:

set_image_2

Agora que temos um inteiro único que representa cada tipo de carta, é possível montar um “guia” que nos diz quais são os identificadores que compõem cada possível set. Por isso, entre as combinacões temos: 036, 048, 057, 012, etc.

Para implementar isso de forma descomplicada eu optei por declarar uma string que representa todas as possíveis combinações, e usá-la para montar as combinações no código de forma mais dinâmica:

const char comb[256] = "036 048 057 147 138 156 258 246 237 012 345 678";

// quando eu precisar montar cada combinacão:
for(int i=0; i<48; i+=4) {
    int a = comb[i  ]-'0';
    int b = comb[i+1]-'0';
    int c = comb[i+2]-'0';
    
    ...
}

Agora vem a parte de implementar a programação dinâmica. Vou utilizar aqui alguns conceitos de BitMask, e consequentemente algumas operações que envolvem a manipulação de bits de números inteiros.

Declarar a minha pd (programação dinâmica) como sendo “int dp[qnt_a][qnt_b]…[qnt_i];” seria um tanto doloroso para que pudéssemos fazer a transição entre estados no futuro. Por exemplo, se eu quisesse recorrer a um estado onde eu removo 3 cartas de tipos diferentes, eu teria que de alguma maneira chamar o estado dp[qnt_a][qnt_b-1][qnt_c-1][qnt_d]…[qnt_i-1]. Mais especificamente, eu teria que levar em consideração e implementar um if para cada tipo de set diferente, e manualmente fazer todo esse relacionamento.

Para facilitar, eu vou tirar vantagem da string de combinações que eu acabei de apresentar acima para fazer as transições entre os estados de forma mais dinâmica. Logo, vou utilizar o conceito de BitMask, que trata-se de representar uma sequência de inteiros ou booleanos como sendo um único inteiro.

Como eu citei acima, após a sequência de passos gulosos que eu implementei eu tenho no máximo 3 cartas de cada tipo. Para representar esses valores em uma BitMask eu preciso encontrar um equivalente em binário para cada número de cartas possíveis, ou seja:

0 cartas = 00
1 carta  = 01
2 cartas = 10
3 cartas = 11

Diferente da maioria das implementações de BitMask que eu havia visto até então, a nossa BitMask precisa de 2 bits para representar cada elemento. Ou seja, num total teremos 2*9 bits (2 bits para cada um dos 9 tipos de cartas), resultando em 2^19-1 estados diferentes.

Alguns exemplos:

Qnt de cartas =    0  0  2  0  0  2  3  3  1
Rep normal    = dp[0][0][2][0][0][2][3][3][1]
Rep BitMask   = dp[00 00 10 00 00 10 11 11 01] = dp[8381]

Qnt de cartas =    1  1  0  0  3  3  0  3  2
Rep BitMask   = dp[01 01 00 00 11 11 00 11 10] = dp[82894]

Resumindo, o objetivo da BitMask aqui é transformar a quantidade de cartas de cada tipo em um único e distinto inteiro, que vai servir como índice e representar nosso estado na programação dinâmica.

A maior vantagem dessa forma de representar nosso estado é que ela é facilmente manipulável em tempo de execução, facilitando nossa transição entre diferentes estados. Antes de continuar, gostaria de apresentar três funções que manipulam bits específicos em uma BitMask:

// encontra o numero de cartas do tipo "pos"
int find(int state, int pos) {
    return ((3 << (pos*2))&state) >> (pos*2);
}

// subtrai "value" no numero de cartas do tipo "pos"
int subtract(int state, int pos, int value) {
    return state - (value << (pos*2));
}

// adiciona "value" no numero de cartas do tipo "pos"
int add(int state, int pos, int value) {
    return state + (value << (pos*2));
}

Estas funções, que talvez mereçam uma melhor explicação e aprofundamento em um futuro post, são tudo o que precisamos para implementar nossa programação dinâmica.

Primeiro, vamos gerar nosso estado inicial:

int state = 0;
for(int i=0; i<9; i++) {
    state = add(state, i, cont[i]);
}

Em seguida, vamos implementar a função recursiva que vai resolver nossa programação dinâmica:

int funcao(int state) {
    if(dp[state] != -1) return dp[state];

    int ans = 0, cont[4], ind, j;
    for(int i=0; i<48; i+=4) {
        int new_state = state;

        for(j=0; j<3; j++) {
            ind = comb[i+j]-'0';

            cont[j] = find(state, ind);
            if(!cont[j]) break;

            new_state = subtract(new_state, ind, cont[j]);
            new_state = add(new_state, ind, cont[j]-1);
        }

        if(j == 3) {
            ans = max(ans, funcao(new_state)+1);
        }
    }
    for(int i=0; i<9; i++) {
        int aux = find(state, i);

        if(aux == 3) {
            int new_state = state;
            new_state = subtract(new_state, i, 3);

            ans = max(ans, funcao(new_state)+1);
        }
    }

    return dp[state] = ans;
}

Deixo a interpretação do código acima a cargo de vocês. Ela faz basicamente o que o código da reducão gulosa fez no início do post.

 

É isso. Se você tiver alguma dúvida, crítica ou sugestão, deixe um comentário abaixo.

Até mais 🙂

7 ideias sobre “#2 Exercícios Aleatórios”

  1. Muito bem explicado como sempre 😀
    Obrigado por sempre dar uma grande ajuda.
    Eu cheguei no top 15 do URI, que era meu objetivo xD, agora vou focar em resolver todos os problemas do Rosalind e os do UVA marcados com estrela no livro de competição competitiva. Acho que o URI(pelo menos por tempo) vai ser só pra fazer os contests 😀

    Vlw parceiro, caso ainda não conheça o Rosalind, são problemas de bioinformática:
    http://rosalind.info/problems/list-view/

    1. Opa, obrigado haha.
      É possível sim, basta iterar entre 0 e 4^9, e aplicar o mesmo algoritmo de escolha de sub-estados.
      Qualquer dúvida sobre a implementacão pode me mandar por e-mail 🙂

  2. Oi amigo!

    Poderia me explicar por que você fez isso:
    new_state = subtract(new_state, ind, cont[j]);
    new_state = add(new_state, ind, cont[j]-1);

    Ao invez de simplesmente isso?
    new_state = subtract(new_state, ind, 1);

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *