I will describe the simple solution. Let George woke up in the h0 hours and m0 minutes, and he slept for h1 hours and m1 minutes. Let's get the number hp = h0 - h1 and mp = m0 - m1. If mp < 0, then you should add to mp 60 minutes and subtract from hp one hour. After that if hp < 0, then add to it 24 hours. You can print the answer in C++ by using the following line:
printf("%02d:%02d", h[p], m[p]).
The complexity is O(1) time and O(1) memory.
Author's solution: 5850831
Consider the number of requirements of the difficulties, which we will cover, and we will come up with and prepare new problem to cover other requirements. It is clear that if we decided to meet the i out of n requirements, it would be better to take those with minimal complexity. Let's simplify i most difficult problems to lightest requirements. If all goes well, then we update the answer by value n - i.
The complexity is: O(n2) time / O(n) memory. Note, that there is an solution with complexity O(n + m).
Author's solution: 5850888
Let's obtain the following irreducible representation of a number p = a1 + a2 + ... + ak, where + is a concatenation, and numbers ai have the form x00..000 (x — is non zero digit, and after that there are only zeroes). Let's determine largest index i, such that a1 + a2 + ... + ai - 1 < ai. If there are no such index i then i = 1. After that is k - i + 1. You can compare numbers by using length of number and first digit. You can prove these solution as home task : )
The complexity is: O(n) time / O(n) memory.
Author's solution: 5850919
To solve this problem you should know about bipartite matching.
Let's consider the center of graph i. After that let's remove arcs that have form (i, u) or (u, i). Let's there are cntWithI arcs of such type. Let's Other = m - CntWithI — number of other arcs.
After that we should found maximal bipartite matching on the bipartite graph. This graph has following idea: left part of this graph is indegrees of all vertexes except vertex i, right part of this graph is outdegrees of all vertexes except vertex i. Also if there an arc (i, j) in our graph then in our bipartite graph there an arc (i, j), where i — vertex from left part, j — vertex from the right part. Let's size of bipartite matching on the bipartite graph equals to leng. Then answer for the current vertex i equals to 2n - 1 - cntWithI + Other - leng + (n - 1) - leng. After that you should update global answer. Why it is correct? It is simple to understand that if we will found bipartite matching on the bipartite graph we will cover maximal number of requirements on in/out degrees. Because of that, we will remove all other arcs, except of maximal matching, and after that we will add this maximal matching to full matching by adding (n - 1) - leng arcs. Note, it is important, that self-loops are not forbidden. Withoud self-loops problem is very hard, I think.
The complexity is: O(n2m) time / O(n + m) memory.
Let's calculate arrays pos[i] — position of number i in permutation p and need[i] — equals to one if we should remove number i from permutation p, and zero if we shouldn't remove i from permutation p.
Let's a1, a2, ..., an - k — numvers, which we should remove. It is clear to understand that we should remove these number in increasing order. It is simple to proof this statement.
Let's iterate i from to 1 to n. Also we the current number we will have special set (set <>in с++, TreeSet in Java) of positions of non-erased numbers (which are smaller then i) of permutation. These position can create an ``obstacle'' for current position of number i. It is simple to support this special set. Also we can add to this set numbers - 1 and n. Now it is easy to find length og the maximal sub-array, where current number is a minimum. You can prosess such query by using standart functions of programming language (lower and higher in Java). After that we should use Fenwick tree to determine quantity of numbers which are not removed on the maximal sub-array.
The complexity is: time / O(n) memory.
Very simple implementation on Java: 5850986