TOPIC

PROBLEM 1740 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Gabriel Duarte replied 4 years ago

    Pro pessoal que está discutindo uma forma de resolver, vcs podem usar uma Treap, com ela vc consegue resolver cada tipo de consulta em O(log n).

    MOD
  • Matheus Pimenta replied 5 years ago

    Cara, tem a Segment Tree... Ela é usada no problema Range Minimum Query, mas dá para adaptar para qualquer tipo de query. O problema é que nesse problema dá para remover e inserir elementos no vetor. A Segment Tree do jeito que eu conheço não suporta isso. Só suporta update nos elementos... Eu tentei reconstruir a ST nas queries de insert e remove, mas continua dando TLE. Talvez tenha algum jeito de adaptar a ST pra suportar insert e remove em O(log n)... Acho que é o único jeito de não estourar o tempo.

  • Jordão Memória replied 5 years ago

    Tentei com lista ligada e vetor. Dá tempo limite excedido. Depois fiz com lista ligada mais com ponteiros espalhado por ela, de forma que quando vou chegar na posição que quero, percorro esses ponteiros, passado blocos de 80 valores. Isso deixa o algoritmo bem mais rápido, mais ainda tá dando tempo limite excedido. Eu sei que só um cara fez até agora, mas o que você acham que pode ser?

  • Marcos Treviso replied 6 years ago

    Runtime error geralmente é acesso a uma posição inválida de memória.

    Mas não adianta implementar usando lista ou vetor, dados o número de elementos na sequência inicial e o número de operações respectivamente:

    N = 10^4 Q = 10^5

    • Para um vetor, no pior dos casos é a remoção ou inserção na posição 1, isso faria com que todos os elementos à direita fossem deslocados, gastando assim no pior dos casos O(n) iterações para isso. Sendo que temos Q operações, e no pior dos casos temos Q iterações que são desse tipo (inserção ou remoção), portanto teriamos um tempo de:

    O(q * n) = 10^9 = 100 segundos aproximadamente. Sendo assim, se pelo menos metade das operações forem ruins, já estouramos o tempo limite que é 4 segundos.

    • Para uma lista, a inserção e a remoção não precisa de deslocamentos, entretanto precisamos iterar até o elemento de posição x para remover ou inserir ali. No pior dos casos (mesmo se usar deque) vamos fazer O(n) passos para encontrar o elemento certo, então vai acontecer a mesma coisa que o vetor.

    Com uma árvore entretanto, podemos garantir um tempo de O(lgn) para inserir, buscar e remover um elemento. Sendo assim, no pior dos casos teriamos O(q lgn) iterações, que é cerca de 0.1s. Porém, temos que percorrer os elementos de uma posição x até uma posição y*. Isso seria trivial num vetor, já numa árvore a coisa fica um pouco mais complexa, e há vários modos de fazer isso. Eu pensei em 3 modos:

    [list:3dbplesv]- Realizar um percorrimento in-order e verificar quando chegamos no nosso limite [x, y-1]. Esse método seria custoso demais, visto que gastaríamos O(n) no pior dos casos, o que resultaria novamente no nosso O(q*n).

    • Buscar o i-ésimo elemento na árvore com custo de O(lgn), de modo que x <= i < y, porém isso resultaria numa complexidade de O(q (y-x)lgn) e visto como y pode ser igual a n e x = 1, esse método é ainda mais custoso que o acima.
    • Guardar um pontiero para o nó sucessor, desse modo gastariamos O(lgn) a mais para inserir e O(1) para deletar caso tenhamos um predecessor também, e com isso gastariamos O(q*(lg(n) + (y-x)). Que é na verdade quasi igual ao primeiro modo.[/list:u:3dbplesv]

    Acredito que tenha algum jeito de melhorar isso, provavelmente pelo fato de saber que se de x a x' está ordenado crescentemente e de x' a y também está ordenado crescentemente, então de x a y também está. Porém não consegui pensar numa estratégia para isso, talvez usando algum outro tipo de árvore balanceada como a interval-tree.

    Testei os 3 modos ali usando uma red-black tree, entretanto todos os casos deram TLE (não custa nada tentar :P). Se alguem souber como resolver, ficaria grato pela ajuda xD.

    Valeu!

  • Roger Benet replied 6 years ago

    Alguém poderia me ajudar, meu código está lançando Runtime Possible runtime error ! Muito Obrigado !

    import java.io.*;
    import java.util.ArrayList;
    public class Main {
    
        public static void main(String[] args) throws IOException{
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
            ArrayList <Integer> list = new ArrayList();
            int n,q,i,opc,x,y;
            String[] aux;
            String w;
            boolean maior,menor;
            while( (w = in.readLine()) != null){
                n = Integer.parseInt(w);
                aux = in.readLine().split(" ");
                for(i = 0; i < n; i++){
                       list.add(Integer.parseInt(aux[i]));
                }
                q = Integer.parseInt(in.readLine());
                while(q > 0){
                         aux = in.readLine().split(" ");
                         opc = Integer.parseInt(aux[0]);
                         x = Integer.parseInt(aux[1]);
                         if(opc == 0){
                        y = Integer.parseInt(aux[2]);
                        list.set(x - 1, list.get(y - 1));
                         }
                        if(opc == 1){
                            y = Integer.parseInt(aux[2]);
                            list.set(x - 1, y);
                        }
                         if(opc == 2){
                            y = Integer.parseInt(aux[2]);
                            list.add(x - 1, list.get(y-1));
                         }
                         if(opc == 3){
                            list.remove(x - 1);
                         }
                         if(opc == 4){
                            y = Integer.parseInt(aux[2]);
                            maior = menor = false;
                        for(i = x - 1; i < y - 1; i++){
                                if(list.get(i) < list.get(i+1)){
                                    menor = true;
                                }
                                if(list.get(i) > list.get(i+1)){
                                    maior = true;
                                }
                        }   
                        if(menor == true && maior == false){
                            out.write("NON DECREASING\n");
                        }
                        else if(maior == true && menor == false){
                            out.write("NON INCREASING\n");
                        }
                        else if(maior == true && menor == true){
                            out.write("NONE\n");
                        }
                        else out.write("ALL EQUAL\n");
    
                        }
                        q--;
            }
            list.clear();
            }
            out.flush();
        }
    }