title: O(n^2) isn't fast enough in solving this. any faster approaches?
body: <p>I've been trying to solve this problem on ACM Timus</p>
  
  <p><a href="http://acm.timus.ru/problem.aspx?space=1&amp;num=1932" rel="nofollow">http://acm.timus.ru/problem.aspx?space=1&amp;num=1932</a></p>
  
  <p>My first approach is O(n^2) which surely isn't fast enough to pass all tests. The below O(n^2) code gives TL on test 10.</p>
  
  <pre><code>import java.util.*;
  import java.io.*;
  
  public class testtest
  {
      public static void main(String[] args) throws IOException
      {
          BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
          int n = Integer.parseInt(rr.readLine());
          String[] p = new String[n];
          for (int i = 0; i &lt; n; i ++)
          {
              p[i] = rr.readLine();
          }
          int[] diff = new int[]{0, 0, 0, 0};
          for (int i = 0; i &lt; n - 1; i ++)
          {
              for (int j = i + 1; j &lt; n; j ++)
              {
                  int ans  = (p[i].charAt(0) == p[j].charAt(0) ? 0 : 1) +
                             (p[i].charAt(1) == p[j].charAt(1) ? 0 : 1) +
                             (p[i].charAt(2) == p[j].charAt(2) ? 0 : 1) +
                             (p[i].charAt(3) == p[j].charAt(3) ? 0 : 1);
                  diff[ans - 1] ++;
              }
          }
          System.out.print(diff[0] + " " + diff[1] + " " + diff[2] + " " + diff[3]);
      }
  }
  </code></pre>
  
  <p>any idea to make this approach faster? I've noticed that only a limited set of characters are allowed in input ('0' .. '9', 'a' .. 'f') so we can create arrays (memory limitation is enough) to do fast checks if characters have been entered before.</p>
  
  <p>Thanks... I don't need actual implementation, just quick idea/thoughts would be great.
  <strong>EDIT:</strong> Thanks for great ideas. I've tried improvements on O(n^2) using bit-logics, but still time limit exceeded. The pascal code is below.</p>
  
  <pre><code>program Project2;
  
  {$APPTYPE CONSOLE}
  
  var
    i, j, n, k, bits: integer;
    arr: array[1..65536] of integer;
    diff: array[1..4] of integer;
    a, b, c, d: char;
  
  function g(c: char): integer; inline;
  begin
    if ((c &gt;= '0') and (c &lt;= '9')) then
    begin
      Result := Ord(c) - 48;
    end
    else
    begin
      Result := Ord(c) - 87;
    end;
  end;
  
  begin
    Readln(n);
    for i := 1 to n do
    begin
      Read(a); Read(b); Read(c); Readln(d);
      arr[i] := g(a) * 16 * 16 * 16 + g(b) * 16 * 16 + g(c) * 16 + g(d);
      for j := 1 to i - 1 do
      begin
        bits := arr[i] xor arr[j];
        k := ((bits or (bits shr 1) or (bits shr 2) or (bits shr 3)) and $1111) mod 15;
        Inc(diff[k]);
      end;
    end;
    Write(diff[1], ' ', diff[2], ' ', diff[3], ' ', diff[4]);
  {$IFNDEF ONLINE_JUDGE}
    Readln;
  {$ENDIF}
  end.
  </code></pre>
  
  <p>So I guess, I've to try other better suggestions..</p>
  
  <p><strong>EDIT:</strong>  I have tried Daniel's algorithm and it is very promising, maybe there is a mistake in the code below, It keeps getting Wrong Answer on Test 10... could anybody take a look? Many thanks...</p>
  
  <pre><code>import java.util.*;
  import java.io.*;
  
  public class testtest
  {
      private static int g(char ch)
      {
          if ((ch &gt;= '0') &amp;&amp; (ch &lt;= '9'))
          {
              return (int)ch - 48;
          }
          return (int)ch - 87;
      }
  
      public static void main(String[] args) throws IOException
      {
          BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
          int n = Integer.parseInt(rr.readLine());
          int[] p = new int[n];
          int[] all = new int[65536];
          int[][] miss = new int[4][4096];
          int[] g12 = new int[256];
          int[] g13 = new int[256];
          int[] g14 = new int[256];
          int[] g23 = new int[256];
          int[] g24 = new int[256];
          int[] g34 = new int[256];
          int[][] gg = new int[4][16];
          int same3, same2, same1, same0, same4;
          for (int i = 0; i &lt; n; i ++)
          {
              String s = rr.readLine();
              int x = g(s.charAt(0)) * 4096 + g(s.charAt(1)) * 256 + g(s.charAt(2)) * 16 + g(s.charAt(3));
              p[i] = x;
              all[x] ++;
              miss[0][x &gt;&gt; 4] ++;
              miss[1][(x &amp; 0x000F) | ((x &amp; 0xFF00) &gt;&gt; 4)] ++;
              miss[2][(x &amp; 0x00FF) | ((x &amp; 0xF000) &gt;&gt; 4)] ++;
              miss[3][x &amp; 0x0FFF] ++;
              g12[x &gt;&gt; 8] ++;
              g13[((x &amp; 0x00F0) &gt;&gt; 4) | ((x &amp; 0xF000) &gt;&gt; 8)] ++;
              g14[(x &amp; 0x000F) | ((x &amp; 0xF000) &gt;&gt; 8)] ++;
              g23[(x &amp; 0x0FF0) &gt;&gt; 4] ++;
              g24[(x &amp; 0x000F) | ((x &amp; 0x0F00) &gt;&gt; 4)] ++;
              g34[x &amp; 0x00FF] ++;
              gg[0][x &gt;&gt; 12] ++;
              gg[1][(x &amp; 0xF00) &gt;&gt; 8] ++;
              gg[2][(x &amp; 0xF0) &gt;&gt; 4] ++;
              gg[3][x &amp; 0xF] ++;
          }
  
          same4 = 0;
          for (int i = 0; i &lt; 65536; i ++)
          {
              same4 += (all[i] - 1) * (all[i]) / 2;
          }
  
          same3 = 0;
          for (int i = 0; i &lt; 4096; i ++)
          {
              same3 += (miss[0][i] - 1) * (miss[0][i]) / 2;
              same3 += (miss[1][i] - 1) * (miss[1][i]) / 2;
              same3 += (miss[2][i] - 1) * (miss[2][i]) / 2;
              same3 += (miss[3][i] - 1) * (miss[3][i]) / 2;
          }
  
          same2 = 0;
          for (int i = 0; i &lt; 256; i ++)
          {
              same2 += (g12[i] - 1) * g12[i] / 2;
              same2 += (g13[i] - 1) * g13[i] / 2;
              same2 += (g14[i] - 1) * g14[i] / 2;
              same2 += (g23[i] - 1) * g23[i] / 2;
              same2 += (g24[i] - 1) * g24[i] / 2;
              same2 += (g34[i] - 1) * g34[i] / 2;
          }
  
          same1 = 0;
          for (int i = 0; i &lt; 16; i ++)
          {
              same1 += (gg[0][i] - 1) * gg[0][i] / 2;
              same1 += (gg[1][i] - 1) * gg[1][i] / 2;
              same1 += (gg[2][i] - 1) * gg[2][i] / 2;
              same1 += (gg[3][i] - 1) * gg[3][i] / 2;
          }
  
          same3 -= 4 * same4;
          same2 -= 6 * same4 + 3 * same3;
          same1 -= 4 * same4 + 3 * same3 + 2 * same2;
          same0 = (int)((long)(n * (n - 1) / 2) - same4 - same3 - same2 - same1);
          System.out.print(same3 + " " + same2 + " " + same1 + " " + same0);
      }
  }
  </code></pre>
  
  <p><strong>EDIT</strong>
  Finally got AC... thanks Daniel for such great algorithm!</p>