387A - George and Sleep
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
387B - George and Round
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
387C - George and Number
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
387D - George and Interesting Graph
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.
387E - George and Cards
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
Can anyone explain the solution of problem C
Well my approach to this question was different , just start from the beginning and take 2 string variables. Let the variables be g and l (for global and local resp.),now g will store the substring starting from the beginning till just before the index from where l started.Now if the next character is '0' then we are bound to include it in the local string otherwise just see that whether g>=l or not , if yes then increase ans by 1 and include l in g (g+=l) and clear l, else make ans=1, g=g+l and clear l. This is because if g<l then obviously the substring in l should occur before g in resultant substring (meaning it will be "lg" instead of "gl"). Finally print the ans........
Hope it helps....
Hello, (sorry for my poor english) My solution traverses the string with 2 pointers and whenever it encounters a string representing a smaller number than what's left then add 1 to the answer. It is not necessary to generate any substrings... Just analyze the representation of strings of equal length. Here's my solution: solutionECMC
I am not generating any substring as such , it was the concept used in my solution, my time complexity is O(n).
I don't understand the solution of D . can anyone explain? what to do? why the last part of answer
(n-1)-leng
for?We will add some arcs to create prefect matching in graph
I think the equation came from these :
ans = 2*(n-1); // for adding the (u,i)and(i,u) edges
ans = ans — (cntWithI) ; // they were already given, so we do not need to delete them,
ans = ans+1 ; // the center must have a self loop according to problem description.
ans = ans + Others ; // delete all the extra edges;
ans = ans — leng ; // do not have to delete the matching edges
ans = ans+ (n-1) ; // add n-1 self loops
ans = ans-leng ; // 'leng' number of vertices do not need self loop;
Hope it helps somebody.
In the problem D, said "The complexity is: O(n2 m) time." But n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ 1000). Can you explain why this complexity wont TLE? thank you.
Yes. First, let's calculate number of operations: it is about 2 * 108. It is not so much. If you have good implementation of Kuhn, it would pass. Also, I know, that number of operation is much lower than 2 * 108.
Test case 4 for Problem D says N = 153, M = 392. But there are only 391 edges in the input file.
http://codeforces.net/contest/387/submission/5868021
Am I misunderstanding something? Thanks.
Testcase is valid.
What does n variable mean in C problem tutorial?
n is the length of the number from the input.
So, for 800101 we have a1 = 800, a2 = 10, a3 = 1, and n = 6. what value has i for this example, 1 or -1?
i equals to -1. I understood, that there is an small mistake: answer is k - i + 1
Sorry for so many questions, but I can't still understand how we count answer answer for 800101. here k equals 3, i equals -1 (as you said), then answer should be k — i + 1 = 3 — (-1) + 1 = 5 when answer here is 3.. What I didn't understand correctly?
Oh, it's my mistake. If there is no such index, index i should be equals to 1, yes.
Okey. Then I understand and I'll think about proof. Thank you! :)
In problem C, the definition of the array need[i] in the description does not match with the code provided. The actual definition of need[i] should be : need[i] — equals to 0 if we should remove number i from permutation p, and 1 if we shouldn't remove i from permutation p. Please correct me if I am wrong.
Yes, description does not match with the code provided. There are only ideas in editorial, so there are can be differences.
Problem C is really a challenge for me!!! Orz!!!
Who cares ?
Sorry, I misunderstood the problem. Now it's much easier.
Who cares ???
Seems you care. :D