5

Participei de um contest e, em um dos problemas, não obtive o score total da questão, um dos casos teste deu wrong answer, mas não consegui identificar exatamente o meu erro.

O enunciado do problema: exemplo de entrada de dados

N borrifadores estão instalados em faixas gramadas de L metros de comprimento e W metros de largura. Cada borrifador está instalado na linha central da faixa gramática. Para cada borrifador é fornecido sua posição como sendo a distância do lado mais a esquerda da linha central e também seu raio de operação.

Qual o menor número de borrifadores ligados para regar toda a faixa gramada?

Entrada

A entrada consiste de até 35 casos. A primeira linha para cada caso contém os inteiros N, L e W sendo 1≤N≤10000, 1≤L≤107, e 1≤W≤100. As próximas N linhas contém 2 inteiros dando a posição x (0≤x≤L) e o raio de operação r (1≤r≤1000) do borrifador.

Saída

Para cada caso de teste a saída deve ser o menor número de borrifadores necessários para regar toda a faixa gramada. Se for impossível regar toda a faixa a saída deve ser -1.

Exemplo de entrada

8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1

Exemplo de saída

6
2
-1

a ideia basicamente do código

  • Percebe-se que a área útil do círculo para cobrir o comprimento a folhagem de comprimento l é o retângulo inscrito à circunferência com os vértices sobre os lados da folhagem. Cada um desses retângulos inscritos na circunferência será um intervalo variando de x1=x-sqrt(r^2 - (w/2)^2) até x2=x+sqrt(r^2 - (w/2)^2)

  • Inserir cada intervalo no vetor e ordenar em ordem crescente de x1

  • iterar o vetor:

  • i) se o primeiro valor encontrado for maior que 0, retorna -1

  • ii) sempre que o x1 do intervalo seguinte no vetor estiver dentro da área coberta (covered), a área coberta é atualizada ou não, dependendo do alcance, incluímos, portanto, ou não esse intervalo na contagem

  • iii)se a extensão L da folhagem estiver coberta, imprimimos a contagem de intervalos, se não imprimimos -1

O meu código:

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#define fori(x, y) for(int i = x; i < y; ++i)
using namespace std;
int numcirc(vector < pair <double, double> > &v, int l){
    double cover = v[0].second;
    int cont = 1;
    if(v[0].first>0) return -1;
    else {
        fori(1, v.size()){
            if(v[i].first > cover) return -1;
            else{
                int t=i;
                double _cover = cover;
                while(v[t].first<=cover && t<v.size()){ //queremos incluir os intervalos de maior alcance
                    _cover=max(_cover, v[t].second);
                    t++;
                }
                if(_cover>cover){
                    cont++;
                    cover=_cover;
                }
                i=t-1; 
            }
            if(cover>=l) return cont;
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int n, l, w, x, r;
    double x1, x2;
    while(cin >> n >> l >> w){
        vector < pair< double, double > > v;
        fori(0,n){
            cin >> x >> r;
            if((double)r > (w/(double)2)){
                x1 = (double)(x - sqrt(abs(r*r - 0.25*w*w)));
                x2 = (double)(x + sqrt(abs(r*r - 0.25*w*w)));
                v.push_back(make_pair(x1, x2));
            }
            else{
                v.push_back(make_pair(10000001, 0.1)); //se r<=w/2, então não serve para cobrir a folhagem
            }
        }
        sort(v.begin(), v.end());
        cout << numcirc(v, l) << "\n";
    }
    return 0;
}

Não pude ter acesso aos casos testes. O que poderia estar ocasionando o wrong answer?

1 Resposta 1

3

Como você mesmo reparou, esse problema pode ser reduzido de cobertura de área para cobertura de segmentos. A título de nivelar quem chegar nesta questão, vou explicar essa transformação. E a área, por incrível que pareça, não é relevante para a questão por um detalhe simples: o enunciado garantiu que todos os borrifadores estarão exatamente no centro.

Assim, o terreno que nos é fornecido é algo assim:

faixa gramada com linha do centro destacada

De modo geral, você só encontrará estes seguintes 3 tipos de círculos nessa linha central:

os 3 possíveis arranjos de círculos com o centro na linha central do retângulo acima

  1. o primeiro é um círculo que tem um diâmetro de irrigação menor do que W
  2. o círculo do meio é aquele que tem um diâmetro maior do que W
  3. o último círculo é aquele que tem um diâmetro de irrigação idêntico a W

Nesse tipo de caso, os pontos mais distantes da linha central do retângulo são aqueles que são mais difíceis de serem regados. Se esse ponto for regado, eu tenho por garantia que todo o segmento vertical associado a esse ponto fixo também é regado.

Então, assim sendo, nosso problema acaba sendo transformado em cobrir esses pontos extremos. Ou seja, cobrir um segmento inteiro.

Então, como faço para transformar o problema de áreas de círculos dentro do retângulo para segmentos?

Primeiro, vamos entender como cada tipo de círculo vai ser projetado no segmento inferior do retângulo (poderia usar simetricamente o superior, apenas escolhi uma projeção conveniente para fazer o desenho)?

O primeiro tipo de círculo não alcança a borda, logo ele não é útil em regar na borda inferior e sempre é desnecessário.

O segundo tipo vai projetar todo um intervalo, como ilustrado abaixo:

projeção em ciano do círculo sobre o segmento inferior do retângulo, raios em vermelho

O raio do círculo foi ilustrado em vermelho, o segmento projetado do círculo foi indicado em ciano. O cálculo para saber onde começa e onde termina esse segmento já está na pergunta: [ x-sqrt(r^2 - (w/2)^2) , x+sqrt(r^2 - (w/2)^2) ], onde x é a posição do borrifador, r o seu raio e w a largura do campo.

Como se chegou nesses valores? Se você fizer um segmento do centro do círculo até a parte inferior do retângulo de maneira perpendicular, perceberá que ele cairá exatamente no meio do segmento. Assim, como ele é perpendicular, se unir esse segmento, um dos raios e pegar o segmento da ponta do segmento perpendicular obterá um triângulo retângulo. A hipotenusa é conhecida, o raio do círculo, r; um dos catetos também é conhecido, que é o comprimento do segmento perpendicular do centro do círculo até o retângulo, que é metade da largura do campo, portanto w/2; sobrando então o outro cateto para se calcular o comprimento que é sqrt(r^2 - (w/2)^2). Então, se eu pegar o ponto do centro do círculo e andar para a esquerda, obtenho o ponto a esquerda do segmento como sendo x-sqrt(r^2 - (w/2)^2), e se andar para a direita x+sqrt(r^2 - (w/2)^2).

O terceiro tipo de círculo adicionará apenas um ponto no segmento inferior. Como estamos tratando de uma quantidade finita de círculos, a união de muitos pontos nunca chegará a fazer um segmento, logo esse tipo de borrifador também não contribuirá para fazer a irrigação, assim como o primeiro tipo de borrifador.

Dito isso, vamos começar a montar o algoritmo?

Primeiro, vamos precisar ler todos os pontos. Então, descartaremos os círculos que não contribuirão para fazer o intervalo; ou seja, ficaremos apenas com círculos cujos raios sejam estritamente maiores do que metade da largura. Então, transformamos os círculos filtrados em intervalos.

Pronto, agora temos apenas intervalos e desejamos saber qual o menor conjunto desses intervalos que cobrem todo um segmento. Sabe o que podemos usar para modelar interseções de intervalos? Um grafo de intervalos!

Sim, agora estou transformando o problema em em problema de grafos. Como montar esse grafo?

Um grafo de intervalo é uma maneira de representar, em grafo, segmentos e interseções. Cada segmento é um vértice e a existência de interseções entre dois intervalos é representado como uma aresta. Então, com o grafo montado, Precisamos sair de algum intervalo que contenha o 0 (origem) e, apenas navegando pelas arestas, chegar em algum intervalo que contenha o L (destino). Se não for possível, seja porque não tem nenhum intervalo que contenha o 0 para partida, seja porque não tem nenhum ponto de chegada que contenha o L ou porque o grafo é disconexo, então retorno -1.

Aqui na rede tem algumas perguntas interessantes que abordam o problema de grafos de intervalo. As que eu me lembro no momento:

Inclusive, sugiro a leitura nessa ordem que coloquei, que não por acaso coincide com a ordem cronológica de publicação

O primeiro passo é descobrir qual o vértice de partida. Independente de qualquer coisa, o ponto de partida precisa englobar o ponto 0. Portanto, devo considerar como vértice candidato à partida todo intervalo cujo valor mais a esquerda é <=0. Similarmente com o vértice de chegada, valor mais a direita >=L.

Agora, como definir de maneiras mais assertivas esses pontos? Para o ponto de partida, aquele que cobrir até o máximo a direita terá cobertura total sobre qualquer outro ponto candidato de partida, portanto sobra apenas aquele cujo valor mais a direita é o maior. De maneira semelhante, o ponto de chegada é aquele cujo valor mais a esquerda é o menor.

Tem o caso especial de que o ponto de partida engloba a saída; nesse caso, existe ainda a possibilidade de que o meu detector de origem/destino encontre pontos distintos de origem e destino, mas é trivial verificar se apenas o borrifador de origem seria o suficiente para cobrir tudo. Para esse caso, basta retornar 1 e ir para a próxima entrada.

Definidos origem e destino, precisamos das arestas para navegar no grafo. A priori, um grafo de intervalo é um grafo não-direcionado. Porém, podemos fazer algumas otimizações e transformar nosso grafo de intervalo num grafo direcionado acíclico.

Eu vou adicionar uma aresta do intervalo [c1, f1] para o intervalo [c2, f2] se e somente se existir interseção entre esses intervalos e o segundo intervalo terminar depois do primeiro intervalo e o segundo intervalo não englobar totalmente o primeiro. Ou seja, se c2 <= f1 (precisa haver interseção) e f2 > f1 (o segundo intervalo necessariamente termina depois do primeiro intervalo) e c2 > c1 (o primeiro intervalo tem um pedaço anterior ao segundo intervalo). Obviamente que ordenar os intervalos pelo seu valor a esquerda de modo crescente nos permite fazer diversas otimizações na construção das arestas

Montando esse grafo, direcionado mesmo, basta rodar qualquer algoritmo de menor distância entre vértices (considere todas as arestas com peso 1) do ponto de origem até o ponto de destino. Se não for possível alcançar o destino, a saída precisa ser -1. Caso contrário, a saída é a distância encontrada mais um.


Pelo que entendi da sua abordagem, você tentou fazer algo mais guloso. Porém, a estratégia gulosa para funcionar precisa decidir com muita calma se deve inserir ou não o próximo intervalo. Pelo que pude olhar, a estratégia de escolher o próximo elemento que você usou foi realmente adequada (olho para frente todos os intervalos que tem alguma interseção com o que já foi coberto até o momento). Porém a escolha do ponto de partida é sempre fixa, não se tenta otimizá-lo para pegar como partida aquele que contém o 0 e vai até o mais longe possível. Aí, sim, você teria uma solução gulosa e sem backtracking.

Também percebi que você adiciona desnecessariamente na lista pontos que eu filtrei fora, fazendo eles serem um peso na ordenação que seria desnecessário (mas que no final das contas não seria significativo).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .