Seletiva IOI 2020 - Dia 1
Se você quiser se preparar para a OBI e seletiva, 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.
Clique aqui para conferir a prova na íntegra *A seletiva da OBI 2019 foi feita para a IOI 2020
Comida
Escrito por Fernando Gonçalves e Henrique Vianna
Conhecimento Prévio Necessário:
Nesse problema, precisamos ajudar Marcos a escolher os pratos que ele consumirá nos próximos 
dias. No 
-ésimo deles há 
opções de pratos disponíveis. Em cada um dos dias, ele comerá exatamente um prato de comida sendo que esse pode ser ou um prato já oferecido ou uma mistura de dois pratos. Sabendo que ele pode gastar no máximo 
reais, queremos maximizar a soma dos sabores dos pratos escolhidos durante os dias (ou se é impossível comprar um prato em cada dia).
Uma primeira observação é que o mínimo custo possível será igual ao custo dos pratos mais baratos de cada dia. Se esse preço for maior que , já sabemos que é impossível escolher um conjunto com preço no máximo , então a resposta será 
. Senão, sabemos que é possível formar um conjunto de pratos, então só temos que achar o maior sabor possível agora.
Além disso, nunca usaremos pratos que têm custo maior e sabor menor que algum outro prato, pois sempre que usamos esse prato, seja ele sozinho ou em uma mistura, poderíamos estar usando o prato que tem custo menor e sabor maior e, com isso, a resposta aumentaria.
Por fim, temos a observação essencial para a resolução do problema. Se pensarmos nos pratos como pontos no plano, sendo a coordenada 
o custo do prato e a coordenada 
o sabor do prato, teremos que sempre serão usados somente os pratos que, além de não terem pratos com custo menor e sabor maior ao deles (como mencionado anteriormente), pertencem upper hull. Isso acontece pois a mistura de dois pratos é um ponto na reta entre esses dois pratos e, assim, o máximo sabor para cada custo estará no upper hull dos pontos.
Então, para descobrir o sabor máximo possível, podemos considerar que começamos comprando os pratos mais baratos de cada dia e vamos gastando dinheiro na mudança de prato que nos dá mais sabor por dinheiro gasto, ou seja, a reta entre dois pontos que tem maior coeficiente angular. Para fazer isso, guardamos um vetor com o coeficiente angular, gasto máximo e sabor máximo de cada reta e passamos por elas do maior coeficiente para o menor. Em uma reta, sempre gasto o máximo que posso (que é limitado pelo dinheiro que tenho sobrando e pela própria reta) e vejo quanto sabor consigo com isso.
Clique aqui para conferir o código
Times
Comentário por João Pedro Castro
Conhecimento prévio necessário:
Para resolver esse problema podemos modelar as partidas de aquecimento como um grafo, com os vértices sendo os participantes e as arestas ligando os dois jogadores presentes em cada partida. Com esse grafo montado podemos usar a ideia de um grafo bipartido, que é aquele onde é possível "colorir" todos os vértices com duas cores tal que para cada aresta os vértices ligados por ela sejam de cores distintas.
Agora podemos reformular o problema para: "dado um grafo diga de quantas maneiras distintas posso bipartir ele". Perceba que se o grafo não é bipartido a resposta é 0, pois não existe nenhuma maneira. Porém, se o grafo for bipartido podemos olhar para cada componente conexa de maneira distinta, já que elas não interferem com umas as outras; e para uma única componente conexa a resposta sempre é 2, já que o estado de um único vértice determina o de todos os outros pertencentes à mesma componente conexa (ou ele faz parte do time 1 ou do 2). Agora, usando desses dois fatos e do princípio multiplicativo da combinatória podemos só multiplicar o resultado das componentes conexas, chegando ao resultado final:
- Se o grafo não for bipartido
- Se o grafo for bipartido
Como percorremos cada vértice um dos vértices e cada uma das 
arestas a complexidade final é 
.