codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

387.md (5444B)


      1 Source: https://codeforces.com/blog/entry/10583
      2 
      3 ### [387A - George and Sleep](/contest/387/problem/A "Codeforces Round 227 (Div. 2)")
      4 
      5 I will describe the simple solution. Let George woke up in the *h*0 hours and *m*0 minutes, and he slept for *h*1 hours and *m*1 minutes. Let's get the number *h**p* = *h*0 - *h*1 and *m**p* = *m*0 - *m*1. If *m**p* < 0, then you should add to *m**p* 60 minutes and subtract from *h**p* one hour. After that if *h**p* < 0, then add to it 24 hours. You can print the answer in C++ by using the following line:
      6 
      7 ```
      8 printf("%02d:%02d", h[p], m[p]).
      9 ```
     10 
     11 The complexity is *O*(1) time and *O*(1) memory.
     12 
     13 Author's solution: [5850831](/contest/387/submission/5850831 "Submission 5850831 by gridnevvvit")
     14 
     15 ### [387B - George and Round](/contest/387/problem/B "Codeforces Round 227 (Div. 2)")
     16 
     17 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*.
     18 
     19 The complexity is: *O*(*n*2) time / *O*(*n*) memory. Note, that there is an solution with complexity *O*(*n* + *m*).
     20 
     21 Author's solution: [5850888](/contest/387/submission/5850888 "Submission 5850888 by gridnevvvit")
     22 
     23 ### [387C - George and Number](/contest/387/problem/C "Codeforces Round 227 (Div. 2)")
     24 
     25 Let's obtain the following irreducible representation of a number *p* = *a*1 + *a*2 + ... + *a**k*, where  +  is a concatenation, and numbers *a**i* have the form *x*00..000 (x — is non zero digit, and after that there are only zeroes). Let's determine largest index *i*, such that *a*1 + *a*2 + ... + *a**i* - 1 < *a**i*. 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 : )
     26 
     27 The complexity is: *O*(*n*) time / *O*(*n*) memory.
     28 
     29 Author's solution: [5850919](/contest/387/submission/5850919 "Submission 5850919 by gridnevvvit")
     30 
     31 ### [387D - George and Interesting Graph](/contest/387/problem/D "Codeforces Round 227 (Div. 2)")
     32 
     33 To solve this problem you should know about bipartite matching.
     34 
     35 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.
     36 
     37 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 2*n* - 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.
     38 
     39 The complexity is: *O*(*n*2*m*) time / *O*(*n* + *m*) memory.
     40 
     41 [5850946](/contest/387/submission/5850946 "Submission 5850946 by gridnevvvit")
     42 
     43 ### [387E - George and Cards](/contest/387/problem/E "Codeforces Round 227 (Div. 2)")
     44 
     45 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*.
     46 
     47 Let's *a*1, *a*2, ..., *a**n* - *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.
     48 
     49 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.
     50 
     51 The complexity is: ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) time / *O*(*n*) memory.
     52 
     53 Very simple implementation on Java: [5850986](/contest/387/submission/5850986 "Submission 5850986 by gridnevvvit")