STREETTA - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Tuan Anh Tran Dang
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Segment Tree

PROBLEM:

Maintain 2 arrays, A[1…N], B[1…N], supporting 3 types of operations:

  1. A[i] = min{A[i], (i - l) * a + b}
  2. B[i] += (i - l) * a + b
  3. print A[i] + B[i]

There are Q operations in total.

EXPLANATION:

Because the only output is A[i] + B[i], and there are no “crossing” operations, we can treat A[] and B[] separately.

For B[] side, it is much easier. First, we can re-write the formula to

B[i] += i * a + l * a + b

, which is also equivalent to

B[i] += i * a' + b'

And, it is worth noting that,

(i * a + b) + (i * c + d) = i * (a + c) + (b + d)

Therefore, we can maintain a segment tree whose node records the interval adds. That is, for each node, which represents interval [l…r], we record the sum of a and b, which are added to the whole interval. And when querying B[i], we can sum up all sum of node on the path from root [1, N] to the leaf [i, i].

All operations related to B[] can be done in O(logN) time.

For A[] side, the idea a little tricky, but I think it is also easy to follow. For each node, which represents interval [l…r], we record a pair of a and b, which means for all i (l <= i <= r), A[i] should be smaller than i * a + b. When a new pair a’, b’ comes, because the two curves are linear, there should be at most one intersection. This is a very important and beautiful fact – it implies that, there are 2 cases:

  1. a’, b’ are totally better or totally worse than a, b. That is, for all i (l <= i <= r), a * i + b <= a’ * i + b’, or for all i (l <= i <= r), a * i + b >= a’ * i + b’.
  2. In at least one of [l, m] and [m + 1, r], the situation will fall in the Case 1.

Therefore, we can recursively update the children, if we are in the Case 2. For the query, we can get the minimum of the nodes on the path from root [1, N] to the leaf [i, i]. And the time complexity is O(logN) too.

Due to the large scale of N, we can not build the whole segment tree. But we can create the nodes, which are related to the queries. With this idea in mind, we can implement a solution using only O(QlogN) memory. Because, for each operation, only O(logN) nodes are related.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

4 Likes
2

I did something a bit different for changes of type 1. I did an offline solution and first found the upper envelope of the set of line segments. I did this by a very simple divide and conquer which was just splitting the lines into two sets, finding the upper envelopes recursively, then merging them. I kept track of all the partial recursive calls as well, so whenever I do queries, I can look at the upper envelope formed by a prefix of all the segments.

3

@shang jingbo i just want to ask you why some people took so much memory i do that in only 3.4 MB.i really want to know their approach.I used a simple line intersection approach to handle type 1 queries and azy propagation to handle type2 queries

4

Author’s Solution is giving TLE !!!

5

My solution:

Queries of type 2 are trivial. Let’s focus only on queries of type 1, and only on points on the line that actually appear in queries of type 3. Let there be N queries of type 3 and M of type 1.

Split the M queries into batches of about sqrt(M) of them. Let’s process queries of types 1 and 2 in the order in which they appear on the input. We’ll maintain an array Q, in which we’ll store the last K (around sqrt(M)) queries of type 1, and another array A, in which we’ll store the answers from any queries that came before that.

When answering a query of type 3, take the maximum of the “old” answer from array A and all the queries in Q. It takes O(K) time per query.

Add queries of type 1 into Q. When size(Q) >= K, “clean” the queries - convert it to answers in array A, and empty Q. There’ll be just around sqrt(M) cleans, so we need to figure out how to do each one of them fast enough.

Traverse all the points from queries of type 3 in increasing order; if we sort Q, we can use an additional pointer to remember the queries covering any current point. Let’s say we’re at point x and have some queries (array QC) covering that point. Take the query q which gives the maximum answer at point x. For all queries in QC other than q, find the smallest point y (can be inf, e.g. 10^9) at which any of these queries gives a value >= than q. Now, we can just iterate over x further until we get to y or add/remove a query from QC; we know that q must give the maximum value.

If we pick K around sqrt(M), this obviously has a complexity of at least O((N+M)sqrt(M)). Possibly worse, but that’s not important - it works! It’s not even among the slowest solutions!

This is the problem of long contests: they’re long enough for one to make a slow program and optimize it to squeeze into the time limit. This took me around a full day of work - useless in a shorter timed contest, but working well here :smiley:

2 Likes
6

I tried a similar tweak with segment trees to get ACed as the slowest solution. But during the rejudge it exceeded time limit, so I was forced to change my approach. Now I think I could have tweaked some more. :stuck_out_tongue:

7

There’s a good strategy when submitting slow solutions (or those that could have a special slow worst-case): wait for long enough. Chances are good that your worst-case could go unnoticed by the author (if it’s special enough), and since you submit late, it’s hard to do a rejudge. If you submit late enough, that is.

3 Likes
8

Thank deepanshum007 for pointing that out! The editorialist should have used wrong version of my solution.
The updated one can be found here:
http://www.codechef.com/viewsolution/3626407

9

You mean: must’ve used :smiley:

2 Likes