NEERC/kequiv/kequiv_mb.java

   1 import java.io.FileReader;
   2 import java.io.IOException;
   3 import java.io.PrintWriter;
   4 import java.util.Scanner;
   5
   6 public class kequiv_mb implements Runnable {
   7     private Scanner in;
   8     private PrintWriter out;
   9
  10     public static final int MAX_LENGTH = 20;
  11     public static final int NUM_DIGITS = 10;
  12     private DigitTrie trie;
  13
  14     static class TrieNode {
  15         public int numLinks;
  16         public TrieNode parent;
  17         public TrieNode[] links;
  18         public boolean isLeaf;
  19     }
  20
  21     static interface TrieNodeProcessor {
  22         boolean process(short[] digits, int length);
  23     }
  24
  25     static class DigitTrie {
  26         private final TrieNode root = new TrieNode();
  27
  28         public void insert(short[] digits, int length) {
  29             //System.out.print("insert: ");
  30             //dumpDigits(digits, length);
  31             //System.out.println();
  32
  33             TrieNode node = root;
  34             for (int i = 0; i < length; i++) {
  35                 if (node.isLeaf) {
  36                     return;
  37                 }
  38                 int digit = digits[i];
  39                 if (node.links == null) {
  40                     node.links = new TrieNode[NUM_DIGITS];
  41                 }
  42                 if (node.links[digit] == null) {
  43                     final TrieNode newNode = new TrieNode();
  44                     newNode.parent = node;
  45                     node.links[digit] = newNode;
  46                     node.numLinks++;
  47                 }
  48                 node = node.links[digit];
  49             }
  50             makeLeaf(node);
  51             while (node != null) {
  52                 optimize(node);
  53                 node = node.parent;
  54             }
  55         }
  56
  57         public boolean contains(short[] digits, int length) {
  58             TrieNode node = root;
  59             for (int i = 0; i < length; i++) {
  60                 if (node.isLeaf) {
  61                     return true;
  62                 }
  63                 int digit = digits[i];
  64                 node = node.links[digit];
  65                 if (node == null) {
  66                     return false;
  67                 }
  68             }
  69             return node.isLeaf;
  70         }
  71
  72         public void enumerate(TrieNodeProcessor processor) {
  73             short[] digits = new short[MAX_LENGTH];
  74             enumerate(processor, root, digits, 0);
  75         }
  76
  77         private boolean enumerate(TrieNodeProcessor processor, TrieNode node, short[] digits, int length) {
  78             if (node.isLeaf) {
  79                 return processor.process(digits, length);
  80             }
  81
  82             if (node.links == null) {
  83                 return true;
  84             }
  85
  86             for (int digit = 0; digit < 10; digit++) {
  87                 if (node.links[digit] != null) {
  88                     digits[length] = (short) digit;
  89                     if (!enumerate(processor, node.links[digit], digits, length + 1)) {
  90                         return false;
  91                     }
  92                 }
  93             }
  94             return true;
  95         }
  96
  97         private void optimize(TrieNode node) {
  98             if (node.numLinks != NUM_DIGITS) {
  99                 return;
 100             }
 101             int numLeafs = 0;
 102             for (int i = 0; i < NUM_DIGITS; i++) {
 103                 if (node.links[i].isLeaf) {
 104                     numLeafs++;
 105                 }
 106             }
 107             if (numLeafs == NUM_DIGITS) {
 108                 makeLeaf(node);
 109             }
 110         }
 111
 112         private void makeLeaf(TrieNode node) {
 113             node.isLeaf = true;
 114             node.links = null;
 115         }
 116     }
 117
 118     public static void main(String[] args) {
 119         new Thread(new kequiv_mb()).start();
 120     }
 121
 122     public void run() {
 123         try {
 124             in = new Scanner(new FileReader("kequiv.in"));
 125             out = new PrintWriter("kequiv.out");
 126
 127             solve();
 128
 129             in.close();
 130             out.close();
 131         } catch (IOException e) {
 132             e.printStackTrace();
 133         }
 134     }
 135
 136     private static void dumpDigits(short[] digits, int length) {
 137         for (int i = 0; i < length; i++) {
 138             System.out.print(digits[i]);
 139         }
 140         for (int i = 0; i < MAX_LENGTH - length; i++) {
 141             System.out.print("?");
 142         }
 143     }
 144
 145     private short[] toDigits(long value) {
 146         short[] result = new short[MAX_LENGTH];
 147         for (int i = 0; i < MAX_LENGTH; i++) {
 148             result[i] = (short) (value % 10);
 149             value /= 10;
 150         }
 151         for (int i = 0; i < MAX_LENGTH / 2; i++) {
 152             short tmp = result[i];
 153             result[i] = result[MAX_LENGTH - i - 1];
 154             result[MAX_LENGTH - i - 1] = tmp;
 155         }
 156         return result;
 157     }
 158
 159     private void insertRange(DigitTrie trie, long lo, long hi) {
 160         final short[] loDigits = toDigits(lo);
 161         final short[] hiDigits = toDigits(hi);
 162         int i = 0;
 163         while (i < MAX_LENGTH && loDigits[i] == hiDigits[i]) {
 164             i++;
 165         }
 166
 167         trie.insert(loDigits, MAX_LENGTH);
 168         trie.insert(hiDigits, MAX_LENGTH);
 169
 170         if (i == MAX_LENGTH) {
 171             return;
 172         }
 173
 174         for (int j = i + 1; j < MAX_LENGTH; j++) {
 175             short backup = loDigits[j];
 176             for (short digit = (short) (loDigits[j] + 1); digit < NUM_DIGITS; digit++) {
 177                 loDigits[j] = digit;
 178                 trie.insert(loDigits, j + 1);
 179             }
 180             loDigits[j] = backup;
 181
 182             backup = hiDigits[j];
 183             for (short digit = (short) (hiDigits[j] - 1); digit >= 0; digit--) {
 184                 hiDigits[j] = digit;
 185                 trie.insert(hiDigits, j + 1);
 186             }
 187             hiDigits[j] = backup;
 188         }
 189
 190         for (int digit = loDigits[i] + 1; digit <= hiDigits[i] - 1; digit++) {
 191             loDigits[i] = (short) digit;
 192             trie.insert(loDigits, i + 1);
 193         }
 194     }
 195
 196     static class EquivalenceChecker implements TrieNodeProcessor {
 197         public boolean isOK = true;
 198
 199         private final DigitTrie trie;
 200         private final short digit1;
 201         private final short digit2;
 202
 203         public EquivalenceChecker(DigitTrie trie, short digit1, short digit2) {
 204             this.trie = trie;
 205             this.digit1 = digit1;
 206             this.digit2 = digit2;
 207         }
 208
 209         public boolean process(short[] digits, int length) {
 210             for (int i = 0; i < length; i++) {
 211                 if (digits[i] == digit1 || digits[i] == digit2) {
 212                     //System.out.print("check ");
 213                     //dumpDigits(digits, length);
 214                     //System.out.print(" to ");
 215                     final short backupDigit = digits[i];
 216                     digits[i] = (short) (digit1 + digit2 - digits[i]);
 217                     //dumpDigits(digits, length);
 218                     isOK &= trie.contains(digits, length);
 219                     //System.out.print(" -> ");
 220                     //System.out.println(isOK);
 221                     digits[i] = backupDigit;
 222                     if (!isOK) {
 223                         return false;
 224                     }
 225                 }
 226             }
 227             return true;
 228         }
 229     }
 230
 231     private boolean areEquivalent(final short digit1, final short digit2) {
 232         if (digit1 == digit2) {
 233             return true;
 234         }
 235         final EquivalenceChecker checker = new EquivalenceChecker(trie, digit1, digit2);
 236         trie.enumerate(checker);
 237         return checker.isOK;
 238     }
 239
 240     private void solve() {
 241         trie = new DigitTrie();
 242         final int n = in.nextInt();
 243         for (int i = 0; i < n; i++) {
 244             final long lo = in.nextLong();
 245             final long hi = in.nextLong();
 246             insertRange(trie, lo, hi);
 247         }
 248
 249
 250         boolean[] usedDigits = new boolean[NUM_DIGITS];
 251         for (short i = 1; i < NUM_DIGITS; i++) {
 252             if (!usedDigits[i]) {
 253                 for (short j = i; j < NUM_DIGITS; j++) {
 254                     if (!usedDigits[j] && areEquivalent(i, j)) {
 255                         out.print(j);
 256                         usedDigits[j] = true;
 257                     }
 258                 }
 259                 out.println();
 260             }
 261         }
 262     }
 263 }