OBI 2023 – Fase 3 – Programação Nível 2
Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos os nossos materiais.
Pirâmide
Comentário escrito por Murilo Maeda Kataoka
Conhecimento prévio necessário:
Para esse problema, podemos simplesmente testar todas as possíveis ordens dos 6 números (que são, no total, $$6! = 720$$) e estabelecer quais posições pertencerão a qual camada. Isto é, guardo os 6 números da entrada em um vetor e determino que as posições $$0,1,2$$ são a primeira camada, $$3,4$$ são a segunda e $$5$$ é a terceira. Depois, testo todas as ordenações dos 6 números possíveis e checo se em alguma dessas ordenações a condição do enunciado é válida. Se sim, então é possível montar, caso contrário, não é possível montar.
Clique aqui para conferir o código
Transportes
Comentário escrito por Enzo Dantas
Conhecimento prévio necessário:
Subtask 1 (11 pontos): K=1
Como todas as arestas são do mesmo tipo, só precisamos pagar para usar a primeira aresta. Se for possível ir de $$A$$ a $$B$$ (checamos isso com uma dfs), printe $$P[1]$$, caso contrário printe -1.
Subtask 4 (11 pontos): $$K \le 100$$
Para essa subtask, usaremos uma ideia clássica de Dijkstra com vértices auxiliares.
Defina $$dist[u][c]$$ = menor distância para chegar no vértice $$u$$ com a cor $$c$$.
Transição: estamos no vértice $$u$$ com a cor $$c$$ e vamos passar por todas suas arestas. Agora estamos olhando para uma aresta $$(u,v,w)$$ (ou seja, uma aresta entre $$u$$ e $$v$$ de cor $$w$$). Se a aresta atual é da cor que estamos agora, essa aresta tem custo 0. Caso contrário ele tem o custo definido no input. Ou seja, se $$c=w$$, então $$dist[v][w] = dist[u][c]+0$$. Caso contrário, $$dist[v][w] = dist[u][c] + P[w]$$.
Como o primeiro vértice do Dijkstra não terá cor definida, podemos dizer que ele tem uma cor 0, pois ela será diferente de todas as outras cores.
Complexidade: O grafo auxiliar criado tem $$K*N$$ vértices e $$K+M$$ arestas. Pela análise de complexidade normal do Dijkstra, a complexidade final é $$O(KM + KNlog)$$.
Subtask 5 (11 pontos): $$N \le 10^5$$, $$K \le N$$
Para resolver o problema completo otimizaremos a ideia da subtask anterior. Em vez de passar por todas as arestas quando estamos no vértice $$(u,c)$$, passaremos apenas pelos vértices de cor $$c$$ (criamos uma lista de adjacência para cada cor). Evidentemente, isso não considera a troca de de cores. Para resolver isso, criamos um vértice auxiliar de cor 0 para todos os vértices, o qual visita todas as arestas do vértice e é visitado com custo 0 quando estamos com alguma cor diferente de 0 no vértice em questão. Assim, passaremos por cada aresta apenas duas vezes (uma vez no vértice de sua cor e outra vez no vértice sem cor), e a complexidade do Dijkstra ficará O(M+Nlog).
Note que, se declarássemos um array global $$dist[n][c]$$ como fizemos na subtask passada, usaríamos $$O(NK)$$ de memória, o que passa dos limites de memória. Sendo assim, usaremos um map em vez de um array. Perceba que não passaremos por todos os $$NK$$ vértices: um vértice $$(u,c)$$ só pode ser acessado se existir uma aresta de $$u$$ de cor $$c$$. Logo, acessaremos apenas $$\sum{grau_i}$$ vértices no total. Pelo mesmo motivo, também usaremos um map para criar a lista de adjacência de cada cor.
Complexidade: para armazenar e acessar todas as listas de adjacência com map é $$O(Mlog)$$, o que não ultrapassa a complexidade do Dijkstra comum. Logo, a complexidade final é $$O(M+Nlog)$$.
Clique aqui para conferir o código
Oficina Mecânica
Comentário escrito por Caique Paiva
Conhecimentos prévio necessários:
Para esse problema, uma pessoa pode pensar em vários algoritmos gulosos diferentes, porém a maior parte deles dá errado, então, é importante que você saiba provar que algoritmos funcionam e saber construir exemplos que quebram um algoritmo. Vamos provar uma observação antes de construir o algoritmo. Primeiramente, defina $$ \{ X_1, X_2, \cdots, X_n \} $$ uma permutação de $$ \{ T_1, T_2, \cdots , T_n \} $$ de modo que, quando trocarmos 2 carros $$X_i, X_j$$ no mecânico, temos que $$i < j$$, e além disso, a resposta do problema é minima.
Observação: Se $$i < j$$ e trocamos $$X_i$$ por $$X_j$$, então $$X_i < X_j$$.
Prova: Vamos olhar para um mecânico $$M_t$$. Seja $$P_1, P_2, \cdots, P_l$$ os carros que passaram por ele, nessa ordem. Veja que
- $$P_1$$ esperou 0 segundos para entrar
- $$P_2$$ esperou $$P_1M_t$$ segundos para entrar
- $$P_3$$ esperou $$P_1M_t + P_2M_t$$ segundos para entrar.
- …
- $$P_l$$ esperou $$P_1M_t + P_2M_t + \cdots + P_{l-1}M_t$$ segundos para entrar
Então, a somas dos segundos esperados para esse mecânico é $$((l-1)P_{1} + (l-2)P_2 + \cdots + P_{l-1})M_t$$, com isso, se $$P_i > P_j$$ com $$i < j$$, então, podemos trocar eles dois de ordem, então conseguimos uma resposta menor, o que é um absurdo, pois essa é a resposta optimal, então $$P_i < P_j$$ sempre que $$i < j$$.
Com isso, podemos supor que $$ \{ X_1 < X_2 < \cdots < X_n \} $$. Essa observação não é tão importante assim, a parte mais importante é que ela nos mostra a forma da resposta para cada mecânico, que é $$((l-1)P_{1} + (l-2)P_2 + \cdots + P_{l-1})M_t$$, com $$P_1 < P_2 < \cdots < P_{l-1}$$. Então, vamos tentar criar o algoritmo guloso colocando os carros no . Vamos olhar para o $$X_n$$, qual mecânico queremos colocar ele?
Bem, como $$X_n$$ é maior que todos os outros elementos do vetor, temos que sua contribuição na resposta final vai ser nula, então podemos colocar ele em qualquer mecânico. Sendo mais geral, os últimos $$n-m$$ carros não contribuirão na resposta, então, seja $$X_i$$ o primeiro carro em qual colocar ele vai afetar nossa resposta, então, podemos escolher colocar ele no $$M_1$$, assim aumentando nossa resposta em $$X_iM_1$$, ou então no $$M_2$$, assim aumentando em $$X_iM_2$$, e assim vai. Veja que, gulosamente o optimal é pegar o $$j$$ tal que $$M_j$$ é minimo, e assim aumentando nossa resposta em $$M_jX_i$$!
Agora, vamos olhar para o $$X_{i-1}$$. Dá mesma maneira do anterior, gulosamente, é melhor pegar o menor $$M_k$$, mas se pegarmos o mesmo em que colocamos o $$X_i$$, a nossa resposta vai aumentar em $$2X_{i-1}M_j$$ ao invés de só $$X_{i-1}M_j$$, portanto, só vale a pena pegar esse $$M_j$$ se $$2M_j$$ ainda for menor que todos os outros $$M_k$$. Vendo esses casos bases, é fácil de ver qual vai ser nosso algoritmo guloso.
Primeiro, vamos olhar para o nosso vetor em ordem decrescente. Seja $$ \{ V_1 > V_2 > \cdots > V_n \} $$ o nosso vetor $$X$$ ordenado em ordem decrescente.
- Passo $$i$$: Para cada mecânico $$M_j$$, seja $$C_j$$ a quantidade de elementos que já colocamos nele. Então, vemos qual é o mínimo entre $$M_jC_j$$, seja ele $$M_jC_k$$. Adicionamos a nossa resposta $$V_iM_kC_k$$, e aumentamos $$C_j$$ em 1.
Para calcular esses mínimos, podemos manter esses valores numa priority_queue, e então, a complexidade do problema fica $$O(MlogM + N)$$.
Clique aqui para conferir o código
Bonecas
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
Uma dica interessante para este problema é ordenarmos os nossos valores, pois a relação entre as alturas importam. Portanto a dica é: se a ordem dos itens não importar, tente ordenar de alguma forma para ver se alguma ideia surge.
Subtarefa 1 <= $$T_i$$ <= 2
Vamos ordenar os valores de T em ordem crescente. Após isso, o nosso vetor pode ficar:
- 111…111 ou 222…222
Observe que, nos dois casos, a resposta vai ser 0. Para os outros casos, vamos separar os valores em triplas. Quando os valores passam de 1 para 2, temos: ou …112…, ou …122… (para todos os outros casos, temos uma tripla só de 1 seguida de uma só de 2). Para …112… a diferença continua sendo 0 (entre os dois menores). Para …122.. temos dois casos: se tivermos outra tripla antes só de 1, podemos “trocar” o 1 da última posição com o 2 que está na segunda, ficando com (1,1,2) e (1,1,2). Assim, a diferença continua 0. O problema é se não tivermos uma tripla só de 1 antes. Por isso, devemos analisar se o N é maior que 3K. Se for, então podemos simplesmente “excluir” o 1 e ficar com 1,2,2,2…2,2,2, tornando a diferença 0. Caso contrário, a resposta vai ser 1.
Subtarefa N <= 30
Vamos fazer duas observações: se ordenarmos em ordem decrescente, podemos manter o número de bonecas com valores menores e isso irá auxiliar o cálculo da nossa resposta – vamos utilizar uma dp. Além disso, suponha que temos selecionamos quatro bonecas cujos valores serão usados na diferença, sendo x,y,z a diferença entre cada valor:
Como eles serão valores que serão contados em nossa resposta, veja que é sempre melhor agrupar as bonecas mais próximas uma das outras (T_a e T_b) e (T_c e T_d), pois ficamos com a soma dos balanceamentos igual a $$x^2 + z^2$$. Com as outras configurações, teríamos (T_a e T_c) e (T_b e T_d): $$(x + y)^ 2 + (y + z)^2$$ ou (T_a e T_d) e (T_b e T_c): $$(x + y + z)^2 + y^2$$.
Com isso, vamos utilizar uma dp para calcularmos as respostas com os seguintes parâmetros: dp[posição que estamos analisando para ser ou não a boneca com o menor valor do trio][quantidade de trios já formados][quantas bonecas não foram utilizadas] = menor valor de balanceamento possível ( dp[pos][i][j]). Observe que o parâmetro das bonecas não utilizadas servirá para guardar quantos valores maiores que T_pos estão disponíveis para ser a boneca de maior valor do trio – só podemos fazer isso porque os valores estão ordenados em ordem decrescente. Para calcular cada estado dp[pos][i][j], fazemos o mínimo entre:
- dp[pos-1][i][j-1] (caso não utilizarmos a boneca com aquele valor para ser a menor do trio)
- caso a boneca daquela posição for a menor do trio, vamos iterar por todas as bonecas das posições menores que pos para ser a segunda boneca maior- vamos definir a posição da outra boneca como l: dp[l-1][i-1][j – (pos – l – 1)] + (T_l – T_pos)$$^2$$
Iniciamos todos os estados da dp com um valor muito grande para indicar que não foi calculado – também para dizer que é impossível. Temos dp[0][0][0] = 0 como caso base. A complexidade dessa ideia é $$O(N^3 * K)$$.
Subtarefa N <= 1000 e K <= 100
Para esta tarefa, vamos utilizar a mesma ideia da anterior. No entanto, vamos remover um dos parâmetros: quantas bonecas não foram utilizadas. Observe que esta informação nos é útil para garantir que há bonecas maiores em um número suficiente para formar a quantidade de trios que queremos. Porém, podemos suprimir este parâmetro. Em vez de guardá-lo, vamos verificar se a quantidade de bonecas já vistas é maior ou igual a 3 vezes o número de trios (ou seja, se pos >= 3*i). Se não for, marcamos que o estado não é possível. Caso contrário, prosseguimos com o cálculo da dp vendo os estados anteriores. Vamos continuar escolhendo de forma quadrática qual a menor e a segunda menor boneca. A complexidade da ideia é $$O(N^2 * K)$$.
Solução Completa:
A observação essencial que devemos fazer é que, se escolhemos a boneca com T_x para ser a menor do trio, devemos também escolher a boneca com o menor valor maior ou igual a T_x, ou seja, T_x-1. Suponha que temos os valores em ordem decrescente T_a, T_b, T_c, T_d e T_e. Digamos que a resposta é (T_a e T_b) e (T_c e T_e) para k = 2. Veja que podemos melhorar a resposta pois T_d está mais próximo de T_c do que T_e está de T_c (também poderíamos falar que T_d está mais perto de T_e). Logo, se for para fixar uma boneca como a menor do trio, temos que selecionar a boneca imediatamente maior para ser a segunda para minimizar o valor. Com isso transformamos a nossa dp em: dp[posição][quantidade de trios já formados] = menor valor (dp[pos][i]). Para calcular os estados:
- verificamos se posição >= 3*quantidade de trios formados. Caso a condição não seja cumprida, dp[pos][i] = inf (valor muito grande)
- fazemos o mínimo entre dp[pos-1][i] e dp[pos-1][i-2] + (T[pos -1] – T[pos])$$^2$$
O caso base é dp[1][0] = 0 e a resposta vai estar armazenada em dp[N][k]. A complexidade fica $$O(N*K)$$.
Clique aqui para conferir o código
Fastfood
Comentário escrito por Arthur Lobo
Conhecimento prévio necessário:
O problema pede para que minimizemos o máximo. Essa expressão “minimizar o máximo” é comumente associada à busca binária na resposta. A base para todo o problema aqui vai ser que fazer fazer uma busca binária vendo se é possível formar os grupo de modo que a a distância máxima seja no máximo $$D$$. Mas como fazer essa busca?
Obs: $$dist(i,j)$$ vai ser a distaância entre os pontos $$i$$ e $$j$$, ou seja, $$ dist(i,j) = |X_i-X_j| + |Y_i-Y_j|$$.
Subtask 2 ($$N \leq 2000$$)
Depois de fixar um $$D$$ na busca binária, vamos transformar o problema em um grafo. Vamos ligar uma aresta entre todos os pares de vértices que não podem estar no mesmo grupo, ou seja, criamos uma aresta entre $$i$$ e $$j$$ se $$dist(i,j) > D$$.
Agora temos um grafo em que queremos pintar cada vértice de azul ou vermelho e uma aresta significa que os vértices não podem ter a mesma cor. Isso é exatamente a descrição de um Grafo Bipartido.
Podemos checar se um grafo é bipartido tentando colorir ele usando uma dfs. Quando estamos um vértice azul, colorimos todos os seus vizinhos de vermelho e vice-versa. Se um vértice já está colorido de uma cor e tentamos colorir ele com outra, então é impossível bicolorir o grafo.
Essa solução funciona em $$O(N^2)$$ por checada da busca binária, então $$O(N^2logD)$$.
Subtask 3 ($$N \leq 10^5$$)
Primeiro, digamos que temos uma função $$MaxDist(A,B)$$ em que, dado dois conjuntos de pontos $$A$$ e $$B$$, retorna o par $$(i,j)$$, com $$i \in A$$ (está contido) e $$j \in B$$, com maior distância de manhattan, e também retorna essa distância $$dmax$$ ($$MaxDist(A,B) = (dmax,i,j)$$. Suponha também que essa função funciona em $$O(logN)$$ ou $$O(1)$$. No final eu explico como fazer isso, por enquanto só imagine que podemos fazer isso.
Vamos dividir os pontos em $$3$$ conjuntos:
- Conjunto $$A$$ dos pontos azuis. Começa apenas com o ponto $$1$$ (pois, sem perda de generalidade, podemos falar que o ponto $$1$$ é azul).
- Conjunto $$V$$ dos pontos vermelhos. Começa vazio.
- Conjunto $$B$$ dos pontos brancos (ainda não coloridos). Começa com todos os pontos menos o ponto $$1$$.
Agora vamos, aos poucos, colocar os pontos de $$B$$ em $$A$$ e $$V$$. Se tiver algum ponto $$i$$ em $$B$$ que está mais longe do que $$D$$ de $$1$$, então obrigatoriamente esse ponto é vermelho, certo? Porque se ele fosse pintado de azul, então teriam dois pontos no mesmo conjunto com uma distância maior do que $$D$$.
A ideia é repetidamente colocar pontos brancos que “não podem” estar no grupo azul no grupo vermelho e vice-versa. Vamos repetidamente fazer esses dois passos.
- Não pode estar no conjunto azul -> vai pro vermelho: Seja $$MaxDist(B,A) = (dmax,i,j)$$, se $$dmax > D$$, então o ponto $$j$$ deve ser pintado de vermelho. Tiramos ele do conjunto $$B$$ e colocamos no $$V$$.
- Não pode estar no conjunto vermelho -> vai pro azul: Seja $$MaxDist(B,V) = (dmax,i,j)$$, se $$dmax > D$$, então o ponto $$j$$ deve ser pintado de azul. Tiramos ele do conjunto $$B$$ e colocamos no $$A$$.
Mas e se em algum momento nenhuma das duas condições acontecerem, ou seja, se não tiver nenhuma obrigatoriedade a ser feita? Podemos pegar qualquer ponto em $$B$$ e mandar ele tanto para $$A$$ quanto para $$V$$, tanto faz (a prova do porque pode fica como um exercício para o leitor, não é difícil).
No final basta checar se $$MaxDist(A,A)$$ ou $$MaxDist(V,V)$$ é maior que $$D$$ (sim, a função funciona entre dois conjuntos iguais). Se algum for, então é impossível colorir os pontos com a distância $$D$$ e temos que pegar uma distância maior do que $$D$$ na busca binária.
Função mágica de maior distância.
Digamos que temos dois pontos, $$(X_1,Y_1),(X_2,Y_2)$$ e queremos saber a distância de manhattan deles, mas vamos tentar encontrar outro jeito de representá-la sem usar os módulos.
Primeiro, vamos lembrar que $$|a-b| = max(a-b,b-a)$$, mas podemos expandir isso ainda mais, transformando a soma de dois módulos em apenas um máximo: $$|a-b|+|c-d| = max(a-b,b-a) + max(c-d,d-c) = max(a-b+c-d, a-b-c+d, -a+b+c-d, -a+b-c+d)$$.
Dessa maneira, podemos representar $$dis(1,2)$$ como máximo entre esses 4 valores:
- $$(X_1+Y_1) – (X_2+Y_2)$$
- $$(X_1-Y_1) – (X_2-Y_2)$$
- $$(X_2+Y_2) – (X_1+Y_1)$$
- $$(X_2-Y_2) – (X_1-Y_1)$$
Vamos fazer isso com dois conjunto $$A$$ e $$B$$ agora. Já que só precisamos pegar o maior entre esses 4 valores, é isso que vamos fazer, vamos ver cada um dos casos. Com $$i \in A$$ (está contido) e $$j \in B$$:
- $$(X_i+Y_i) – (X_j+Y_j) \rightarrow i$$ vai ser o ponto em $$A$$ com maior $$(X+Y)$$ enquanto $$j$$ vai ser o ponto em $$B$$ com menor $$(X+Y)$$.
- $$(X_i-Y_i) – (X_j-Y_j) \rightarrow i$$ vai ser o ponto em $$A$$ com maior $$(X-Y)$$ enquanto $$j$$ vai ser o ponto em $$B$$ com menor $$(X-Y)$$.
- $$(X_j+Y_j) – (X_i+Y_i) \rightarrow i$$ vai ser o ponto em $$A$$ com menor $$(X+Y)$$ enquanto $$j$$ vai ser o ponto em $$B$$ com maior $$(X+Y)$$.
- $$(X_j-Y_j) – (X_i-Y_i) \rightarrow i$$ vai ser o ponto em $$A$$ com menor $$(X-Y)$$ enquanto $$j$$ vai ser o ponto em $$B$$ com maior $$(X-Y)$$.
Para manter os maiores e menores valores de $$X+Y$$ e $$X-Y$$ enquanto colocamos/tiramos pontos dos conjunto, podemos usar dois sets do C++, um para $$X+Y$$ e outro para $$X-Y$$. Dessa maneira, para cada iteração da busca binária nosso algoritmo de checar funciona em $$O(NlogN)$$, deixando uma complexidade de $$O(NlogNlogD)$$ para a nossa solução. Dependendo da implementação e da constante, essa solução pode ou não passar no tempo limite.
Já que apenas adicionamos pontos em $$A$$ e $$V$$ e apenas removemos pontos de $$B$$, é possivel evitar o uso dos sets deixar a solução $$O(NlogD)$$. Isso será deixado como um exercício para o leitor. O código do site apresenta essa solução em $$O(NlogD)$$.