gridnevvvit's blog

By gridnevvvit, 6 years ago, translation, ,

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.

5850946

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

• +35

 » 6 years ago, # |   +2 Can anyone explain the solution of problem C
•  » » 6 years ago, # ^ |   +1 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
•  » » » 6 years ago, # ^ |   0 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
•  » » » » 6 years ago, # ^ |   0 I am not generating any substring as such , it was the concept used in my solution, my time complexity is O(n).
 » 6 years ago, # | ← Rev. 2 →   0 I don't understand the solution of D . can anyone explain? what to do? why the last part of answer (n-1)-leng for?
•  » » 6 years ago, # ^ |   0 We will add some arcs to create prefect matching in graph
•  » » 3 years ago, # ^ |   0 I think the equation came from these :ans = 2*(n-1); // for adding the (u,i)and(i,u) edgesans = 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 edgesans = ans+ (n-1) ; // add n-1 self loopsans = ans-leng ; // 'leng' number of vertices do not need self loop; Hope it helps somebody.
 » 6 years ago, # | ← Rev. 13 →   0 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.
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 Test case 4 for Problem D says N = 153, M = 392. But there are only 391 edges in the input file.http://codeforces.com/contest/387/submission/5868021Am I misunderstanding something? Thanks.
•  » » 6 years ago, # ^ |   0 Testcase is valid.
•  » » » 6 years ago, # ^ |   0 What does n variable mean in C problem tutorial?
•  » » » » 6 years ago, # ^ |   0 n is the length of the number from the input.
•  » » » » » 6 years ago, # ^ |   0 So, for 800101 we have a1 = 800, a2 = 10, a3 = 1, and n = 6. what value has i for this example, 1 or -1?
•  » » » » » » 6 years ago, # ^ |   0 i equals to -1. I understood, that there is an small mistake: answer is k - i + 1
•  » » » » » » » 6 years ago, # ^ |   0 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?
•  » » » » » » » » 6 years ago, # ^ |   0 Oh, it's my mistake. If there is no such index, index i should be equals to 1, yes.
•  » » » » » » » » » 6 years ago, # ^ |   0 Okey. Then I understand and I'll think about proof. Thank you! :)
 » 6 years ago, # |   0 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.
•  » » 6 years ago, # ^ |   0 Yes, description does not match with the code provided. There are only ideas in editorial, so there are can be differences.
 » 6 years ago, # |   0 Problem C is really a challenge for me!!! Orz!!!
•  » » 6 years ago, # ^ |   0 Who cares ?
•  » » » 6 years ago, # ^ |   0 Sorry, I misunderstood the problem. Now it's much easier.
•  » » » » 6 years ago, # ^ |   0 Who cares ???
•  » » » » » 6 years ago, # ^ |   0 Seems you care. :D