December Course 2024
Contest Analysis: DS III
Apology
Sorry
Other editor note: we are not sorry
Scoreboard
shamelessad4
mfw q1 isn’t trivial
Abridged Statement
Given an array (of positive integers), support the following operations:
Subtask 1: Only output sum of range
This is quite literally just static range sum query.
If you can’t solve this, you shouldn’t be in advanced.
(Sorry for being harsh)
Use prefix sums to AC.
Remember to mod!
Subtask 2: Point multiply update, range sum query only
Use your preferred DS 2 technique to update a point to its new value, then take the range sum as per normal.
If you wish to use fenwick tree without modifying too much, you can use sum(L, L) to get the value at a point, then update by adding (K-1) * L.
Remember to mod!
Subtask 3: Range mult upd, range sum query only
We do lazy propagation.
We only need to maintain the sum of each node’s range.
When we apply a range multiply by k, the sum is also multiplied by k.
As for stacking, if we range multiply by X, then by Y, we get a range multiply of (X * Y).
Subtask 3: Range mult upd, range sum query only
if (s != e && lazy != 1){
l->sum *= lazy;
r->sum *= lazy;
l->lazy *= lazy;
r->lazy *= lazy;
lazy = 1;
} //anything missing?
Subtask 3: Range mult upd, range sum query only
if (s != e && lazy != 1){
l->sum *= lazy; l->sum %= MOD;
r->sum *= lazy; r->sum %= MOD;
l->lazy *= lazy; l->lazy %= MOD;
r->lazy *= lazy; r->lazy %= MOD;
lazy = 1;
} //lol don’t forget to modulo
Subtask 4: Point mult update, range sum query, range product query
Point update. We just maintain a DS II segment tree with two values instead, a sum and a product.
product = (l->product * r->product)%MOD;
sum = (l->sum + r->sum)%MOD;
Subtask 5: Everything all at once (sorry, tho it’s only 10 pts)
The main issue is this is your propagation function.
How do you predict how the product will change when you multiply all values by K?
Subtask 5: Everything all at once (sorry, tho it’s only 10 pts)
Consider a range with elements {1, 3, 7}.
Initially, product is 21.
What happens if we multiply throughout by 2?�{2, 6, 14}
Product is 168.
168 = 8 * 21 = (2^3) * 21
!!!
Subtask 5: Everything all at once (sorry, tho it’s only 10 pts)
General formula:�Multiplying all values by K on a range of length L results in this:�product *= (K ^ L);
We can’t naively calculate this, as it would be too slow!
Subtask 5: Everything all at once (sorry, tho it’s only 10 pts)
We apply binary/fast exponentiation to solve the problem.
Each propagate function call now takes O(logN) time, so the whole segment tree slows down to O(log^2 N) for each query/update.
cokemoresugar
mfw q2 isn’t trivial either
Abridged Statement:
You have two arrays F and S of length N.
Support the following operations:
Subtask 1: No updates to F and S
This is another version of static range sum queries�:clown:
Just construct an array A where Ai = (Fi * Si).
Then all queries can be answered by prefix sum on A.
Subtask 2: All updates are point updates
Use a standard segment tree, with a value sumProduct where:
sumProduct = l->sumProduct + r->sumProduct
We also maintain global arrays F and S.
When we get to a leaf node, we can just calculate its value by multiplying F and S together at that leaf node’s position after updating the arrays.
Subtask 3: Only point queries
This subtask is a little troll.�We just need to maintain F and S, because we can answer all queries just using that array.
To maintain F and S, instead of using arrays, we can use a Range Update Point Query Fenwick/Segment tree to solve.
Subtask 4: Anything goes
The issue is once again how we store values and propagate.
If we want to maintain sumProduct, we need to know how it affects sumProduct when we do an update.
Subtask 4: Anything goes
Initially, sumProduct = F1 * S1 + F2 * S2 + F3 * S3
If we add 5 to all F, in the range [1, 3]
sumProduct = (F1+5)*S1 + (F2+5)*S2 + (F3+5)*S3
= F1*S1 + 5*S1 + F2*S2 + 5*S2 + F3*S3 + 5*S3
= F1*S1 + F2*S2 + F3*S3 + 5*(S1 + S2 + S3)
= initial sumProduct + 5 * sum of S
Subtask 4: Anything goes
In general, if we update a node by adding K to F,
its sumProduct increases by K * (sum of S).
Using the same idea, we can get that
if we update a node by adding K to S,
its sumProduct increases by K * (sum of F).
Subtask 4: Anything goes
How to get sum of S and sum of F?�We maintain it as other values in the segment tree node!
Sum of S and sum of F are not difficult to maintain when updates occur.
Now we know how to maintain sumProduct, sumS,
and sumF!
Subtask 4: Anything goes
So how does stacking and lazy propagation work?
We store lazy as a pair of {changeF, changeS}.
Let’s consider how this stacks.
Compare the following:�Change F, then change S
Change S, then change F
There’s no difference in the final result!
Subtask 4: Anything goes
Stacking can then just be done independently for each
F and S. When propagating, we just do lazy.first and
lazy.second separately, and the answer will work out.
gohcart2
progression_easy
Abridged Statement
You have an array of booleans.
Support the following queries:
Subtask 1: Flip whole array, query whole array
Truly one of the problems of all time
Note that there are only two possible states of the array, one before flipping and one after flipping.
Hence, we can just compute the longest subarray of 1s of both possible arrays in O(n) time to solve the problem.
(Just iterate through lol)
Side Note: Contest Strategy in NOI
It’s 3 points, do you still grab it?
ABSOLUTELY YES!! You will not know medal cutoff.
Subtask 2: Point query
Truly one of the problems of all time
Query boils down to checking if that point is 0 or 1
�We can just maintain a Range Update Point Query Fenwick tree. A range update is add 1 to range. Then the value is 1 at a point if the value at that point is odd, 0 otherwise.
Subtask 2: Point query
Truly one of the problems of all time
Query boils down to checking if that point is 0 or 1
�We can just maintain a Range Update Point Query Fenwick tree. A range update is add 1 to range. Then the value is 1 at a point if the value at that point is odd, 0 otherwise.
Subtask 3: No updates
We consider a segment tree’s node values.
In order to maintain max num of 1s (mx1), we need the following:
mx1 = max( { l->mx1, r->mx1, l->suffix1 + r->prefix1 } );
prefix1 is the longest prefix of 1s
suffix1 is the longest suffix of 1s
Subtask 3: No updates
mx1 = max( { l->mx1, r->mx1, l->suffix1 + r->prefix1 } );
The l->mx1 and r->mx1 is obvious
However, a new better subarray may be created by crossing between l and r
L R
[0, 1, 1, 1, 0, 1, 1] [1, 1, 0, 0, 1, 1, 1]
l->mx1 = 3 r->mx1 = 3
Subtask 3: No updates
Now that means we need to maintain longest prefix and suffix of 1s!
Notice that the longest prefix is almost always equal to the left segment’s longest prefix.
[1, 1, 0, 0, 1, 0] [1, 1, 0, 1, 0, 0]
However, there is one case where this is untrue.
When the entire left segment is 1!
Subtask 3: No updates
[1, 1, 1, 1, 1, 1] [1, 1, 0, 1, 0, 0]
In this case, the longest prefix of 1s is
l->prefix + r->prefix
(equivalent to l->size + r->prefix)
Subtask 3: No updates
Do the same for the suffix case.
Now, we can maintain the solution yay
Subtask 4: Full solution
nearly done
Now, to maintain the number of consecutive 1s after a flip, notice that this number is equivalent to the number of consecutive 0s before the flip.
In other words,
swap(pref1, pref0)
swap(suff1, suff0)
swap(mx1, mx0)
Subtask 4: Full solution
Ok now we just maintain everything and we win yay
morexiaoyang
btw, xiaoyang did approve to use his name
Abridged Statement
There are N points on a huge grid.
Pick a point, such that when a vertical line and horizontal line passes through it, it splits the points into 4 quadrants.
Your score is the minimum of num of points in each quadrant.
Maximise score. (and find the point that does so)
Subtask 1: N <= 500
We only care about x-values and y-values that exist at some point within the N points. (Line sweep idea)
This is because as we change X for example, if we do not pass over a point’s x-coordinate, our answer remains the same.
Subtask 1: N <= 500
Hence, we generate all possible X and Y coordinates, bruteforce all pairs of them, and check in O(N).
Subtask 2: N <= 2000
Very cringe
Discretise, then do 2D prefix sum or fenwick tree or something lah
Just optimise your checking to O(1).
Subtask 3: Xi is 0 or 1
Notice that if we choose X == 0, the left two quadrants always get 0.�Hence, our X must be 1.
We try every Y, then check minimum quadrant sum using prefix sums.
Subtask 4: n <= 4*10^4
Subtask 5: 0 <= Xi, Yi <= 10^6
Subtask 6: t = 1
Subtask 7: No additional constraints
Waw
Everything
Firstly, we discretise to make our constant time much better.
Then, we binary search the answer.
Then, we line sweep.
Everything
Given a guess G, we first iterate through all possible X values.
Then, we determine if it is possible to find a Y-value such that we get at least G in each quadrant.
The bottom-left and bottom-right both have a minimum Y-value such that they are fulfilled.
The top-left and top-right both have a maximum Y-value such that they are fulfilled.
Everything
The bottom-left and bottom-right both have a minimum Y-value such that they are fulfilled.
The top-left and top-right both have a maximum Y-value such that they are fulfilled.
Anything higher than the minimum and lower than the maximum will pass.
Hence, we just need to find the minimum and maximum to determine if a valid Y exists for this X.
Everything
BSTA on segment tree/fenwick tree!�Determine the minimum index Y1 such that pref[Y] >= G for both bottom-left and bottom-right.
Then, determine the maximum index Y2 such that suff[Y] >= G for both top-left and top-right.
It is only possible if Y1 < Y2.
Everything
Subtask 4 is for O(N log^3 N) solutions
Subtask 5 is for solutions that fail to discretize.
Subtask 6 is for solutions that fail to handle multitest.
fakeidol
google it
Abridged Statement
You have a permutation A. Support swap updates.
After each swap, construct an array B such that:
Output the maximum number of distinct elements in an optimal construction. (you don’t have to output the construction.)
I have no idea how to do any of the subtasks.
Observation (ie magic): The answer is the number of prefixes that contain all numbers from 1 to the size of the prefix
Proof: the only possible time you can increase a score is when everyone before you has a smaller value than everyone after this point.
I have no idea how to do any of the subtasks.
Observation 2: A sufficient condition to check whether a prefix is a valid permutation of consecutive numbers is whether sum(prefix) = i*(i+1)/2, where i is the length of the prefix.
Observation 3: All numbers are positive and distinct. Hence sum(prefix) >= i*(i+1)/2 ie sum(prefix) - i*(i+1)/2 >= 0
I have no idea how to do any of the subtasks.
Hence we store a segment tree where tree[i] = -i*(i+1)/2 + prefix sum of A up to i
This can be done using range updates in O(log N)
Query is the number of 0s in the leaves of the segment tree, which is the number of minimums in the segtree.
I have no idea how to do any of the subtasks.
Swap updates is just updating the prefix sum array, can be done with range updates.
Alternate Solution (With subtask sols)
You still need the first observation: That the answer is the number of prefixes i where the set
{A[1], A[2], …, A[i]} = {1, 2, …, i}
This observation can be motivated by seeing that if u occurs before v, and u>v then u and v have to be the same value. This is just a natural result of that.
Alternate Solution (ST 1 & 2)
Brute force O(NQ) will pass the first 2 subtasks.
Alternate Solution
We need to find a fast way to check our condition:
{A[1], A[2], …, A[i]} = {1, 2, …, i}
One way to approach this would be to count the number of values in A[1] to A[i] that are not in the range [1, i].
Alternate Solution
One way to approach this would be to count the number of values in A[1] to A[i] that are not in the range [1, i] in segtree[i].
It turns out that this is relatively easy to maintain, you only really need to support range adds (left as exercise to reader). The problem becomes counting the number of 0s in the segment tree.
Alternate Solution
Counting the number of occurrences of a certain element in a segment tree is not a easy problem.
It turns out that you can calculate this quickly because 0 is the smallest number in the segment tree. But what if you didn’t notice this?
Alternate Solution (ST 5, adj swaps)
Swaps are all adjacent
If you think about what is stored in your segment tree, you can see that this means at most 2 values in your segment tree change after every update.
So the number of 0s can be maintained quite easily here.
Alternate Solution (ST3, N, Q 105)
We want to count the number of occurrences of a number in a segment tree, and we need to support range add updates.
This is solvable with Square Root Decomposition, namely buckets. (You should probably read the slides in extra lecture first)
Alternate Solution (ST3, N, Q 105)
Build sqrt(N) buckets, each of size sqrt(N), call this B.
The ith bucket corresponds to the range [(i-1)*B, i*B], and will store the number of occurrences of each value from 0 to N in the elements of the list with those indices.
Alternate Solution (ST3, N, Q 105)
When an update covers an entire bucket, you can just store the “offset” in O(1), so you don’t need to manually update the occurrence array(which would take O(sqrtN) time per bucket).
This is similar to what you do for https://codebreaker.xyz/problem/cups
When you query that bucket just remember about the offset.
Alternate Solution (ST3, N, Q 105)
The number of fully covered buckets is at most sqrtN, so we did updates on fully covered buckets in O(sqrtN)
If an update only covers part of a bucket, just rebuild the bucket. This takes O(sqrtN) time and occurs at most 2 times per update.
Alternate Solution (ST3, N, Q 105)
Time complexity O((N+Q)sqrtN)
Full solution
Same as in the other solution.
Store the min, and the number of occurrences of the min.