TFC 2022 - Programação Nível 2

Para conferir a prova na íntegra, clique aqui.

Portas

Escrito por Enzo Dantas

Conhecimento prévio necessário:

• Update em range (BIT ou Lazy update (Segment Tree))
• Algorimo de Kadane

Ao ler o enunciado, percebe-se que o problema pode ser dividido em duas partes: 1) Construir o array e 2) Achar o subarray máximo desse array (o valor da posição $x$ do array é o valor das cartas que estão no baú de posição $x$). Tal estruturação é evidente pois todos os updates são realizados antes da query, ou seja, ele é estático. Problemas dinâmicos (que possuem updates intercalados com queries) geralmente têm uma solução bem mais complexa do que a versão estática.

Primeiramente, o problema de achar o maior subarray de um array é bastante conhecido: ele pode ser implementado em $O(N*log_n)$ (utilizando um $set$ ou uma $priority$ $queue$) ou em $O(N)$ utilizando o algoritmo de Kadane. Como é um problema clássico, não vou explicá-lo aqui - há uma infinidade de vídeos no YouTube e blogs explicando-o.

Secundariamente, a parte de construir o array pode ser feita de várias formas. Para os leitores que têm familiaridade com lazy update, adicionar um valor a um intervalo [l,r] deve ser uma etapa simples. Tal processo é clássico e é explicado na aula do NOIC citada acima, então também não será explicado aqui.

Finalmente, o único detalhe restante é que a implementação deve ser feita com $scanf/printf$ ou com a linha

ios::sync_with_stdio(false); cin.tie(0);

para ler o input mais rapidamente, pois o input é muito grande $(N=10^6)$. Caso contrário, seu código vai receber TLE.

Clique aqui para conferir o código

Reencontro

Escrito por Caique Paiva

Conhecimento prévio necessário:

• DFS

Vamos transformar o problema em um grafo, onde os vértices são as cidades e as arestas são as estradas. Primeiramente, temos que, se dois vértices $u$ e $v$ estão na mesma componente conexa, então, se $u$ pode participar do reencontro, $v$ também pode, pois, como eles estão na mesma componente conexa, significa que tem um caminho de $u$ para $v$, logo, basta a pessoa em $v$ ir até $u$, e então ir junto com ela para a cidade em que vai ter a reunião.

Com isso, vamos resolver a subtask 2, que é $k = 0$. Nesse caso, vamos dividir o grafo em várias componentes conexas, e então, a resposta vai ser a maior componente conexa do grafo, por conta do que foi dito acima. Então, para dividir o grafo em componentes conexas, vamos fazer várias dfs! A entrada da dfs vai ser $dfs($ int $v$, int $con)$, onde $v$ é um vértice no grafo, e $con$ qual componente conexa a gente está marcando agora. Então, crie um vetor $mark$ com $n$ elementos, e inicialize $con$ com 1 , com todos inicializados com $0$. Agora, vamos fazer um for com $i = 1$ e indo até $n$, onde, se $mark[i] == 0$, fazemos a  $dfs(i, con)$, e depois $con++$.

Dentro da $dfs(v, con)$, fazemos o seguinte: Se $mark[v] != 0$, paramos a dfs. Então, fazemos $mark[v] = con$, e pecorremos todos os $x$ em $g[v]$, e chamamos $dfs(x, con)$. A ideia desse algoritmo todo é que, se $u$ e $v$ estão em componentes conexas diferentes, então $mark[u] \neq mark[v]$.

Agora, vamos criar um vetor $sum$ também com $n$ elementos, e então, fazemos um for de $i = 1$ até $n$, e fazemos $sum[mark[i]]++$. Então, $sum[i]$ vai nos dizer qual o tamanho da componente conexa $i$, que sabemos que temos $con-1$ componentes conexas no total. Com isso, basta retornar o maior valor em $sum$.

Então vamos resolver o problema geral. Para calcular o tamanho de cada componente conexa já tá feito acima, e então, a chave final do problema é ver que, se ligarmos dois vértices de duas componentes conexas, elas se tornam uma componente conexa só, então, para chegar na quantidade máxima de vértices, basta ligar as maiores $k$ componentes conexas do grafo, e vamos conseguir a maior componente conexa possível.

Para fazer isso, basta fazer um sort no vetor $sum$, e somar as $k+1$ maiores componentes conexas.

Clique aqui para conferir o código

Xor Máximo

Escrito por Arthur Lobo

Conhecimento prévio necessário:

• Bitmask
• Programação Dinâmica
• Bitmask DP

O problema nos fala que o conjunto $A$ tem uma peculiaridade: Para qualquer par de inteiros distintos $i$,$j$ do conjunto $A$, o AND entre $A_i$ e $A_j$ é menor que $2^{15}$. Mas o que exatamente isso quer dizer?

Primeiro vamos relembrar uma propriedade das potências de 2: a soma de todas as potências de 2 menores que $2^i$ é menor que $2^i$. Formalmente, $2^0 + 2^1 + ... + 2^{i-1} < 2^i$.

Devido à essa propriedade, podemos concluir que a única forma de o AND entre dois números ser maior ou igual à $2^{15}$ é se eles tiverem algum bit (potência de 2) ativo em comum que é maior do que $2^{15}$, pois caso contrário, o AND deles terá somente bits menores que $2^{15}$, e, pela propriedade citada a cima, sabemos que a soma de potências de 2 menores que $2^{15}$ sempre é menor que $2^{15}$.

Recapitulando, podemos concluir que, para qualquer $i \geq 15$, existe no máximo um elemento em $A$ que tem o bit $i$ (potência $2^i$) ativo. Então, já que $A_i < 2^{30}$, temos no máximo $15$ números maiores ou iguais à $2^{15}$, todos os outros são menores.

Parcial 1 ($N \leq 16$)

Nessa parcial o $N$ é bem pequeno, então não precisamos nem usar a peculiaridade do conjunto para resolve-la. Podemos testar todas as $2^N$ combinações possíveis de sub-conjuntos e ver qual delas possui o maior XOR.

Para conseguir listar todas as combinações, podemos usar uma Bitmask, em que se o $i-esimo$ bit estiver ativo, então o $i-esimo$ elemento está no sub-conjunto que a bitmask representa, caso contrário, ele não está.

Parcial 2 ($A_i$ AND  $A_j < 16$)​

Agora vamos precisar usar a peculiaridade que o problema nos apresenta, mas ao invés de $2^{15}$, temos $2^4$, ou seja, temos no máximo um número com cada um dos bits $4...30$ ativo.

Devido à propriedade de potências de $2$, sempre vai valer a pena escolher esses número que tem os bits $4...30$ativo. Podemos provar isso por contradição: Digamos que o xor atual seja $X$ e não escolhemos um número $V$ que tem um dos bits $4...30$ ativo, digamos que seja o bit $b$; se colocarmos o $V$ nesse sub-conjunto do XOR $X$, sabemos que ele vai fazer com que o bit $b$ seja ativado (já que ele não estava ativado antes em $X$) e, no pior dos casos vai fazer com que os bits $0, 1, 2$ e $3$ sejam desativados (já que ele não possui nenhum bit maior ou igual à 4 ativo diferente de $i$. Mas já que $2^i$ é maior do que $2^0+2^1+2^2+2^3$, sempre vai valer a pena colocar $V$ no conjunto. Portanto, podemos concluir que todos os números que tem um dos bits $4...30$ ativo vai estar no nosso conjunto.

Agora só precisamos saber quais dos outros números vão entrar nesse conjunto também. Já que eles não tem nenhum bit maior que $3$ (potência $2^3$) ativo, os números que sobraram serão menores que $2^4$, ou seja, serão os números $0, 1, ... 14, 15$, mas eles podem estar repetidos, então temos que deletar as copias desnecessárias.

Depois de deletar as repetições, o conjunto de números que estamos pensando em colocar ou não no XOR tem no máximo $16$ números, então conseguimos resolver assim como resolvemos a parcial anterior, mas primeiro temos que colocar os número que com certeza estarão no sub-conjunto do XOR.

Clique aqui para conferir o código

Laser

Escrito por Enzo Dantas

Conhecimento prévio necessário:

• BIT

Após simular alguns casos mentalmente, percebe-se que a seguinte ideia parece promissora: uma matriz só pode estar completamente preenchida se 1) há um laser em todas as colunas da matriz ou se 2) há um laser em todas as linhas da matriz.

Assim, precisamos de uma estrutura que mantém quais linhas e quais colunas tem um laser e consegue adicionar e remover rapidamente um laser (a coluna e a linha dele, mais precisamente). Além disso, ela deve responder rapidamente a pergunta "em um intervalo $[l,r]$, existe um laser em toda linha de $l$ a $r$ (ou em toda coluna)?". Em outras palavras, essa estrutura deve armazenar quais posições de um array estão "ligadas", "ligar" e "desligar" posições e responder rapidamente se todas as posições de um intervalo $[l,r]$ estão "ligadas". Para tanto, usaremos uma BIT.

Por fim, manteremos um array de frequência para as linhas e colunas. Ao adicionar um laser, devemos checar se ele é o único laser naquela coluna - se esse for o caso, atualizamos a BIT na posição correspondente (a mesma coisa é feita em relação às linhas). Assim, quando utilizarmos a operação da BIT de soma em um intervalo, contaremos apenas a quantidade de lasers em linhas (ou colunas) diferentes.

Cada operação da BIT tem uma complexidade logarítmica no tamanho do array, então a complexidade final é $O(Q*log_n)$.

Clique aqui para conferir o código