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:
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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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'; | |
| } |
Retas
Comentário escrito por Fernando Gonçalves
Conhecimento prévio necessário:
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 abscissa $$X_1$$.
Para tanto, podemos manter um map de frequências, indicando quantas retas existem em um $$y$$ na abscissa $$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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } | |
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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //[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 = pos*2, d = pos*2 + 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); | |
| } |
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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //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 = pos*2, d = pos*2 + 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); | |
| } |
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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| #define INF 0x3f3f3f3f | |
| using namespace std; | |
| const int MAXN = 1e5 + 10; | |
| const int LOG = 22; | |
| int seg[MAXN*4],marc[MAXN*4], 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 = pos*2, d = pos*2 + 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 = pos*2, d = pos*2 + 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); | |
| } | |
| } | |
| } |
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.
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.
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.