Solução escrita por Malu Azevedo & Márcio Vitor
Conhecimentos necessários:
O problema nos pede para determinar o número total de fotos válidas (intervalos contíguos de competidores ) em que todos os competidores presentes no intervalo estão satisfeitos. Um competidor fica satisfeito se não tem preferências () ou se pelo menos um de seus amigos também está incluído no mesmo intervalo .
Subtarefa 2 ($N \le 100$) (12 pontos):
para toda intervalo de foto $L,R$ itere por cada competidor de $L$ à $R$ verifique se ele não tem amigos ou se pelo menos um de seus amigos está entre $L$ e $R$. Se todos os competidores satisfazerem a condição adicione um a resposta.
iteramos por $N^2$ fotos no máximo $N$ competidores em cada foto e no máximo $N$ amigos para cada competidor. Portanto a complexidade é $\mathcal{O}(N^4)$ que é suficiente.
Subtarefa 3 ($N \le 500$) (13 pontos):
A observação fundamental para resolver o problema de forma eficiente reside na seguinte observação: para determinar se um competidor (com ) fica insatisfeito em uma foto , não precisamos olhar para todos os seus amigos de forma individual.
Na prática, o que realmente importa são apenas dois pontos de referência:
- O amigo mais à esquerda de que possui índice menor do que (vamos chamar de
esq), se existir. - O amigo mais à direita de que possui índice maior do que (vamos chamar de
dir), se existir.
portanto temos que verificar no máximo $2$ amigos para cada competidor no intervalo e assim a complexidade fica $\mathcal{O}(N^3)$
Subtarefa 4 ($N \le 5000$) (17 pontos):
Para otimizar mais ainda vamos verificar se o intervalo de foto é válido dinamicamente
Fixando $L$ e iterando $R$ de $L$ a $N$, vamos manter uma variável $cnt$ inicializada com $0$ no laço de repetição do $L$ que guarda quantos competidores da foto atual são válidos, perceba que um intervalo é válido se $cnt = R-L+1$ ou seja a quantidade de competidores com amigos no intervalo ou sem amigos é igual ao tamanho do intervalo.
Se o $R$ atual que estamos fixando não tiver amigos ou $esq_R \ge L$ quer dizer que ele já é válido então podemos aumentar $cnt$ direto.
Caso contrário adicione um em $acc[dir[r]]$ caso ele tenha amigo a direita dele onde $acc_i$ guarda quantos caras vão ficar válidos assim que $i$ entrar na foto.
Então adicione $acc[R]$ à $cnt$, e verifique se $cnt = R-L+1$ então aumente a resposta.
Complexidade: $\mathcal{O}(N^2)$
Subtarefa 5 (Para todo competidor $i$ com $a_i \gt 0$, todos os seus amigos têm
índice maior do que $i$) (24 pontos):
Para essa subtarefa em especifico perceba que o intervalo $L,R$, tem que ser tal que $a_R = 0$, pois caso contrário o competidor $R$ não seria satisfeito já que seus amigos tem indice maior que ele
Podemos fixar $L$ iterando da direita para esquerda mantendo uma pilha que guarda quais são os $R$ últimos tais que $a_R = 0$ e não existe nenhum $L \le k \lt R$ tal que $dir_k \gt R$ ou seja alguém pra esquerda de precisa de um amigo depois de na foto.
Se $a_L = 0$ Então adicionamos $L$ à pilha.
Caso contrário remova todos os elementos da pilha em que $R \lt dir[L]$.
Adicione o tamanho da pilha à resposta.
Complexidade é $\mathcal{O}(N)$ já que cada elemento é iterado uma vez é removido e adicionado a pilha uma vez
Subtarefa 6 (Sem restrições adicionais) (100 pontos):
A ideia central consiste em mapear a condição de insatisfação de cada competidor em uma restrição geométrica no plano delimitada pelos índices de seus amigos mais próximos à esquerda e à direita, criando retângulos de proibição nas coordenadas de início e fim da foto. Para contar quantas fotos válidas existem, utilizamos a técnica de varredura (Line Sweep) no eixo , processando a linha da esquerda para a direita, combinada com uma Segment Tree com Lazy Propagation para gerenciar dinamicamente as colunas de . À medida que a linha de varredura avança, os retângulos de proibição que se iniciam em são ativados somando +1 aos intervalos de na árvore, e os retângulos cujos prazos expiraram são removidos subtraindo -1. Em cada passo de , consultamos a Segment Tree para descobrir quantos valores de possuem zero violações ativas (vmin == 0), acumulando essa quantidade para obter o total exato de fotos válidas em tempo otimizado.
Abordagem completa
Lemos o número de competidores e, para cada competidor com , iteramos sobre sua lista de amigos para encontrar o limite do amigo mais à esquerda (esq) e o limite do amigo mais à direita (dir). Com esses valores, definimos o retângulo de restrição no eixo (intervalo de a ) e no eixo (intervalo de a ). Armazenamos esses eventos em vetores de listas chamados inicio e fim.
Em seguida, chamamos a função varrer, que inicializa a Segment Tree utilizando a função build. A árvore armazena o valor mínimo de violações (vmin) e a quantidade de ocorrências desse mínimo (qtdmin), contando com o mecanismo de propagação retardada (push e lazy) para lidar com atualizações de intervalos. Percorremos o eixo de 1 até : ativamos os retângulos de inicio[l] somando 1 com o update, consultamos quantos elementos em (de até ) possuem zero violações usando a função query, somamos o resultado ao acumulador de fotos e, por fim, removemos os retângulos de fim[l] subtraindo 1 com o update. A complexidade total da solução é $\mathcal{O}(S + N log_2{N})$.