OBI 2024 Terceira fase P2

Esta página é dedicada aos comentários da OBI 2024. Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!

Construtora

Comentário por Henrique Vianna

Conhecimento prévio necessário:

Loops

Perceba, primeiramente, que podemos considerar um segmento de prédios de mesma altura como um único prédio. Da mesma forma, perceba que a seguinte estratégia é válida e minimiza a quantidade de fases necessárias para a construtora completar a obra: selecionar o menor prédio e aumentar a sua altura até que ele atinja a altura do menor prédio entre seus vizinhos, removê-lo do vetor e refazer o processo até que reste um único prédio (o maior deles). Podemos remover o menor justamente porque ele passaria a formar um segmento de mesma altura com seu vizinho. Esse processo pode ser facilmente simulado com um vector ou até mesmo recursivamente.

Deve-se ressaltar que, no caso desse problema, soluções $\mathcal{O}(N^3)$ também recebiam $100$ pontos. Além disso, é possível resolvê-lo em $\mathcal{O}(N)$ .

Segue o código:

	#include <bits/stdc++.h>
	using namespace std;

	const int INF = 110; // Valor maior que todos os outros

	int main()
	{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;

	vector<int> a(n);
	for(auto &x : a) cin >> x;

	int resp = 0;

	while(a.size() > 1)
	{
	int mn = *min_element(a.begin(), a.end()); // Valor minimo em a
	int mnPos = 0;

	for(int i = 0; i < a.size(); i++)
	{
	if(a[i] == mn)
	{
	mnPos = i;

	int direita = (i + 1 < a.size() ? a[i + 1] - a[i] : INF);
	int esquerda = (i - 1 >= 0 ? a[i - 1] - a[i] : INF);

	// Igualo menor valor ao menor de seus vizinhos
	resp += min(direita, esquerda);

	break;
	}
	}

	// Removo o minimo do vetor
	a.erase(a.begin() + mnPos);
	}

	cout << resp << '\n';
	}

view raw

Construtora.cpp

hosted with ❤ by GitHub

Retas

Comentário escrito por Fernando Gonçalves

Conhecimento prévio necessário:

Contagem de Inversões

Subtarefa 2: $N = 2$

Só precisamos checar se a intersecção das duas retas está no intervalo $[X_1, X_2]$ .

A equação da abscissa $x$ da intersecção de duas retas é $x = \frac{B_1 - B_2}{A_2 - A_1}$ , sendo as retas $(A_1, B_1)$ e $(A_2, B_2)$ .

Obs: Quando $A_1 = A_2$ , não existe intersecção e, assim, a fórmula dá erro por divisão por 0.

Subtarefa 3: $N \leq 1000$

A solução é a mesma que para $N = 2$ , mas fazemos para cada par de retas.

Subtarefa 4: $A_i = A_j$ para todo $1 \leq i, j \leq N - 1$

As primeiras $N-1$ retas não tem intersecção entre si (elas têm todas a mesma inclinação).

Portanto, posso fazer a mesma ideia de $N \leq 1000$ , mas só testo os pares com a última reta.

Subtarefa 5: $X_1 = X_2$

Só queremos ver quantas retas têm intersecção na $X_1$ .

Para tanto, podemos manter um map de frequências, indicando quantas retas existem em um $y$ na $X_1$ .

Passo por todas as retas, quando estou na $i$ -ésima, somo $freq_{A_i * X_1 + B_i}$ na resposta e, em seguida, adiciono um na frequência desse y.

Subtarefa 6: $X_2 = X_1 + 1$ e $A_i \leq 30$ para todo $1 \leq i \leq N$ .

Podemos fixar quais os $A$ das duas retas que vamos testar.

Com isso, sabemos que as retas devem ter $X_1 * (A_j - A_i) \leq B_i - B_j \leq X_2 * (A_j - A_i)$ , o que é um intervalo fixo para cada par de valores de $A$ . Obs: É preciso garantir que $A_i < A_j$ .

Podemos, então, calcular essa quantidade por meio de uma line sweep e um two pointers, para cada par de valores de $A$ .

Subtarefa 7: Sem restrições adicionais

Existem quatro casos da intersecção de duas retas: elas se encontram antes de $X_1$ , elas se encontram depois de $X_2$ , elas não se encontram, elas se encontram entre $X_1$ e $X_2$ .

Note que somente no caso de intersecção no meio a ordem relativa dos $y$ dessas retas muda da abscissa $X_1$ para a abscissa $X_2$ .

Dessa forma, só precisamos ordenar as retas pelo $y$ delas em $X_1$ e checar a quantidade de inversões na ordenação em $X_2$ , esta será a nossa resposta.

Obs: existe corner quando a intersecção ocorre em $X_1$ ou em $X_2$ , que pode ser corrigido por desempate na ordenação das retas.

Clique aqui para conferir o código.

Comentário por Murilo Maeda Kataoka

Conhecimento prévio necessário

Binary Lifting

OBS: perceba que $pai[i] < i$ e que sempre podemos pegar o ancestral $k$ níveis acima

Subtarefa 2: A estrutura forma uma linha

Para essa subtarefa podemos perceber que, em qualquer momento, se soubermos o pai de um certo vértice $i$ , podemos facilmente calcular qual é o vértice que está $k$ níveis acima dele. Isso porque se algum vértice $v$ ainda possui filhos, com certeza, nenhum vértice acima dele sofreu reestruturação. Sabendo disso, podemos calcular facilmente o vértice que está $x$ posições acima de $v$ , já que o vértice com profundidade $prof$ tem índice $prof + 1$ , pois $p[i + 1] = i$ . Então, o vértice que está $x$ posições acima de $v$ é o vértice $v - x$ . Consequentemente, para um vértice $i$ , quem está $k$ níveis acima dele será o vértice $pai[i] - (k - 1)$ .

Agora, basta encontrar uma maneira de encontrar rapidamente o pai de um dado vértice $i$ . Para fazer isso, vamos manter qual foi o menor índice que sofreu uma operação e um vetor que guarda o pai original dos vértices. Só precisamos saber do menor número porque as operações feitas em vértices de maior índice não importam, uma vez que o vértice menor é ancestral desses vértices maiores e, por isso, agora são todos filhos diretos do vértice menor. Seja $u$ o menor número que sofreu reestruturação. Assim, em qualquer momento, para saber o pai de um determinado vértice $i$ , caímos em dois casos:

i é menor que u ou ainda não houve reestruturação: nesse caso, a resposta é $pai[i]$ .
i é maior que u: nesse caso, a resposta é $u$ .

A complexidade fica $O(Q)$

Subtarefa 3: $N, Q \leq 500$

Nessa parcial, para uma reestruturação no vértice $v$ , podemos simplesmente passar na subárvore de $v$ e setar que o pai desses vértices na subárvore é $v$ . Precisamos também criar um vetor de marcação, onde marcamos todos os vértices que possuem algum ancestral que sofreu reestruturação. Fazemos isso porque se a operação de reestruturação for em algum vértice que está marcado no vetor de marcação, não fazemos nada, já que ele não possuirá nenhum filho.

Agora, para saber quem está $k$ posições acima de um certo vértice $i$ , vamos utilizar a mesma observação da parcial anterior, de que se um vértice ainda possui filhos, nenhum ancestral dele sofreu reestruturação. Então, podemos simplesmente subir $k$ ancestrais fazendo $pai[ pai[ ... pai[ i ] ... ] ]$ , onde pegamos o pai $k$ vezes.

A complexidade fica $O(Q \times N ^ {2})$ .

Subtarefa 4: A estrutura forma uma árvore binária completa

Como a estrutura é uma árvore binária completa e $N = 2 ^ {m}- 1$ , a sua principal característica é que a sua altura (ou profundidade) será no máximo $m - 1$ , já que há $2 ^ i$ vértices que possuem profundidade $i$ . E isso nos ajuda porque $m \leq log_2 (10 ^5)$ , ou $m \leq 17$ .

Nesse caso, quando fizermos uma reestruturação no vértice $v$ , podemos simplesmente utilizar um vetor de marcação para indicar que houve reestruturação nesse vértice. Vou mostrar a seguir o porquê disso bastar para essa parcial.

Quando quisermos pegar o ancestral $k$ níveis acima de um vértice $i$ , novamente queremos o ancestral de menor índice que sofreu reestruturação, pois temos a observação da subtask 1. Para achar esse ancestral, podemos simplesmente iterar por todos os ancestrais de $i$ e pegar o ancestral de menor índice que está marcado no vetor de marcação. Então, a partir desse ancestral que achamos, basta subir $k - 1$ níveis e acharemos a resposta. Se não acharmos nenhum ancestral que esteja marcado, subimos $k$ níveis a partir de $i$ .

A complexidade fica $O(1)$ para reestruturações e $O(log_2 N)$ para achar o superior $k$ níveis acima.

Subtarefa 5: Os nobres só têm que entregar relatórios para seus superiores diretos (pai)

Nesse subtask, basta saber o pai atual do vértice $i$ para responder as perguntas de entrega de relatório.

Agora, precisamos saber encontrar esse pai. Para fazer isso, basta saber para cada vértice qual é o ancestral de menor índice que sofreu alguma reestruturação (já que esse ancestral será seu pai atual). A fim de encontrar isso, podemos perceber que, quando fazemos reestruturação em um certo vértice $v$ , que não possui nenhum ancestral que sofreu reestruturação, todos os vértices na sua subárvore irão ter ele como ancestral de menor índice que sofreu reestruturação e como pai.

Então, queremos uma estrutura que faça as seguintes operações:

Retorne para um vértice $v$ qual é o ancestral de menor índice que sofre reestruturação (se nenhum ancestral tiver sofrido reestruturação, retorna o pai na árvore original).
Atualize para todos os vértices na subárvore de um vértice $v$ que $v$ é o ancestral de menor índice que sofreu reestruturação (se $v$ já tiver um ancestral que sofreu reestruturação, ele não terá nenhum filho, então, nesse caso, essa atualização não deve fazer nada).

Para fazer essa estrutura, vamos primeiro linearizar a árvore utilizando Euler Tour, que está descrito na subtask 3 desse problema.

Código do euler tour:

	int timer, tin[MAXN], tout[MAXN];

	void dfs(int u, int p)
	{
	tin[u] = ++timer;

	for(auto v : adj[u])
	{
	if(v == p) continue;
	dfs(v, u);
	}

	tout[u] = timer;
	}

view raw

euler_tour.cc

hosted with ❤ by GitHub

Agora, temos uma ordenação dos vértices que permite encontrar todos os vértices na subárvore de $v$ facilmente, já que todos os vértices $j$ tais que $tin[v] < tin[j] \leq tout[v]$ estão na subárvore de $v$ .

Observação importante: Se todos os vértices de uma subárvore, representada pelo intervalo $[i, j]$ de $tin$ , possuem o mesmo pai $v$ depois de uma reestruturação nesse vértice, para todas as operações de reestruturação subsequentes, eles terão o mesmo pai, isto é, $pai[i] = pai[i + 1] = ... pai[j]$ . Note que, no futuro, pode ser que esse pai em comum não seja $v$ , e sim um outro vértice $u$ que era ancestral de $v$ e sofreu reestruturação. Essa observação é verdadeira porque todas as reestruturações que mudam quem é o pai de algum vértice no intervalo em questão devem ter sido feitas em alguém que é ancestral de $v$ e, como a subárvore de $v$ está contida na subárvore de todos os seus ancestrais, todos os vértices na subárvore de $v$ terão como novo pai o ancestral de $v$ que foi reestruturado.

Com isso, podemos fazer uma segment tree no vetor da árvore linearizada (isto é, o índice $i$ nesse vetor representa o vértice que possui $tin$ igual a $i$ e fazemos uma seg nesse vetor). Mas, como estamos querendo fazer updates em um intervalo e queries em um índice específico, essa seg será um pouco diferente.

Cada nó $v$ da seg cai em dois casos:

Caso 1: Todos os vértices cujos tin estão no intervalo representado por $v$ possuem o mesmo ancestral de menor índice $i$ que sofreu reestruturação. Nesse caso, $seg[v] = i$ .
Caso 2: Os vértices no intervalo de tin de $v$ NÃO possuem o mesmo ancestral de menor índice $i$ que sofreu reestruturação. Nesse caso, $seg[v] = INF$ .

Utilizando a observação feita logo acima, fica fácil perceber que se todos os vértices no intervalo de $tin$ de um nó $v$ da seg tiverem o mesmo ancestral que sofreu reestruturação, eles sempre terão o mesmo ancestral para as operações seguintes. Por isso, podemos setar $seg[v] = i$ . Por outro lado, se eles não possuem esse ancestral em comum, ainda não podemos afirmar nada sobre os seus pais atuais só com o vértice $v$ . É necessário, então, descer para fazer a busca nos filhos de $v$ .

Observe a situação inicial para maior clareza.

O update na seg será da seguinte forma:

	//[ini,fim] é o intervalo representado pelo nó "pos" da seg
	//queremos setar o intervalo [p,q] para ter pai igual a "val"
	void update(int pos, int ini, int fim, int p, int q, int val)
	{
	//se o [ini,fim] e [p,q] são disjuntos, não faz nada
	if(p > fim \|\| q < ini) return;

	//se [ini,fim] está inteiramente contido no intervalo [p,q]
	if(p <= ini && fim <= q)
	{
	//com a observação, podemos só setar seg[pos] = val
	//não é necessário descer para os filhos de pos
	seg[pos] = min(seg[pos],val);
	return;
	}

	int m = (ini + fim)/2;
	int e = pos2, d = pos2 + 1;

	//se não está inteiramente contido, desce até achar um que esteja inteiramente contido em [p,q].
	update(e,ini,m,p,q,val);
	update(d,m+1,fim,p,q,val);
	}

view raw

update_Burocracia.cpp

hosted with ❤ by GitHub

Perceba que temos que fazer $seg[pos] = min(seg[pos],val)$ para evitar que ocorram reestruturações que, por exemplo, reestruturem um vértice $v$ e depois um filho de $v$ . Como $pai[i] < i$ , fazer $seg[pos] = min(seg[pos],val)$ faz com que essa segunda atualização não faça nada, que é o esperado.

A query será dessa forma:

	//o nó "pos" representa o intervalo de tin [ini,fim]
	//queremos saber o pai do vértice i tal que tin[i] = id
	int query(int pos, int ini, int fim, int id)
	{

	//se id não está em [ini,fim], retorna que é inválido (é bom ter, mesmo que isso nunca aconteça)
	if(id > fim \|\| id < ini) return -1;

	//se for diferente de INF, todos os filhos tem o mesmo pai (seg[pos])
	//como id já está em [ini,fim], só retorna seg[pos]
	if(ini == fim \|\| seg[pos] != INF)
	return seg[pos];

	int m = (ini + fim)/2;
	int e = pos2, d = pos2 + 1;

	//se o id que estamos buscando está na esquerda, retorna o da esquerda
	//caso contrário retorna o da direita
	if(id <= m) return query(e,ini,m,id);
	else return query(d,m+1,fim,id);
	}

view raw

query_burocracia.cpp

hosted with ❤ by GitHub

Para ficar mais claro, segue um exemplo de reestruturação:

Após reestruturação no vértice 5 (o update na seg fará com que os vértices com $tin$ no intervalo $[tin[5] + 1, tout[5]] = [5,7]$ tenham como ancestral de menor índice que sofreu reestruturação o vértice 5).

As queries e os updates ficam $O(log N)$ .

Subtask 6: sem restrições adicionais

Agora que já sabemos como fazer reestruturações rapidamente, basta descobrir como responder quem é o superior $k$ posições acima de um certo vértice $v$ rapidamente.

Para fazer isso utilizamos binary lifting! Para fazer o binary lifting, computamos a $dp[i][x]$ normal, que guarda, para um $i$ , qual é o vértice que está $2 ^{x}$ posições acima dele. Agora que temos isso, para saber quem está $k$ níveis acima de $i$ , basta fazer $i = dp[i][x]$ , para todo $x$ tal que $2 ^ {x}$ e $k$ tenham um bit ativo em comum na notação binária desses números. Note que é o mesmo processo feito para igualar a profundidade de $u$ e $v$ no algoritmo de lca.

Observação importante: Se um certo vértice $v$ possui filhos, nenhum ancestral seu sofreu reestruturação e são todos iguais aos da árvore original. Isso é porque, se algum deles tivesse sofrido reestruturação, todos os filhos de $v$ seriam agora desse ancestral de $v$ que foi reestruturado.

Como sabemos o pai atual de um certo vértice $v$ (já que temos a seg descrita na parcial anterior), basta subir $k - 1$ posições a partir do seu pai utilizando binary lifting. Como $k - 1$ possui no máximo $log_2 N$ bits, a complexidade de uma operação desse tipo é $O(log N)$ .

Segue o código para ficar mais claro:

	#include<bits/stdc++.h>
	#define INF 0x3f3f3f3f
	using namespace std;

	const int MAXN = 1e5 + 10;
	const int LOG = 22;
	int seg[MAXN4],marc[MAXN4], dp[MAXN][LOG], tin[MAXN], tout[MAXN];
	int N,temp = 0;
	vector<int> grafo[MAXN];

	//Lineariza a árvore
	void setup(int v, int p)
	{
	tin[v] = ++temp;
	for(int viz : grafo[v])
	{

	if(viz == p)
	continue;
	setup(viz,v);
	}
	tout[v] = temp;
	}

	//[ini,fim] é o intervalo representado pelo nó "pos" da seg
	//queremos setar o intervalo [p,q] para ter pai igual a "val"
	void update(int pos, int ini, int fim, int p, int q, int val)
	{
	//se o [ini,fim] e [p,q] são disjuntos, não faz nada
	if(p > fim \|\| q < ini) return;

	//se [ini,fim] está inteiramente contido no intervalo [p,q]
	if(p <= ini && fim <= q)
	{
	//com a observação, podemos só setar seg[pos] = val
	//não é necessário descer para os filhos de pos
	seg[pos] = min(seg[pos],val);
	return;
	}

	int m = (ini + fim)/2;
	int e = pos2, d = pos2 + 1;

	//se não está inteiramente contido, desce até achar um que esteja inteiramente contido em [p,q].
	update(e,ini,m,p,q,val);
	update(d,m+1,fim,p,q,val);
	}

	//o nó "pos" representa o intervalo de tin [ini,fim]
	//queremos saber o pai do vértice i tal que tin[i] = id
	int query(int pos, int ini, int fim, int id)
	{

	//se id não está em [ini,fim], retorna que é inválido (é bom ter, mesmo que isso nunca aconteça)
	if(id > fim \|\| id < ini) return -1;

	//se for diferente de INF, todos os filhos tem o mesmo pai (seg[pos])
	//como id já está em [ini,fim], só retorna seg[pos]
	if(ini == fim \|\| seg[pos] != INF)
	return seg[pos];

	int m = (ini + fim)/2;
	int e = pos2, d = pos2 + 1;

	//se o id que estamos buscando está na esquerda, retorna o da esquerda
	//caso contrário retorna o da direita
	if(id <= m) return query(e,ini,m,id);
	else return query(d,m+1,fim,id);
	}

	//Responde quem está k posições acima do vértice v
	int responde(int v, int k)
	{
	//acha o pai de v
	int paiCur = query(1,1,N,tin[v]);

	//Faz o binary lifting para ver quem está k - 1 posições acima do pai de v
	k--;
	for(int i = 0; i < LOG; i++)
	{
	if(k & (1 << i))
	{
	paiCur = dp[paiCur][i];
	}
	}
	return paiCur;
	}

	int main()
	{
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;

	//Lê o grafo e inicializa a dp do binary lifting
	dp[1][0] = 1;
	for(int i = 2; i <= N; i++)
	{
	cin >> dp[i][0];
	grafo[dp[i][0]].push_back(i);
	}

	setup(1,1);

	//Calcula a dp do binary lifting
	for(int i = 1; i < LOG; i++)
	{
	for(int j = 1; j <= N; j++)
	{
	dp[j][i] = dp[dp[j][i-1]][i-1];
	}
	}


	//Inicializa todo nó da seg como INF
	for(int i = 1; i <= 4*N; i++)
	{
	seg[i] = INF;
	}

	//Inicializa as folhas da seg como os os pais dos vértices na árvore inicial
	for(int i = 1; i <= N; i++)
	{
	update(1,1,N,tin[i],tin[i],dp[i][0]);
	}

	int Q; cin >> Q;

	while(Q--)
	{

	int type; cin >> type;

	if(type == 1)
	{
	int v,k; cin >> v >> k;

	cout << responde(v,k) << "\n";
	}
	else
	{
	int v; cin >> v;
	//Veja que o update é de tin[v] + 1 até tout[v] e não de tin[v] até tout[v]
	//Isso porque não podemos setar que o pai de v é o próprio v
	update(1,1,N,tin[v] + 1,tout[v],v);
	}
	}

	}

view raw

burocracia.cpp

hosted with ❤ by GitHub

Brigadeiros

Comentário escrito por João Pedro Castro

Conhecimento prévio necessário:

Introdução à Programação Dinâmica
Problema da Mochila - Tecnicamente opcional, mas meio impossível fazer sem ter as ideias daqui.

Subtarefa 2: $N \leq 50$ , $K \leq 3$ , $T \leq 1000$

Vamos brutar tudo (testar todas as possibilidades de algo). Primeiro, vamos brutar as $K$ posições finais, isso é $O({N \choose K})$ . Agora, para cada uma dessas possibilidades vamos brutar a ordem que cada um vai (se o primeiro menor das posições iniciais vai com a segunda menor das posições finais, etc), isso é $O(K!)$ . Por fim, para cada um desses casos conseguimos calcular em $O(K)$ (mas até $O(N)$ passaria) o $t$ mínimo para chegar nessa posição, e se $t \leq T$ falamos que a resposta é o máximo entre a resposta atual e a soma da quantidade de brigadeiros nas posições finais. A complexidade final é $O({N \choose K} \cdot K! \cdot K)$ .

Dica de implementação: para brutar todas as possibilidades, você pode criar um vetor de $N$ posições que comece com $N - K$ 0s e depois tenha $K$ 1s. E então, usar next_permutation para ver todas as possibilidades. Em uma dada permutação desse vetor original você pode dizer que se e somente se a i-ésima posição for igual a 1 tem alguém do grupo.

Subtarefa 3: $N \leq 16$ , $T \leq 1000$

Podemos fazer a mesma estratégia da parcial anterior mas com uma observação a mais: sejam as posições iniciais do grupo $s_1 < s_2 < ... < s_k$ , e as finais $f_1 < f_2 < ... < f_k$ : para conseguir o tempo mínimo de chegar nessa posição é ideal dizer que o cara na posição $s_i$ vai para a posição $f_i$ para todo $1 \leq i \leq k$ ; ou seja, o menor vai com o menor, o segundo menor vai com o segundo menor, etc. A intuição disso é bem simples, e não é difícil "provar" (sem muita formalidade) fazendo umas contas.

Assim, conseguimos só brutar as $O({N \choose K})$ possibilidades de escolhas, e calcular o tempo para chegar lá em $O(K)$ . A complexidade final é $O({N \choose K} \cdot K)$ .

Dica: o caso onde ${a \choose b}$ é maior é quando $b = \frac{a}{2}$ , então nesse caso o pior é ${16 \choose 8} \approx 10^{4.1}$ , que ainda passa tranquilamente.

Subtarefa 4 e 5: $N \leq 50$ , $T \leq 10^5$

Vamos usar programação dinâmica! Aqui a definição de cada parte:

Estado: nosso estado vai ser $dp_{i, j, t} = s$ , onde:
- $i$ significa que usamos as posições de 1 até $i$ para as posições finais dos membros do grupo que colocamos até agora.
- $j$ significa que já colocamos os $j$ primeiros membros do grupo.
- $t$ significa o tempo máximo que podemos usar para chegar na melhor soma possível.
- $s$ significa a melhor soma possível que conseguimos dado $i$ , $j$ e $k$ .
Caso base: o único caso base necessário é $dp_{0, 0, 0} = 0$ . O resto, se não calcularmos, pode ser visto só como $-\infty$ .
Transição: vou colocar várias possibilidades, e vai ser só o máximo entre elas.
- Podemos só não botar nada em $i$ : $dp_{i - 1, j, t}$ .
- Podemos ficar parados sem fazer nada: $dp_{i, j, t - 1}$ .
- Se $j > 0$ , podemos botar o $j$ -ésimo (do menor para o maior em posição) membro do grupo na posição $i$ : $dp_{i - 1, j - 1, t - |i - posicao_j|} + p_i$ (perceba que essa transição só funciona por conta da nossa observação que é sempre melhor colocar o menor com menor, segundo menor com segundo menor, etc.)
A resposta, dado o estado, é $dp_{N, K, T}$ .

A complexidade é $O(N^2 \cdot T)$ .

Subtarefa 6: $N \leq 100$

Vamos fazer a mesma DP, só que com uma observação a mais. Responda essa pergunta: se posso fazer trocas de elementos adjacentes, qual o número máximo de swaps para ordenar o vetor?

Se você já viu a técnica de bubble sort, essa pergunta tem uma resposta bem direta: é $O(N^2)$ , e na verdade sempre vai ser menor que $N^2$ (não convém mostrar a conta aqui). Logo, posso chegar de qualquer ordenação do vetor para qualquer outra em menos de $N^2$ operações, ou seja, logo após receber o $T$ podemos dizer que $T = min(T, N^2)$ e a resposta ainda estaria certa, pois se existe uma resposta válida fazendo mais que $N^2$ trocas, também existirá uma fazendo menos que $N^2$ trocas.

Assim, tendo que $T \leq N^2$ , temos uma complexidade de $O(N^4)$ .

Subtarefa 7: Sem restrições adicionais.

Quando você leu o enunciado, idealmente se atentou de um detalhe específico que não seria colocado sem motivo: $0 \leq P_i \ leq 9$ . Ou seja, todo prato tem entre $0$ e $9$ brigadeiros, mas o que isso faz a gente pensar? Se você já está acostumado com problemas de DP, é direto: a soma máxima é $O(N)$ .

E uma técnica legal de problemas de DP, é que em diversos problemas se você tem algo como $dp_{a, b, c} = d$ (ou em um caso geral com quantas variáveis você quiser), você pode dizer que $dp_{a, b, d} = c$ , ou qualquer outra troca. Ou seja, se você tem $X$ variáveis que indicam seu estado, e mais $1$ que indica sua resposta, você pode trocar qualquer uma das que indicam o estado com a da resposta que o estado ainda vai ser perfeitamente expressado. Claro que varia de problema a problema, e vai ter trocas melhores que outras, mas em problemas de DP sempre pense em qual a maneira com menos possibilidades de guardar esse estado.

No nosso caso, ao invés de fazer a $dp_{i, j, t} = s$ , vamos fazer a $dp_{i, j, s} = t$ . Já que o máximo de $t$ é $O(N^2)$ e o máximo de $s$ é $O(N)$ . Agora a DP significa: colocando os $j$ primeiros do grupo em algumas das $i$ primeiras posições, qual o menor tempo $t$ para atingir a soma $s$ ? Se for impossível podemos só dizer que $dp_{i, j, s} = \infty$ .

O estado foi explicado acima, o caso base é o mesmo, e o resto fica assim:

Transição: de novo, colocarei várias coisas aqui, e agora só pegue o mínimo entre elas.
- Não colocamos nada em $i$ : $dp_{i - 1, j, s}$ .
- Colocamos o $j$ -ésimo do grupo em $i$ : $dp_{i - 1, j - 1, s - P_i} + |i - posicao_j|$ .
A resposta vai ser o maior $S$ tal que existam quaisuer $x$ e $y$ com $dp_{x, y, S} \leq T$ .

Temos $O(9 \cdot N^3)$ estados, cada transição é $O(1)$ , logo a complexidade final é $O(9 \cdot N^3) = O(N ^3)$ .

OBS: A complexidade acaba ficando apertada, então para ficar tranquilo você tem que fazer pequenas "otimizações" (basicamente não passar por estados impossíveis), veja o código abaixo para ver as que fiz.

Clique aqui para conferir o código.

Jogo de Pratos

Comentário escrito por Fernando Gonçalves

Conhecimento prévio necessário:

Esse problema têm duas partes que trabalharemos separadamente: a parte dos feitiços e a das refeições. Neste comentário, será discutida a ideia geral do problema e, ao final, haverá discussão das parciais.

Parte dos feitiços

Temos $N$ equações de reta. Podemos usar cada uma delas quantas vezes quisermos e em qualquer ordem, contanto que sejam usadas exatamente $K$ delas no total. Queremos achar, dado um $X$ inicial, qual o máximo valor que podemos atingir.

Para tanto, usaremos, a todo momento, a equação que mais aumenta o nosso $X$ , só precisamos agora achar qual essa reta para toda operação.

Prova

Todas as retas são estritamente crescentes (é garantido pelo enunciado).

Assim, se eu tiver um $X$ maior, consigo um resultado maior em todas as retas.

Portanto, uma estratégia que não maximiza o $X$ após a operação nunca é ótima.

Utilizando o Convex Hull Trick, conseguimos achar a reta ótima para cada intervalo de $X$ . Dessa forma, conseguimos, por meio de uma busca binária nesse convex hull de retas, achar em $O(log_2N)$ a reta ótima para um $X$ qualquer. Isso nos dá uma complexidade de $O(K * log_2N)$ por query.

Estamos, contudo, fazendo algumas operações desnecessárias.

Note que, quando a reta ótima for aquela com maior $A$ do convex hull, todas as operações restantes serão feitas nesta reta. Se sobraram $K'$ operações, o $X$ final ( $X'$ ) será $X' = X + K' * B$ (caso $A == 1$ ) ou $X' = A(A(A(...A(A*X + B)+B)+B)...)+B = A^{K'}*X + B*\sum_0^{K'-1}A^i = A^{K'}*X + B*\frac{A^{K'} - 1}{A - 1}$ (caso $A > 1$ ).

Além disso, no máximo uma operação será usada em qualquer outra reta.

Prova

Sendo as retas do convex hull $(A_1, B_1)$ , $(A_2, B_2)$ , ..., $(A_n, B_n)$ , com $A_i < A_{i+1}$ para todo $1 \leq i < n$ , temos que $B_i > B_{i+1}$ (uma reta "dominada" por outra nunca é ótima).

Quando usamos uma reta $i$ , nenhuma outra reta menor que $i$ será usada daqui para frente. Portanto, suponha sem perda de generalidade que usamos a reta $1$ .

Após essa operação, temos que $X' = A_1 * X + B_1 => X' > B_1 => X' > B_i$ para todo $1 \leq i \leq n$ .

Suponha, por contradição, que agora usaremos a reta $i$ ( $1 \leq i < n$ ).

Sabemos, assim, que $A_i * X' + B_i > A_n * X' + B_n$ (pois $i$ é ótima) $<=> (A_n - A_i) * X' < B_i - B_n$ .

Entretanto, $X' > B_i$ e $A_n > A_i$ e $B_n \geq 0$ . Assim, $(A_n - A_1) * X' > X' > B_i > B_i - B_n => (A_n - A_1) * X' > B_i - B_n$ , o que é uma contradição.

Dessarte, depois de uma operação, somente a última reta será usada.

Desta forma, só precisamos achar a reta ótima para o $X$ inicial, aplicar uma operação com esta, e aplicar todas as outras com a última reta. A complexidade disso é $O(log_2N)$ por query, ou seja, $O(Qlog_2N)$ no total.

Parte das refeições

Temos $M$ equações de reta. Precisamos usar cada uma delas exatamente uma vez, mas podemos escolher a ordem. Essa ordem, portanto, será alguma permutação $p$ de tamanho $M$ .

Note que, para um dado $X$ , o resultado de todas as operações será $X' = a'_{p_M} * (a'_{p_{M-1}} * (... a'_{p_2} * (a'_{p_1} * X + b'_{p_1}) + b'_{p_2}) ... ) + b'_{p_{M-1}} ) + b'_{p_M}$ . Assim, temos que $X' = X * \prod_1^M a'_{p_i} + \sum_1^M ( b'_{p_i} * \prod_{i+1}^M a'_{p_j})$ , ou seja, a ordem ótima independe do $X$ .

Dessa forma, só precisamos calcular o maior somatório possível.

Intuitivamente, uma solução gulosa deveria funcionar (afinal, achar o maior valor de uma soma de produtos é um problema classicamente guloso), contudo a ordenação não é óbvia. Usaremos, então, um argumento da troca para achar essa ordenação ótima.

Suponha que temos uma ordem qualquer $p$ tal que, quando trocamos a ordem de $p_i$ e $p_{i+1}$ , o somatório aumenta. Como o prefixo e o sufixo das duas ordens é igual, temos que $a'_{p_{i+1}} * b'_{p_i} + b'_{p_{i+1}} < a'_{p_i} * b'_{p_{i+1}} + b'_{p_i} <=> (a'_{p_{i+1}} - 1) * b'_{p_i} < (a'_{p_i} - 1) * b'_{p_{i+1}}$ . Dessa forma, excetuando-se o caso em que um dos $a'$ é $1$ (estes sempre estão no prefixo da ordem), a troca acontece quando $\frac{b'_{p_i}}{a'_{p_i} - 1} < \frac{b'_{p_{i+1}}}{a'_{p_{i+1}} - 1}$ e, portanto, nossa ordem gulosa é a ordenação por maior $\frac{b'}{a'-1}$ .

Tanto esse somatório quanto o produto dos $a'$ podem ser calculados no começo do código, e sua conta calculada ao final de cada query. Resolvemos, então, essa parte em $O(Mlog_2M)$

Resumo da solução

Começamos o código ordenando as operações do segundo por maior $\frac{b'}{a'-1}$ (Cuidado: os $a' = 1$ devem ser colocados no prefixo).

Então, calculamos tanto o produto dos $a'$ dessas $M$ operações quanto o somatório $\sum_1^M (b'_i * \prod_{i+1}^M a'_j)$ provenientes desse ordenamento. Salvaremos esses números para calcular a resposta final em cada query.

Em seguida, ordenamos as operações do primeiro tipo por $a$ crescente, e calculamos o convex hull das retas. Podemos, também, calcular os intervalos de $X$ ótimo para cada reta, para facilitar a implementação futura, mas isso não é estritamente necessário.

Agora, começamos a lidar com as queries. Para cada uma, vamos usar uma busca binária (ou ternária, caso os intervalos de $X$ não tenham sido calculados) para encontrar a primeira reta usada. Depois disso, usamos todas as $K-1$ operações restantes na última reta do convex hull (que é aquela com maior $a$ ). Finalmente, aplicamos a operação do segundo tipo, calculando, com isso, a resposta.

A complexidade total desse código é $O(Qlog_2N + Nlog_2N + Mlog_2M)$ .

Clique aqui para conferir o código.

Subtaks

Nem todas as subtaks do problema precisavam dessas observações e/ou desses algoritmos. Apresentaremos ideias gerais de cada uma delas abaixo.

Subtarefa 2 ( $N = M = K = 2$ ): Nessa parcial, somente a independência entre o $X$ e a ordem da segunda operação precisa ser notada: podemos só testar toda combinação de cada operação. Nota: É necessário fazer as partes separadamente para evitar overflow.
Subtarefa 3 ( $M = 1, Q = 1$ , é garantido que a quantidade final não excede $10^9 + 7$ ): Aqui, não é preciso resolver a segunda parte do problema. Ademais, a primeira parte pode ser resolvida com a mesma ideia, mas sem o uso do convex hull. Além disso, soluções que contém erro no cálculo do módulo ou que tentam maximizar o resto da resposta ao invés da resposta em si passam aqui.
Subtarefa 4 ( $N, Q, K \leq 500, M = 1$ ): Ainda não é necessário resolver a segunda parte; a primeira parte pode ser resolvida apenas testando qual a melhor reta para cada operação.
Subtarefa 5 ( $N, Q, K, M \leq 500$ ): A segunda parte precisa ser resolvida como descrito; a primeira parte pode ser resolvida apenas testando qual a melhor reta para cada operação.
Subtarefa 6 ( $N, Q \leq 3000$ ): A segunda parte precisa ser resolvida como descrito; todas as observações da primeira parte são necessárias, mas pode-se só testar a reta ótima para o primeiro $X$ , ao invés de implementar convex hull.
Subtarefa 7 (Sem restrições adicionais): A solução descrita no comentário.