Autor da análise: cesargm
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2944
Resumo
Estranhos são pontos na forma $(x,y,z)$ ($1 \le x,y,z \le m$).
Dados n estranhos 'vilões', encontrar o número de estranhos 'heróis', ou seja, estranhos $(x^*,y^*,z^*)$ tais que, para cada vilão $(x,y,z)$, vale que:
$x^* > x$ ou $y^* > y$ ou $z^* > z$
Solução
Podemos modelar o problema de forma geométrica. Cada estranho $(x,y,z)$ é representado pelo cubo com pontas em $(x-1,y-1,z-1)$ e $(x,y,z)$. Para cada vilão $(x,y,z)$, os estranhos que não podem vencê-lo (e portanto, não podem ser heróis) são representados pela caixa com pontas em $(0,0,0)$ e $(x,y,z)$. O número de heróis representados por uma figura desse tipo é obviamente o volume da figura.
Então a solução do problema é obtida calculando o volume da união das caixas determinadas por cada vilão (obtendo o número de estranhos que não podem ser heróis) e retirando-o do total ($m^3$).
Para isso, começamos ordenando os pontos em ordem decrescente de uma coordenada (z, por exemplo) e criando um set<pair> para guardar os "pontos de interesse", que são os cantos da figura quando vista de cima (Note que os elementos desse set irão sempre formar uma "escada"). O set começa com os pontos (0,m+1) e (m+1,0) para não precisarmos nos preocupar com os limites.
Processe cada ponto em ordem decrescente de z: Se o ponto (x,y) já está contido na escada (existe (x',y') tal que $x' \ge x$ $y' \ge y$) não é necessário fazer nada. Caso contrário, insira o ponto (x,y) no set, e vá eliminando os pontos com as duas coordenadas menores que o ponto atual e calculando a área adicionada à figura. Se $A$ é a área adicionada (ou seja, a diferença entre a área atual e a área antes de inserir o ponto), some $zA$ ao volume do objeto ($V$).
No final calcule $m^3 - V$. essa é a resposta do problema
Discuta o problema
Quem conseguiu resolver esse, alguma dica?
O máximo que eu cheguei foi à uma solução O(n^2), que toma TLE. Acho que da pra diminuir a complexidade com alguma estrutura de dados esperta, mas não consegui achar.
Eu resolvi com um algoritmo $n \lg n$. A minha solução foi interpretar o problema como um problema de geometria, cada pessoa corresponde a um ponto no espaço 3d, onde cada coordenada é um habilidade. As pessoas que não podem vencer um vilão na coordenada (x,y,z) estão dentro da caixa formada pelos vértices em (0,0,0) e (x, y, z). Então o problema se resumi a calcular o volume da união dessas caixas. Para isso eu reduzi o problema para duas dimensões, olho para os cortes paralelos ao plano yz, calculo a área desses cortes e com essas áreas eu consigo calcular a volume total. Eu começo com o corte vazio e vou adicionando vilões do maior x para o menor. Usando uma árvore balanceada (o map da stl serve) eu consigo atualizar o corte em $\lg n$ e eu só preciso dos cortes que passam por algum vilão, logo n cortes no total. Note que o corte sempre vai ter a forma de uma escada irregular. Fui inspirado pelo algoritmo do problema de achar o maior retangulo num skyline.
Eu cheguei a pensar em alguma coisa assim.
Mas eu não consegui ver como usar o map (ou uma árvore balanceada) para adicionar pontos ao corte e calcular a área dele em $\textrm{lg} \, n$.
Pense em como vc resolveria o problema se houvesse apenas duas habilidades. Tem uma solução que é linear. Talvez isso ajude.
Corrigindo o que eu falei, no caso de 2 dimensões, não sei se tem algoritmo linear. Me enganei porque precisa ordenar os elementos primeiro por alguma dimensão, mas o resto do algoritmo, que é a parte mais interessante, é linear.
Eu consigo pensar nessa solução, basta ordenar por alguma das dimensôes, daí se vc varre os pontos em ordem decescente nessa dimensão e vai guardando o máximo que vc atingiu na outra dimensão, enquanto "soma" as áreas que vc conseguiu.
Isso é equivalente à calcular a área de uma função escada decrescente.
Generalizando essa idéia pra 3d que eu cheguei no meu algoritmo $O(n^2)$ que eu comentei no primeiro post.
Bom, vou pensar um pouco mais, e se ainda não conseguir eu volto a encher o saco :) valeu!
O problema se resume mesmo a só calcular o volume e depois m³ - volume ou tem algum otro detalhe (eu uso long long para calcular a area e o volume)?
voce usou Map mesmo? Como? Eu implementei de um jeito usando Set, mas to tomando WA…
Sim, o problema se resume a calcular o volume. Eu usei set e long long e passou!
Minha solução:
Tenho um set<Point> S, que serve pra guardar os "quinas" das escada formada pelos pontos adicionados até então, no começo o set possui apenas os pontos (0,m+1) e (m+1,0) que servem apenas para delimitar os extremos para eu não me preoculpar em acessar regiões antes do primeiro e último iterator .
Encaro os pontos da entrada como pontos 3d (x,y,z).
Ordeno-os pelo valor de z.
Começando do último ponto $(x_i,y_i_,,z_i)$ (ponto com maior z), acrescento o volume dele toamdno o cuidado de retirar as interseções. Faço isso dando um upper_bound(Point($x_i,y_i$)) (Point é orientado do menor para maior x), e retrocedo enquando $y_i$ é menor do que o y atual a tualizando meu volume acumulado …
Espero que dê pra entender, estou meio sem tempo, mais ainda essa semana vou ver se posto a solução pro problema lá em cima, explicando melhor com resolver.
O meu algoritmo esta quase identico ao seu, uso tambem set com (0,m+1) e (m+1,0) pra nao me preocupar com os limites, pego o upper bound do ponto que quero inserir e se o y for maior ou igual, termino. Depois procuro até achar algum y maior que o dele, e nesse processo vou retirando retangulos e no final somo o retangulo correspondente ao ponto que estou inserindo (retiro os pontos do set e insiro o novo apenas depois de achar os limites e removo todos de uma vez).
Uma diferença é que eu faço isso pela 1ª coordenada, mas nao deveria dar resposta errada.
Na hora de calcular o volume eu começo com $$x_f=m$$, a area$$A$$ nula e volume $$V$$ nulo, ai quando eu pego o ponto com x maior e somo no volume $$A\times (x_f - x_i)$$ , atualizo a area e faço $$x_f\gets x_i$$, até eu pegar o ultimo x, depois de processá-lo eu somo ao volume $$A\times x_f$$ entao obtenho a resposta fazendo $$m^3-V$$
Esqueci de um detalhe importantíssimo!
Eu levei WA também, submetendo com G++!!!!!! Quando subeti o mesmo código com C++ parssou!!!!!!!! =O
Fiz esse teste, porque o Raphael Ribas fez o problema primeiro, e me alertou que teve problemas com isso, e imagina que a versão do G++ no PKU é antiga e pode conter erros na STL.
Valeu pelo detalhe, eu nunca pensaria que mudar o compilador tornaria WA em AC (acabei de passar o mesmo codigo em C++ e deu AC).
Valeu!
Vocês tem exemplos que podem falhar (pontos na mesma linha, coluna, sei lá)?
Estou usando a idéia acima, mas continuo tomando wa (os exemplos que eu consegui pensar parecem funcionar…).
(estou mandando com o compilador C++)
Eu não tenho nenhum caso de teste não… Mas tem uma coisa na sua explicação que não me parece certa (ve se voce ta fazendo a mesma coisa na sua solução):
Não seria somar $(z_i - z_{i+1}) A$? (Onde $z_1, ..., z_n$ são as coordenadas dos viloes em ordem decrescente)
Me expressei mal… A é a área adicionada à figura com a inclusão do ponto, não a área da figura. Vou tentar escrever de outro jeito.
Perdi um tempo debuggando o meu código, vou colocar o caso de testes que eu usei pra achar o problema aqui, talvez ajude quem for debuggar também.
Entrada
2 3
1 1 1
1 1 2
2 3
1 1 1
1 2 1
3 5
1 1 1
1 2 1
1 2 2
4 6
4 1 6
2 2 5
1 4 4
3 3 3
0 0
Saida
25
25
121
165