OBI 2017 – 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 nossos materiais.
Para conferir a prova na íntegra, clique aqui.
Taxa
Comentário escrito por Caique Paiva
Conhecimento prévio necessário:
Seja $$v$$ o vetor em que guardamos como vamos dividir o terreno. Vamos fazer uma dp em intervalo para esse problema! Seja dp[$$l$$][$$r$$] para ser o menor valor para dividir o terreno em $$r-l+1$$ intervalos de tamanho $$v[l], v[l+1], \cdots, v[r]$$. Então, primeiro veja que $$dp[i][i] = 0$$ para todo $$i$$, e então, a transição vai ser
$$dp[i][j] = max(dp[i][k] + dp[k+1][j] + max(sum(i, k), sum(k+1, j))$$
Onde $$k = i$$ e vai até $$j-1$$ e $$sum(i, j)$$ é a soma dos vetores de $$i$$ até $$j$$. Veja que todos essas funções (dp e sum) são cíclicas, então por exemplo, se $$n = 3$$, então $$sum(1, 2) = v[1] + v[2]$$ e $$sum(2, 1) = v[2] + v[3] + v[1]$$. No final, basta retornar $$min(dp[i+1][i])$$ para todo $$i$$.
Para fazer um vetor circular (como é mostrado no código), a ideia é fazer todas as operações módulo $$n$$, ou seja, quando fazemos $$i-1$$, se $$i$$ for ficar negativo, fazemos $$(n+i-1) % n$$.
Clique aqui para conferir o código
Postes
Comentário escrito por Enzo Dantas
Conhecimento prévio necessário:
Devemos contar quantos postes devem ser substituídos e quantos devem ser consertados. Para fazer isso, devemos contar quantos postes tem uma altura menor que 50 e quantos tem uma altura entre 50 e 84 (a partir de 85 ele pode ser usado normalmente). Assim, vamos manter dois contadores: $$substitui$$ e $$conserta$$. Ao lermos o input, aumentaremos $$substitui$$ em 1 toda vez que encontrarmos um número menor que 50 e aumentaremos $$conserta$$ em 1 toda vez que encontrarmos um número maior ou igual a 50 e menor que 85.
No fim, printaremos $$substitui$$ e $$conserta$$.
Clique aqui para conferir o código
Dividindo o Império
Comentário escrito por Arthur Lobo
Conhecimento prévio necessário:
O problema fala que “Alguns pares de cidades estão ligados diretamente por estradas bidirecionais e, por uma antiga tradição, esses pares são escolhidos de maneira que sempre é possível ir de qualquer cidade para qualquer outra cidade por exatamente um caminho (um caminho é uma sequência de estradas).”. Isso quer dizer que o grado do problema é uma árvore.
Então, dado uma árvore, o problema pergunta qual a aresta a ser removida tal que o tamanho das 2 árvores geradas após a remoção seja o mais próximo possível.
A ideia aqui vai ser calcular qual é esse valor para cada aresta e pegarmos o mínimo. Para isso, vamos enraizar a árvore em algum vértice, digamos que seja o vértice 1, e definimos $$S_u = $$tamanho da subárvore que tem $$u$$ como raiz. Exemplo:
Para calcular o valor de $$S_u$$, basta perceber que o tamanho da subárvore de $$u$$ é o somatório do tamanho da subárvore dos filhos $$+1$$, então podemos fazer uma $$dfs$$ em que calculamos primeiro os $$S$$ dos filhos de $$u$$ e depois $$S_u$$.
Perceba que ao deletarmos a aresta entre qualquer vértice $$u \ne 1$$ e seu pai, o tamanho das duas árvores resultantes serão $$S_u$$ e $$N-S_u$$, então basta fazermos um for e pegarmos o menor valor de $$|S_u-(N-S_u)|$$.
Clique aqui para conferir o código
Arranha-céu
Comentário escrito por Caique Paiva
Conhecimento prévio necessário:
Esse problema é uma aplicação simples de BIT. Vamos codar uma BIT de soma, igual a feita na aula colocada no link acima, e nós sabemos que ela responde a query e faz o update em $$O(log n)$$. Além disso, vamos guardar o vetor atual, que guarda a quantidade de pessoas em cada apartamento. Na query, retornamos o valor de $$query(pos)$$ que ele nos dá, e no update, fazemos $$update(pos, val – v[pos])$$ com o valor e posição que eles no dá na query, e fazemos $$v[pos] = val$$.
Clique aqui para conferir o código
Código
Comentário escrito por Arthur Lobo
Conhecimento prévio necessário:
O problema nos dá uma lista $$S_1,S_2,…,S_N$$ $$strings$$ com 10 caracteres cada e nos pergunta se existe qual é a primeira $$string$$ $$S_i$$ que é uma $$substring$$ da contatenação de duas $$strings$$ $$S_a,S_b$$, com $$1 \le a,b < i$$, ou dizer que não existe nenhum.
*Para uma string $$T$$, vamos definir $$T[a:b]$$ como sendo a $$substring$$ $$T_{a},T_{a+1},…,T_{b}$$, ou seja, a $$substring$$ de $$a$$ até $$b$$ de $$T$$. Além disso, vamos usar 0-indexado, ou seja, a $$string$$ $$T$$ inteira é $$T[0:T.size()-1]$$.
Parcial 1 ($$ N \le 100$$)
Nossa primeira ideia pode ser, para cada $$i$$, testar todo par $$a,b < i$$ e ver se existe alguma $$substring$$ de $$S_aS_b$$ igual à $$S_i$$. Para cada par, vamos criar uma nova $$string$$ $$T = S_aS_b$$ e ver se $$T[j:j+9] = S_i$$, para $$0 \le j \le 10$$, se algum for, então encontramos o $$i$$.
A para cada par $$a,b$$, nós checamos em 10 operações (apesar de ser $$O(1)$$, 10 é uma constante relativamente alta). Já que existem $$O(N^2)$$ pares para cada $$i$$, e temos $$N$$ $$i$$s, a complexidade final fica $$O(N^3)$$, fazendo na verdade ~$$10*N^3$$ operações, que é o suficiente para essa subtask.
Parcial 2 (Sem restrições adicionais)
Vamos dar uma olhada em uma representação visual de quando $$S_i$$ é uma $$substring$$ de $$S_aS_b$$, com as posições correspondentes em $$S_i$$ e na contatenação sendo iguais.
Basicamente vai existir um $$x$$ tal que $$S_i$$ é a contatenação das últimas $$x$$ posições em $$S_a$$ e as primeiras $$10-x$$ posições em $$S_b$$.
Para ser mais específico, para que $$i$$ seja uma $$substring$$, deve existir algum $$0 \le x \le 10$$ tal que
- Para algum $$a < i$$, $$S_i[0:x-1] = S_a[10-x:9]$$ (primeiras $$x$$ posições de $$i$$ e últimas $$x$$ de $$a$$ são iguais).
- Para algum $$b < i$$, $$S_i[x:9] = S_b[0:9-x]$$ (últimas $$x$$ posições de $$i$$ e primeiras $$x$$ de $$b$$ são iguais).
Agora basta guardarmos num set $$pre$$ todos os prefixos das strings que já passamos, e em $$suf$$ todos os sufixos das strings que já passamos.
Agora quando estamos em $$i$$, basta checarmos se existe algum $$x$$ tal que $$S_i[0:x-1]$$ está em $$suf$$ e $$S_i[x:9]$$ está em $$pre$$. Se existir, então $$i$$ é a resposta. Por fim, colocamos todos os prefixos de $$S_i$$ em $$pre$$ e o mesmo com os sufixos em $$suf$$.
A complexidade fica $$O(N*10*log(N)$$.
Clique aqui para conferir o código