gridnevvvit's blog

Editorial Codeforces Round #227 (Div. 2)
By gridnevvvit, 11 years ago, translation, In English

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

  • Vote: I like it
  • +35
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can anyone explain the solution of problem C

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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....

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am not generating any substring as such , it was the concept used in my solution, my time complexity is O(n).

        → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't understand the solution of D . can anyone explain? what to do? why the last part of answer (n-1)-leng for?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We will add some arcs to create prefect matching in graph

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
← Rev. 13   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Test case 4 for Problem D says N = 153, M = 392. But there are only 391 edges in the input file.

http://mirror.codeforces.com/contest/387/submission/5868021

Am I misunderstanding something? Thanks.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Testcase is valid.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What does n variable mean in C problem tutorial?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        n is the length of the number from the input.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          So, for 800101 we have a1 = 800, a2 = 10, a3 = 1, and n = 6. what value has i for this example, 1 or -1?

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i equals to -1. I understood, that there is an small mistake: answer is k - i + 1

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Oh, it's my mistake. If there is no such index, index i should be equals to 1, yes.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Okey. Then I understand and I'll think about proof. Thank you! :)

                  → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, description does not match with the code provided. There are only ideas in editorial, so there are can be differences.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is really a challenge for me!!! Orz!!!

→ Reply