616A - Comparing Two Long Integers
Note that solutions in Java with BigInteger class or input() function in Python2 will fail in this problem. The reason is the next: standard objects stores numbers not in decimal system and need a lot of time to convert numbers from decimal system. Actually they are working in O(n2), where n is the legth of the number.
To solve this problem you should simply read the numbers to strings and add leading zeroes to the shorter one until the numbers will be of the same length. After that you should simply compare them alphabetically.
Complexity: O(n).
Firstly you should find the minimum value in each row and after that you should find the maximum value over that minimums. It's corresponding to the strategy of Jack and Emma.
Complexity: O(nm).
Let's enumerate all the connected components, store their sizes and for each empty cell store the number of it's component. It can be done with a single dfs. Now the answer for some impassable cell is equal to one plus the sizes of all different adjacent connected components. Adjacent means the components of cells adjacent to the current impassable cell (in general case each unpassable cell has four adjacent cells).
Complexity: O(nm).
