Editorial #2

Tive um tempo e resolvi comentar mais dois problemas bem legais. Eles estão disponíveis no URI Online Judge, mas são da prova da maratona de programação ACM/ICPC South America Contest 2007:

URI 1365: Procurando Assentos / Finding Seats (link para o problema)

URI 1364: Emoticons :-) (link para o problema)

No primeiro problema, temos um tabuleiro retangular RxC, e cada posição do tabuleiro pode estar ocupada ou não. Queremos achar o menor retângulo que contém pelo menos K elementos.

Vamos usar uma matriz M que armazena, para cada posição (i, j) do tabuleiro, o número de elementos no retângulo (1 - i) x (1 - j). Por exemplo, no primeiro exemplo, M[2][5] = 5 e M[3][3] = 6, e é fácil ver o porquê.

M[2][4] = 5 já que há 5 pontos na área azul

M[3][3] = 6 já que há 6 pontos na área verde

Para montar a matriz, basta ver que:
 

A gente consegue descobrir a matriz em ordem de O(RxC). Beleza! Tendo a matriz, conseguimos descobrir quantos elementos há em qualquer retângulo. Por exemplo, se queremos saber quantos tem no retângulo (2-3)x(3-4):

A interseção dos retângulos azuis é considerada duas vezes e deve ser descontada

OK, quase lá. Como queremos achar o menor retângulo com pelo K elementos, podemos testar todos os retângulos possíveis, certo? Se N é o lado do tabuleiro, seriam N⁴ possibilidades... 300⁴ > 10⁹, o que estoura o tempo.

Na verdade, há como otimizar isso. Por exemplo, para cada retângulo (?-i)x(c-j) da matriz, não precisamos testar todos os valores possíveis de ?, apenas o valor tal que (?-i)x(c-j) tenha a menor área que contém K elementos. Nesse caso, só precisamos testar os trios (i, j, c) e teremos algo próximo de N³

Confuso? Imagina que buscamos K = 3 no primeiro exemplo, e que queremos checar todos os retângulos que tem como cantor inferior direito (3,3) (ou seja, i = 3, j = 3, variando c).

A grande vantagem é que o valor de '?' varia pouco cada vez que variamos C. Então, só precisamos checar todos os pontos (i,j) e para cada um, variar C e computar a menor área possível, ou seja, crescer ou decrescer '?' em relação ao valor anterior até o máximo permitido. Quando M[i][j] < K, não precisamos testar para essa posição.

Vamos para o segundo problema. :-)

Este é mais intuitivo. Temos uma lista de emoticons e um texto, e temos que trocar o menor número possível de caracteres do texto por espaços de forma a remover todos os emoticons. Podemos usar uma técnica gulosa (fazer a decisão que parece ser a melhor no momento). O limite de tempo é 3 s e são poucos emoticons, então tempo não é uma preocupação.

Marcamos todos os caracteres que terminam um emoticon. No primeiro exemplo da entrada, são ')' '(' ':'. Cada vez que encontramos um caractere destes no texto, checamos se a parte anterior da string é um emoticon. Se sim, trocamos o caractere por espaço e computamos +1. Se não, continuamos.

Testando o algoritmo no segundo exemplo da entrada, teríamos:

Espaços indicam os caracteres que retiramos, que totalizam 8

Um dos jeitos de fazer isso é manter uma lista ordenada dos emoticons ao contrário, e quando acharmos um caractere "fim de emoticon" no texto, damos uma procurada na lista pelas letras que antecedem.

Uma coisa que pode fazer quebrar a cabeça é que não dá certo marcar o primeiro caractere do emoticon. Por exemplo, imagine que temos os emoticons 1234 e 23. Se o texto é 1234 e fazemos o algoritmo buscando pelo primeiro caractere, iríamos ter que remover dois números, enquanto pelo fim, só removemos o número 3.

Até mais!