So this was an interesting problem. You could have technically solved it manually but that would have taken too much time. If you didn’t mind at most 7 WA’s you could have just tried all 8 solutions one at a time and gotten it correct. I did it the long way; making my program solve it for me.<\/p>\n
I used this string normalization technique I was ‘taught’ in college. It’s a neat little trick that I seem to use every chance I get. Pretty easy solution once you know you can map all permutations of a string to just one string!<\/p>\n
\r\nimport java.io.PrintWriter;\r\nimport java.util.Arrays;\r\nimport java.util.Scanner;\r\n\r\n\/**\r\n * \r\n * @author Sanchit M. Bhatnagar\r\n * @see http:\/\/uhunt.felix-halim.net\/id\/74004\r\n * \r\n *\/\r\npublic class P12478 {\r\n\r\n public static void main(String[] args) {\r\n Scanner sc = new Scanner(System.in);\r\n PrintWriter out = new PrintWriter(System.out);\r\n\r\n String[] grid = new String[] { "OBIDAIBKR", "RKAULHISP", "SADIYANNO", "HEISAWHIA", "IRAKIBULS", "MFBINTRNO", "UTOYZIFAH", "LEBSYNUNE", "EMOTIONNAL" };\r\n\r\n String[] originalNames = new String[] { "RAKIBUL", "ANINDYA", "MOSHIUR", "SHIPLU", "KABIR", "SUNNY", "OBAIDA", "WASI" };\r\n\r\n String[] names = new String[originalNames.length];\r\n int[] count = new int[names.length];\r\n\r\n for (int i = 0; i < names.length; i++) {\r\n names[i] = normalize(originalNames[i]);\r\n }\r\n\r\n \/\/ Check Horizontally\r\n for (int zz = 0; zz < 9; zz++) {\r\n for (int i = 0; i < 9; i++) {\r\n for (int j = i + 4; j <= 9; j++) { \/\/Shortest name is 4 characters so we are checking for sub-strings of at least that length. We could also have capped the sub-string to at most 7 characters based on the names provided.\r\n String substring = normalize(grid[zz].substring(i, j));\r\n for (int k = 0; k < names.length; k++) {\r\n if (substring.equals(names[k])) {\r\n count[k]++;\r\n }\r\n }\r\n }\r\n }\r\n }\r\n\r\n \/\/ Check Vertically\r\n String[] grid2 = new String[grid.length];\r\n for (int j = 0; j < 9; j++) {\r\n char[] tmp = new char[9];\r\n for (int i = 0; i < 9; i++) {\r\n tmp[i] = grid[i].charAt(j);\r\n }\r\n grid2[j] = new String(tmp);\r\n }\r\n\r\n for (int zz = 0; zz < 9; zz++) {\r\n for (int i = 0; i < 9; i++) {\r\n for (int j = i + 4; j <= 9; j++) {\r\n String substring = normalize(grid2[zz].substring(i, j));\r\n for (int k = 0; k < names.length; k++) {\r\n if (substring.equals(names[k])) {\r\n count[k]++;\r\n }\r\n }\r\n }\r\n }\r\n }\r\n\r\n for (int i = 0; i < count.length; i++) {\r\n if (count[i] == 2) {\r\n out.println(originalNames[i]);\r\n }\r\n }\r\n\r\n out.close();\r\n sc.close();\r\n }\r\n\r\n \/\/ Normalizes all strings\r\n private static String normalize(String word) {\r\n char[] list = word.toCharArray();\r\n Arrays.sort(list);\r\n return new String(list);\r\n }\r\n}\r\n<\/pre>\nEdit: Further explanation. I’ve also updated the code to avoid the IndexOutOfBounds exception I was strangely using a try-catch for.<\/p>\n
Firstly let us cover the normalize function. As you can tell by the code, it\u00a0takes a word, splits it into a character array, sorts the character array and then converts it back into a string. Let us take some examples so that this is clear.<\/p>\n
Take a word, let’s say: apple once you run it through the normalize function it will become aelpp. The same will happen for all permutations of apple (I won’t list them all) for example aplpe, ppael, leapp, etc. This allows us to quickly check if a particular permutation of a word is in the grid.<\/p>\n
If this part is clear then we can just move on to the checking part.<\/p>\n
We will go through the grid one row at a time (the code with the comment stating horizontal). Find all substrings within that line, normalize them and then compare them with the names array. If they are in the array then we increment a counter (named count). We do the same thing for the grid vertically.<\/p>\n","protected":false},"excerpt":{"rendered":"
So this was an interesting problem. You could have technically solved it manually but that would have taken too much time. If you didn’t mind at most 7 WA’s you could have just tried all 8 solutions one at a time and gotten it correct. I did it the long way; making my program solve … Continue reading UVA 12478 – Hardest Problem Ever (Easy)<\/span>