UVa 256: Quirksome Squares

João Pedro Neto

Neste segundo treino vamos resolver e submeter o problema UVa 256.

Vamos resolver o problema de duas formas diferentes: por força bruta e depois usando um pouco de matemática para obter uma solução mais inteligente.

Analisando o enunciado percebemos que existem apenas quatro instâncias do problema, para 2, 4, 6, e 8 dígitos. Podíamos simplesmente calcular estas quatro soluções, armazená-las num array de Strings, e imprimir consoante o que fosse pedido. Ou podemos ser um pouco mais preguiçosos (a grande virtude do programador, se bem usada!) e só calcular se for pedido, mas sem nos esquecermos de guardar a solução porque, como se pode ver no exemplo do enunciado, é possível pedir uma instância mais que uma vez.

Como são pedidos poucos dígitos, vamos primeiro fazer à bruta e calcular todas as hipóteses!

Este excerto de código faz esse trabalho:


 StringBuffer sb = new StringBuffer();      // keep solutions in a StringBuffer
 String format = "%0" + digits + "d";       // useful for leading zeros
 int  maxValue = (int)Math.pow(10, digits);
 int  split    = (int)Math.pow(10, digits/2);

 for(int i=0; i < maxValue; i++) { 
   // given that 'i' is evenly split in parts 'ab', 
   // we wish to include only when i == (a+b)^2
   // eg: 3025 == (30+25)^2,  with i=3025, a=30, b=25
   int a = i/split,
       b = i%split;
     
   if (i == (a+b)*(a+b)) 
     // the condition is met, add to current solutions
     sb.append(String.format(format, i)+"\n");
 }

Vejam se entendem este ciclo, ele é a essência desta solução do problema!

Reparem que se usou a função String.format para adicionar os zeros à esquerda (leading zeros em inglês). Dá jeito saber o que as classes standard do Java podem fazer: isso poupa-nos muito trabalhinho!

Agora só nos resta adicionar o resto do código para ler o input e escrever o output.


public class UVa_256_Quirksome_Squares {
  
  public static void main(String[] args) {

    /// REMOVE BEFORE SUBMITION ///////////////////////////////////
    if (1>0)    // if true: read from files; else: read from System.in
      try {   // redirect System.in and System.out to in/out text files
        System.setIn (new FileInputStream("data/uva0256.in.txt" ));
        System.setOut(new     PrintStream("data/uva0256.out.txt") );
      } catch (Exception e) {}    
    ///////////////////////////////////////////////////////////////
    
    Scanner sc = new Scanner(System.in);

    // there are only four solutions, 
    // let's compute and save them in case the input repeats itself
    String[] sols = new String[4];    
    
    while (sc.hasNextInt()) {
      
      // solve one problem instance
      int digits = sc.nextInt();      

      if (sols[digits/2-1]==null) {    // if not computed yet...
        
        StringBuffer sb = new StringBuffer();      // for increased performance 
        String format = "%0" + digits + "d";       // useful for leading zeros
        int  maxValue = (int)Math.pow(10, digits);
        int     split = (int)Math.pow(10, digits/2);

        // This cycle is where 99.9% of the computation occurs, 
        // so it must be as light as possible
        for(int i=0; i < maxValue; i++) {
          // given that 'i' is evenly split in parts 'ab', 
          // we wish to include only when i == (a+b)^2
          // eg: 3025 == (30+25)^2,  with i=3025, a=30, b=25
          
          int a = i/split,
            b = i%split;
          
          if (i == (a+b)*(a+b))     
            // the condition is met, add to current solutions
            sb.append(String.format(format, i)+"\n");
        }
        
        sols[digits/2-1] = sb.toString();  // save solutions for future use
      }
        
      System.out.print(sols[digits/2-1]);      
    }
    sc.close();
  }
}

Reparem também que as soluções que vão sendo calculadas são guardadas. Quando uma nova instância é pedida, verificamos se ela já existe ou não para evitar repetir computações. Este tipo de tática é muitíssimo útil e nós vamos aprender a usá-la para resolver problemas muito mais complicados (e úteis)!

Com este código, fomos ao UVa e submetemos (experimentem!). A solução foi aceite e demorou 0.45 segundos. Nada mau para uma força bruta!

Mas não deixa de ser uma solução pouco elegante. Podemos fazer melhor? Podemos!

Para isso vamos analisar o problema em termos de Álgebra (como é? A Álgebra serve para alguma coisa?)

A solução do problema passa por encontrar números $i$ que são compostos por sequência de dígitos $ab$ tal que:

$$i = (a+b)^2$$

Por exemplo, no enunciado $i=3025$ composto por $a=30$ e $b=25$ é solução porque $3025=(30+25)^2$

Ora se i tem d dígitos, a e b são compostos por $d/2$ dígitos, e o valor máximo de a e b é majorado por $b_{max}=10^{d/2}$.

Assim temos:

$$i = b_{max} \times a + b$$

Os valores de a e b têm de satisfazer:

$$(a+b)^2 = b_{max} \times a + b$$

desenvolvendo (e agora vem a Álgebra: respirar fundo...):

$$a^2 + 2ab + b^2 = b_{max} \times a + b$$ $$a^2 + (2b-b_{max}) \times a + b^2- b = 0$$

(já acabou?)

Obtemos um polinómio de grau 2 que queremos resolver em a. Como fazer? Para uma instância do problema, geramos os b possíveis (o que é muito menos do que todos os i possíveis) e resolvemos a equação (usando a famosa fórmula resolvente). As soluções inteiras serão aquelas que vamos guardar e imprimir!

Sugiro que tentem implementar esta solução por vocês antes de analisar a solução seguinte:

. . .

Nesta solução incluiu-se uma função auxiliar solveSecondDegreeEquation para calcular as raízes via a fórmula resolvente.


public class UVa_256_Quirksome_SquaresMath {
  
  /**
   * This method solves ax^2 + bx + c = 0
   * @return an array with the solutions of the equation
   * (max 2 solutions; null if there are no solutions)
   */
  public static double[] solveSecondDegreeEquation(double a, double b, double c) {
    // Result values for x 
    double[] solutions = null;

    double q = b * b - 4 * a * c;
    if (q > 0 && a != 0) {
      // case there are two roots
      solutions = new double[2];
      solutions[0] = (-b + Math.sqrt(q))/ (2 * a); 
      solutions[1] = (-b - Math.sqrt(q))/ (2 * a); 
    }
    else if (q == 0) {
      // case there is one root
      solutions = new double[1];
      solutions[0] = (-b) / (2 * a); 
    }
    else {
      // case there are no roots
    }
    return solutions;
  }

  /////////////////////////////////////////////////////////////
  
  public static void main(String[] args) {

    /// REMOVE BEFORE SUBMITION ///////////////////////////////////
    if (1>0)    // if true: read from files; else: read from System.in
      try {   // redirect System.in and System.out to in/out text files
        System.setIn (new FileInputStream("data/uva0256.in.txt" ));
        System.setOut(new     PrintStream("data/uva0256.out.txt") );
      } catch (Exception e) {}    
    ///////////////////////////////////////////////////////////////
     
    Scanner sc = new Scanner(System.in);

    // there are only four solutions, 
    // let's compute and save them in case the input repeats itself
    String[] sols = new String[4];    
    
    while (sc.hasNextInt()) {
      
      // solve one problem instance
      int digits = sc.nextInt();      

      if (sols[digits/2-1]==null) {    // if not computed yet...
        
        List foundSols = new LinkedList();;
        int bMax = (int)Math.pow(10, digits/2);

        StringBuffer sb = new StringBuffer();      // for increased performance 
        String format = "%0" + digits + ".0f";     // useful for leading zeros

        for(int b=0; b<bMax; b++) {

          // get quadratic solutions
          double[] aSols = solveSecondDegreeEquation(1,2*b-bMax,b*b-b);
          
          if (aSols!=null)        // if there are solutions...
            for(double a : aSols)  
              // only want integer solutions and with (digits/2) digits 
              if ((int)a == a && a < bMax)
                // compose solution & add it to list
                foundSols.add(String.format(format, a*bMax + b)); 
        }
        
        Collections.sort(foundSols);        // sort solutions for presentation purposes
        for(String sol : foundSols)        // add them into one string
          sb.append(sol+"\n");
        
        sols[digits/2-1] = sb.toString();  // save solution for future use
      }
        
      System.out.print(sols[digits/2-1]);      
    }
    sc.close();
  }
}

Quando se submete esta nova versão observamos de imediato o ganho de desempenho. Em vez dos 0.45 segundos, demorou-se 0.07 segundos! A segunda versão foi sete vezes mais rápida. Esta diferença seria ainda maior se o problema admitisse números com 10 ou mais dígitos (nesse caso, a primeira solução de força bruta seria rejeitada com um TL, i.e., Time Limit Exceeded, porque iria demorar muito mais que os três segundos admissíveis ao cálculo de uma solução.

O uso de conceitos matemáticos é um trunfo na resolução de muitos problemas. É um tema comum nos concursos de programação e a maioria nem precisa de matemática muito avançada. Neste exemplo precisámos apenas de material dado no 2º e 3º ciclo de escolaridade.

O que precisamos é de um espírito crítico quando analisamos um novo problema. E isso vem com a prática. Há medida que forem treinando vão aprender a usar estas técnicas, muitas das quais já conhecem mas que se foram esquecendo por falta de uso. Eis uma boa oportunidade para reverter essa situação. Podem consultar o capítulo 5 do livro do Halim que apresenta bastantes exemplos deste assunto. Com tempo iremos abordar alguns deles nos treinos.

Happy Coding!

Last modified: Thursday, 13 October 2016, 2:20 PM