Problema B - Trabalhadores em linha

O Problema

Dado o número $N$ de trabalhadores, $K$ de problemas que estão inicialmente na posse do primeiro trabalhador, o valor $P_i$ do tempo que cada trabalhador demora a verificar um problema e o tempo $Q$ que demora cada trabalhador a entregar um problema ao próximo, calcula o menor tempo possível no qual se conseguem verificar todos os problemas.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ $N$ ≤ 100 000		Número de trabalhadores
1 ≤ $K$ ≤ 1 000 000		Número de problemas a verificar
0 ≤ $Q$ ≤ 1 000 000		Tempo de transportar um problema entre trabalhadores
0 ≤ $P_i$ ≤ 1 000 000		Tempo do trabalhador i verificar um problema

Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:

Grupo	Número de Pontos	Restrições adicionais
1	10	1 ≤ $N$ ≤ 10, 1 ≤ $K$ ≤ 10
2	15	$N$ = 2
3	15	1 ≤ $N$ ≤ 100, 1 ≤ $K$ ≤ 100
4	15	$K$ = 2
5	15	$Q$ = 0
6	30	-

Introdução

Este problema é um pouco não convencional no que toca a problemas das ONI. Mesmo a solução mais simples parece impossível, há tantas estratégias possíveis, como é que as podemos gerar a todas? Para resolver este problema é importante pensar muito no que está a acontecer e tentar perceber que estratégias nunca funcionam e que estratégias funcionam. Para isso vamos desconstruir o problema aos poucos.

Resolver o grupo 4:

Parece estranho, mas vamos começar por resolver o grupo 4, simplesmente porque é o grupo que requer menos observações sobre o problema.

Visto que só há dois problemas, temos de descobrir quem é que os vai verificar, visto que cada problema tem de ser verificado por alguém. Existem cerca de $N^2$ possibilidades para os trabalhadores que verificam os dois problemas, o que é demasiado.

Porém, se o último trabalhador (por último quermos dizer o mais à direita) a verificar um problema for o trabalhador $j$, então o restante problema ou é verificado pelo próprio $j$ ou pela melhor estratégia até $j$, ou seja, a estratégia que otimizava a verificação de apenas um problema (o que seria equivalente a um problema em que $K = 1$ usando apenas os primeiros $j - 1$ trabalhadores). Assim, podemos primeiro pré-calcular qual o trabalhador que minimiza este valor para apenas um problema, para cada valor possível de $j$ (ou seja, a resposta a um problema em que $K = 1$ usando apenas o primeiro trabalhador, a resposta a um problema em que $K = 1$ usando apenas os dois primeiros trabalhadores, etc), o que conseguimos fazer em $O(N)$ ao iterar sobre os $N$ trabalhadores e para cada $j$ calcular o tempo que demoraria a um problema de ser entregue a $j$ e depois processado por $j$, atualizando se este valor for melhor do que os anteriores calculados.

Tendo este valor pré-calculado podemos guarda-lo numa array $precalc[i]$, ou seja, a resposta ao problema em que $K = 1$ usando apenas os primeiros $i$ trabalhadores. Podemos calcular quanto tempo demora a verificar os dois problemas caso o último trabalhador a verificar seja o trabalhador $j$, para todos os $j$. Se $j$ for o último trabalhador, então ou: ele verifica um problema, e demora $Q \cdot i + P_i$ e o outro problema demora $Q + precalc[i - 1]$ a ser verificado (temos um fator adicional de $Q$ pois temos de esperar que o primeiro trabalhador envie o primeiro problema até podermos enviar o segundo), ou seja, o tempo total é o máximo destes dois; ou ele verifica ambos os problemas e demora $Q \cdot i + 2 \cdot P_i$.

Esta solução tem complexidade temporal $O(N)$, visto que apenas fazemos dois ciclos pelos trabalhadores todos, mas só funciona se $K = 2$, logo obtém 15 pontos.

Resolver o grupo 5

Neste grupo temos a restrição adicional que o tempo de entregar um problema é 0, o que significa que qualquer problema pode ser verificado por qualquer trabalhador sem qualquer custo adicional tirando o seu custo de verificação, isto é, se o trabalhador $j$ tiver que verificar $x$ problemas ele demora no total $P_j \cdot x$ segundos. Assim, a única coisa que temos de fazer é distribuir problemas por utilizadores.

Vamos considerar que já distribuimos os primeiros $i$ problemas de forma ótima e que queremos escolher um trabalhador para verificar o problema $i + 1$. Reparem que o tempo para verificar os problemas é o máximo dos tempos que cada trabalhador demora a verificar os seus problemas. Assim, queremos escolher o trabalhador que ao verificar este novo problema aumenta este máximo o mínimo possível. Para isso podemos ver como mudaria o máximo se escolhessemos o trabalhador $j$, para todos os $j$, e no fim escolhemos o melhor. Podemos repetir esta ideia $N$ vezes, começando com uma distribuição vazia, escolhemos o trabalhador que menos altera o máximo dos tempos de todos os trabalhadores para verificar o primeiro problema, de seguida o mesmo para o segundo, etc. Para escolhermos qual o trabalhador que menos altera o máximo temos que calcular o tempo total que cada trabalhador demoraria se processasse o novo problema além dos que já estava a verificar. Podemos fazer isso iterando por todos os trabalhadores, mas assim cada uma destas operações precisa de tempo $N$ e temos $K$ problemas a adicionar, o que faria a nossa solução ficar $O(NK)$, o que é muito lento.

Para melhorar esta complexidade podemos fazer o seguinte: guardamos o número de problemas que cada um verifica (inicialmente 0), e o tempo que demorariam se verificassem mais um, que demora tempo total $O(N)$. Agora, podemos guardar estes valores numa estrutura de dados de acesso logarítmica, como uma árvore binária de pesquisa balanceada. Se não conhecem este conceito consultem o artigo relevante:

Utilizando esta estrutura de dados, para adicionar um problema escolhemos o trabalhador com menor tempo de demoraria se verificasse mais um problema. De seguida atualizamos este trabalhador ao alterar o seu valor na estrutura de dados para o valor que tinha mais o seu custo de verificar um problema.

A complexidade desta solução é então $O(K\log(N))$, visto que adicionar um problema tem agora custo $O(\log(N))$, graças ao uso da estrutura de dados. Assim, esta solução obtém 15 pontos.

Resolver os grupos 1 e 2

A primeira observação que podemos fazer sobre o problema geral, é que se um trabalhador entregar alguns problemas e verificar outros, é sempre melhor entregar primeiro todos os problemas que tem a entregar e apenas depois verificar os que tem a verificar. Isto pois o tempo que o próprio demora a executar as suas ações não muda com o alterar a ordem das suas ações, mas quanto mais cedo ele entregar os seus problemas mais cedo pode o seu vizinho começar a executar as suas ações neles. Não é óbvio que o tempo é igual para qualquer ordem das suas ações, e se ele tiver que esperar por um problema? Por exemplo, se ao entregar um problema tiver que esperar um pouco até receber o próximo, é possível que tivesse sido melhor simplesmente verificá-lo. Bom, vamos considerar primeiro o trabalhador 1. Ele nunca espera por problemas, por isso é claro que para ele esta propriedade verifica-se. E para o trabalhador 2? Vamos assumir que o trabalhador 1 segue esta regra, ou seja, entrega primeiro todos os problemas que tem a entregar e apenas depois verifica os que tem a verificar. Neste caso os problemas chegam ao trabalhador 2 em intervalos de $Q$ segundos. Se o trabalhador 2 decidir entregar o primeiro problema que recebeu, assim que terminar passaram exatamente $Q$ segundos, logo já recebeu o problema seguinte. Visto que $Q < P_i$ para todos os $i$, se ele decidir verificar o primeiro problema em vez de o entregar, também não há nenhum tempo de espera por mais um problema. Logo o mesmo se aplica para o trabalhador 2. Se assumirmos o mesmo com o trabalhador 2, usando o mesmo raciocínio concluimos que o trabalhador 3 também verifica a propriedade. E o 4 então. E o 5... Ou seja todos verificam (formalmente, o argumento segue por indução).

Assim, podemos resolver o problema ao tentar todas as possibilidades de, para cada trabalhador, quantos problemas ele entrega e quantos verifica. Por exemplo, se $N = 2$, isto corresponde a verificar todos os pares $(x, K - x)$, onde $x$ é o número de problemas a verificar pelo trabalhador 1, e $K - x$ pelo 2. Como sabemos a ordem em que cada um verifica/entrega problemas, isto chega para definir uma estratégia.

Para valores maiores de $N$, basta fazer algo como uma função recursiva que recebe como argumento o trabalhador atual e o número $X$ de problemas restantes. De seguida tentamos todas as possibilidades de a este trabalhador todos os valores entre $0$ e $X$, e calcular recursivamente o ótimo para o seu vizinho, com o número de problemas restante. Paramos quando tivermos processado todos os problemas.

Após ter uma distribuição de problemas por trabalhadores, onde o trabalhador $i$ verifica $X_i$ problemas, podemos calcular o tempo que demora a executar a nossa estratégia da seguinte forma: o trabalhador $i$ espera $Q \cdot (i - 1)$ segundos até receber o primeiro problema (visto que o trabalhador 1 tem de passar um problema ao 2, que tem de passar ao 3 e por ai for até ao $i$; seja $Y_i$ o número de problemas que todos os trabalhadores a seguir ao i-ésimo verificam (o que é equivalente a dizer $X_{i + 1} + \ldots + X_{N}$), posteriormente demora $Q \cdot Y_i$ a entregar esses problemas ao seu vizinho; finalmente demora $P_i \cdot X_i$ a verificar os problemas que tem de verificar. No total, o trabalhador $i$ termina o seu trabalho $Q \cdot (i - 1) + Q \cdot Y_i + P_i \cdot X_i$ segundos após o início.

De certa forma, a solução para o grupo 1 parece mais complicada do que a solução do grupo 2. Para este estilo de solução isso é verdade, mas o grupo 1 também admitia soluções mais "brutas" que testassem todas as estratégias possíveis, o que não é possível para o grupo 2.

A complexidade desta solução é proporcional ao número de maneiras de particionar $K$ em $N$ conjuntos. Para quem sabe um pouco de combinatória, isto é equivalente a $\binom{N + K - 1}{K}$. Assim, esta solução resolve os dois primeiros grupos e obtém 25 pontos.

Resolver o grupo 3

Nota: é importante ler as soluções anteriores para perceber esta solução completamente.

Mesmo com a observação importante que fizemos no problema anterior, parece impossível testar todas as estratégias possíveis para valores de $N$ e $K$ maiores. Porém, quando temos um problema em que há muitas estratégias ou estados, muitas vezes é possível aplicar uma técnica que já ouvimos falar repetidamente: programação dinâmica. Se nunca ouviram falar, como sempre, consultem o artigo:

Vamos considerar o seguinte estado de programação dinâmica $(i, j)$ que representa o menor tempo necessário para verificar $j$ problemas considerando apenas os primeiros $i$ trabalhadores e entregar os restantes $K - j$ problemas ao vizinho do trabalhador $i$ (ou seja, ao trabalhador $i + 1$). Para o estado $(1, j)$, isto é, menor tempo necessário para o trabalhador 1 verificar $j$ problemas e entregar os restantes $K - j$, a resposta é fácil: $P_1 \cdot j + Q \cdot (K - j)$.

Para um outro estado $(i, j)$, podemos colocar o trabalhador $i$ a verificar um qualquer número $l$ entre $0$ e $j$ (visto que só os primeiros $j$ problemas são processados pelos primeiros $i$ trabalhadores) e entregar o resto. Notem que isto equivale a testarmos quantos problemas é que o trabalhador $i$. O valor a que tal corresponde é o mínimo, para todos os valores possíveis de $l$ no intervalo $0$ e $j$, de entre: o máximo entre o valor do estado $(i - 1, j - l)$ (o tempo que os primeiros $i - 1$ trabalhadores demoram a verificar os primeiros $j - l$ problemas, visto que $l$ deles vão ser processados pelo trabalhador $i$) e $Q \cdot (i - 1) + Q \cdot (K - j)) + P_i \cdot l$ (o tempo que o trabalhador $i$ demora a esperar que o primeiro problema atravesse os $i - 1$ trabalhadores anteriores e lhe chegue à sua pilha, mais entregar os restante $K - j$ problemas e finalmente verificar $l$ problemas). No fim, a resposta é o mínimo dos valores de $(i, K)$ para todos os $i$ entre $1$ e $N$.

Assim torna-se evidente como aplicar programação dinâmica aqui: quando calcularmos o valor de um certo estado $(i, j)$ guardamos esse valor e não o voltamos a calcular, quando voltarmos a precisar de o usar usamos o valor que temos guardado.

A nossa programação dinâmica tem $NK$ estados e para cada um precisamos de no máximo $K$ operações para calcular o seu valor, para uma complexidade temporal total de $O(NK^2)$. Esta solução é suficiente para obter os grupos 1, 4 e, claro, 3, ou seja, para aproximadamente 40 pontos.

Solução ótima

Nota: é importante ler as soluções anteriores para perceber esta solução completamente.

Depois de tantas soluções e observações, vamos finalmente ver como resolver o problema por completo. Para isso vamos primeiro simplificar o problema ligeiramente e tentar resolver primeiro esta versão simplificada. Em vez de perguntar "Qual o menor tempo possível para verificar todos os problemas" vamos perguntar "Dado um valor $t$, será que conseguimos verificar todos os problemas com no máximo $t$ segundos?".

Podemos observar que, para esta versão simplificada do problema, cada trabalhador só tem de se preocupar em obedecer ao tempo limite de $t$ segundos. Isto significa que o melhor a fazer é verificar o máximo de problemas possível e entregar os restantes (sendo que sabemos que vamos primeiro entregar os problemas e só depois verificar). Podemos ver que isto funciona porque se um trabalhador não o fizer, vai sempre produzir uma distribuição com tempo mínimo maior ou igual, pois o melhor é aproveitar ao máximo o tempo que tem disponível.

Assim, para cada trabalhador $i$ calculamos o máximo número de problemas que ele pode verificar $j$ tal que o tempo que ele demora a verificá-los e a passar os restantes não exceda $t$. Claramente este valor depende dos problemas verificados pelos trabalhadores anteriores, por isso temos de calcular este valor progressivamente para cada trabalhador do 1 até ao $N$. Vamos supor que os trabalhadores até ao trabalhador $i$ coletivamente verificaram $x$ problemas, então queremos calcular o maior valor de $j$ entre $0$ e $K - x$ (pois restam $K - x$ problemas para verificar) tal que o tempo que ele demora, ou seja, $Q \cdot (i - 1) + Q \cdot (K - x - j) + P_i \cdot j$ (a fórmula que já vimos várias vezes), seja menor que $t$. Se fizermos algumas contas podemos ver que o valor é exatamente $\left \lfloor \frac{t - Q \cdot (i - 1 + K - x)}{P_i - Q} \right \rfloor$ (onde $\left \lfloor x \right \rfloor$ significa $x$ arredondado para baixo). Estas contas não são difíceis, basta manipular a inequação $Q \cdot (i - 1) + Q \cdot (K - x - j) + P_i \cdot j \leq t$, isolando o valor de $j$ na expressão da esquerda.

A ideia agora é então aplicar este método e descobrir o número máximo de problemas que o trabalhador 1 consegue verificar no limite de tempo $t$, usar este valor para calcular o número máximo de problemas que o trabalhador 2 consegue verificar no limite de tempo $t$, etc. Se eventualmente tivermos que os primeiros $i$ trabalhadores verificaram os $K$ problemas, podemos parar e sabemos que a resposta é sim, conseguimos verificar todos os problemas com no máximo $t$ segundos. Caso contrário, se depois de passarmos pelos $N$ trabalhadores ainda tivermos problemas por verificar, então a resposta é não, não conseguimos verificar todos os problemas com no máximo $t$ segundos.

Reparem que a solução deste problema simplificado é $O(N)$, pois só temos de percorrer todos os trabalhadores. Mas como podemos usar a solução deste problema simplificado para resolver o problema original? Observem que se conseguimos verificar todos os problemas em $t$ segundos, também conseguimos em $t + 1$ segundos e, analogamente, que se não é possível verificar em $t$ segundos também não é em $t - 1$ segundos. Isto significa que podemos aplicar a técnica clássica de pesquisa binária. Vamos considerar que $M$ é o tempo máximo que os trabalhadores podem demorar, ou seja, um limite superior que sabemos que vai ser sempre maior que a reposta (por exemplo 1 000 000 000 000 é um valor possível, dados os limites do problema, visto que o no pior caso o trabalhador 1 pode verificar todos os problemas). Vamos ver se conseguimos verificar todos os problemas em $M / 2$ segundos. Se não, vemos se conseguimos verificar em $M / 2 + M / 4$. Se sim, vemos se conseguimos verificar em $M / 4$ segundos, e por ai fora. Se nunca ouviram falar de pesquisa binária, consultem o artigo relevante:

A complexidade desta solução é então o número de vezes que resolvemos o problema simplificado ($\log(N)$) vezes o tempo que demoramos a resolver cada instância do problema simplificado ($O(N)$), ou seja, no total é $O(N\log(M))$, o que seria suficiente para os 100 pontos.