2022 NUS Dec Course BAPS Editorial

Finding Grass

omg is this a touching grass reference?!?!?

Also please read the full story

Abridged Statement

There are two arrays A and B of length N, as well as Q updates, each changing the value of exactly one element.

Before the first update, and after every update, find any index 1 ≤ k ≤ n such that:

​

Subtask 2: N ≤ 2000, Q ≤ 50

Just brute force.

For each answer, just try all possible indices k and check if it’s possible in O(N).

Time complexity: O(QN²)

Subtask 3: N ≤ 20 000, Q ≤ 50

Better brute force.

For each k, how to check if it’s possible in log time?

(aka how does the checker work?)

​

Subtask 3: N ≤ 20 000, Q ≤ 50

Use a segment tree.

Each node stores the sum of elements and number of elements with value in its range.

For each a_k, to calculate , split into a_i ≤ a_k and a_i > a_k.

Sum for a_i ≤ a_k: a_k*root->number(-INF, a_k) - root->sum(-INF, a_k)

Sum for a_i > a_k: root->sum(a_k+1, INF) - a_k*root->number(a_k+1, INF)

This can be done similarly to calculate . (Use another segment tree.)

Check for all k, time complexity O(NQ log A) where A is the range of values of a and b.

Subtask 3: N ≤ 20 000, Q ≤ 50

Apparently you can scam with subtask 2 solution by only finding a new index if the previous index fails.

I tried to kill; my code runs in >15s on polygon but only takes 2s on codebreaker for some reason.

Subtask 4: N ≤ 20 000, Q ≤ 10 000

Hmm.. how to O(NQ)?

For each k, how to check if it’s possible in O(1) time?

​

Subtask 4: N ≤ 20 000, Q ≤ 10 000

Hmm.. how to O(NQ)?

For each k, how to check if it’s possible in O(1) time?

Idk, instead let’s make an observation!

What if min(ai) ≤ min(bi), max(ai) ≥ max(bi)?

I initially wanted to add this subtask but thought it might be too revealing of the full solution.

Draw the points on a number line. (Assume a, b are sorted.)

a

b

x

What if min(ai) ≤ min(bi), max(ai) ≥ max(bi)?

What is ?

It is the sum of distances from a_k to all other a_i!

a

b

What if min(ai) ≤ min(bi), max(ai) ≥ max(bi)?

What is ?

It is the sum of distances from a_k to all other a_i!

k = 1:

a

b

What if min(ai) ≤ min(bi), max(ai) ≥ max(bi)?

What is ?

It is the sum of distances from a_k to all other a_i!

k = N:

a

b

What if min(ai) ≤ min(bi), max(ai) ≥ max(bi)?

What is ?

It is the sum of distances from a_k to all other a_i!

Add k = 1 and k = N: Hmmm… isn’t this just n(a_n - a₁)?

a

b

What if min(ai) ≤ min(bi), max(ai) ≥ max(bi)?

What is ?

It is the sum of distances from a_k to all other a_i!

Add k = 1 and k = N: Hmmm… isn’t this just n(a_n - a₁)?

a

b

What about ?

What if min(ai) ≤ min(bi), max(ai) ≥ max(bi)?

What is ?

It is the sum of distances from a_k to all other a_i!

Add k = 1 and k = N: Hmmm… isn’t this just n(a_n - a₁)?

a

b

What about ?

What if min(ai) ≤ min(bi), max(ai) ≥ max(bi)?

What is ?

It is the sum of distances from a_k to all other a_i!

Add k = 1 and k = N: Hmmm… isn’t this just n(a_n - a₁)?

a

b

What about ?

Hmmm…

This is also n(a_n - a₁)!

What if min(ai) ≤ min(bi), max(ai) ≥ max(bi)?

What is ?

It is the sum of distances from a_k to all other a_i!

Add k = 1 and k = N: Hmmm… isn’t this just n(a_n - a₁)?

What about ?

Hmmm…

This is also n(a_n - a₁)!

Since adding up k = 1 and k = N makes both sides equal, at least one of k = 1 and k = N is a solution!

The general case

What if the range of b is out of the range of a?

The general case

What if the range of b is out of the range of a?

a

b

The general case

What if the range of b is out of the range of a?

increases, but stays the same.

a

b

Observation 1

What if the range of b is out of the range of a?

increases, but stays the same.

​

Thus by adding k = 1 and k = N, we get LHS ≤ RHS.

So at least one of k = 1 and k = N is a solution!

Subtask 4: N ≤ 20 000, Q ≤ 10 000

Check min and max element of a in O(N) time for each answer, output the one which satisfies the inequality.

Time complexity: O(NQ)

Subtask 5: 1 ≤ a_i, b_i, v_i ≤ 200 000

This is for full solutions which did not use lazy node creation for segment trees.

Subtask 6: No additional constraints (Solution 1)

Combine solutions for subtask 3 and 4:

For each answer, check min and max element of a in O(log A) using a segment tree.

Time complexity: O((N+Q) log A) where A is the range of values of a and b.

Subtask 6: No additional constraints (Solution 2)

(did anyone actually read this…?)

​

​

​

But where is the magical solution???

Subtask 6: No additional constraints (Solution 2)

Instead of finding an a_k which satisfies the inequality, let’s try finding any integer x such that

Subtask 6: No additional constraints (Solution 2)

Instead of finding an a_k which satisfies the inequality, let’s try finding any integer x such that

a

b

x

Subtask 6: No additional constraints (Solution 2)

Instead of finding an a_k which satisfies the inequality, let’s try finding any integer x such that

a

b

x

x'

Subtask 6: No additional constraints (Solution 2)

Instead of finding an a_k which satisfies the inequality, let’s try finding any integer x such that

a

b

x

x'

x''

Subtask 6: No additional constraints (Solution 2)

Instead of finding an a_k which satisfies the inequality, let’s try finding any integer x such that

a

b

x

x'

x''

As x increases from max(a_i) to infinity, LHS increases at least as much as RHS

Observation 2

Instead of finding an a_k which satisfies the inequality, let’s try finding any integer x such that

As x increases from max(a_i) to infinity, LHS increases at least as much as RHS.

If x = infinity works, then x = max(a_i) also works. (Note: the converse is not true.)

Similarly, if x = -infinity works, then x = min(a_i) also works.

Furthermore, adding up both sides for x = infinity and x = -infinity, both sides are equal to 2n*infinity (you can do the math).

Therefore LHS ≤ RHS for at least one of x = infinity and x = -infinity.

Subtask 6: No additional constraints (Solution 2)

Now suppose x = -infinity works. Then means

​

(a₁+INF) + (a₂+INF) + … + (a_n+INF) ≤ (b₁+INF) + (b₂+INF) + … + (b_n+INF)

a₁ + a₂ + … + a_n ≤ b₁ + b₂ + … + b_n

​

Note that the converse is true as well.

Subtask 6: No additional constraints (Solution 2)

For each answer,

• If sum(a_i) ≤ sum(b_i), output the index of the min element of a.
• Otherwise, output the index of the max element of a.

​

Time complexity: O((N+Q) log N)

Removal Costs

Div 2C - shiwei

Not Abridged Statement

Observation 1a

For all positions that have a_i ≥ i, the minimum possible contribution to cost is a_i - i as doing the operations can only decrease i.

On the other hand, for all positions that have a_i < i, the minimum possible contribution to cost is 0 as we can do the operations to decrease i until a_i = i before doing an operation on i.

It is actually possible to achieve the minimum for both cases.

​

Observation 1b

Algorithm to achieve minimum:

1. Find the largest position i such that a_i ≥ i and do operation on it.
2. Update the positions of all elements after position i.
3. Go back to step 1 until array is empty.

Since we do the operation on the largest position with a_i ≥ i, we do not affect the cost of all other positions j with a_j ≥ j, and at the same time reducing the costs of all j > i since a_j < j. We only do operations on them the moment a_j = j due to step 1, hence this is the most optimal.

Observation 2

With observation 1a, we discover that each element is independent of the rest, hence we can consider the contribution of each element individually.

Full solution

Let x be the number of -1 and S be the set of elements not in the permutation yet.

For each position i, if a_i ≠ -1, then cost is max(a_i - i, 0) * x!

Otherwise, cost = Σ_{v ∈ S} max(v - i, 0) * (x - 1)!

To calculate the cost for the second case quickly, we can use sliding window to take note of which term of the max is used as i increases.

Reopening Shop

When you thought the opening shop plugs could not get worse

(thx errorgorn for q)

Abridged Statement

Nodes 1 to N form a tree, and you have node 0 connecting to each of them

When you select an edge (u,v) you will update

d[v] = min(d[v], d[u] + t_i) for some positive unknown t_i

Find a sequence of edges such that d[u] = shortest distance from 0 to u for all nodes u

Observation 0

Always take the roads going out from 0 first.

Your sequence should always start with

0 x_i�0 x_j�0 x_k�0 x_l�0 x_m

…

Subtask 1 (M <= 2)

You just dfs/bfs from the 2 points to the entire tree

​

Why does this work?

M = 1: DFS from 1 point

M = 2: DFS from first point, then second point (d[u] = min(d[first point dfs], d[second point dfs]

Subtask 2 (tree = line)

You just go along the line

1

2

3

4

5

6

7

0

Subtask 2 (tree = line)

And back

1

2

3

4

5

6

7

0

Subtask 2

Why does this work?

There are only at most 3 cases for a node (5 in prev example)

Either from left, right or 0

0 alr considered (Observation 0)

From 4 is the first pass (min path to 4 from left)

From 6 is the reverse pass (min path to 6 from right)

4

5

6

0

Subtask 3 (Full Solution)

Here is a 🌳🌳tree🌳🌳

​

​

​

​

​

​

From observation 0, you see that we can just ignore 0

1

2

3

4

5

6

7

Subtask 3 (Full Solution)

A shortest path only has 3 cases

1

2

3

4

5

6

7

Subtask 3 (Full Solution)

Up the Tree

​

This is simple, just dfs�Go from cur to par in post-order

​

Why not pre-order?

Then the path 5-2-1 breaks at 2 (as 1 updated before 2)

1

2

3

4

5

6

7

Subtask 3 (Full Solution)

Down the Tree

​

Also simple, just dfs�Go from cur to child in pre-order

​

Why not post-order?

Then the path 1-2-5 breaks at 2 (as 5 updated before 2)

1

2

3

4

5

6

7

Subtask 3 (Full Solution)

Up then down a tree

​

If we used the up the tree case then down the tree�It would work!

​

�

This is because after handling up the tree�d[1] = min(path from parent, path from child, 0 to 1)�And then going down the tree will just update d[4] according to min dist of 1

1

2

3

4

5

6

7

Subtask 3 (Full Solution)

2 DFS solves problem, yay

Time complexity O(V + E)�Wow so fast!!!!

​

​

​

​

(Note that you can arbitrarily root the tree)

1

2

3

4

5

6

7

Valves

A valve is a device or natural object that regulates, directs or controls the flow of a fluid (gases, liquids, fluidized solids, or slurries) by opening, closing, or partially obstructing various passageways. -Wikipedia

Abridged Statement

Range Add Range Sum but support “valves” and these two additional queries.

Initially, the only open valve is at infinity (implicitly)

Open i h: Insert h into the open valves of i

Close i h: Erase h into the open valves of i

Let x_i be the lowest open valve of i. Then, after each operation, sweep from 1 to N-1 (tower N will not overflow),

If val[i]>x_i, val[i+1]+=val[i]-x_i, val[i]=x_i.

Observation 0:

Only the lowest open valve matters

Maintain a set for all open valves for all towers

Remember this for all the future solutions

​

​

Subtask 2: Queries will only be on tower 1

Only care about operations if they involve 1

Maintain a set of the open valves for tower 1 only

When pour, answer = max(answer+X, open)

When open and close, update set accordingly

answer=min(answer, lowest_open)

When query, just output answer

​

​

Subtask 3: No valve operations

Literally Range Add Range Sum Segtree lol

Subtask 4: N,Q <= 3000

Just simulate

Keep a counter of overflow

Maintain a set of all open valves, when pour just check accordingly.

If open a lower valve, rmbr to overflow into next valve

Query just add them up

O(NQ)

​

​

Subtask 5: N,Q <= 100 000

Intended for SQRT solutions

But the SQRT solution uses similar tricks to full solution.

Tricks explained later

Subtask 6: Point Update Point Sum

Actually, the brute force solution passes this subtask 🤡

Might have accidentally gotten this subtask

Notice that we can only overflow at most Q times

So amortised O(Q) overflows

Time complexity O(Qlog(Q))

​

​

Subtask 7: Point Update Range Query

Maintain 2 segtrees, 1 is for the lowest open valves

In the other valve, store height-valve, call this segtree deficit.

When pour at L, check if it overflows.

If it does, do a binary search to find the last position it will fill.

Range set all between the L to last pos filled to 0. Then update the non-overflow thing appropriately

​

​

Subtask 7: Point Update Range Query

On open/close, check if it affects the lowest valve, then update accordingly

When query, take Valves(L,R)-Deficit(L,R) and take the mod.

Remember not to mod until right before outputting the answer. If take mod, then deficit will be inaccurate and cannot be updated correctly

Anyway, total amt of water is 1e5*1e8=1e13, so it will definitely not overflow

​

​

Subtask 8: Range Update Point Query

The main issue here is: “How can we handle many overflow fast?”

If we simply check all the overflow, it will be too slow.

We need a faster idea.

Observation 1:

Water can only go from underflow to overflow Q times.

Make use of that amortisation

You may want to keep an array that keeps track of whether the tower will overflow

​

Observation 2:

Consider towers 1,2,3,4 are filled and tower 5 is not. Then when we pour 1-5 with 4, we are really adding 20m to tower 5.

But what if tower 3 is unfilled? Then we pour 12m into tower 3 and 8m into tower 5.

So, we realise that when something overflows, we can just dump it into the next guy that is not overflowing.

Then when we add, we can add length of segment* amount.

But how do we add unequal segment lengths?

Magic: we store deficit as deficit/length instead.

Observation 2:

Assuming we cover the whole length of segment

Added value is just (length of segment)*amt.

We can keep track of the length of segment with a map.

We invert deficit to now store valve-height.

To detect when we overflow, we store it inside a RMQ segtree, when the largest value is >=0, then it means something has overflowed

Now, we store (valve-height)/length instead, inside a RMQ segtree

When we range add, we just add it to this new value.

Subtask 8: Range Update Point Query

Pour L R X:

Find the first point where length is not 0 for both L and R. Then update the whole range by adding X.

Of course, it might not cover the whole range.

So compensate by “refunding” the segments they do not cover.

When refunding, remember that it is refunding val/len and not val itself

​

Subtask 8: Range Update Point Query

Open i h:

If it is not the new lowest, can just push into set and ignore.

Else, update the valve height and the deficit accordingly

​

​

Subtask 8: Range Update Point Query

Closing is similar,

If it is not the lowest, just ignore

If it is, update lowest valve and deficit accordingly

​

​

Subtask 8: Range Update Point Query

Query:

Find the valve height + deficit*length (to reverse what we divided by) then output it

If it is overflowing as indicated by array, just output valve height.

​

​

​

Subtask 8: Range Add Point Sum

After every operation, we check if the largest value in the RMQ >=0. If it is, then it means we have overflowed. Find the next point where it has not overflowed, and pour it into there, by adding (overflow/length)

Then, set the value to -inf, to ensure it never becomes positive again, and set length=1.

​

​

Implementation Detail

Doubles are able to pass this question, but there is an implementation with fractions (which is the model code)

Remember to take mod only on the valve segtree.

Check maomao90 submissions to valves should be one of them

Subtask 9: No closing operations

Idk lmao

It’s mostly a debugging subtask

​

​

A Subproblem

Consider a subproblem

You have arrays A and B, support the following operations:

Add L R X => A[i]+=B[i]*X for all L<= i <= R

Update X V => B[X]= V

Query L R => find the sum of all A[i] for L<=i<=R

​

A Subproblem

Store two segment trees, for A and B.

When add, do the lazy flag same as normal segment tree.

When adding to A, add B->query(s,e)*flag instead;

When updating a value of B, remember to first push down all updates on A containing the value, so that we do not mess things up.

Query remains similar.

Subtask 10: Full Solution

How does this help us with the full solution?

In subtask 8, we could only come up with query at a point as we could not do sum on fractions.

In subtask 7, we could only update at a point as we could not do addition on the various lengths.

How about we combine them?

Subtask 10: Full Solution

Store 4 segtrees.

Valves segtree: Keeps track of the lowest open valve for all 1 to N, and can take sum easily.

RMQ segtree: Same as subtask 8, store it as deficit/length

Length segtree: In a similar idea to our subproblem, we store the lengths of the “pouring segment”. This is our array B from the subproblem.

Sum segtree: This is our array A from the subproblem, here we store actual deficit

Then, for the four operations, do these actions accordingly

Subtask 10: Full Solution

Initially, set all valves to be at inf, all values in sum segtree to be -inf (%mod), RMQ segtree to be -inf, len=1, and length segtree to be all 1

Also, set inf to be 3e18, as it is a value we will never attain.

At worst, open half, pour half = Q/2*Q/2*X=2.5x10^17

Subtask 10: Full Solution

Pour L R X: Update RMQ segtree with X and sum segtree with X.

Open i h: Update the set, and check if it is new lowest. If it is, update accordingly

Close i h: Update the set, and check if the closed one was the lowest. If it was, update accordingly

Query L R: Do valves(L,R)-actual deficit(L,R)

​

Subtask 10: Full Solution

Then, after every operation, we do the following

Query RMQ segtree to see if highest value >=0.

If it is, we join it to the next available non-overflow (which can be kept track of using a map), pouring the overflow into the next one.

Update the value in Length Segtree (remember to propo all updates on sum segtree first)

And update the length in the RMQ segtree to reflect the length changes.

Implementation Detail

You may have noticed that the values are really large. Actually, we only need to take mod on the valves segtree and the sum segtree. If we mod the other two, it will be incorrect. (you cannot mod RMQ)

Subtask 10: Full Solution

Since there can only be at most Q overflows, we will only do it Q times, each time taking log(N) time.

Each operation is on a segment tree/set, so takes at most log(N+Q) time ( or logQ if you do some lazy tricks)

In total, time complexity is O((N+Q)log(N+Q))

Subtask 10: Full Solution

Actually you can combine the RMQ and Sum segtree into 1.

Author AC Code is about 250 lines long.

Contact __sheep on discord (if you have handle) for any queries/clarification/help/request for code/feedback

Subtask 10: Summary

4 segtrees

​

valves segtree, just normal purq segtree

​

length segtree, just normal purq segtree

(before update point X, call sumSegtree->query(X,X) to propo all)

​

​

​

​

​

​

​

Subtask 10: Summary

sumSegtree:

addLength: set flag to be X

addPoint: propo down to point, every node that it crosses add X

propo function: val+=length->query(s,e)

query normally

​

​

Subtask 10: Summary

rmqSegtree:

store: deficit as (valve-height)/length

addEntireRange: deficit+=X

addPoint: deficit-=X/length

changing the length: deficit*length/newlength

set to zero: length=0, deficit=-inf

(rmbr to check if length=0 to avoid div by 0 lmao)

​

Subtask 10: Summary

pour:

sumSegtree->upd(L,R,X)

rmqSegtree->upd(L,R,X)

​

open:

add to set, if it is new lowest,

sumSegtree->updPoint(i,old-new)

rmqSegtree->addPoint(i,old-new)

​

Subtask 10: Summary

close

remove from set, if it was the lowest, (we break up the segments)

sumSegtree->updPoint(i,old-new)

rmqSegtree->addPoint(i,old-new)

sumSegtree->querySum(i)

sumSegtree->querySum(tail) (tail refers to ending point of segment)

(this is to propagate the length stuff)

length->upd(i,new length)

length->upd(tail,new length)

change length on rmq segtree

Subtask 10: Summary

query

valves->query(L,R)+sumSegtree->query(L,R)

​

then after each operation:

while true, check if RMQ segtree return is >=0; if no, break, else it means overflowed.

calculate overflow by deficit*length.

find next non-overflow and throw it there by updating:

sumSegtree->addPoint(next,next,overflow)

rmqSegtree->addPoint(next,next,overflow)

rmqSegtree->changeLength(currLen+len of overflowed segment)

rmqSegtree->setZero(overflowed segment)

upd their respective lengths in the length segtree

Now go upsolve :)

Hungry Rabbits 3

The Rabbits are hungry again

Abridged Statement

There are n piles of carrots in a row. The i-th such pile has c_i carrots.

​

Every minute, a rabbit can be placed at either pile 1 or pile n. Rabbits starting from pile 1 move right every minute, while those from pile n move left every minute.

​

Every rabbit eats a carrot from the current pile before moving.

​

Determine the maximum minimum amount of time that can pass before all carrots are eaten.

Subtask 2: n = 1

yea.

Observation 1

If we finish at time T, any rabbit that was released earlier than T - n will have gone over every single pile no matter where it started.

Subtask 3: n ≤ 15

We can brute force all 2ⁿ possible ways to place the last n rabbits.

​

Then, we compute find the largest pile left and that will be the number of additional rabbits needed.

​

Note that we need to handle the case of t ≤ n separately, but that doesn’t affect the final time complexity of O(n 2ⁿ).

​

Observation 2

If we can finish at time T, we can finish at a time T’ > T

​

Similarly, if we cannot finish at time T, we cannot finish at time T’ < T

​

Thus, we can binary search the answer.

Subtask 4: n ≤ 1000

We BSTA on the time we need T. We now want to clear all piles by time T.

​

We subtract max(0, T-n+1) carrots from each pile to account for the rabbits that will clear all piles. Our goal is to make every pile 0.

​

Let us look at the last n-1 rabbits. The i-th last rabbit to be placed will cover exactly i piles from the side they come from. From now on this is rabbit i.

Subtask 4: n ≤ 1000

For every rabbit i > n/2, they will always cover some middle section.

Subtask 4: n ≤ 1000

Thus, we can treat each such range as a range smaller than n/2 and subtracting one from the sections that will be covered regardless of which direction it comes from.

Subtask 4: n ≤ 1000

Now for each range we can either let it start from the left or right and it will subtract 1 from a prefix/suffix

Subtask 4: n ≤ 1000

We can “shorten” a range as needed.

Subtask 4: n ≤ 1000

We process from the middle outwards. In each step, we attempt to clear the piles on both sides that we are processing.

Subtask 4: n ≤ 1000

We also maintain a counter storing the number of ranges we can use to subtract 1.

Subtask 4: n ≤ 1000

If we have values > 0, we must use ranges to remove them until they are 0.

Subtask 4: n ≤ 1000

We have at most n ranges. Each range subtracts from at most n piles.

​

Time complexity is O(n² log 10⁹)

Subtask 5: n ≤ 100000

Use a fenwick. Time complexity O(n log n log 10⁹)

Subtask 6: n ≤ 1000000

Don’t use a fenwick.

​

Use a cumulative sum of the number of ranges used on each side so far.

​

Time complexity O(n log 10⁹)

Subtask 6: n ≤ 1000000 but fast

If the maximum size of a pile is K, we use at least K minutes and at most K - n + 1 minutes.

​

Time complexity O(n log n)

Subtask 6: n ≤ 1000000

The intended solution is an inequality bash. Won’t be presented because it would take too long to explain.

​

​