SRM 533, 535 e Codeforces #108

Junho 10, 2012

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

Anúncios

SRM 527

Dezembro 25, 2011

Depois de quase 5 anos competindo no Topcoder, finalmente meu rating ficou amarelo (+1500) \o/. Entretanto, não acredito que eu vá sustentar essa cor por muito tempo.

Como de costume comecei pelo problema fácil (275). Como não consegui pensar em nenhuma solução além de uma força-bruta complicada e como a pontuação do problema médio estava menor do que o de costume (450 contra 500), resolvi lê-lo. Então vamos começar por ele.

P8XMatrixRecovery

(Enunciado do problema)

Minha primeira ideia foi modelar como emparelhamento bipartido máximo de custo mínimo, mas não estava conseguindo modelar a função objetivo.

Depois de pensar mais, acabei lembrando de uma técnica que consiste em fixar um parâmetro do problema visando simplificá-lo. Um caso especial dessa técnica é o uso de busca binária num problema de otimização para transformá-lo em um problema de decisão.

Um problema que me lembro que pode ser resolvido com a técnica mais geral é o seguinte: encontrar o emparelhamento máximo de um grafo bipartido de forma que se minimize o custo da aresta de maior custo (a versão clássica do emparelhamento máximo de custo mínimo seria minimizar a soma dos custos das arestas).

A solução é, para cada possível custo de aresta C, criar um subgrafo G' contendo apenas as arestas de custo menores ou iguais a C. A resposta será o menor C para o qual existe um emparelhamento máximo em G'.

No problema em questão, podemos ter várias permutações de colunas que mapeiam uma matriz na outra, por causa dos caracteres coringas (‘?’). Entretanto, o problema pede a lexicograficamente menor. A ideia é fixar o primeiro caractere ‘?’ em ‘0’ e verificar se ainda existe um mapeamento.

Se sim, então podemos manter o caractere em ‘0’ e proceder para o próximo caractere ‘?’. Caso contrário, não existe nenhum mapeamento com ‘0’ e como o enunciado diz que sempre existe uma solução, então tem que existir alguma com ‘1’ e portanto podemos trocar para esse valor. Fazendo isso para todo caractere ‘?’ encontraremos a matriz lexicograficamente menor.

Para decidir se existe um mapeamento podemos resolver o problema do emparelhamento máximo bipartido. Criamos duas partições com vértices correspondendo a cada coluna de cada matriz. Adicionamos uma aresta entre dois vértices se as colunas correspondentes são iguais. Note que o “igual” nesse caso deve levar em conta que ‘?’ é igual a ‘?’, ‘0’ ou ‘1’. Se houver um emparelhamento perfeito, significa que existe uma bijeção entre as colunas das duas matrizes.

O emparelhamento máximo bipartido pode ser resolvido através do algoritmo de caminhos de aumento (augmenting paths) com complexidade O(NM) onde N é o número de vértices e M é o número de arestas.

Note que devemos resolver o problema do emparelhamento para cada ‘?’. No pior caso podemos ter matrizes só com ‘?’ (N^2) e nesse caso o grafo bipartido teria O(N^2) arestas, levando a uma complexidade total O(N^5). No problema o valor de N era igual a 30. Eu achei que ia estourar, mas minha solução acabou passando (código no github).

P8XGraphBuilder

(Enunciado do problema)

Depois que resolvi o problema médio, voltei a pensar na solução para esse problema. Cheguei a pensar na seguinte proposição:

Proposição: Dado um vetor de N elementos com valores maiores ou iguais a 1 e de tal forma que a soma desses elementos seja 2(N-1), é possível construir uma árvore de N vértices, de forma que exista uma correspondência entre os graus dos vértices e os elementos desse vetor.

Por exemplo, se N = 4, temos os vetores [3, 1, 1, 1] e [2, 2, 1, 1] e suas permutações. Dado um vetor, seu custo é dado pela soma dos pesos de seus elementos. O problema original então se reduz a encontrar o maior custo de um vetor satisfazendo as restrições da proposição.

É possível resolver esse novo problema através de programação dinâmica. Podemos definir C(n, s) como a melhor solução de um vetor de n elementos e somando exatamente s. A recorrência fica:

C(n, s) = \max_{d=1}^{N-1} C(n - 1, s - d) + b(d)

Onde b(d) é o valor do elemento d (dado pelo vetor scores). A base é quando n = 0. Nesse caso, se s = 0, temos 0, caso contrário não existe solução e retornamos -\infty.

Durante a prova, não tinha cheguei a provar a proposição, mas ela me pareceu correta. Mas infelizmente não tive tempo de implementar essa solução, que agora adicionei ao github.

Pra fins de completude, vou apresentar agora a prova da proposição.

Prova: Primeiro, sem perda de generalidade, vamos supor que os elementos do vetor estão ordenados em ordem não-crescente. Vamos usar um argumento construtivo. Dado um vetor v = \{d_1, d_2, \cdots, d_N\}, seja k o número de elementos com valor maior ou igual a 2. Crie um nó raíz com d_1 filhos. Faça um desses filhos ter d_2 - 1 filhos, um dos “netos” ter d_3 - 1 filhos e assim sucessivamente, até um nó ter d_k - 1 filhos.

Por exemplo, dado o vetor v = {4,4,3,1,1,1,1,1,1,1} construímos a árvore da figura abaixo.

Árvore com graus {4,4,3,1,1,1,1,1,1,1}

Temos uma árvore onde k nós têm grau igual aos primeiros k elementos de v e o resto dos nós têm grau 1. Resta provar que o número desses nós de grau 1 é exatamente N - k, ou equivalentemente, que essa árvore tem N nós. É fácil ver que o número de filhos “gerados” é a soma d_1 + (d_2 - 1) + (d_3 - 1) + \cdots + (d_k - 1) = (\sum_{i = 1}^k d_i) - k + 1.

O único vértice que não foi contado acima foi a raíz, então se N' é o número de nós da árvore gerada, temos N' = (\sum_{i = 1}^k d_i) - k + 2.

Usando a restrição de que o vetor deve somar 2(N-1), com um pouco de álgebra:

\sum_{i = 1}^k d_i + \sum_{i = k+1}^N d_i = 2N - 2

\sum_{i = 1}^k d_i + (N-k) = 2N - 2

Concluímos que N = (\sum_{i = 1}^k d_i) - k + 2 e que N' = N


Topcoder: SRM 523

Novembro 27, 2011

No SRM 523 demorei bastante para fazer o problema fácil (50 min!) e por isso sobrou pouco tempo para fazer o médio. Cheguei a bolar uma solução, mas descobri no final que ela estava errada.

Depois de muito tempo voltei acertar um challenge! O erro em questão era um típico caso de Off-by-one error no problema fácil.

Depois de passada a competição, consegui encontrar o erro da minha ideia original e resolvi o problema médio. Neste post vou explicar minha solução.

BricksN

Considere que temos um número infinito de blocos de tamanho 1 a k. Queremos construir uma torre sobre uma base de largura w e altura máxima h usando esses blocos, com a seguinte restrição: só podemos posicionar um bloco em uma dada posição, se todas as posições logo abaixo desse bloco estiverem preenchidas (sem buraco). A pergunta é: quantas torres diferentes podemos formar seguindo essas restrições?

Exemplo de configuração proibida

(Observação: se duas torres têm mesma “forma”, mas existem blocos em posições diferentes, elas também são consideradas diferentes)

Soluções consideradas diferentes

Descrição do problema original.

Solução

Primeiramente, notei que este era um problema de contagem e portanto havia uma grande chance da solução ser por programação dinâmica.

Para encontrar a recorrência em programação dinâmica, é interessante pensar em casos particulares. Vamos por exemplo pensar em uma torre de altura 1 (uma linha) e largura w. Além disso, vamos supor que não há buracos. De quantas maneiras podemos formar tal torre usando blocos de tamanho até k?

Seja C_k(w), o número de maneiras de construir uma linha de comprimento w, permitindo blocos de tamanho até k. Considere todas as soluções com essas características. Podemos particionar essas soluções em grupos nos baseando no tamanho do último bloco utilizado.

Considere um grupo onde o tamanho do último bloco é i. Se removermos esse bloco, teremos linhas de comprimento (w-i). Todas as possíveis soluções diferentes com comprimento (w-i) continuarão diferentes ao adicionarmos o bloco de tamanho i de volta.

Fazendo isso para todos os blocos de tamanho 1 a k, obteremos todas as possíveis soluções contadas em C_k(w). Note que não estamos contando soluções repetidas pois duas soluções com o último bloco diferente, serão diferentes independentemente do que tem anteriormente. Note também que não estamos deixando de contar nenhuma solução, já que qualquer solução deverá conter como último bloco algum entre 1 e k.

Logo, temos a seguinte recorrência:

C_k(w) =  \sum_{i=1}^k C_k(w-i)

Para i \ge  w e com C_k(0) = 1.

Agora vamos generalizar um pouco mais e considerar linhas que podem ter buracos. A receita para encontrar uma recorrência é a mesma: precisamos particionar todas as possíveis soluções e para cada grupo, tentar reduzir para um subproblema.

Seja B_k(w) o número de maneiras de se formar uma linha de comprimento w, permitindo buracos.

Nesse caso, podemos particionar as soluções pela posição onde um buraco primeiro aparece, ou seja, temos um pedaço contíguo de blocos de tamanho i, seguido de pelo menos um buraco. Uma vez que estamos considerando um grupo de soluções para um dado i, qualquer solução diferente formada depois do buraco (posição i+2 em diante), continua sendo diferente ao adicionarmos o pedaço contínuo de comprimento i mais o buraco.

Também temos que contar os casos em que não há buracos. Dessa forma teremos a recorrência

B_k(w) = C_k(w) + \sum_{i=0}^{w-1} C_k(i) \cdot B_k(w-i-1)

Aqui também temos B_k(0) = 1 e podemos argumentar que soluções para i’s diferentes são diferentes (não estamos contando repetições) e também que todas as soluções estão sendo contempladas (inclusive a vazia).

Finalmente, vamos generalizar para torres de altura h. Seja A_k(w,h) o número de soluções respeitando as condições do problema original, sobre uma base w e altura h.

Observamos que devido às restrições do problema, não podemos fazer “pontes” com buracos em baixo. Assim, se tivermos um pedaço contínuo de comprimento w’ no primeiro nível de uma torre com altura máxima h, a construção que pode estar sobre ele são todas as torres sobre uma base w’, com altura máxima h-1.

Com essa observação, podemos continuar com nossa recorrência de B, mas agora temos que considerar todas as possíveis torres que vão sobre o primeiro bloco contínuo. Note que não precisamos nos preocupar com o restante dos blocos depois do buraco, pois qualquer diferente solução obtida continuará diferente após juntarmos com a nossa primeira torre.

Assim, ficamos com a recorrência:

A_k(w, h) = C_k(w) \cdot A_k(w, h-1) +
\; \sum_{i=0}^{w-1} C_k(i) \cdot A_k(i, h-1) \cdot A_k(w-i-1, h)

A implementação dessa ideia é direta. Coloquei no gitbhub essa solução.


Topcoder: SRM 517

Outubro 30, 2011

Já faz um tempo que ocorreu o SRM 517, mas só agora resolvi estudar a solução. No dia resolvi só problema mais fácil (250) e ainda errei um challenge :(

Neste post vou apresentar apenas a solução do problema médio, que estava mais difícil do que o normal, o que estava sugerido por sua pontuação (600 ao invés de 500).

Adjacent swaps

Descrição

Seja um vetor de N elementos v = {0, 1, 2, …, N-1} e uma permutação de p = {p[0], p[1], …, p[N-1]} de v. Definimos como troca-completa o conjunto das N-1 possíveis trocas entre elementos nas posições i e e i+1 (i variando de 0 a N-2) executadas exatamente uma vez, em uma ordem arbitrária.

O problema pede para encontrar quantas trocas-completas levam a v a p.

Solução

A primeira observação é que ao invés de considerar trocas-completas que levem v a p, consideramos aquelas que levam p a v. Existe uma bijeção entre uma troca-completa do problema original e do novo problema, que é simplesmente inverter a ordem das trocas e portanto a resposta é a mesma para os dois problemas.

A solução proposta no editorial é resolver esse problema através de programação dinâmica. Para tanto, definimos

u(i,j, k) — como o número de trocas-completas que ordenam o subvetor p[i…j] = {p[i], p[i+1] …, p[j]}, usando apenas as trocas entre elementos consecutivos entre i e j-1, com a restrição adicional de que a última troca efetuada seja entre k e k+1. (0 <= i <= k < j <= N-1).

Seja t(i,j) = \sum_{k = i}^{j-1} u(i,j,k). A solução que estamos procurando é então t(0, N-1). Além do mais, para o caso base i=j, temos um vetor de um único elemento ordenado e já não resta movimentos, portanto, t(i,i) = 1 para i=0, N-1.

Vamos ver como podemos calcular u(i,j,k).

Seja q[i…j] o subvetor p[i…j] ordenado e q'[i..j] o subvetor q[i..j] antes de fazer a troca entre k e k+1. Assim, q'[k] = q[k+1] e q'[k+1] = q[k], ou seja q'[i…j] = {q[i], q[i+1], …, q[k-1], q[k+1], q[k], q[k+2], …, q[j]}.

Observação 1: (q[i] < q[i+1] < … q[k-1] < q[k+1]) e (q[k] < q[k+2] < … < q[j]).

Por definição, q[i…j] e q'[i…j] são permutações de p[i..j]. Isso implica que todo elemento de q'[i…k] pertence a p[i…k] ou p[k+1…j]. Porém, como por hipótese a troca k,k+1 não foi feita ainda, um elemento de q'[i…k] não pode ter vindo de p[k+1…j]. Logo, concluímos que q'[i…k] deve ser uma permutação de p[i…k]. Temos assim duas condições a serem satisfeitas:

Condição 1: O subvetor p[i…k] deve ser uma permutação de q'[i…k].

Condição 2: O subvetor p[k+1…j] deve ser uma permutação de q'[k+1…j].

Na verdade podemos mostrar que as condições 1 e 2 são equivalentes. Supondo que as condições são satisfeitas, pela Observação 1, temos que q'[i…k] está ordenado, logo q'[i…k] = q[i…k], que é uma ordenação de p[i…k]. É possível argumentar o mesmo para q'[k+1…j] e p[k+1…j].

Por definição, t(i,k) conta o número de trocas-completas que leva p[i…k] em q[i…k] (o mesmo para t(k+1,j)). Assim, a princípio poderíamos combinar cada troca-completa em t(i,k) com cada troca-completa em t(k+1,j), levando à recorrência u(i, j, k) = t(i, k)*t(k+1, j).

Entretanto, há um número bem maior de combinações. Considere uma dada troca-completa A de t(i,k) e outra B de t(k+1, j). Embora a ordem das trocas em A e em B sejam fixas, não há restrição de ordem entre uma troca feita em A e outra feita em B. Por exemplo, poderíamos fazer todas as trocas de A primeiro e depois todas as de B ou qualquer combinação de intercalação entre os elementos de A e B.

Podemos mostrar que o número total de intercalações possíveis é dada por um coeficiente binomial C(n,r). No nosso caso em particular, n é o número total de trocas disponíveis, ou seja, j-i-1 (k-i de A e j-(k+1) de B) e r é o número de trocas em A (ou em B), ou seja, C(j-i-1, k-i). Para ver o porquê, considere que temos posições de 1 a j-i-1. Queremos escolher k-i dessas posições para atribuir a elementos de A e o restante das posições fica para B. Agora basta pensarmos nessas posições como a ordem em que as trocas são efetuadas.

Isso dá a recorrência

u(i, j, k) = t(i, k)*t(k+1, j)*C(j-i-1, k-i)

No caso de as condições 1 e 2 não serem satisfeitas, u(i, j, k) = 0.

Podemos usar a recorrência C(n,r) = C(n-1, r-1) + C(n-1, r) para pré-computar os valores dos coeficiente binomiais em O(N^2). Também podemos pré-computar se para uma dada tripla i, j, k, as condições 1 e 2 serão satisfeitas, em O(N^3) (usando ordenação linear para encontrar q).

Dado isso, podemos computar cada u(i, j, k) em O(1) e cada t(i, j) m O(N). A complexidade total das recorrências fica O(N^3), que também é a complexidade total do algoritmo.

Decidi colocar minhas implementações de SRM’s também no github.

Conclusão

Achei a solução desse problema bastante complicada e como de costume fiquei surpreso de tanta gente ter conseguido resolvê-lo durante os 75 minutos de competição.

Programação dinâmica é uma técnica que eu acho difícil aprender, porque em geral não consigo encontrar uma estrutura no problema que me indique a forma de atacá-lo. Minha esperança é continuar estudando suas aplicações e quem sabe aprender por “osmose” :P

O uso do coeficiente binomial para contar intercalações é bem engenhoso! Lembro que alguma outra vez estudei um problema em que a contagem por coeficiente binomial também não era trivial de ver.


Google Code Jam 2011

Setembro 18, 2011

O Google Code Jam é uma competição de algoritmos anual promovida pelo Google, que acontece desde 2007 se não me engano. Esse ano eu fui até o round 2, mas acabei não me classificando entre os 500 primeiros para avançar ao round 3:( Entretanto, acabei ganhando um prêmio de consolação por ter ficado entre os 1000 primeiros, que é a camiseta do evento.

Camiseta (frente)

Embora a competição tenha acabado em Julho, a camiseta só chegou a algumas semanas. O desenho na parte de trás são linhas de código em diversas linguagens de programação e tem o formato do Japão que é onde foi a final mundial, na qual o japonês Makoto Soejima (rng_58 no topcoder) sagrou-se vencedor.

Detalhe da parte de trás

Com a chegada da camiseta, lembrei que eu tinha ficado de estudar a solução dos problemas do round 2 que eu não havia conseguido resolver. Felizmente os problem setters apresentam a solução, mas também vou descrevê-las aqui do meu jeito.

C. Expensive Dinner

O enunciado desse problema está aqui. A solução está baseada em três proposições principais.

Proposição 1: Dado um grupo de amigos x_1, x_2, \dots, x_i, o valor da conta é sempre LCM(x_1, x_2, \dots, x_i) não importa a ordem em que eles cheguem. LCM representa o mínimo múltiplo comum.

Prova: Seja y o valor da conta.

Parte 1 – mostrar que y \ge LCM(x_1, x_2, \dots, x_i)
Essa parte é direta, dada a definição de mínimo múltiplo comum e que a conta tem que ser divisível por todo x_i.

Parte 2 – mostrar que y \le LCM(x_1, x_2, \dots, x_i)
Quando um amigo x_i pede alguma coisa, o valor da conta vai para o próximo múltiplo de x_i. Como LCM(x_1, x_2, \dots, x_i) é múltiplo de todos, o valor da conta não poderá “pular” esse valor e uma vez que esteja nesse valor, todos estarão satisfeitos e a conta não irá mais aumentar.

Juntando as partes 1 e 2, provamos a proposição.

Seja M o número de vezes que o garçon é chamado e M_{\max} e M_{\min} o maior e o menor valor possível de M, respectivamente. O problema pede M_{\max} - M_{\min}. Sejam p_1, p_2, \dots, p_P os P primos menores ou iguais a n (o número de amigos). Além do mais, seja e_i o maior inteiro tal que p_i^{e_i} \le n.

Proposição 2: M_{\max} = 1 + \sum_{i=1}^P{e_i}

Prova: vamos quebrar em duas partes novamente.

Parte 1 – mostrar que M_{\max} \ge 1 + \sum_{i=1}^P{e_i}
Para isso basta exibir um caso onde M = 1 + \sum_{i=1}^P{e_i}. Esse é o caso em que os amigos chegam na ordem 1, 2, \dots, n. Considere a chegada de x_i tal que x_i = p_i^k. É fácil ver que LCM(x_1, x_2, \dots, x_{i-1}) não é divisível por p_i^k e portanto o garçon terá de ser chamado. Quantos x_i existem satisfazendo x_i = p_i^k? Justamente \sum_{i=1}^P{e_i}. Além disso, quando x_1 = 1 chegar a primeira vez, o garçon também deverá ser chamado. Portanto, o número de vezes que o garçon foi chamado é pelo menos 1 + \sum_{i=1}^P{e_i}

Parte 2 – mostrar que M_{\max} \le 1 + \sum_{i=1}^{e_i}
Pela Proposição 1, o valor final da conta deverá ser LCM(x_1, x_2, \dots, x_n), que é igual a \prod_{i=1}^P p^{e_i}. Para qualquer ordem de amigos, temos LCM(x_1, x_2, \dots, x_i) = k \cdot LCM(x_1, x_2, \dots, x_{i-1}) para um inteiro k. É fácil ver que se um garçon for chamado, então k > 1, ou seja, estamos aumentando a potência que algum fator primo até chegarmos em \prod_{i=1}^P p^{e_i}, logo o garçon não pode ser chamado mais do que o número total de fatores na conta final, ou seja, \sum_{i=1}^{e_i} (+1 por causa da primeira chamada).

Juntando as partes 1 e 2, provamos a proposição.

Proposição 3: M_{\min} = P

Prova: vamos quebrar em duas partes novamente.

Parte 1 – M_{\min} \le P
Para isso basta exibir um caso onde M = P. Considere uma ordem onde os P primeiros amigos a entrarem são exatamente aqueles iguais a p_i^{e_i} para todo i = 1, \dots, P. É fácil ver que depois que eles entratem, o valor da conta será já LCM(x_1, x_2, \dots, x_n) e todo mundo que entrar depois já estará satisfeito, tendo o garçon sido chamado apenas P vezes.

Parte 2 – M_{\min} \ge P
Vamos por contradição: suponha que existe uma ordem de P-1 ou menos amigos tal que LCM(x_1, x_2, \dots, x_{P-1}) = LCM(x_1, x_2, \dots, x_n) = \prod_{i=1}^P p^{e_i}. Note que, para cada p_i, deve existir um amigo com fator p_i^{e_i} (caso contrário o LCM seria menor). Pelo princípio das casas dos pombos, como existem apenas P-1 amigos e P primos, há de haver algum amigo múltiplo de p_i^{e_i} e p_j^{e_j}. Entretanto, ambos p_i^{e_i} e p_j^{e_j} são maiores que \sqrt{n}. Isso implica que esse amigo tem valor maior que n, uma contradição.

Juntando as partes 1 e 2, provamos a proposição.

Dadas essas proposições, o problema se reduz a calcular (1 + \sum_{i=1}^P {e_i}) - P para todo primo P \le n. Considerando que podemos calcular e_i em O(\log(n)), levando a um algoritmo O(n \log(n)). Porém, como n pode ser até 10^{12}, temos que fazer melhor.

A sacada é reescrever a equação como 1 + \sum_{i=1}^P ({e_i} - 1). Isso quer dizer que só estamos interessados em fatores primos com potências maiores que 1. Logo, podemos nos restringir a primos menores ou iguais a \sqrt{n}, levando a um algoritmo O(\sqrt{n} \log(n)).

Depois dessa teoria toda, o algoritmo fica bem simples. Aqui está minha versão em C++, usando o crivo de eratóstenes para encontrar os primos.

D. A.I. War

Este problema se reduz para o seguinte problema: Dado um grafo G(V, E), encontrar o menor caminho entre s e t em um grafo não-direcionado e não-ponderado. Se houver várias soluções, escolha o caminho com maior vizinhança. Consideramos a vizinhança de um caminho como a união das vizinhanças dos vértices desse caminho, excluindo os vértices do próprio caminho. O problema pede para imprimir o comprimento desse caminho e o tamanho de sua vizinhança.

Vamos denotar por N o número de vértices nesse grafo e M o número de arestas.

Primeiramente encontramos as menores distâncias a partir de s, para todos os vértices, através de uma busca em largura. Denotamos por dist(v) a menor distância de s a v. O tamanho do menor caminho é dist(t).

Construímos então um grafo direcionado G' = (V, A), com mesmo conjunto de vértices do grafo de entrada e um arco (u, v) \in A se a dist(u) + 1 = dist(v). Podemos argumentar que todo caminho mínimo s-t no grafo original corresponde a um caminho direcionado de s a t nesse novo grafo.

Solução para o caso pequeno: podemos fazer uma força bruta a partir de s e, sempre que chegarmos em t, calculamos o tamanho da vizinhança desse caminho. Dessa forma estamos enumerando explicitamente todos os possíveis menores caminhos. Fiz uma estimativa e me pareceu que no pior caso, haverá cerca de O(\sqrt{N}^{\sqrt{N}}) caminhos. No caso fácil, P=36, o que dá uma ordem de 50k operações. No caso difícil, P=400, o que torna a abordagem inviável. De qualquer maneira, eis aqui minha solução para o caso fácil.

Solução para o caso geral: uma ideia é usar programação dinâmica para guardar o tamanho da vizinhança para um dado caminho, mas note que não basta representar um caminho por seu último vértice, pois ao adicionar um vértice a este caminho, sua contribuição para o tamanho da vizinhança pode depender de mais vértices nesse caminho.

A observação chave é que na verdade, a contribuição de um novo vértice c só depende do último e penúltimo vértice desse caminho. Para entender porque, suponha que dist(c) = D + 1 e sejam b e a o último e penúltimo vértices de um caminho, respectivamente. Então dist(b) = D e dist(a) = D-1. Se c possuísse vizinhança comum com algum vértice x tal que dist(x) \le D-2, então o menor caminho até c seria menor ou igual a D, uma contradição.

Logo, é suficiente representar um caminho por seus dois últimos vértices. Seja f(b, c) o tamanho da maior vizinhança de um caminho terminado em b \rightarrow c. Podemos definir a seguinte recorrência:

f(b, c) = \max \{ (a, b) \in A(G') | f(a, b) + g(c, a, b) \}

Aqui, g(c, a, b) é o número de vértices na vizinhança de c que não está contido nem na vizinhança de a nem na de b. O caso base é f(s, c), onde o valor é simplesmente o tamanho da união da vizinhança de s e c.

Se pré-computarmos g(c, a, b), podemos resolver a recorrência acima em O(N) e como cada par (b, c) deve pertencer a A(G'), o algoritmo tem complexidade O(NM).

Porém, calcular g(c, a, b) é a parte mais demorada. A solução mais simples seria enumerar todas as triplas de vértices e processar cada vértice v vizinhança de c, levando a um algoritmo O(N^4), o que dá na ordem de 25 \times 10^9, que é muito lento.

A sacada é usar o fato que c e v devem ser adjacentes, assim como os vértices a e b. Assim, para cada par de arestas e_1 e e_2, supomos e_1 = (c, v) e e_2 = (a, b). Usando uma matriz de adjacência, podemos verificar se v pertence à vizinhança de a e b em O(1), levando a uma complexidade total de O(M^2) ~4M operações. O editorial do Google Code Jam apresenta essa e outras 3 alternativas para pré-computar g(c, a, b). Minha implementação da solução apresentada se encontra aqui.


Algoritmo de Karatsuba

Julho 3, 2011

Depois de bastante tempo, decidi voltar ao problema Scott New Trick, do Facebook Hacker Challenge desse ano. Eu analisei uma solução em um post anterior, no qual também disse que ia estudar a solução usando o algoritmo de Karatsuba.

Entretanto, descobri que o algoritmo de Karatsuba é usado apenas para realizar a multiplicação de polinômios rapidamente, em O(nˆ(log_2(3))) ou aproximadamente O(nˆ1.58). A multiplicação ingênua leva O(nˆ2).

Primeiro vou explicar a solução e depois descrever o algoritmo. Baseei minha análise no código do tomek.

Para relembrar o que o problema pede, cito um parágrafo do post anterior:

Dados dois vetores A e B de inteiros aleatórios, com tamanhos N e M, respectivamente, um primo P e um inteiro 1 ≤ L ≤ P contar quantos índices 1 ≤ i ≤ N e 1 ≤ j ≤ M satisfazem (A[i] * B[j]) mod P < L.

Lembrando que N e M são da ordem de 10,000,000 e P é da ordem de 250,000.

Raíz primitiva módulo P

Dado um inteiro P, dizemos que G é uma raíz primitiva módulo P, se para todo coprimo i de P (i.e. i < P tal que mdc(i, P)=1), existe uma potência de G módulo P que é igual a i, ou seja, existe um inteiro k, tal que Gˆk % P = i, onde k é dito logaritmo discreto de i.

Em particular, se P é primo e G é uma raíz primitiva módulo P, para todo número i de 1 a P-1 existe uma potência de G módulo P igual a i.

Uma maneira de determinar a raíz primitiva módulo P é através do seguinte teorema: um número G é raíz primitiva módulo P se a ordem multiplicativa de G módulo P é .

Em outras palavras, isso quer dizer que se o menor k positivo tal que Gˆk % P = 1, é k = , então G é uma raíz primitiva módulo P. Lembrando que para P primo, o código abaixo determina uma raíz primitiva G, além de calcular gpow[k] = Gˆk % P e gpowinv[k] = x, onde x é tal que Gˆx % P = k.

vector<int> gpow, gpowinv;
void CalcGen(int P){
    gpow.resize(P);
    while(1){
        long long G = rand() % (P - 1) + 1;
        gpow[0] = 1;
        bool ok = true;
        for(int i=1; i<P-1; i++){
            gpow[i] = long long(gpow[i-1])*G % P;
            if(gpow[i] == 1){
                ok = false;
                break;
            }
        }
        if(ok) break; 
    }
    gpowinv.resize(P);
    for(int i=0; i<P; i++) gpowinv[gpow[i]] = i;
}

Esse algoritmo probabilístico fica chutando candidatos a raízes primitivas até encontrar algum que tenha ordem multiplicativa igual a P-1. Não sei ao certo qual a sua complexidade, mas deve ser algo em torno de O(P√P) igual ao algoritmo do post anterior.

Representação por polinômio

Antes de mais nada, vamos supor que os elementos de A e B são menores do que P. Se não for, basta fazer A[i] = A[i] % P que a contagem não mudará.

Vimos no post anterior que podemos guardar os elementos de A e de B em um vetor de frequências de tamanho P de acordo com seu módulo P, como por exemplo fazendo fA[A[i]]++ para todo elemento A[i] de A. Entretanto vimos também que isso leva a um algoritmo O(Pˆ2), o que não passa no tempo.

A sacada é representar A[i] por Gˆx % P, onde x = gpowinv[A[i]] e B[j] por Gˆy % P, onde y = gpowinv[B[j]]. Note que A[i]*B[j] é equivalente a Gˆ(x+y) % P.

Que tal se fizermos nosso vetor de frequências baseado em x e y, por exemplo fA[x]++ e fB[y]++? Então, fA[x]*fB[y] conta quantos pares de elementos A[i] e B[j] existem em A e B, tal que A[i]*B[j] = Gˆ(x+y) % P = gpow[x + y]. Então, se gpow[x + y] < L, existem fA[x]*fB[y] pares que devem ser contados.

Se considerarmos fA e fB como um polinônimo, sendo fA[x] o coeficiente do termo de grau x, e fAB sendo o resultado de fA*fB, então fAB[z] é a soma de todos os coeficientes fA[x]*fB[y] tais que x+y=z, ou seja, fAB[z] conta todos os pares A[i] e B[j] tais que A[i]*B[j] = Gˆz % P.

O problema se reduz a contar a quantidade fAB[k] para todo k tal que gpow[k % (P-1)] < L. Observe que o módulo deve ser P-1 pois o período de Gˆk % P é P-1, ou seja, gpow[k] = gpow[k + P-1].

Algoritmo de Karatsuba

O algoritmo de Karatsuba é baseado em divisão e conquista. Dado um polinômio na forma:

Dado m = n/2, podemos representá-lo como:


ou de forma compacta por . Multiplicar dois polinômios x e y é então dado por:

Chamando de

(i)
(ii)

é possível mostrar a seguinte relação:

(iii)

Podemos multiplicar recursivamente para calcular (i), (ii) e a primeira multiplicação de (iii). A complexidade da recorrência é 3O(n/2) + cn, o que no total, usando o teorema mestre, é .

A multiplicação resultante é dada por:

Segue uma implementação em C++. Ela supõe que o vetor de entrada tem o tamanho que é uma potência de 2. Isso não é uma restrição muito forte, pois podemos completar o polinômio com zeros até que o tamanho satisfaça a restrição.

/**  
 * Karatsub algorithm. Fast multiplication of the first n
 * positions of fa and fb.
 * PS. Assumes n is power of 2 
 **/
void Karatsuba(int n, i64 *fa, i64 *fb, Poly &fab)
{
    int m = n/2;
    /* Base */ 
    if(n <= 16){
        fab.assign(2*n - 1, 0);
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                fab[i+j] += fa[i]*fb[j];
        return;
    }
    Poly z0, z1, z2, tmp;
    /* Find z0 and z2 recursively */
    Karatsuba(m, &fa[0], &fb[0], z0);
    Karatsuba(m, &fa[m], &fb[m], z2);
    /* Find z1 recursively */
    Poly fai(m), fbi(m);
    for(int i=0; i<m; i++){
        fai[i] = fa[i] + fa[i+m];
        fbi[i] = fb[i] + fb[i+m];
    }
    Karatsuba(m, &fai[0], &fbi[0], z1);
    for(int i=0; i<z1.size(); i++)
        z1[i] -= (z0[i] + z2[i]);
    /* Merge z0, z1 and z2 in fab */
    fab.assign(2*m + z2.size(), 0);
    for(int i=0; i<z0.size(); i++){
        fab[i] += z0[i];
        fab[i+m] += z1[i];
        fab[i+2*m] += z2[i];
    }
}
/* Example of calling */
Karatsuba(fa.size(), &fa[0], &fb[0], fab);

O código completo encontra-se aqui.

Conclusão

No final das contas o algoritmo de Karatsuba era apenas uma maneira de resolver um problema conhecido (multiplicação de polinômios) de maneira rápida.

Achei a solução muito interessante de se transformar o domínio do problema para que ele possa ser resolvido de maneira mais eficiente. Isso me lembra a transformada de Fourier, mas como não sei muito sobre o assunto, posso estar enganado.


Seletiva Interna da Maratona Unicamp 2011

Junho 19, 2011

O prova da seletiva aconteceu ontem, 18 de Junho. Esse ano conseguimos realizar a seletiva da maratona mais cedo. Essa sempre foi a ideia, já que esperávamos que com times formados, os alunos estivessem mais motivados a treinar nas férias.

Apesar se não estar ajudando com o treinamento, ajudei com a organização da prova, escolhendo alguns dos problemas e ficando de fiscal.

Dos competidores

Foram 23 participantes, sendo que decidimos formar por enquanto apenas 3 times. O restante dos times (2 ou 3) serão formados com base na dedicação, mas ainda não decidimos como será a seleção.

A motivação para essa nova regra é que com base em anos passados, temos que os competidores dos primeiros times são já mais experientes e comprometidos com treinamentos, enquanto o restante era um pessoal mais novo na maratona e muitos desaparecem após a regional. No fim das contas, o intuito de formar os times adicionais é justamente manter os novos competidores motivados para se tornarem bons maratonistas nos anos seguintes.

Competidores

A classificação foi a seguinte (número de problemas entre parênteses):

  1. Marcelo Póvoa (9)
  2. Douglas Santos (8)
  3. Bruno Crepaldi (7)
  4. Igor Wolff (7)
  5. Ruan Silva (6)
  6. Thiago Cavalcante (6)
  7. Patrícia Hongo (5)
  8. Mauro Lopes (4)
  9. Gabriel Borges (4)
  10. Victor Pompêo (3)

Comentários gerais: O Mauro desistiu por não ter tempo para treinar e então o Victor Pompêo entrou para o terceiro time.

O Marcelo, que fechou a prova, é de longe o competidor mais experiente. Ao escolhermos os problemas da prova consideramos a possibilidade dele fechá-la, mas nosso objetivo mesmo era classificar os outros competidores e por isso os problemas da prova estavam relativamente fáceis.

A briga esse ano ficou entre o Douglas, Bruno, Igor, Ruan e Thiago. Eles estiveram empatados por um tempo, até que o Douglas, Bruno e Igor despontaram no final da prova.

A revelação foi o Gabriel Borges. Me disseram que ele é bixo, mas não sei se é da Ciência ou Engenharia.

Competidores 2

Dos problemas

Os problemas foram selecionados do SPOJ:

Os problemas mais fáceis eram para ser o “To and Fro” e “Army Strength”; Os médios-fáceis eram “Rectangles”, “Street Parade” e “Sorting Bank Accounts”; Os médios-difíceis eram “Distinct Subsequences”, “Cow Cars”, “Cleaning Robot” e “Subset sum”. No final a única diferença foi que o “Rectangles” era mais fácil do que imaginávamos e o “Army Strength” mais difícil.

Além disso, o problema City Game estava entre os problemas originais da prova mas tivemos que remover. A razão é que incluímo-no antes de implementá-lo. Nossa ideia era que uma programação dinâmica O(n^3), explicada em um treino, passasse, mas vimos que os limites exigem um algoritmo O(n^2). Não é ruim que o problema seja mais difícil do que imaginávamos, mas é péssimo o fato de que podíamos ter induzido quem foi no treino a perder tempo com uma solução que estouraria o tempo.

Do futuro

Até agora era o Igor quem estava conduzindo os treinos, mas em breve ele irá fazer um estágio no Facebook (o processo começou na seletiva do ano passado :) e defender antes do final do ano. Com isso, o Mário César, do LOCo, assumirá o cargo de técnico. Embora não tenha experiência na maratona, o Mário é doutorando em Teoria de Computação e conhece vários tópicos importantes vistos na maratona. Além do mais, ele tem acompanhado o Igor nos treinamentos para se familiarizar com a maratona, principalmente a parte de programação.

Mário, o novo coach

Vamos torcer para que a Unicamp se classifique para o mundial esse ano, que será em Varsóvia, Polônia!