DS III Contest Analysis

Topic

segmenttree2 hmmm

workload2 DS+greedy

stackweights DS+observation

segmenttree3 multi dimensional queries

goodsubsegments impossible problem

segmenttree2

segmenttree2

Just copy code implement

workload2

Subtask 1: N,Q <= 1,000

Recall from greedy lecture that the answer is the maximal number of tutorials held concurrently.

​

An obvious solution is to declare a segment tree over the time. If there is a tutorial, it is a range add.

​

Then we just query the maximal value over all time.

Time Complexity: O(NQ log(40000))

Code: https://pastebin.com/KJYLURrf

Subtask 1: N,Q <= 1,000

But there is a way without segment trees!

​

We are basically building a new segment tree in each query where we do all updates before doing a single query.

​

We can actually use prefix sums to find the number of tutorials held at a single time in O(40000).

Time complexity: O(Q(N+40000)) and it passes comfortably

Code: https://pastebin.com/d07WCnWQ

​

​

Subtask 2: N,Q <= 40,000

You weren't meant to solve this. This was put to force people to grab subtasks.

​

Idea:

• 3D Mo's Algorithm to maintain to contribution to range
• this O(N) code is fast (idk why ¯\_(ツ)_/¯)
• ask errorgorn for more details

Assume N=Q for the time complexity.

Time Complexity: O(N^(5/3)+N^2/w)

stackweights

Solution

Let a[c] be -1 if coin c is put on the left, 0 if it hasnt been added and 1 if its on the right.

​

If we have a suffix such that the sum is >0, we can make the weights of the coins in that suffix sufficiently heavy so that it ignores the weights of the prefix. Then, the left stack will be heavier.

​

Similarly, we can make the right stack heavier if there is a suffix with sum <0.

​

​

Subtask 1: N,U,Q<=500

Literally do what the problem statement tells you

​

Time Complexity: O(N^2(U+Q))

Subtask 2: N<=1000, d-u<=10

In each row, we build a fenwick tree that does RURQ operations.

​

Time Complexity: O((U+Q)*10*(logN))

Code: https://pastebin.com/ZkNAMsBw

​

Or just prefix sum on each row.

​

Time Complexity: O(N^2+(U+Q)*10)

Subtask 3: N<=5000, U,Q<=20000

Intended solution is to extend RURQ fenwick to 2 dimensions. We have 4 fenwick trees. (Work out the math yourself :P)

• fenxy is linear to xy
• fenx is linear to x
• feny is linear to y
• fen is a constant

This can also handle when the updates are not all before the queries.

Time Complexity: O(N^2+(U+Q) log^2(N)), but the constant is huge

Code: https://pastebin.com/j7Exsahx

Subtask 3: N<=5000, U,Q<=20000

Actually there is a better way.

​

​

​

​

​

We do prefix sums again to get something we can query easily.

​

Time Complexity: O(N^2+Q+U)

prefix sum

Subtask 4: N <= 100000, Q <= 100000

Imagine RURQ fenwicks on each column. Each cell will now have 2 values, which the RURQ fenwicks track.

Subtask 4

When we do a update of v from row u to d on column x, we do 4 updates on the 2 grids:

​

value 1: +v to (u,x) and -v to (d+1,x)

value 2: - (u-1) * v to (u,x) and +v*d to (d+1,x)

​

This is expandable to ranges of columns by changing +v to (u,x) to +v to (u,l:r) etc.

Subtask 4

Let’s do sliding line on the rows, maintaining 2 RURQ fenwicks along the way which keep track of values 1 and 2. Whenever we reach row y, we can loop through all of the updates where y = u or y = d+1 and range and do updates as per the previous slide.

Subtask 4

Queries are answered by taking:

(range sum on [l,r] for value 1) * y + (range sum on [l,r] for value 2).

for row y

​

This gets the sum for the query except u is set to 1. We can get the answer by using this formula for row = u-1 and subtracting the result from the formula for row = d.

Subtask 4

This solution is expandable to ranges of columns by changing point updates to range updates.

Final complexity: NlogN

Code: https://pastebin.com/phvZ1vX6

Subtask 4

Alternative solution: sqrt! (this barely passes TL)

​

We will assume that the updates are randomly generated (this is not needed but it allows for more lazy imple).

​

We will do a sweep on the rows of the matrix.

​

​

Subtask 4

To make the updates easier to handle we instead change a single update into 2 updates where the rows extend to infinity.

​

​

​

​

Subtask 4

We update K rows at a time. Since we assumed that updates are randomly generated, we should only expect around 2K ranges to be updated in this region. So we split the columns into these 2K ranges.

​

​

We can easily handle operations in O(K) time now.

Time complexity: O(NK+N^2/K)

Code: https://pastebin.com/8603c6zF

​

​

goodsubsegments

Q5 from last year contest but buffed

Subtask 1: Q=1, l=1,r=N

Mademadics

• An interval [l,r] is good if
• Rearrange terms,
• This is cool because if we can maintain the above sum, we only need to count 0.
• Proof (kind of):
• Sort the elements in the range of [l,r] let the sorted order be A, B, C, D …
• To be valid, 1 = B-A = C-B = D-C … which implies that max - min = r - l
• Since each element is unique, B-A, C-B >= 1
• Hence if an element is missing, then we will be larger than r - l

​

Sliding Line

• Define
• Define
• We wish to get S(r+1) quickly from S(r)

​

​

Sliding Line

We store a stack that stores {value,position} but actually value=arr[position]

For the array {4,7,3,2,5}

At position 4, the array is [{7,1},{3,2},{2,3}]

At position 5, the array is [{7,1},{5,4}]

Notice how when updating this stack, it is removing a suffix of the stack and adding the new element.

Then we just have to do a range add operation for those positions that change their max value. You can show that we only do O(N) segment tree updates since we only do updates when we delete an element from the stack and when we add an element to the stack.

​

​

S(4)

S(5)

Sliding Line

Now, we need to maintain

Earlier, we have shown how to maintain max using a stack and range add operations. Maintaining min is very similar. To maintain (r-l) is also a range add operation. Therefore, using a range add segment tree, we can maintain that value.

However, in this problem, we also need to count the number of 0 in the range of a segment tree.

​

​

Counting 0s

Notice that

Its quite obvious but this is important to be able to the number of 0s in a range.

We maintain the minimum element of a range and the occurrences of it.

​

Complexity: O(NlogN)

Code:

Subtask 2

Crazy Segment Tree

ask errorgorn privately.