[PYTHON] Codeforces Educational Codeforces Round 101 C. Building a Fence Manage scope YES/NO

https://codeforces.com/contest/1469/problem/C Just read the condition correctly and implement it. Speaking only. Judgment is made by managing "upper and lower limits of the height at which the block may be placed".

Overview

--n Install a fence with a height of just k in this area. However, the ground is uneven and given the heights of integers greater than or equal to zero $ h_1, h_2, ... h_n $. ――This fence can float in the air. However, there are the following restrictions. ―― 1. All fences to be installed must be in contact with the front and rear fences at least one frame. --2. The first and last (= fences installed at $ h_1 $ and $ h_n $) must be in contact with the ground. ―― 3. The fence must not be more than $ k $ away from the ground of the terrain ―― 4. Don't immerse yourself in the terrain (this is an implicit rule)

Please answer YES/NO if this kind of installation is possible.

Understanding the rules

―― 1: is simple. As shown in the figure, it is sufficient if one square is covered. If $ x $ is under the previous fence, then $ x --k-- 1 $ is the limit under the next fence (green dashed line). The limit on the next fence is $ (x + k) + (k -1) $ (dashed blue line). ―― 2: is also simple. The $ h_1 $ and $ h_n $ fences are always placed on the ground. That is, it cannot be placed like the dashed red line in the $ h_1 $ and $ h_n $ areas, it must be placed as the blue square. ―― 3: As shown in the figure on the far right, if the height of the fence is 3, it must not be more than 2 (this is $ k-1 $) from the terrain.

―― 4: Also, although it is not explained on purpose, do not dig into the terrain as shown in the figure below.

Understanding the sample

Now let's look at the example introduced in the question text. sample1 is shown below.

The black shaded area is the ground, and the blue shaded area is the part that is definitely determined. Only the blue line is the fence written in the example. The orange line is an example other candidate.

Now look at Example 3. The blue diagonal fence is confirmed by Rule 2. From Rule 1 (the fence is in contact), the middle fence cannot be placed in either of the red squares. However, according to Rule 3, this fence must not be more than 2 away from the ground (0) (a fence starting at a height of 2 can be placed, but that will not reach the first fence).

I thought like this

Manage the height at which the fence can exist at the current location as a range. When moving to the next area, make sure that you can place it so that it can be connected to the current fence. If it is possible to place it, replace the possible height with the following area, but within the range that does not violate the conditions. Repeat this. I will describe this procedure below

Let $ curLow $ be the minimum height at which the current fence can exist and $ curHigh $ be the maximum height.

--0: First, since it is certain that the first fence will be placed, let $ curLow and curHigh $ be $ h_1 + 1, h_1 + k $. --1: Look at the next area $ i $. If the next area is the last area, jump to 5. What you should check here is "2-1: Will the previous fence be reached?" And "2-2: Is the previous fence above the ground?" --2-1: $ h_i + (k-1) + k $ can reach the top of the fence in the next area. $ k-1 $ is the height that floats above the ground. If this does not reach (or less than) $ canLow $, it will not reach the previous fence. Therefore, it becomes "NO". --2-2: If $ canHigh $ is less than $ h_i $, the previous fence has not reached the current terrain and cannot be fenced. Therefore, it becomes "NO". —— 3: If you can clear the above two items, you can place a fence, so update $ curLow and curHigh $. --4-1: Considering curLow, according to Rule 1, $ canLow-(k-1) $ is the lower limit of the fence that can be placed when not thinking about the ground. But don't dig into the ground as in Rule 4. So if $ h_i $ is greater than or equal to the above formula, then $ h_i + 1 $ is $ curLow $. The reason for $ + 1 $ is that the fence will only start one square above the ground. --4-2: Considering curHigh, according to Rule 1, $ canHigh + (k-1) $ is the upper limit of the fence that can be placed. Rule 3 is relevant for this. In the next area, there is a limit to the height that can be floated as described in 2-1. So, if $ h_i + (k-1) + k $ is lower, this is the upper limit. ―― 5: If it is not the last area, it returns to 1. In the last area, the location of the fence is fixed at $ h_n + 1, h_n + k $. Therefore, check if the current $ curLow, curHigh $ (that is, the position where the previous fence can be placed) overlaps with this.

Implementation

def do():
    n, k = map(int, input().split())
    dat = list(map(int, input().split()))
    # first wall
    canLow, canHigh = dat[0]+1, dat[0] + k-1+1
    for i in range(1, n-1):
        maxCurBlock = dat[i] + (k-1) + k
        if maxCurBlock < canLow: # current block can reach prev block?
            print("NO")
            return
        if canHigh <= dat[i]: # prev block cannot reach current ground?
            print("NO")
            return
        canLow = max(dat[i] + 1, canLow - (k-1))
        canHigh = min(maxCurBlock, canHigh + (k-1))
    # last wall
    if (canLow - dat[n-1]) > k:
        print("NO") # n-1 wall is too high
        return
    if canHigh <= dat[n-1]:
        print("NO") # last wall's ground is too high
        return
    print("YES")

q = int(input())
for _ in range(q):
    do()

https://codeforces.com/contest/1469/submission/102669172