Clube de Programação - Help

Comentário por Fernando Kiotheka

Use busca binária dando preferência ao uso de inteiros.

Comentário por Fernando Kiotheka

Conceito de definição recursiva de uma sequência, fácil

Mais: [HaHa13] p. 80

[HaHa13] p. 208

[HaHa13] p. 225

[HaHa13] p. 186

[HaHa13] p. 137

[HaHa13] Sec. 9.25

Comentário por Prof. Ricardo Oliveira (UTFPR), autor do problema

Primeiramente, é importante notar que, ao adicionar uma letra a uma string, as demais strings do jogo não são alteradas. Logo, as strings são independentes entre si. O jogo pode então ser decidido da mesma maneira que o jogo NIM, onde as strings são análogas às pilhas do jogo. O grundy number de cada string é calculado separadamente, e o grundy number do jogo inteiro é dado pelo XOR dos grundy numbers de cada string. O primeiro jogador (no caso, Tyrion) perde se e semente se o grundy number resultante for igual a zero.

Para calcular os grundy numbers de cada string, é necessário construir a árvore de estados do jogo. Para tal, constrói-se antes a estrutura de Aho-Corasick com os adjetivos dados. Então, cada estado da árvore de jogo é dado por um par \([u][f]\), onde \(u\) é um nó da estrutura de Aho-Corasick e \(f\) é a quantidade de letras que ainda podem ser colocadas na string. Se \(f=0\) ou se o nó \(u\) é um nó terminal, o estado \([u][f]\) não tem filhos, pois ou não é possível adicionar mais letras a esta string, ou ela contém um adjetivo. Caso contrário, o estado terá \(L\) filhos, um para cada possível letra adicionada à string. O filho do estado \([u][f]\) referente à adição da letra \(l\) será o estado \([u'][f-1]\), onde \(u'\) é o nó da estrutura de Aho-Corasick resultante do processamento da letra \(l\) a partir do nó \(u\).

Por fim, o grundy number de um estado sem filhos é \(0\). O grundy number de um estado com filhos é dado pelo menor natural excluído (MEX) dos grundy numbers de seus filhos.

A complexidade esperada da solução é \(O(T*L*max{F_i})\) (\(+\) entrada), onde \(T\) é igual a soma dos tamanhos dos adjetivos dados.

Algumas leituras interessantes:

• http://letuskode.blogspot.com.br/2014/08/grundy-numbers.html
• https://www.cs.ox.ac.uk/files/2735/Composite_games.pdf
• https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

Assumamos sem perda de generalidade que estamos trabalhando com uma permutação \(\pi\) de \(\{1,\dotsc,n\}\) tomada sob distribuição uniforme (o problema garante que você pode assumir que os inteiros no array são todos distintos, o que facilita). Seja \(X\) a variável aleatória que assume o número de inversões numa dada permutação \(\pi\), i.e. o número de pares \((i,j)\) tais que \(i < j\) e \(\pi(i) > \pi(j)\). É óbvio que o que o problema pede, o número esperado de trocas do Bubble Sort para ordenar \(\pi\), é \(\mathbb E(X)\), i.e. o valor esperado de \(X\). Sendo \(Y_{ij}\) a variável aleatória que assume o valor 1 se o par \((i,j)\) é uma inversão, ou 0 caso contrário, temos obviamente que

\begin{equation*} \mathbb E(X) = \mathbb E\biggl(\sum_{i}\sum_{j>i} Y_{ij}\biggr). \end{equation*}

Da linearidade da esperança:

\begin{equation*} \mathbb E(X) = \sum_{i}\sum_{j>i} \mathbb E(Y_{ij}). \end{equation*}

Deixo como exercício você continuar as contas e fechar uma fórmula \(O(1)\) em função de \(n\) para \(\mathbb E(X)\).

• Complexidade: \(O(1)\) para o cálculo de \(E(X)\) (denominador e numerador) \(+\) \(O(\log n)\) para o Algoritmo de Euclides (para simplificar a fração).

Se fixamos um \(N\) e um \(A\in\{1,N\}\), o número de pares \((A,B)\) tais que \(B>1\) e \(B\leq N\bmod A\) é obviamente \(N\bmod A\). Então, o que o problema pede, dado \(N\), é simplesmente a fração \(\rho(N)/N^2\), simplificada usando o Algoritmo de Euclides (Cuidado, porque a resposta pode não caber em 32 bits!), sendo \(\rho(N)=\sum_{i=1}^N(N\bmod i)\). Como \(N\leq 10^8\), computar \(S(N)\) de um modo ingênuo é inviável, mesmo que a entrada consistisse de um só caso de teste. Vamos precisar manipular \(\rho(N)\) um pouco.

Primeiro observemos que \((N\bmod i) - ((N-1)\bmod i)\) é: \(1\), se \(i\) não divide \(N\); \(1-i\), caso contrário. Assim, tentando estabelecer uma recorrência para \(\rho(N)\) (lembrando que \(\sigma(N)\) é a soma dos divisores de \(N\)):

\begin{gather*} \rho(N)-\rho(N-1) = \sum_{i\text{ não divisor de }N}1 +\sum_{i\text{ divisor próprio de }N}(1-i) = \sum_{i=1}^{N-1}1-\sum_{i\text{ divisor próprio de }N}i\\ = N - 1 - \sum_{i\text{ divisor de }N}i + N = 2N - 1 - \sigma(N) \end{gather*}

Então, a recorrência é: \(\rho(N) = 2N-1-\sigma(N)+\rho(N - 1)\). Resolvendo:

\begin{equation*} \rho(N) = \sum_{i=1}^N(2i-1-\sigma(i)) =2\sum_{i=1}^Ni-N-\sum_{i=1}^N\sigma(i)=N^2-\sum_{i=1}^N\sigma(i) \end{equation*}

Então, nosso problema agora se resume a computar \(\sum_{i=1}^N\sigma(i)\). Uma vez computada essa soma, podemos obter \(\rho(N)\) em \(O(1)\). Deixo a cargo de vocês agora pesquisar como calcular essa soma em tempo \(O(\sqrt N)\) ;)

• Complexidade: \(O(\sqrt N)\)

Comentário por Prof. Ricardo Oliveira (UTFPR), autor do problema

O problema pode ser resolvido por programação dinâmica. Cada estado consiste apenas de um soldado \([u]\), e responde o tamanho da maior sequência terminando nele. Seu cálculo é dado por \(1 + \max(PD[u'])\), onde \(u'\) é um soldado posicionado a sudoeste de \(u\) e é mais forte que \(u\).

Entretanto, o cálculo de cada estado não pode ser feito em tempo linear em \(N\), uma vez que isto tornaria todo o algoritmo quadrático em \(N\).

Entretanto, é possível manter um conjunto \(S\), tal que, quando o estado \([u]\) for visitado, \(S\) contém exatamente todos os soldados mais fortes que \(u\). Para tal, é possível inverter o grafo dado (i.e. criar um arco \(i\to j\) quando \(i\) é mais fraco que \(j\)). Note que este grafo é uma floresta. É feita então uma busca em profundidade (DFS). Quando o vértice \(u\) for visitado, o conjunto \(S\) será dado pelos vértices atualmente na pilha. Logo, um vértice deve ser incluído em \(S\) ao ser empilhado, e removido de \(S\) ao ser desempilhado.

Por fim, é necessário, em cada estado \([u]\), consultar os vértices que estão em \(S\) e que estão a sudoeste de \(u\). Isto pode ser feito com uma árvore de segmentos 2D. As respostas dos estados \([u']\) são inseridas (removidas) da estrutura quando o vértice é inserido em (removido de) \(S\). O máximo das respostas dos vértices a sudoeste de \(u\) é dado pela consulta pelo retângulo \([-400,-400,x[u]-1, y[u]-1]\).

Embora a Quad-tree também possa ser utilizada, sua constante é consideravelmente maior que a árvore de segmentos, o que pode ocasionar em TLE, dependendo da implementação.

• Complexidade: \(O(N\log^2(800)) = O(N)\) considerando uma constante.

[HaHa13] p. 293

[HaHa13] p. 208

[HaHa13] p. 228

[HaHa13] p. 328

[HaHa13] p. 323

[HaHa13] p. 328

[HaHa13] Sec. 5.7

[HaHa13] Sec. 6.6.5

[HaHa13] p. 72

Como as dimensões do grid são pequenas e o número de cores também, podemos atacar o problema com força-bruta, tendo alguns cuidados para podar o backtracking e evitar um Time Limit Exceeded. As estratégias de poda listadas a seguir são suficientes para fazer o código passar:

• Sendo \(min_k\) o menor número de cliques descoberto até o momento que torna a configuração inicial do jogo monocromática, se o número \(k\) de cliques já feitos não é menor que \(min_k\), podemos podar o ramo corrente do backtracking.
• Quando a escolha de uma cor para recolorir a componente em que se encontra a casa \((0,0)\) não aumenta o número de casas da componente, podemos podar o ramo corrente do backtracking para explorar outras cores (as operações de recoloração podem ser feitas através de uma DFS simples).
• Quando uma cor não ocorre na vizinhança da componente em que se encontra a casa \((0,0)\), não precisamos explorá-la agora, pois ela certamente não aumentará o número de casas da componente.

[HaHa13] p. 77 Tip 5

[HaHa13] Sec. 3.2.2 e 8.2.1

Comentário por Diego Rangel (UFMG)

Use um array de diferenças (link1, link2) ao invés de uma árvore de segmentos ou uma BIT.

Comentário por Diego Rangel (UFMG)

Seja \(T\) uma árvore geradora mínima de \(G\). Para toda aresta \(e = (uv)\) de \(E(G)\) queremos saber qual é a árvore geradora mínima que contém \(e\). Se fizemos \(T+\{e\}\) teremos um ciclo então precisamos remover alguma aresta de \(T\) para manter uma árvore e ainda que seja mínima que contenha \(e\), note que quando inserirmos \(e\), temos que remover alguma aresta do caminho de \(u, v\) então basta remover a maior aresta do caminho de \((u, v)\) para obtermos a árvore que queremos. A melhor mst que contém a aresta \(e\) é \(T-fmax(u,v)+e(uv)\), onde \(f\) é uma função que retorna a maior aresta do caminho de \(u,v\). Dica de como processar a maior aresta entre cada par: tente resolver com o lca usando Binary Lifting, pense na recorrência do cálculo do parent de cada vértice.. caso não consiga: https://www.geeksforgeeks.org/query-to-find-the-maximum-and-minimum-weight-between-two-nodes-in-the-given-tree-using-lca/

[HaHa13] Sec. 4.2.4

Por Combinatória básica (Princípio Multiplicativo), é fácil mostrar que, sendo \(p_1^{m_1}\dotsb p_k^{m_k}\) a decomposição em fatores primos de \(N\), o número de divisores de \(N\) pode ser dado por:

\begin{equation*} (m_1+1)(m_2+1)\dotsb(m_k+1) \end{equation*}

Assim, para resolver este problema, precisamos:

1. gerar todos os primos no intervalo \([2..10^7]\) através do Crivo de Eratóstenes;
2. fatorar \(N\) para descobrir a multiplicidade \(m(p)\) de cada primo \(p\) na decomposição do inteiro \(N\) (note que, se \(p\) não aparece na decomposição de \(N\), então, \(m(p)=0\); observe ainda que \(\sqrt{N}\leq 10^6\), o que significa que os primos que geramos são suficientes para a decomposição de \(N\), pois, se esgotarmos todos os primos gerados pelo Crivo e ainda \(N>1\), então, o que tiver sobrado de \(N\) é um primo novo, o qual devemos inserir no nosso vetor de primos);
3. para cada consulta definida por um primo \(p\) dito por Dolores, precisamos incrementar \(m(p)\) e calcular o produto \(\prod_{q < p}(m(q)+1)\), módulo \(10^9+7\) (para obter esses produtos acumulados de modo eficiente em uma estrutura que permita atualizações, utilize uma árvore de segmentos ou uma BIT).

A função tociente de Euler \(\phi(n)\) é o número de coprimos de \(n\) menores que \(n\). Por exemplo, os coprimos de \(13\) menores que \(13\) são todos os números entre \(1\) e \(12\), afinal, \(13\) é primo; logo, \(\phi(13)=12\). Outro exemplo: os coprimos de \(12\) menores que \(12\) são \(1\), \(5\), \(7\) e \(11\) apenas; logo, \(\phi(12)=4\).

Como podemos, dado um número \(n\), calcular \(\phi(n)\)? Tomemos \(n=12\), por exemplo. Quem são os fatores primos de \(12\)? São os números \(2\) e \(3\), claro. Independentemente de suas multiplicidades, o fator \(2\) cancela metade dos números entre \(1\) e \(12\) para serem coprimos do \(12\), enquanto que o fator \(3\) cancela um terço dos números. Confira: \(2\) cancela \(2\), \(4\), \(6\), \(8\), \(10\) e \(12\); \(3\) cancela \(3\), \(6\), \(9\) e \(12\). E não importa que o \(6\) e o \(12\) sejam cancelados duas vezes. O que importa é que, dos \(12\) números entre \(1\) e \(2\), metade deles não são cancelados pelo \(2\), e, dessa metade que sobrevive, dois terços não são cancelados pelo \(3\). Logo,

\begin{equation*} \phi(12) = 12\Bigl(\frac12\Bigr)\Bigl(\frac23\Bigr) = 4 \end{equation*}

De um modo genérico, sendo \(p_1, p_2,\dotsc,p_k\) os fatores primos de \(n\), independentemente de suas multiplicidades:

\begin{equation*} \phi(n)=n\Bigl(1-\frac1{p_1}\Bigr)\cdots\Bigl(1-\frac1{p_k}\Bigr) \end{equation*}

O método mais apropriado para competições de Programação quando estamos interessados em calcular o valor de \(\phi(n)\) para um único inteiro \(n\) é, então, através da decomposição de \(n\) em fatores primos, a qual pode ser obtida em tempo \(O(\sqrt n\log\log n)\) (consulte [HaHa13] Sec. 5.5). No entanto, o que este problema envolve é o cálculo de \(\phi(n)\) para todos os inteiros entre 1 e \(n\). Neste caso, podemos combinar de um jeito criativo a ideia-base do Crivo de Eratóstenes.

Tomemos como exemplo \(n=10\). Inicializemos \(\phi(n)\) com \(n\) para todo \(n\):

\(n\)	1	2	3	4	5	6	7	8	9	10
\(\phi(n)\)	1	2	3	4	5	6	7	8	9	10

Agora vamos iterar um laço para \(i\) de \(2\) até \(n\). Na primeira iteração, \(i=2\). Notemos que \(\phi(i)=i\), o que significa que \(i\) é primo. Agora vamos aninhar um outro laço para uma variável \(j\) de \(i\) até \(n\) pulando os números de \(2\) em \(2\). Cada \(j\) desses é um múltiplo de \(2\), o que significa que \(2\) é um fator primo de \(j\), ou seja, que \(1-1/2\) faz parte do produto que expressa \(\phi(j)\) como discutido acima. Assim, para \(i=2\), ficamos com:

\(n\)	1	2	3	4	5	6	7	8	9	10
\(\phi(n)\)	1	1	3	2	5	3	7	4	9	5

Na próxima iteração, \(i=3\), e \(j\) itera agora de \(3\) em \(3\), e multiplicamos \(\phi(j)\) por \(1-1/3\):

\(n\)	1	2	3	4	5	6	7	8	9	10
\(\phi(n)\)	1	1	2	2	5	2	7	4	6	5

Com agora \(i=4\), temos que \(\phi(i)\neq i\), o que significa que \(\phi(i)\) já foi dividido por algum \(i\) anterior, o que significa que \(i\) não é primo. Então, ignoramos \(i=4\). Com \(i=5\), ficamos com:

\(n\)	1	2	3	4	5	6	7	8	9	10
\(\phi(n)\)	1	1	2	2	4	2	7	4	6	4

Ignoramos \(i=6\). Com \(i=7\):

\(n\)	1	2	3	4	5	6	7	8	9	10
\(\phi(n)\)	1	1	2	2	4	2	6	4	6	4

Ignoramos \(i=8,9,10\). E pronto! Temos todos os valores de \(\phi(n)\) que queríamos. A complexidade é \(O(n\log\log n)\).

Tendo \(\phi()\) para todos os valores de \(1\) a \(n\), podemos resolver o problema facilmente.

Uma fórmula fechada (bom exercício de Combinatória: entender esta fórmula!):

\begin{equation*} 9\times\frac{9\times 10^{k-2} - 10^{\lceil\frac k2\rceil-1}}2 \end{equation*}

Ou: https://www.youtube.com/watch?v=S0DR39XC3RU

[HaHa13] Sec. 4.5

[HaHa13] Sec. 9.24

• https://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-1-introduction/
• https://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-2-implementation/

• https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/?ref=rp
• https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree-set-2/?ref=rp

[HaHa13] Sec. 4.2.8

[HaHa13] p. 143

[HaHa13] p. 163

[HaHa13] Sec. 9.23 - Min Cost (Max) Flow

• https://cp-algorithms.com/graph/min_cost_flow.html
• https://onlinejudge.org/board/viewtopic.php?t=11719

[HaHa13] Sec. 4.3.4 - Second Best Spanning Tree

[HaHa13] Sec. 4.3.4 - Minimum Spanning Subgraph

[HaHa13] Sec. 4.2.6

[HaHa13] Sec. 6.5.1

Comentário por Matheus Dall Rosa (UFFS)

Primeiro calculamos todos os primos até \(10^6\) com o crivo de Eratóstenes, e então para computar os primos reversos podemos verificar se o reverso de cada inteiro no intervalo \([10^6,10^7]\) é um número primo menor que \(10^6\).

Para respondermos a operação query podemos utilizar uma BIT e para calcular a soma acumulada dos fatores primos de todos os primos reversos em \(O(\log N)\) onde \(N\) é a quantidade de primos reversos.

Para processarmos a operação deletion devemos remover o número de fatores primos deste primo reverso da BIT.

Também devemos removê-lo da lista de primos reversos, podemos fazer está operação em \(O(N)\), visto que o número de operações do tipo deletion é no máximo 3500 e como o número de primos reversos no intervalo dado é aproximadamente 79000 então temos: \(3500\times 79000=276500000\), um algoritmo com esta complexidade provavelmente não passaria se o problema tivesse multiplos casos de teste porém o problema em questão só possui um caso de teste.

• Complexidade: Assim teremos \(O(Q\times \log N)\) para responder as operações do tipo query e \(O(D\times N)\) para responder todas as operações do tipo deletion.