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:
| #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:
| 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:
| //[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:
| //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:
| #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.