Edvard's blog

Editorial of Educational Codeforces Round 4
By Edvard, history, 9 years ago, translation, In English

612A - The Text Splitting

Let's fix the number a of strings of length p and the number b of strings of length q. If a·p + b·q = n, we can build the answer by splitting the string s to a parts of the length p and b parts of the length q, in order from left to right. If we can't find any good pair a, b then the answer doesn't exist. Of course this problem can be solved in linear time, but the constraints are small, so you don't need linear solution.

Complexity: O(n2).

612B - HDD is Outdated Technology

You are given the permutation f. Let's build another permutation p in the following way: pfi = i. So the permutation p defines the number of sector by the number of fragment. The permutation p is called inverse permutation to f and denoted f - 1. Now the answer to problem is .

Complexity: O(n).

612C - Replace To Make Regular Bracket Sequence

If we forget about bracket kinds the string s should be RBS, otherwise the answer doesn't exist. If the answer exists each opening bracket matches to exactly one closing bracket and vice verse. Easy to see that if two matching brackets have the same kind we don't need to replace them. In other case we can change the kind of the closing bracket to the kind of the opening. So we can build some answer. Obviously the answer is minimal, because the problems for some pair of matching pairs are independent and can be solved separately.

The only technical problem is to find the matching pairs. To do that we should store the stack of opening brackets. Let's iterate from left to right in s and if the bracket is opening, we would simply add it to the stack. Now if the bracket is closing there are three cases: 1) the stack is empty; 2) at the top of the stack is the opening bracket with the same kind as the current closing; 3) the kind of the opening bracket differs from the kind of the closing bracket. In the first case answer doesn't exist, in the second case we should simply remove the opening bracket from the stack and in the third case we should remove the opening bracket from the stack and increase the answer by one.

Complexity: O(n).

612D - The Union of k-Segments

Let's create two events for each segment li is the time of the segment opening and ri is the time of the segment closing. Let's sort all events by time, if the times are equal let's sort them with priority to opening events. In C++ it can be done with sorting by standard comparator of vector<pair<int, int>> events, where each element of events is the pair with event time and event type ( - 1 for opening and  + 1 for closing).

Let's iterate over events and maintain the balance. To do that we should simply decrease the balance by the value of the event type. Now if the balance value equals to k and before updating it was k - 1 then we are in the left end of some segment from the answer. If the balance equals to k - 1 and before updating it was k then we are in the right end of the segment from the answer. Let's simply add segment [left, right] to the answer. So now we have disjoint set of segments contains all satisfied points in order from left to right. Obviously it's the answer to the problem.

Complexity: O(nlogn).

612E - Square Root of Permutation

Consider some permutation q. Let's build by it the oriented graph with edges (i, qi). Easy to see (and easy to prove) that this graph is the set of disjoint cycles. Now let's see what would be with that graph when the permutation will be multiplied by itself: all the cycles of odd length would remain so (only the order of vertices will change, they will be alternated), but the cycles of even length will be split to the two cycles of the same length. So to get the square root from the permutation we should simply alternate (in reverse order) all cycles of the odd length, and group all the cycles of the same even length to pairs and merge cycles in each pair. If it's impossible to group all even cycles to pairs then the answer doesn't exist.

Complexity: O(n).

612F - Simba on the Circle

The author solution for this problem uses dynamic programming. I think that this problem can't be solved by greedy ideas. Let's calculate two dp's: z1i is the answer to the problem if all numbers less than ai are already printed, but the others are not; and z2i is the answer to the problem if all numbers less than or equal to ai are already printed, but the others are not. Let's denote dij — the least distance between i and j on the circular array and odij is the distance from i to j in clockwise order. Easy to see that z2i = minj(zj + dij) for all j such that the value aj is the least value greater than ai. Now let's calculate the value z1i. Consider all elements equals to ai (in one of them we are). If there is only one such element then z1i = z2i. Otherwise we have two alternatives: to move in clockwise or counterclockwise direction. Let we are moving in clockwise direction, the last element from which we will write out the number would be the nearest to the i element in counterclockwise direction, let's denote it u. Otherwise at last we will write out the number from the nearest to the i element in clockwise direction, let's denote it v. Now z1i = min(z2u + odiu, z2v + odvi). Easy to see that the answer to the problem is mini(z1i + dsi), over all i such that ai is the smallest value in array and s is the start position.

Additionally you should restore the answer. To do that, on my mind, the simplest way is to write the recursive realization of dp, test it carefully and then copy it to restore answer (see my code below). Of course, it's possible to restore the answer without copy-paste. For example, you can add to your dp parameter b which means it's need to restore answer or not.

Complexity: O(n2).

Code

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

Comments Comments (33)
| Write comment?
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can we get the editorial in english ? Please....

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

    I'm working on it.

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

      Thanks

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

        Done.

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

          It would be nice if we get the sample codes for all the problems ....

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

            Not like there aren't hundreds of solutions to all the questions as it stands... just look at some other people's code, you'll gain a lot of new tricks you never knew about before!

            → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For A, there's also a simple O(N) DP solution in which F[i] is true if we can represent i as A*p+B*q or false otherwise. It's easy to restore a possible sequence if F[n] is true :)

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

    Also you can simply iterate from 0 to max_possible_B and check if ((n — i*q) mod p == 0). If found — its an answer. If not — impossible.

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

Hi there!

In trying on Problem E, I implemented the idea per the Editorial, to create and sort events, and linearly scan them. But I got TLE on input #19. Any ideas?

I'm not sure if it's appropriate to paste my code here. But if so, I'd love to share with you and receive any feedbacks!

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    You can post a link to you submission. When looking at your profile history, I see the submission history anyway.

    Your I/O is too slow. There has been written a lot about cout/cin vs. scanf/printf on Codeforces, just search.

    First, do not use endl after every line — it flushes the output buffers, therefore is slow.

    Second, add this code at start of main():

        ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    Then try again and it should be AC.

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

Totally lost in editorial of "The Union of k-Segment". what is the "balance" and what is "decrease the balance".

what is the deal with event time?in simple words please.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    The algorithm being used is a Sweep line algorithm. We're sweeping the x-axis from left to right. It makes sense to call the openings and closings of the given segments 'events'. Since we want to sweep the x-axis from left to right, we're going to create a bunch of events, sort them by x-coordinate, then process them.

    The balance is the number of segments that have been opened so far as I'm sweeping the x-axis. When this balance is increased to k, you're in a satisfied part of the x-axis. When the balance decreases from k to k-1, you're on the boundary of a satisfied part of the x-axis.

    → Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I am not able to understand Square Root of Permutation editorial can someone provide detailed expalnation for that ?? It will be really helpfull :)

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

    Here are some hints: http://math.stackexchange.com/questions/266569/how-to-find-the-root-of-permutation

    The answer still may be too advanced to understand if haven't studied the math of permutation groups. Basically, every permutation can be expressed in a cyclic notation. To do that, first write the permutation as multiplication of transpositions (a transposition is a cycles with two elements). For the example q = [4, 5, 1, 2, 3], 1 maps to 4, 2 to 5 and so on, so we write it down:

    q = (1 4)(2 5)(3 1)(4 2)(5 3)

    Now some transpositions can be merged. In fact in this example all of them can be merged, but that will not always be the case:

    q = (1 4 2)(2 5)(3 1)(5 3) = (1 4 2 5)(3 1)(5 3) = (1 4 2 5 3)(3 1) = (1 4 2 5 3)

    The resulting cycle of length 5 denotes the same original permutation q, just in a different way.

    Now if q=(i1, i2, i3, i4, i5) then in q^2 element i2 moves one step away from i1: q^2=(i1, ..., i2, ...), element i3 one step away from i2 and so on (modulo the size of the permutation): q^2=(i1, i4, i2, i5, i3)

    In the example, q^2 = (1 4 2 5 3)^2 = (1 2 3 4 5). Written back in the original form, it is the permutation p = [2 3 4 5 1].

    The analysis so far works for cycles with odd length. For a cycle with even length l, for example p = (i1, i2, i3, i4) element i_n-2 maps back to i1 and so on; the result in this case is two cycles with length l/2: p = (i1 i3)(i2 i4)

    To solve the exercise, you need to do the opposite: permute every odd-sized cycle back, and merge every pair of same-sized even cycles. (If there are more than one pair of cycles with size 2n, then multiple solutions exist.) If there are even-sized cycles with no pair, then a solution does not exist.

    Finding the cycles in the given permutation requires some preprocessing, but it can be done in O(n) time.

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

      thank you.

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

      It seems that while explaining how to find the square of a permutation, you have explained how to find the root of the permutation.

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

Link to editorial(tutorial) added under contest material on contest page is not working(redirecting to edit blog link).

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

D getting TLE for O(NlogN) in python.

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

    Python isn't really a good choice for competitive programming. Some simple algorithms works there like 40 times slower than C#/Java/C++.

    On top of than you should have very fast console i/o. It could be impossible to solve this task in Python at all.

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

      You are right. I just wanted to know if anyone got AC for that problem in python.

      → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Question to people who solved problem E in round what made you think of this problem as a graph problem? and what lead you to that observation i mean i've been to solve graph problems for a while and still i can't reach that graph mentality which enables me to realize the point of such a problem if anyone would kindly share their experience or a few pointers that would be great (p.s: sorry for double post but first time was by mistake in russian)

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

    It is quite standart idea to consider a permutation graph. And in this problem some outputs for small cases helped me to get the right idea;)

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

      Can you please provide some links to tutorials or problems , where this idea has been used .

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        I don't know about articles on English about it, you may take a look at Wikipedia though or try to find some other information in Google. There had been some problems on Codeforces with such idea but i could not find them now. One of the famous problems is to find the k-th power of the given permutation of size n. It can be solved with O(n log k) complexity using binary exponentiation but with idea of the permutation graph it can be done in O(n).

        → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It seems to me that the solution for F is a bit incorrect. Especially, recalculating of z1. It is claimed that we need to move only in one direction (i.e. clockwise or counterclockwise). However, sometimes we need to move in one direction, then return to the initial point and continue moving in the direction, opposite to the initial direction. For example, test:

10 5
1 1 1 0 0 0 1 1 1 1

We need to do the following sequence of steps: +0, -1, +2 (or -1, +1, +1) firstly. And the suggested author's solution gives correct answer to this test. Can you please explain, what's going on?

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

    I know it's been three years, but I also stumbled on this, so maybe it will help future upsolvers.

    If you define $$$z1_i$$$ as the minimal cost of starting at position $$$i$$$ and visiting all positions with values greater than or equal to $$$a_i$$$, then indeed you have to consider a general case: move in one direction to some $$$j$$$, then move in other direction to some $$$k$$$:

            j <------ i
          -------------> k

--------X---X-X---X--X---X---------------

    In the picture above going only in one direction from $$$i$$$ will give too big cost $$$z1_i$$$. But note that cost $$$z1_j$$$ will be calculated correctly.

    Now consider calculating $$$z2_x = \min_y(z1_y + d_{xy})$$$ for some position $$$x$$$ where $$$a_x$$$ is the biggest value smaller than $$$a_i$$$. If it's optimal to move from $$$x$$$ to $$$i$$$ (i.e. $$$y=i$$$ achieves minimum), then we make a move from $$$x$$$ to $$$i$$$ and then to $$$j$$$. Since all values $$$a_i$$$ will be visited on path from $$$j$$$ to $$$k$$$, we could have moved directly from $$$x$$$ to $$$j$$$. Thus $$$y=j$$$ also achieves minimum, and since $$$z1_j$$$ is correct, then $$$z2_x$$$ will also be correct.

    To summarize: values $$$z1_i$$$ in author's solution are sometimes bigger than advertised, but it doesn't matter, since there is at least one correct value that achieves minimum.

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

Question about 612E: I didn't get what the editorial means with merge cycles in each pair. For example, the permutation 2 1 4 3 has two cycle of size 2 which are 2->1->2 and 4->3->4. How should I merge this?

I ran one correct solution for this input and I got 3 4 2 1 which means that the result of merge should be 3->2->4->1->3. But I didn't get the idea behind the merge process.

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

Can someone explain me why C problem 11-th test answer is 7? Input:

(([{>}{[{[)]]>>]

My program outputs 3 and I when I tried to do this manually I also found that only 3 changes are needed:

(([{>}{[{[)]]>>]

'<'([{>}'<'['<'[)]]>>]

Did I misunderstand the problem or the test is wrong?

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

Why in Problem D. The Union of k-Segments in first sample test with input:

3 2
0 5
-3 2
3 8

we get output 

2
0 2
3 5

and not 

1
0 5

as far as I can see all the points of interval 0 5 belongs to at at least 2 segments therefore set of one segment (0 5) is the smallest?

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

    Actually it's not. Here the problem says that all satisfied points (I presume that you are mistaking for satisfied INTEGER points) must be included. Indeed, 2 and 3 are satisfied points but 2.5 is not

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

you can solve problem A using dp in linear time 167881923

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

For the future solvers

Problem D

test#1 case ans is two segments because all the real numbers between 2 and 3 aren't satisfying the condition

test#2 case all the real numbers between 2 and 3 also satisfying the condition so only one interval is required

My appraoch

since real numbers check is required so our standard sweep line template wont work, we need to add some more checks, the way i did it quite easy to understand i think,

lets say our current interval is [ a , b ] and previous valid interval is [ c , d ] if these points are integer then can't have the information of the numbers in between two intervals so we need real numbers, but that will not be very intuitive when implementing.

so what i did is, multiplied each interval end point by 100,

and updated the map, mp[left]++ , mp[right+1]--;

now if two intervals differ less than 2 then they can be merged if not they will be seperated,

this above implementation is same as having real number of precision of 0.01, but we are doing it with integers only.

here is the my AC code implementation:

my c++ code
→ Reply