NEERC/database/database_gk_generic.java

   1 import java.io.File;
   2 import java.io.FileNotFoundException;
   3 import java.io.PrintWriter;
   4 import java.util.ArrayList;
   5 import java.util.Arrays;
   6 import java.util.Collections;
   7 import java.util.HashMap;
   8 import java.util.List;
   9 import java.util.Map;
  10 import java.util.Scanner;
  11 import java.util.TreeMap;
  12
  13 public class database_gk_generic {
  14     static final int MAX_N = 10000;
  15     static final int MAX_M = 100;
  16
  17         static interface Type<V> {
  18                 Pair<Integer, Integer> solve(V[] col1, V[] col2);
  19         };
  20
  21         static interface Generator<V, T> {
  22                 T key(V value1, V value2);
  23         }
  24
  25         static class HashType<V, T> implements Type<V> {
  26                 Generator<V, T> generator;
  27
  28                 public HashType(Generator<V, T> generator) {
  29                         this.generator = generator;
  30                 }
  31
  32                 @Override
  33                 public Pair<Integer, Integer> solve(V[] col1, V[] col2) {
  34                         Map<T, Integer> map = new HashMap<T, Integer>();
  35                         for (int r1 = 0; r1 < col1.length; r1++) {
  36                                 Integer r2 = map.put(generator.key(col1[r1], col2[r1]), r1);
  37                                 if (r2 != null) {
  38                                         return new Pair<Integer, Integer>(r1, r2);
  39                                 }
  40                         }
  41                         return null;
  42                 }
  43         }
  44
  45         static class TreeType<V, T> implements Type<V> {
  46                 Generator<V, T> generator;
  47
  48                 public TreeType(Generator<V, T> generator) {
  49                         this.generator = generator;
  50                 }
  51
  52                 @Override
  53                 public Pair<Integer, Integer> solve(V[] col1, V[] col2) {
  54                         Map<T, Integer> map = new TreeMap<T, Integer>();
  55                         for (int r1 = 0; r1 < col1.length; r1++) {
  56                                 Integer r2 = map.put(generator.key(col1[r1], col2[r1]), r1);
  57                                 if (r2 != null) {
  58                                         return new Pair<Integer, Integer>(r1, r2);
  59                                 }
  60                         }
  61                         return null;
  62                 }
  63         }
  64
  65         static class SortType<V, T extends Comparable<T>> implements Type<V> {
  66                 Generator<V, T> generator;
  67
  68                 public SortType(Generator<V, T> generator) {
  69                         this.generator = generator;
  70                 }
  71
  72                 @Override
  73                 public Pair<Integer, Integer> solve(V[] col1, V[] col2) {
  74                         List<Pair<T, Integer>> pairs = new ArrayList<Pair<T, Integer>>();
  75                         for (int r = 0; r < col1.length; r++) {
  76                                 pairs.add(new Pair<T, Integer>(generator.key(col1[r], col2[r]), r));
  77                         }
  78                         Collections.sort(pairs);
  79                         for (int i = 0; i < pairs.size() - 1; i++) {
  80                                 if (pairs.get(i).f.compareTo(pairs.get(i + 1).f) == 0) {
  81                                         return new Pair<Integer, Integer>(pairs.get(i).s, pairs.get(i + 1).s);
  82                                 }
  83                         }
  84                         return null;
  85                 }
  86         }
  87
  88         static final Generator<String, String> CONCAT_GENERATOR = new Generator<String, String>() {
  89                 @Override
  90                 public String key(String value1, String value2) {
  91                         return value1 + "," + value2;
  92                 }
  93         };
  94
  95         static final Generator<String, String> CONCAT_ERROR_GENERATOR = new Generator<String, String>() {
  96                 @Override
  97                 public String key(String value1, String value2) {
  98                         return value1 + value2;
  99                 }
 100         };
 101
 102         static final Generator<Object, Pair<Object, Object>> PAIR_GENERATOR = new Generator<Object, Pair<Object, Object>>() {
 103                 @Override
 104                 public Pair<Object, Object> key(Object value1, Object value2) {
 105                         return new Pair<Object, Object>(value1, value2);
 106                 }
 107         };
 108
 109         static final Type<String> HASH_CONCAT = new HashType<String, String>(CONCAT_GENERATOR);
 110         static final Type<String> HASH_CONCAT_ERROR = new HashType<String, String>(CONCAT_ERROR_GENERATOR);
 111         static final Type<?> HASH_PAIR = new HashType<Object, Pair<Object, Object>>(PAIR_GENERATOR);
 112         static final Type<?> TREE_PAIR = new TreeType<Object, Pair<Object, Object>>(PAIR_GENERATOR);
 113         static final Type<String> SORT_CONCAT = new SortType<String, String>(CONCAT_GENERATOR);
 114         static final Type<?> SORT_PAIR = new SortType<Object, Pair<Object, Object>>(PAIR_GENERATOR);
 115         static final Type<?> HASH_NESTED = new Type<Object>(){
 116                 @Override
 117                 public Pair<Integer, Integer> solve(Object[] col1, Object[] col2) {
 118                         Map<Object, Map<Object, Integer>> outter = new HashMap<Object, Map<Object, Integer>>();
 119                         for (int r1 = 0; r1 < col1.length; r1++) {
 120                                 Map<Object, Integer> inner = outter.get(col1[r1]);
 121                                 if (inner == null) {
 122                                         inner = new HashMap<Object, Integer>();
 123                                         outter.put(col1[r1], inner);
 124                                 }
 125                                 Integer r2 = inner.put(col2[r1], r1);
 126                                 if (r2 != null) {
 127                                         return new Pair<Integer, Integer>(r1, r2);
 128                                 }
 129                         }
 130                         return null;
 131                 }
 132         };
 133         static final Type<Integer> PACK_LONG = new Type<Integer>(){
 134                 @Override
 135                 public Pair<Integer, Integer> solve(Integer[] col1, Integer[] col2) {
 136                         int n = col1.length;
 137                         long[] pairs = new long[n];
 138                         for (int r = 0; r < n; r++) {
 139                                 pairs[r] = ((long) col1[r] * MAX_N * MAX_M + col2[r]) * n + r;
 140                         }
 141                         Arrays.sort(pairs);
 142                         for (int i = 0; i < n - 1; i++) {
 143                                 if (pairs[i] / n == pairs[i + 1] / n) {
 144                                         return new Pair<Integer, Integer>((int) (pairs[i] % n), (int) (pairs[i + 1] % n));
 145                                 }
 146                         }
 147                         return null;
 148                 }
 149         };
 150
 151         static Scanner in;
 152         static PrintWriter out;
 153
 154         final Type<?> type;
 155         final boolean compact;
 156
 157         int n;
 158         int m;
 159
 160         database_gk_generic(Type<?> type, boolean compact) {
 161                 this.type = type;
 162                 this.compact = compact;
 163         }
 164
 165         static class Pair<F, S> implements Comparable<Pair<F, S>> {
 166                 final F f;
 167                 final S s;
 168
 169                 Pair(F f, S s) {
 170                         this.f = f;
 171                         this.s = s;
 172                 }
 173
 174                 @Override
 175                 @SuppressWarnings("unchecked")
 176                 public int compareTo(Pair<F, S> that) {
 177                         int f = ((Comparable) this.f).compareTo(that.f);
 178                         return f != 0 ? f : ((Comparable) this.s).compareTo(that.s);
 179                 }
 180
 181                 @Override
 182                 public boolean equals(Object o) {
 183                         @SuppressWarnings("unchecked")
 184                         Pair<F, S> that = (Pair<F, S>) o;
 185                         return this.f.equals(that.f) && this.s.equals(that.s);
 186                 }
 187
 188                 @Override
 189                 public int hashCode() {
 190                         return f.hashCode() * 31 + s.hashCode();
 191                 }
 192         }
 193
 194         public void run() {
 195                 n = in.nextInt();
 196                 m = in.nextInt();
 197                 in.nextLine();
 198
 199                 String[][] values = new String[m][n];
 200                 for (int i = 0; i < n; i++) {
 201                         String[] parts = in.nextLine().split(",");
 202                         for (int j = 0; j < m; j++) {
 203                                 values[j][i] = parts[j];
 204                         }
 205                 }
 206
 207                 if (compact) {
 208                         Map<String, Integer> intern = new HashMap<String, Integer>();
 209                         Integer[][] indices = new Integer[m][n];
 210                         int maxIndex = 0;
 211                         for (int j = 0; j < m; j++) {
 212                                 for (int i = 0; i < n; i++) {
 213                                         String value = values[j][i];
 214                                         Integer index = intern.get(value);
 215                                         if (index == null) {
 216                                                 index = maxIndex++;
 217                                                 intern.put(value, index);
 218                                         }
 219                                         indices[j][i] = index;
 220                                 }
 221                         }
 222
 223                         @SuppressWarnings("unchecked")
 224                         Type<Integer> type = (Type<Integer>) this.type;
 225                         for (int c1 = 0; c1 < m; c1++) {
 226                                 for (int c2 = c1 + 1; c2 < m; c2++) {
 227                                         Pair<Integer, Integer> result = type.solve(indices[c1], indices[c2]);
 228                                         if (result != null) {
 229                                                 out.println("NO");
 230                                                 out.println(((int) result.f + 1) + " "  + ((int) result.s + 1));
 231                                                 out.println((c1 + 1) + " "  + (c2 + 1));
 232                                                 return;
 233                                         }
 234                                 }
 235                         }
 236                 } else {
 237                         @SuppressWarnings("unchecked")
 238                         Type<String> type = (Type<String>) this.type;
 239                         for (int c1 = 0; c1 < m; c1++) {
 240                                 for (int c2 = c1 + 1; c2 < m; c2++) {
 241                                         Pair<Integer, Integer> result = type.solve(values[c1], values[c2]);
 242                                         if (result != null) {
 243                                                 out.println("NO");
 244                                                 out.println(((int) result.f + 1) + " "  + ((int) result.s + 1));
 245                                                 out.println((c1 + 1) + " "  + (c2 + 1));
 246                                                 return;
 247                                         }
 248                                 }
 249                         }
 250                 }
 251                 out.println("YES");
 252         }
 253
 254         static void run(Type<?> type, boolean compact) throws FileNotFoundException {
 255                 in = new Scanner(new File("database.in"));
 256                 out = new PrintWriter("database.out");
 257
 258                 new database_gk_generic(type, compact).run();
 259
 260                 in.close();
 261                 out.close();
 262         }
 263 }