When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

DmitryKlenov's blog

By DmitryKlenov, 14 years ago, In English
As there is no tutorial of Codeforces Beta Round #5 in English, I have decided to write this one. Possibly, some ideas will be similar to ones, expressed in Russian tutorial made by SkidanovAlex, but I hope everybody will find some useful in this problem analysis too.

Problems A and B.


Both are implementation problems. The only difficult, many participants faced with - to read data correctly. It is recommended to use gets(s) or getline(cin, s) in C++, readLine() method of BufferedReader class in Java.

Problem C.


First of all, for each closing bracket in our string let's define 2 values:
  • d[j] = position of corresponding open bracket, or -1 if closing bracket doesn't belong to any regular bracket sequence.
  •  c[j] = position of earliest opening bracket, such that substring s(c[j], j) (both boundaries are inclusive) is a regular bracket sequence. Let's consider c[j] to be -1 if closing bracket doesn't belong to any regular bracket sequence.
It can be seen, that c[j] defines the beginning position of the longest regular bracket sequence, which will end in position j. So, having c[j] answer for the problem can be easily calculated.

Both d[j] and c[j] can be found with following algorithm, which uses stack.
  1. Iterate through the characters of the string.
  2. If current character is opening bracket, put its position into the stack.
  3. If current character is closing bracket, there are 2 subcases:
  • Stack is empty - this means that current closing bracket doesn't have corresponding open one. Hence, both d[j] and c[j] are equal to -1.
  • Stack is not empty - we will have position of the corresponding open bracket on the top of the stack - let's put it to d[j] and remove this position from the stack. Now it is obvious, that c[j] is equal at least to d[j]. But probably, there is a better value for c[j]. To find this out, we just need to look at the position d[j] - 1. If there is a closing bracket at this position, and c[d[j] - 1] is not -1, than we have 2 regular bracket sequences s(c[d[j] - 1], d[j] - 1) and s(d[j], j), which can be concatenated into one larger regular bracket sequence. So we put c[j] to be c[d[j] - 1] for this case.

Problem D.


This problem can be solved by careful case handling. Let's construct O(1) solution for it.

First of all, let's define 2 functions:

  1. dist(speed, time) - calculates the distance will be covered in specified time, if car's current speed is speed. This function will not take car's speed limit into account. Also it assumes, that car is always driven with maximum acceleration a. It is obvious that required distance is equal to .
  2. travelTime(distance, speed) - calculates the time, required to travel specified distance, if car have starting speed equal to speed. This function will also take care about car's speed limit.
    We will have the following quadratic equation for time t: . This equation will have exactly 2 different roots. Using Viete's formulas it can be concluded, that one root of the equation is non-positive and other is non-negative. Let's define the larger root of the equation as tAll. It will be the answer, if there is no car's speed limit. To take the limit into account let's find the time, required to gain car's max speed. tMax = (v - speed) / a. If tMax ≥  tAll, function should just returns tAll as a result. Otherwise result is tMax hours to achieve car's maximal speed plus (distance - dist(speed, tMax)) / v hours to cover remaining distance.

Having these functions, solution will be the following:

  1. If v ≤ w, answer is travelTime(l, 0).
  2. Calculate tw = w / a -  time, required to gain speed w.
  3. Consider dw = dist(0, tw).
  4. If dw ≥ d, we will pass the point there sign is placed before we gain speed w. Answer for this case is travelTime(l, 0) as well.
  5. Otherwise, we will gain speed w before the sign. Let's consider segment of the road [dw, d]. We need to find out the best strategy to drive it. It is obvious, that we definitely should have speed w at the both ends of this segment. Also we know, that acceleration is equal to deceleration. Taking these facts into account we can see, that the speed in the optimal solution will be symmetrical with respect to the middle of the segment [dw, d]. Hence answer for this case will be tw + 2 *  travelTime(0.5 * (d - dw), w) + travelTime(l - d, w).

Problem E.


Let's reduce the problem from the circle to the straight line. Perform the following actions to do it:

  1. Find the hill with the maximal height (if it is not unique, choose any).
  2. Rotate all the sequence in such a way that hill with maximal height goes first.
  3. For convenience, add one more hill with maximum height to the end of the sequence. (It will represent the first hill, which goes after the last in the circle order).
Now we have almost the same problem on the straight line. One exception is that now first hill is doubled.

General idea of the solution:

Consider there is a pair of hills, such that these hills are visible from each other. Let's define hill with lower height (if heights are equal - with lower position) as responsible for adding this pair to the answer.

From this point of view, hill x will adds to the answer 3 kinds of hills as his pair:
  • First hill to the left of the x, which is strictly higher than x. (Let's define its position as l[x])
  • First hill to the right of the x, which is strictly higher than x. (Let's call this hill y and define it's position as r[x]).
  • All hills that are as high as x and are located between x and y. (Let's define this count as c[x]).
Arrays r[x] and c[x] can be calculated by the following piece of code:

c[n] = 0;
for(int i = n - 1; i >= 0; --i) {
    r[i] = i + 1;
    while (r[i] < n && height[i] > height[r[i]]) r[i] = r[r[i]];
    if (r[i] < n && height[i] == height[r[i]]) {
        c[i] = c[r[i]] + 1;
        r[i] = r[r[i]];
    }
}

I am not going to prove here, that it works for the O(N) time, but believe it does :)

Pay attention, that r[x] is undefined for hills with maximum height and this algorithm will find r[x] = n for such hills.

Array l[x] can be found in a similar way.

Having l[x], r[x] and c[x], it's not so difficult to calculate the answer. We should just notice, that:
  • Each hill will add c[x] pairs to the answer.
  • Each hill, lower than maximal, will also add 2 pairs (x, l[x]) and (x, r[x]) to the answer. The only corner case here is l[x] = 0 and r[x] = n, because (x, 0) and (x, n) is the same pair of hills in the original problem, where hills are circled.
  • Vote: I like it
  • +12
  • Vote: I do not like it

| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Excellent Tutorial. Specially for explanation of Problem C.
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

very nice. but what is the exact meaning of array c[]?

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why time complexity is O(N) in prob E !

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

    have u figured it out?i'm little confused too:(

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

      I do not think that is O(N). How much time does it take your implementations to finish the tests?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the output for these 2 test cases: Input1: )((())))(()()) Output1: 6 2

Input2: ()(())() Output2: 8 1

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    How the regular bracket sequence goes, in context free grammar you can define it like this.

    S = SS | (S) | empty

    some examples — (), ()(), ()()(), (()), (()()), (())() etc.

    In 1st case there are 2 substrings of length 6 — ((())) starting at 2 and (()()) starting at 9.

    In 2nd case there is 1 substring of length 8 which is the whole string itself.

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

      In problem C, I am unable to figure out how to count regular brackets from above explanation. Please help!

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

        My solution for C: Take dp[i] as the longest bracket sequence ending at index i.

        Now if s[i]=='(' put dp[i]=0

        else s[i] must pair up with a '(' before it. this '(' should be at index j=i-dp[i-1]-1. we use the observation that s[x,...,y] is a palindrome if x-1 matches up with y+1 to prove this. proof: let the index be j0 now if j0 > j then s[j0+1,...,i-1] should be a palindrome by observation so but also s[j,...i-1] is also a palindrome and since s[j0]=='(' so it must match up with some later character but all the characters after j0 are matched with each other as s[j0+1,...,i-1] is palindrome. so we get no match for j0, a contradiction. for j0<j s[j0+1,...i-1] is palindrome but its length becomes longer than dp[i-1] a contradiction so j0=j. now dp[i] = dp[i-1]+((2+dp[i-dp[i-1]-2]) if s[i]!=s[i-dp[i]-1])

        code for reference

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Old problems... Is there anyone like me doing these as practice?

I use monoStack to solve probloem E, it's O(N) and easier to understand.

Keep a decending monoStack of (height,count). Each step, ans+=sum{count|height<=cur_height}

https://codeforces.com/contest/5/submission/81430803

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, this dp can better be optimized by a stack but s seg tree.

  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In addition, Fenwick Tree and Sparse Table run fast than Segment Tree.