1ª Maratona de Programação do Sul - Editorial

Comentário do autor do problema: Ricardo Pfitscher

Este problema é bem simples. Basta procurar por cada sobrenome e contar a quantidade de não-vogais consecutivas. Ao chegar em número maior ou igual a 3 aquele sobrenome é díficil. O ponto de atenção é a primeira letra que é maiúscula (atenção ao caso) e que algumas vogais podem ter acento, assim, são consideradas consoantes.

Comentário do autor do problema: Leandro Zatesko

Seja \(f_i\) o fator de flutuação ref. ao \(i\)-ésimo ano, i.e.

\begin{equation*} f_i = 1 + F_i / 100\,. \end{equation*}

Assim, o fator de flutuação ref. ao período de dois anos é dado por \(f_1 \times f_2\) e, portanto, a resposta é ser impressa é dada por

\begin{equation*} (f_1 \times f_2 - 1) \times 100 . \end{equation*}

Comentário do autor do problema: Ricardo Pfitscher

Este problema consiste em utilizar o conceito de lista circular, diminuindo a capacidade da garrafa térmica a cada passo de iteração.

Atenção aos competidores que tendem a utilizar o resto da divisão, o que é válido. Nesse caso, é preciso ajustar as casas decimais e depois calcular a quantidade restante na térmica.

Comentário do autor do problema: Ricardo Pfitscher

A solução deste problema passa pelo mapeamento das relações de parentesco em um grafo direcionado.

Depois, o programador pode realizar uma ordenação topológica com busca em profundidade e verificar se os dois animais da linha de teste estão na mesma ordem. Outra opção é executar uma busca em profundidade a partir de cada animal do grafo gerando uma lista de animais explorados, caso os dois animais do teste estiverem no resultado da exploração, então, eles são parentes.

Comentário do autor do problema: Alesom Zorzi

Basicamente a ideia do problema é percorrer todos os genomas e descobrir a maior sequência que está presente em ao menos uma poupulação, de forma gulosa mesmo.

Na minha solução eu utilizei bitmask para salvar os conjuntos e não precisar percorrer todas as populações.

Comentário do autor do problema: Leandro Zatesko

Comentário do autor do problema: Leandro Zatesko

Vamos primeiro considerar a seguinte solução, ingênua, para o problema. Para cada uma das \(\leq N^2\) posições livres do tabuleiro, podemos simular o movimento de uma dama partindo daquela posição em cada uma das 8 direções possíveis, contando quantas direções estão livres, i.e. em quantas direções conseguimos mover até a borda do tabuleiro sem encontrar pinhão algum. Deste modo, conseguimos descobrir quantos pinhões uma dama colocada em cada casa livre do tabuleiro atacaria. Então, basta tomar o máximo dos valores calculados sobre todas as casas, e temos a resposta procurada. No entanto, a simulação do movimento da dama em cada uma das 8 direções possíveis custa tempo \(O(N)\), e, portanto, esta solução tem complexidade \(O(N^3)\). Como \(N \sim 10^3\), esta solução não passa no limite de tempo..

Para cada linha, cada coluna, e cada diagonal do tabuleiro, criemos um vetor das posições daquela linha/coluna/diagonal em que há pinhões. É possível criar esses vetores todos numa única varredura linear sobre o tabuleiro, i.e. em tempo \(O(N^2)\). Depois, vamos considerar cada uma das posições livres do tabuleiro, numa segunda varredura linear. Para cada posição considerada, onde queremos simular o posicionamento de uma dama, basta ver quais vetores de linha, de coluna, de diagonal ascendente, e de diagonal descendente intersectam aquela posição. Assim, tudo o que precisamos fazer, para cada um desses 4 vetores considerados, são os seguintes testes: se o vetor é vazio; se é não-vazio e a posição onde estamos simulando posicionar a dama é menor\(^{\ast}\) que a primeira posição gravada no vetor; se é não-vazio e a posição onde estamos simulando posicionar a dama é maior\(^{\ast}\) que a última posição gravada no vetor. Todos esses testes podem ser feitos em \(O(1)\), o que faz com que o tempo total da solução seja linear no tamanho da entrada, i.e. \(O(N^2)\).

\(^{\ast}\) menor/maior de acordo com a ordem das posições naquela linha/coluna/diagonal sob a qual foi construído o vetor correspondente.

Veja que não é necessário, na verdade, armazenar todo o conteúdo de cada vetor, sendo relevantes apenas o primeiro e o último elementos. No entanto, armazenar o vetor todo ou só o primeiro e o último elementos não faz diferença na eficiência da solução, assintoticamente. Fica a cargo daquilo que o programador acha mais fácil de codificar.

Comentário do autor do problema: Cristhian Bonilha

Vamos definir a função \(f(T)\) como a quantidade de views que o vídeo recebeu até o momento \(T\). É possível notar que essa função é não-decrescente, ou seja, se \(A < B\), então \(f(A) \leq f(B)\).

Isso é o suficiente para que possamos usar a técnica de busca binária para encontrarmos o menor momento em que a quantidade de views seja maior ou igual a \(K\).

Para calcular \(f(T)\), basta iterar sobre todas as pessoas e calcular quantas vezes ela já assistiu o vídeo no momento \(T\), que é igual a:

\begin{equation*} \left\{ \begin{aligned} & 0\,,&&\text{se \(T < a_i\);}\\ & 1 + \Bigl\lfloor\frac{T - a_i}{b_i}\Bigr\rfloor\,,&&\text{se \(T \geq a_i\).} \end{aligned}\right. \end{equation*}

A complexidade desta solução é \(O(N \ast \lg Q)\), onde \(Q\) representa o intervalo de busca. O intervalo \([1, 2\ast 10^{18}]\) é suficiente. Como \(\lg Q\) é uma constante, pode-se dizer que a complexidade é \(O(N)\).

Note que, dependendo da entrada e do valor \(T\), o resultado de \(f(T)\) pode ultrapassar os limites de uma variável long (\(2^{64}\)). Logo, ao calcular \(f(T)\), se o valor ultrapassar \(K\), evite continuar com o cálculo antes que dê overflow.

Comentário:

TBA

Comentário do autor do problema: Maicon Zatelli

A ideia para resolver o problema é aplicar o princípio da inclusão–exclusão de teoria dos conjuntos para remover as sobreposições de divisores e "percorrer" rapidamente o intervalo de até 1 bilhão por meio de soma de termos de uma progressão aritmética. Não devem ser aceitas soluções que tentem percorrer o intervalo de \(I\) até \(F\) de maneira trivial.

Comentário do autor do problema: Gabriel Galli

Resumidamente, a solução do problema é calcular o fecho convexo formado pelos planetas e verificar se o asteroide está dentro, exatamente em uma das arestas, ou em um dos pontos do polígono formado pelo fecho convexo. É importante perceber que o Sol é um vértice válido do fecho convexo, apesar de não ser dado na entrada. Mas pela descrição do problema e pelos cálculos que se precisa fazer (que são relativos ao Sol, mas não são dadas as coordenadas dele), deduz-se que ele se encontra em \((0, 0)\). Somando a isso o fato de o número mínimo de planetas ser 2, basta imaginar um triângulo entre os planetas e o Sol que é facilmente perceptível a validade dessa configuração perante o que é pedido.

Não precisamos guardar todos os planetas, mas sim os pontos que eles representam no plano cartesiano. Assim, ao ler cada planeta da entrada podemos já calcular as coordenadas \((x, y)\), convertidas das coordenadas polares, e guardar o respectivo ponto encontrado. Para isso, foi utilizado busca binária no intervalo de zero ao dobro da anomalia média para encontrar a anomalia excêntrica. O resto é calculado a partir das fórmulas apresentadas na descrição do problema e de fórmulas conhecidas de elipse.

Note que, por causa da precisão do double, as funções \(sin()\) e \(cos()\) não retornam exatamente 0.0 quando o retorno deveria ser 0.0. Então precisamos checar se elas retornaram 0.0 dentro do erro \(EPS\) estabelecido (\(10^{-9}\)) e aí atribuir 0.0 às respectivas variáveis. Dessa meneira, fazemos com que elas percam esses erros de precisão que causariam WA no futuro devido às multiplicações que aumentam esse erro (apenas no caso do sin(), aqui, entretanto). Na busca binária para resolver a Equação de Kepler, isso não é necessário porque a multiplicação é com algo entre 0 e 1. Todas as operações de comparação com as variáveis double estão sendo feitas com macros que consideram esse erro \(EPS\).

O algoritmo para encontrar o fecho convexo é o mesmo encontrado no livro dos Halim, com algumas alterações para atender as condições do problema:

• o uso do \(EPS\), para tratar aqui também os erros de precisão do double;
• sempre retornar um fecho vazio caso tenhamos menos que três pontos no vetor passado como referência, ou ele tenha três pontos e eles sejam colineares, ou todos os pontos são colineares. No caso de três pontos não colineares, os Halim readicionam o ponto 0 ao fim do vetor e retornam ele mesmo. Entretanto, precisamos garantir que os pontos estão ordenados para o código que verifica se um ponto está dentro de um polígono funcione, então deixo esse caso ser executado normalmente.

Para verificar se um ponto está dentro de um polígono, os Halim utilizam a função que funciona para qualquer polígono somando os ângulos e verificando se encontramos \(2 \ast PI\). Entretanto, o método para polígonos convexos que apenas verifica se o ponto está sempre à esquerda do vetor definido por dois pontos consecutivos do fecho convexo é suficiente para este problema.

Foram utilizados os seguintes sites como referência e apoio no desenvolvimento deste problema:

• https://en.wikipedia.org/wiki/Kepler's_laws_of_planetary_motion#Position_as_a_function_of_time
• https://en.wikipedia.org/wiki/Eccentricity_(mathematics)#Ellipses
• http://mathworld.wolfram.com/KeplersEquation.html (veja que há um gráfico mostrando a relação entre M e E: uma curva nunca decrescente).

Comentário do autor do problema: Leandro Zatesko

Suponhamos que os valores de \(H_i\) para todo \(i\) já estejam computados (discutiremos sobre isso na sequência). A primeira coisa a se observar sobre este problema é a evidente propriedade gulosa que tem sua estrutura combinatória. Seja \(N(i)\) o conjunto de todas as Anciãs para as quais a Anciã \(i\) pode enviar uma mensagem diretamente (num único voo). Seja também \(nxt[i]\) (\(pre[i]\)) o menor (maior) índice \(j > i\) (\(j < i\)) tal que \(H_j > H_i\), i.e. o "Next (Previous) Greater Element" de \(i\), definindo \(nxt[i] = n + 1\) (\(pre[i] = 0\)) caso não haja tal \(j\). Os arrays \(nxt[]\) e \(pre[]\) podem ser computados através de uma varredura linear cada um, com o auxílio de uma pilha. Como \(N(i)\) coincide com o intervalo inteiro fechado entre \(nxt[i]\) e \(pre[i]\), podemos observar que \(N(nxt[i])\) inclui \(N(i) \setminus \{pre[i]\}\) e que \(N(pre[i])\) inclui \(N(i) \setminus \{nxt[i]\}\). Desta propriedade de inclusão de vizinhanças segue a propriedade gulosa: se a Anciã \(i\) quer enviar uma mensagem para a Anciã \(j > i\) (\(j < i\)) e \(j \notin N(i)\), então sempre compensa que no primeiro voo a Gralha-Azul leve a mensagem para a Anciã \(k\) que "enxergue o mais longe possível", i.e. para a qual o maior (menor) valor em \(N(k)\) seja o maior (menor) possível.

Consideremos, então, uma query "\(i\quad j\)", supondo que \(j > i\) (o caso \(j < i\) é simétrico). Alguém poderia erroneamente concluir que o problema se resume a encontrar o menor valor de \(\ell\) tal que \(nxt^l[i] \geq j\), sendo \(nxt^l[i]\) definido por: \(nxt^1[i] = nxt[i]\); \(nxt^{\ell}[i] = nxt[nxt^{\ell - 1}[i]]\) para \(\ell > 1\). No entanto, o exemplo discutido no enunciado do problema já evidencia que essa estratégia nem sempre é ótima, pois às vezes pode compensar fazer com a Gralha-Azul voe para \(pre[i]\), quando \(pre[i]\) "enxerga mais longe" que \(nxt[i]\). Redefinindo \(nxt^{\ell}[i]\) como abaixo, contudo, a estratégia funciona:

\begin{align*} nxt^1[i] &= nxt[i]\,;\\ nxt^{\ell}[i] &= \max(nxt[nxt^{\ell - 1}[i]], nxt[pre^{\ell-1}[i]]),\quad \text{para }\ell > 1\,. \end{align*}

Simetricamente:

\begin{align*} pre^1[i] &= pre[i]\,;\\ pre^{\ell}[i] &= \min(pre[nxt^{\ell - 1}[i]], pre[pre^{\ell-1}[i]]),\quad \text{para }\ell > 1\,. \end{align*}

Isto é, sob estas definições, o problema de fato se resume, para cada query "\(i\quad j\)" com \(j > i\) (\(j < i\)), a encontrar o menor valor de \(\ell\) tal que \(nxt^{\ell}[i] \geq j\) (\(pre^{\ell}[i] \leq j\)). Temos, no entanto, \(8\times 10^4\) queries para responder. É de se supor que, em casos extremos, o menor valor de \(\ell\) que estamos procurando seja linearmente proporcional a \(N\). Assim, não podemos nem nos dar ao luxo de encontrar esse valor de \(\ell\) em tempo \(O(N)\) por query, nem tampouco querer precomputar uma tabela de tamanho \(O(N^2)\) relacionando todas as Anciãs com todos os valores possíveis de \(\ell\). Uma estratégia possível (provavelmente não a única) para responder eficientemente às queries, contudo, é usar a técnica de "salto binário" (Binary Lifting), precomputando (iterativamente e de modo bottom–up, com o laço mais externo em \(\ell\)) as tabelas para \(nxt\) e \(pre\) de modo que cada entrada \(nxt[\ell][i]\) represente não \(nxt^{\ell}[i]\), mas \(nxt^{2^{\ell}}[i]\). Assim, cada query pode ser respondida em tempo \(O((\lg N)^2)\).

Para calcular os valores \(h_i\) (e assim obter os valores \(H_i = h_i + a_i\)), o recomendado é utilizar o Autômato de Aho–Corasick. Há de se tomar um cuidado, no entanto. Em muitas implementações do autômato encontradas na Internet, o que se faz, durante o processamento do texto, é: a cada nó visitado, navegar pelos links de saída (exit links) incrementando o número de ocorrências de todas as palavras do dicionário gravadas nesses nós. Isso faz com que a complexidade de construção do autômato mais a complexidade de processamento do texto seja linear na soma dos seguintes números: o tamanho total das palavras do dicionário; o tamanho do texto; o número total de pares \((w, i)\) sendo que \(w\) é uma palavra do dicionário que ocorre na posição \(i\) do texto. Com esta implementação provavelmente não seja possível passar no limite de tempo do problema, mas há como facilmente trocar o número total de pares \((w, i)\) como especificado pelo número total de pares \((u, i)\) sendo que \(u\) é um nó do autômato e todas as palavras do dicionário gravadas no nó \(u\) ocorrem na posição \(i\). Para tanto, basta colocar um contador dentro do nó e incrementar apenas esse contador durante o processamento do texto. Assim, ao final do processamento, é possível percorrer o autômato linearmente propagando os valores dos contadores dentro de cada nó a todas as palavras do dicionário gravadas naquele nó.

Comentário do autor do problema: Leandro Zatesko

Apesar de o enunciado deste problema, à primeira impressão, remeter a alguma variante do problema de dominação em grafos, o fato de que toda província possui exatamente uma província-irmã, podendo apenas no máximo uma delas receber um diretório, permite-nos modelar o problema como uma variante do problema da satisfazibilidade booleana (SAT). Podemos supor, sem perda de generalidade, que, para cada par de províncias-irmãs, exatamente uma delas recebe um diretório, pois, se há alguma solução válida para o problema em que ambas as províncias de um par de províncias-irmãs ficam sem receber diretório, então atribuir arbitrariamente um diretório para uma delas não altera a viabilidade da solução. Formamos, então, uma fórmula booleana na forma normal conjuntiva da seguinte maneira:

1. Associamos a cada par de províncias-irmãs uma variável \(x\) das \(N\) variáveis da fórmula, sendo uma das duas províncias associada ao literal \(x\), e a outra ao literal \(\neg x\);
2. Para cada província \(i\), criamos uma cláusula na fórmula que contém o literal associado a \(i\), o qual chamaremos da cabeça da cláusula, e os 6 literais correspondentes às províncias diretamente alcançáveis a partir de \(i\), compondo o que chamaremos de cauda da cláusula.

Nosso objetivo é encontrar uma valoração das variáveis da fórmula que, para cada cláusula \(C\), satisfaça a cabeça de \(C\), ou então satisfaça ao menos dois literais da cauda de \(C\). Não só é garantida a existência de tal valoração pelo enunciado do problema, como também é prometido que existe uma valoração \(T^{\ast}\) que, para cláusula \(C\), satisfaz a cabeça de \(C\) e ao menos três literais da cauda de \(C\), ou então satisfaz ao menos quatro literais da cauda de \(C\).