TOPIC

TLE no Java - Passa nos testes

Gabriel Costa asked 7 months ago

Alguma sugestão em como eu poderia otimizar o meu código? Não consegui pensar em uma maneira sem criar cópias de cada metade do array de cartas;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException{
        InputStreamReader ir = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(ir);

        int N = Integer.parseInt(in.readLine());

        int[] cards = new int[N];
        int[] tempCards = new int[N];
        int[] half1 = new int[N/2];
        int[] half2 = new int[N/2];

        int mid = N/2;
        int counter = 0;

        for(int i = 0; i < N; i++) {
            cards[i] = i+1;
            tempCards[i] = i+1;
        }
        while (counter <= 0 || tempCards[0] != cards[0]) {
            System.arraycopy(tempCards, 0, half1, 0, half1.length);
            System.arraycopy(tempCards, mid, half2, 0, half2.length);

            for (int i = 0; i < N / 2; i++) {
                tempCards[i * 2] =  half2[i];
                tempCards[i * 2 + 1] = half1[i];
            }
            counter++;
        }
        System.out.println(counter);
    }
}

Remember not post solutions. Your post may be reviewed by our moderators.

  • Alex Bôa Morte replied 4 months ago

    Olá Gabriel Costa, acabei de resolver esse. Veja, problemas desse tipo, uma solução de busca completa, testando as possibilidades diretamente, em geral se obtém TLE, além de Java ser mais lento que C/C++. Veja que a entrada é até 10⁵ elementos. Te aconselho a pensar matematicamente.

    Descubra o padrão e com base nos movimentos de um elemento, tente descobrir quantos movimentos são necessários para que o elemento que moveu, volte a sua posição original. Pense o seguinte: Se eu escolher o elemento an, na primeira ordenação, ele sai de ordem, e o elemento an só voltará a posição n, quando tudo estiver ordenado novamente! A ordenação é feita com um padrão, que foi descrito e a estrutura é linear, matematicamente, é uma situação propicia para haver um padrão. Eu estou tentando resolver por relação de recorrência(matemática discreta) agora, mas, a solução que fiz, já passa em 0.000s

    Bons estudos!

  • vprime5 replied 3 months ago

    Alex, pensei a mesma coisa q vc, fiz um código, testei varias vezes no replit e parece certo pra mim, mas ele nao aceita, alguma ideia do pq?

    #include <stdio.h>
    int main() {
          long int n, V[200000],i,aux,num,mmc,mdc;
          scanf("%li",&n);
          mmc = 1;
          for (i=1;i<=n;i++)
                  V[i] = 0;
          for (i=1;i<=n;i++)
          if(V[i]==0){
                  aux = (2*i)%(n+1);
                  num = 1;
                  V[i] = 1;
                  while(aux != i){
                          num = num + 1;
                          V[aux] = 1;
                           aux = (2*aux)%(n+1);
                  }
                  mdc = mmc;
                  mmc = mmc*num;
                  while(num%mdc != 0){
                          aux = num;
                          num = mdc;
                          mdc = aux%mdc;
                  }
                  mmc = mmc/mdc;
          }
          printf("%li\n", mmc);
          return 0;
    }