SRM 533, 535 e Codeforces #108

Desde o último post-mortem, participei de várias competições de programação. No SRM 533 falhei nos dois problemas que submeti (Casket of Star e Magic Board) e por causa disso voltei a virar azul :(

No Codeforces #108, passei um bom tempo pensando no problema Garden, mas não consegui resolver.

No SRM 535 achei um bug na minha solução e tive que re-submeter o problema fácil por 75 pontos. Além disso errei um challenge (-25 pontos). Finalmente, pensei bastante no problema Fox and Business, mas a complexidade da minha solução estava muito alta dado os limites do problema.

Neste post vou apresentar um resumo das soluções para os quatro problemas mencionados.


Casket of Star

A descrição do problema se encontra aqui. Estou supondo que o vetor de entrada é chamado w e possui tamanho n.

Minha abordagem durante a prova foi gulosa: remover sempre o elemento i tal que w[i-1]*w[i+1] seja máximo. Na hora me pareceu correto e todos os casos de teste passaram, mas eis um contra-exemplo: (2, 5, 10, 5, 2). O algoritmo irá remover o 10, gerando um produto de 5*5=25, deixando (2, 5, 5, 2). Aí não tem muito o que fazer: vamos tirar os dois 5, gerando os produtos 10 e depois 4, para um total de 39. Entretanto, se retirarmos os 5’s antes do 10, teremos 20 + 20 + 4, para um total de 44.

Programação dinâmica

Durante a prova cheguei a pensar em uma abordagem por programação dinâmica, mas encontrei dificuldades em definir os subproblemas independentes. Minha única ideia foi a de remover um dado elemento i (adicionando um valor w[i-1]*w[i+1]) e então pensar em alguma coisa com os subproblemas [0,i-1] e [i+1, n-1], mas eles não são independentes, pois poderíamos remover o elemento i+1 e o valor obtido dependeria do valor no outro subvetor.

Depois da prova pensei em outras alternativas. Uma delas foi: e se ao invés de tentar separar em subproblemas a partir do primeiro elemento removido, tentar separar a partir do último? Essa ideia aleatória matou o problema porque se eu sei que o elemento i será o último a ser removido, então os intervalos [0,i] e [i, n-1] são independentes! Isso porque o valor obtido da remoção de um elemento de 0 a i-1 não dependerá do valor de i+1 a n-1 e vice-versa.

Se chamarmos de f(i, j) o melhor valor obtido para a subsequência [i, j], podemos derivar a seguinte recorrência:

f(i, j) = \max_{i +1 \le k \le j-1} \left\{ f(i, k) + f(k, j) + w(i)w(j) \right\}

No caso estamos tentando com todos os possíveis valores de k entre i+1 e j-1 e supondo que k será o último elemento a ser removido. O resultado das remoções feitas em f(i, k) será o vetor {i,k} e o de f(k, j) será o vetor {k, j}, ou seja, {i, k, j}. Agora a única possibilidade é remover k e somamos w(i)w(j) no valor. O caso base é quando temos menos de 2 elementos, o qual devemos retornar 0.

Resumo

Achei a dificuldade do problema elevada, além do fato de ele ser bem tricky. A taxa de acerto foi de 31%.

A técnica de “pensar ao contrário” (nesse caso, olha para o último elemento a ser removido ao invés do primeiro), que eu já havia usado em problemas passados, foi essencial.


Magic Board

Neste problema, devemos encontrar um caminho que passe exatamente por todas as células marcadas de um grid, com a seguinte restrição: só podemos ir de uma célula para outra usando linhas verticais ou horizontais, sendo que no caminho devemos alternar entre linhas verticais e horizontais, começando por uma linha horizontal.

Minha abordagem foi a seguinte. Seja s o vértice inicial e t o vértice final do caminho. Nesse caso, somamos 1 na contagem da coluna de s. Se o número de vértices for par, então a última aresta é horizontal e nesse caso também somamos 1 na contagem da coluna de t. Por outro lado, se o número de vértices for ímpar, a última aresta é vertical e então somamos 1 na linha de t. Agora, verificamos se todas as colunas e linhas possuem uma contagem par.

Temos que chutar todos os possíveis pares s e t para ver se algum satisfaz a condição acima, ou seja, o algoritmo é O(N^4), para N = 50.

Essa abordagem parecia correta, mas eu tomei um challenge. O motivo: essa contagem não faz a verificação da conexidade. Pode existir um caminho válido mas com “ciclos” disjuntos, como no seguinte exemplo:


##...
.#...
...##
...##

Figura 1: Ciclo disjunto

A componente no alto à esquerda é válida, assim como o ciclo abaixo à direita, mas eles são disjuntos. É possível eliminar esse caso fazendo uma simples busca em profundidade e verificar se todo vértice é alcançável a partir do outro usando apenas arestas ortogonais.

No editorial, a solução é modelar o tabuleiro como grafo bipartido. Cada coluna representa um vértice da primeira partição, enquanto cada linha representa um vértice da segunda partição. O problema consiste em decidir se existe um caminho euleriano, com a restrição de que a primeira aresta usada no tabuleiro seja horizontal.

Resumo

Esse foi outro problema tricky, pelo fato de não haver casos de testes com o problema da conexidade.

A modelagem de um tabuleiro usando um grafo bipartido é uma técnica que eu já havia utilizado anteriormente. Tentar trocar arestas com vértices (dualidade) no grafo pode ser útil para conseguir resolver o problema. Nesse caso, um problema que parecia um caminho hamiltoniano (NP-difícil) acabou ficando parecido com um caminho euleriano (para o qual existe um algoritmo polinomial)

Dois problemas relacionados que me veem à mente são o Rectilinear Polygon [4] e o The Necklace [5].


Fox and Business

Podemos modelar este problema matematicamente da seguinte maneira:

\min (\sum_{i \in S} p_i a_i t) + tK

Onde, S é representa os empregados que serão escolhidos na solução, p_i é o custo por unidade de trabalho do empregado i e a_i é a quantidade de unidades de trabalho dele em uma hora. A variável t é o tempo de cada trabalhador e K é o número de trabalhador que deverá ser usado.

Essa função objetivo está sujeita a

\sum_{i \in S} a_i t = T

onde T é o total de trabalho que deve ser feito. Durante a prova só consegui pensar em uma abordagem de programação dinâmica, mas minha ideia tinha uma complexidade que não passaria no tempo.

A abordagem usada no editorial é muito engenhosa e não utiliza PD. A ideia se você dividir a função objetivo por uma constante positiva, a solução ótima não muda. Como T é uma constante, podemos dividir a função objetivo por ela, obtendo

(\sum_{i \in S} p_i a_i t) + tK = \dfrac{(\sum_{i \in S} p_i a_i t) + tK}{T}

Substituindo o valor de T, podemos nos livrar da variável t,

= \dfrac{(\sum_{i \in S} p_i a_i) + K}{\sum_{i \in S} a_i}

Bom, isso não pareceu ajudar muito, mas a segunda sacada é transformar esse problema de otimização em um problema de decisão, ou seja, dado um valor C, existe uma solução S tal que

C \ge \dfrac{(\sum_{i \in S} p_i a_i) + K}{\sum_{i \in S} a_i}?

Com um pouco de álgebra podemos reescrever essa desigualdade como

C \sum_{i \in S} a_i \ge (\sum_{i \in S} p_i a_i) + K \rightarrow

\sum_{i \in S} a_i(C - p_i) \ge K

O valor máximo do lado esquerdo da desigualdade pode ser calculado de maneira gulosa, escolhendo os K maiores de a_i(C - p_i)! Se esse valor máximo for menor do que K, então não existe uma solução. Assim, temos um algoritmo para resolver o problema de decisão.

Para obter o valor ótimo de C, podemos usar a técnica da busca binária. O valor esperado pelo problema será C T

Resumo

Ideias utilizadas: Manipulação algébrica e busca binária para transformar um problema de otimização em um de decisão.


Garden

Neste problema temos um tabuleiro n x m onde cada célula tem um inteiro positivo que representa um custo. Duas células são ditas adjacentes se tocam em um dos lados (não consideramos diagonal). Duas células podem ser conectadas através de um caminho de células adjacentes. O custo desse caminho é a soma dos custos das células nesse caminho. São dados então k pontos desse tabuleiro que devem ser conectados com o menor custo. Mais detalhes no enunciado do problema.

Esse problema lembra um caso particular do problema da árvore de Steiner, onde é permitido adicionar novos vértices para tentar obter uma árvore de custo menor do que a árvore geradora mínima.

Achei a solução do editorial bastante resumida e com um inglês meio difícil de compreender. De qualquer maneira, deu pra entender que se trata de programação dinâmica. No editorial é dada a recorrência, mas tive que quebrar a cabeça para entender de onde ela veio.

Programação dinâmica

A ideia básica da recorrência é: dada uma cobertura de um conjunto de pontos, quebramo-na em cobertura menores, cobrindo subconjuntos do conjunto inicial de pontos. Faremos a quebra em pontos compartilhados pelas coberturas menores o qual chamaremos de pivots.

Seja C(P, p) a cobertura de menor custo cobrindo o conjunto de pontos P e que possua o ponto p. No nosso caso, P é um subconjunto dos pontos a serem cobertos e pode ser representado com uma máscara de bits. Já o ponto p é uma célula qualquer do tabuleiro. A solução que queremos é \max_p \{C(P, p)\} com P igual ao conjunto dos pontos a serem cobertos.

Há dois tipos de recorrência que vamos considerar. Primeiro, considere um grafo que conecta os pontos desejados como o exemplo da Figura 2(a). Queremos particioná-lo em 2 subgrafos que cobrem subconjuntos desses pontos e que compartilham apenas o ponto verde (pivot). Uma possibilidade de quebra é a da Figura 2(b).

Figura 2

Agora podemos resolver recursivamente cada componente e calcular o custo da componente completa somando os custos. Porém, veja que o pivot está sendo contado duas vezes e portanto devemos subtrai-lo. Definimos C_1(P, q) como:

C_1(P, p) = \max_{P'}\{C(P',p) + C(P \setminus P', p) - custo(p)\}

Onde P' representa todos os subconjuntos próprios não vazios de P.

Porém, pode ser o caso de não conseguirmos particionar o grafo de forma que o pivot seja o único ponto compartilhado, como é o caso da segunda componente de Figura 2(b). Neste caso queremos modificar o nosso pivot, mas para isso devemos considerar a distância entre o pivot antigo e o novo, representados por p e q em nosso exemplo:

Figura 3

Nesse caso definimos C_2(P, p) como:

C_2(P, p) = \max_{q}\{C(P \setminus \{p\}, q) + dist(p, q) - custo(q)\}

Onde q é um ponto qualquer do tabuleiro. Um cuidado que devemos ter aqui é que se p pertence a P, devemos removê-lo antes de chamar a recursão. Novamente, veja que o custo da célula q está sendo considerado duas vezes e portanto precisamos descontar um delas.

Finalmente, temos que C(P, p) = \max\{C_1(P, p), C_2(P, p)\}

Não bastasse isso, o problema ainda pede para mostrar o grafo que conecta os pontos (se houver mais de um com custo ótimo, pode ser qualquer um). Para isso devemos guardar as decisões tomadas durante as recorrências para recuperar a solução.

Complexidade

A distância entre pares de pontos pode ser pré-computada usando o algoritmo de Floyd-Warshall. Denotando nm por N, temos O(N^3).

Para calcular a complexidade da recursão vemos que são O(2^k N) estados. Na primeira recorrência devemos analisar outros O(2^k) estados, enquanto na segunda são O(N), levando a uma complexidade total O(2^kN(2^k + N)). Os limites do problema são k \le 7 e N \le 200, o que dá na ordem de O(8\cdot10^6) operações.

Resumo

Ideias utilizadas: Observar os limites dos problemas, particularmente o valor de k, que sugerem que no estado da programação dinâmica podem ser usadas máscara de bits.

Além disso, notar que se quebrarmos em subproblemas particionando o conjunto inicial de pontos, as soluções parciais não podem ser utilizadas imediatamente para compor a solução do problema original por que há células que seriam compartilhadas entre ambas as soluções e portanto devemos remover a contagem repetida.

A grande sacada é ver que podemos supor que as sub-soluções compartilham exatamente uma célula se permitirmos a troca de pivot.

Códigos-fontes

Disponibilizei os códigos-fontes de todos os problemas discutidos no post, no github (SRM 533, SRM 535 e Codeforces #108).

Referências

[1] Editorial SRM 533
[2] Editorial Codeforces #108
[3] Editorial SRM 535
[4] UVa 11106 – Rectilinear Polygon
[5] UVa 10054 – The Necklace

Os comentários estão fechados.

%d bloggers like this: