OBI 2024 Programação Júnior Terceira Fase

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 nossos materiais.

Cadeado

Comentário por Henrique Vianna

Conhecimento prévio necessário:

Loops

Perceba que cada um dos discos do cadeado é independente dos outros. Isso quer dizer que para minimizar o total de cliques, basta minimizar a quantidade de cliques para cada um dos discos. Para cada disco há duas opções: girá-lo no sentido horário ou anti-horário (até que se chegue no dígito desejado). Então, para cada um dos deles, deve-se calcular o número de cliques para cada sentido e escolher o menor.

Segue o código:

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

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

	int n; cin >> n;

	int resp = 0;

	for(int i = 1; i <= n; i++)
	{
	int c, s; cin >> c >> s;

	int horario = (c > s ? c - s : s - c);
	int antihorario = (c > s ? 10 + s - c : 10 + c - s);

	resp += min(horario, antihorario);
	}

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

view raw

Cadeado.cpp

hosted with ❤ by GitHub

Amigos

Comentário por Murilo Maeda Kataoka

Para resolver esse problema, são necessárias apenas algumas observações.

Vamos antes, definir que $sup[i]$ guarda em que lugar o i-ésimo amigo de Luiza que está no lado superior está sentado e que $inf[i]$ guarda a mesma informação, mas para os amigos no lado inferior da mesa.

Observação 1: Não haverá mudança de ordem relativa entre os amigos de um mesmo lado da mesa (não haverá uma situação onde um dos amigos de luiza troca de lugar com outro amigo de luiza).

Prova: Para provar isso, vamos supor que, na configuração final que minimiza o número de trocas, dois amigos, $a$ e $b$ , que, estavam posicionados de forma que $a$ estava na esquerda de $b$ , acabam com $a$ na direita de $b$ , assim como é mostrado na imagem:

Mas, trocar não é ótimo para chegar na posição final, já que, imagine o momento em que $a$ troca de lugar com $b$ (ou vice-versa). Ao invés de fazer essa troca, poderíamos fazer $a$ ir para o lugar final que era de $b$ e $b$ ir para o lugar final de $a$ e, como não faz diferença quem está sentado na frente de quem, atingimos o mesmo resultado com 1 operação a menos. Então, não faz sentido mudar a ordem relativa dos amigos, já que sem mudar a ordem relativa, a resposta é sempre menor do que trocando a ordem relativa. Portanto, o primeiro da parte superior sentará na frente do primeiro da parte inferior, o segundo da parte superior sentará na frente do segundo da parte inferior e assim por diante.

Observação 2: O número mínimo de trocas para colocar o i-ésimo da parte superior com o i-ésimo da parte inferior é $|sup[i] - inf[i]|$

Prova: Perceba que, a cada troca que fazemos que move ou o amigo superior em direção ao inferior ou o inferior em direção ao superior, a diferença entre as suas posições descresce em 1. Então, o mínimo possível para colocá-los um na frente do outro é se todas as trocas que fizermos com esses dois diminuir a distância entre suas posições em 1.

Observação 3: A resposta ótima é $\sum_i ^ K |sup[i]-inf[i]|$ e sempre é possível atingir essa construção.

Prova: Como visto na observação 2, o mínimo para colocar dois amigos um na frente do outro é $|sup[i] - inf[i]|$ , então faz sentido o mínimo total ser $\sum_i ^ K |sup[i]-inf[i]|$ . Para provar que é sempre possível atingir esse resultado, basta ver que a seguinte maneira de construir a resposta o atinge sempre: quando for colocar o i-ésimo amigo superior com o i-ésimo inferior, basta pegar o que está mais para a direita dos dois e fazer trocas com ele para a esquerda até ele chegar na mesma posição do outro. Por exemplo, se sup[i] = 5 e inf[i] = 7, basta que o amigo da parte inferior faça duas trocas para a esquerda até chegar na posição do amigo que está na parte superior da mesa. Nessa construção, são usadas $|sup[i] - inf[i]|$ trocas para cada i, ou seja, $\sum_i ^ K |sup[i]-inf[i]|$ no total. Essa maneira de fazer a resposta sempre é possível porque $min(sup[i],inf[i]) < min(sup[i+1],inf[i+1])$ para todo i, então sempre é possível ir levando o que está mais para a direita para o que está mais para a esquerda sem nenhuma interferência.

Solução:

Agora, basta calcular $\sum_{i = 1} ^ {K} |sup[i] - inf[i]|$ . Para fazer isso, basta iterar pelos $i$ possíveis e somar $|sup[i] - inf[i]|$ na resposta.

Segue o código:

	#include<bits/stdc++.h>
	using namespace std;
	const int MAXN = 150010;

	int sup[MAXN],inf[MAXN];


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

	int N,K; cin >> N >> K;


	//Leitura da entrada
	int cntSup = 0;
	for(int i = 1; i <= N; i++)
	{
	int cur; cin >> cur;

	if(cur == 1)
	{
	cntSup++;
	sup[cntSup] = i;
	}
	}

	int cntInf = 0;
	for(int i = 1; i <= N; i++)
	{
	int cur; cin >> cur;

	if(cur == 1)
	{
	cntInf++;
	inf[cntInf] = i;
	}
	}

	//Cálculo do somatório
	long long int resp = 0;
	for(int i = 1; i <= K; i++)
	{
	resp += abs(sup[i] - inf[i]);
	}

	cout << resp << "\n";
	}

view raw

amigos.cpp

hosted with ❤ by GitHub

Entrevistas

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

Subtarefa 2 e 3: N<=500 e K<= 50

Observe que a tabela de amizades nada mais é do que uma matriz de adjacência, ou seja, podemos resolver o problema utilizando o conceito de grafos. Com isso, a amizade entre dois candidatos representa uma aresta que liga os vértices dessas duas pessoas. Logo, para responder cada entrevista, marcamos todos os candidatos presentes por meio de um vetor que indica se o vértice é um candidato ativo ou não. Depois, para cada candidato, fazemos uma dfs a partir dele. Se nessa dfs chegarmos em um vértice que está ativo, quer dizer que pelo menos dois candidatos são amigos e, por isso, a resposta tem que ser 'S'. A complexidade fica $O(E*K*N)$ .

Subtarefa 4: Cada candidato possui no máximo um amigo

Como cada candidato possui no máximo um amigo, basta verificarmos, para cada entrevista, se o amigo daquele candidato está presente ou não. Ao ler a entrada da tabela de amizades, vamos criar um vetor para guardar um único valor, que será o índice do amigo daquele candidato.Em seguida, em cada entrevista, vamos marcar em um vetor quais candidatos estão ativos. Daí, para cada candidato, vamos consultar no vetor com o amigo de cada pessoa se o candidato está ativo ou não. Se estiver, quer dizer que tem dois amigos e, por isso, marcamos a resposta como 'S'. A complexidade fica $O(E*K)$ .

Subtarefa 5: Sem restrições adicionais

Como visto anteriormente, vamos transformar a tabela de amizades em um conjunto de grafos. Observe que podemos ter vária componentes, ou seja, vários grupos de amigos que não compartilham arestas em comum. Por isso, para resolver o problema, para cada candidato, de 1 até N, vamos verificar se ele já pertence a uma componente ou não, ou seja, se ele já foi visitado anteriormente por uma dfs. Se ele já tiver sido visitado, continuamos. Caso contrário, adicionamos +1 na variável que mostrará quantas componentes já temos. Em seguida, fazemos uma dfs a partir dele. Com isso, todo mundo que é conectado com ele por algum amigo irá pertencer ao mesmo grupo.

Depois, para cada entrevista, criamos um set para indicar as componentes do candidatos presentes. Para cada candidato, verificamos se a componente dele está presente no set. Se estiver, quer dizer que alguém do mesmo grupo dele já foi adicionado anteriormente e, por isso, a resposta tem que ser 'S'. Caso contrário, adicionamos o índice da nova componente em nosso set e continuamos. Ao final, se não tiver repetido componentes, a resposta será 'N'. A complexidade fica $O(N + E*logK)$ .

Clique aqui para conferir o código.

Hotel Nlogônia

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

Subtarefa 2: N <= 400 e W <= 3000

Vamos guardar a soma de prefixos dos preços dos hotéis. Depois, vamos testar todos os intervalos [L,R] para ver se a soma não ultrapassa o limite W. Para isso, vamos percorrer L até R e achar o maior valor para um intervalo de D dias consecutivos. Podemos fazer isso pegando o maior resultado de SomaPrefixo[i] - SomaPrefixo[i-D-1], desde que i - D não seja menor que L. Esse resultado representa a maior quantia de dinheiro que poderá ser economizada. Em seguida, basta verificar se SomaPrefixo[R] - SomaPrefixo[L-1] - maiorValorParaDDias é menor ou igual a W. Ao final, queremos saber qual é o tamanho do maior intervalo válido (R-L+1). A complexidade fica $O(N^3)$ .

Subtarefa 3: N <= 3000, W <= 3000 e $p_i$ = 1 ou $p_i$ = W + 1

Para cada dia, vamos guardar a quantidade de dias anteriores consecutivos que têm preço igual a 1. Vamos também guardar a quantidade de dias posteriores consecutivos que têm preço 1. Após isso, para cada dia $i$ , vamos ver qual é a quantidade de preços 1 consecutivos antes a ele e a quantidade de dias com preço igual a 1 consecutivos depois do dia $i + D$ . Com isso, a nossa resposta será o maior valor de $max(resposta, D + min(W, anterior[i] + posterior[D + i])$ . A complexidade fica $O(N)$ .

Subtarefa 4: N <= 3000 e W <= 3000

Vamos utilizar a técnica da programação dinâmica para achar a maior quantidade de dias. Os estados da nossa $dp[i][W_j][2]$ serão: dp[posiçao atual][dinheiro restante][0 - se não foi utilizado os D dias gratuitos ou 1 - se os D dias já foram utilizados]. Com isso, as transições serão as seguintes:

dp[i][ $W_j$ ][1] = max(dp[i-1][ $W_j$ -p[i]][1] + 1, dp[i-D][ $W_j$ ][0] + D)
dp[i][ $W_j$ ][0] = dp[i-1][ $W_j$ - p[i]][0] + 1

Depois de calcular o valor, vamos ver se a maior quantidade de dias é maior que o máximo até aquele momento. Se for, atualizamos a resposta. A complexidade fica $O(N*W)$ .

Subtarefa 5: $p_i$ >= $p_(i+1)$

Como os preços vão estar ordenados, vamos começar do final e ir somando os dias até o limite de W. Depois, adicionamos D. Com isso, temos a resposta. A complexidade fica $O(N)$ .

Subtarefa 6: Sem restrições adicionais

Vamos manter a ideia de armazenar as somas de prefixos. Além disso, para acharmos a resposta vamos utilizar a técnica de Two Pointers. Basicamente, vamos definir o início do intervalo e ir aumentando o fim do nosso intervalo até que a soma a ser paga seja maior que W. Quando atingir a soma maior que W, avançamos em uma posição o início do nosso intervalo. Toda vez que avançarmos o final, vamos adicionar o preço a uma variável que indica a soma dos preços do intervalo e adicionamos a soma dos últimos D dias que acabam naquele mesmo final em um Multiset. Como queremos maximizar a quantidade de dias, vamos pegar o maior valor do Multiset e ver se a diferença entre a soma do dos preços do intervalo menos esse maior valor é maior que W. Se for não for, o intervalo [L,R] é válido e a quantidade de dias é R-L+1. Daí basta atualizar a resposta se necessário. Se a diferença for menor, vamos avançar o início do intervalo. Ao fazer isso, vamos tirar o preço daquela posição da soma de preços e remover do multiset a soma dos últimos D dias relacionados àquela posição. Atenção para retirar somente uma ocorrência do valor no multiset. Ao final, teremos salva a resposta e é só imprimir. A complexidade é $O(N*logN)$ .