FNCS - Editorial

data-structure
fenwick
medium-hard
nov14
segment-tree
sqrt-decomp

#1

PROBLEM LINK:

Author: Devendra Agarwal

Tester: Sergey Kulik

Editorialist: Florin Chirica

DIFFICULTY:

medium-hard

PREREQUISITES:

sqrt decompositions, Fenwick Trees (or Interval Trees).

PROBLEM:

You’re given an array, which can modify in time. You’re given some functions which return sum of some contiguous subsequence (subarray). Answer queries, which ask sum of a contiguous subsequence of functions.

QUICK EXPLANATION (thanks to Sunny Aggarwal):

In the begining, we can find the value of every function and thus we can easily find the sum of functions of every chunk in the beginning easily. Now we need to take care for updating.
For updating, we need in O(1) time for each chunk that how many time x comes in summation of the functions in that chunk. We can precompute this factor in O(N*sqrt(N)) space and time.

Thus, we can update this structure in O(sqrt(N)) by traversing through all the chunks and applying +(yfactor)-(prevfactor) at every chunk.

We will quickly travel between 2 points which has full chunks. Only thing to worry is with partial chunks. We can use BIT’s to achieve this in O( sqrt(N)*log(N) ).

EXPLANATION:

Complexity of the official solution

This looks like a weird start, isn’t it? Well, actually the idea is that you might try to find a complexity better than needed. Our solution uses O(log(n) * sqrt(n)) per update and O(sqrt(n)) per query. If you’re trying to find a better complexity, this might be a hint to look for this complexity, as it passes the systests. If you have a solution with better complexity, please share it with us in the comments!

Smart brute force

A brute force solution would be at following: do an update in O(1) and query by iterating over all functions from m to n and for each function iterate all elements from L to R. This gives a running time of O(n ^ 2) per query worst case… not good.

An optimization might be pretty obvious for those who know Segment Tree / Fenwick Tree. We keep iterating all functions from m to n. But, for a function i, we can avoid calculating it in O(n) worst case. A function f(i) asks you for a sum of a range. Also, updates change a single element. Both Fenwick Trees and Segment Trees allow changing an element and asking for a sum in O(log(n)) time. So, for an update, using this technique, we can get O(log(n)) time and for a query we can get O(n * log(n))… still not good enough.

No updates version

Suppose we have no updates - then we can precalculate some information. In this way, a query can be answered faster. A well know trick is used: sqrt decomposition. If you don’t know it, please read it from here.
We keep L “buckets” of length L (L = sqrt(n)). First bucket will contain sum of 1st, 2nd, …, Lth functions. Second bucket will contain sum of (L+1)th, (L+2)th, …, (2*L)th functions and so on. As showed in the link, when we’re given a query, we can iterate over “full blocks”. These values are already calculated. Also, there can be at most 2 “incomplete blocks”. For functions in incomplete blocks, but which are in query range, we need to calculate the values of the functions using the Fenwick tree. This way we get O(log(n)) per update and O(log(n) * sqrt(n)) per query.

Full version

What happens when a position gets a new value? Firstly, we need to update Fenwick tree (or Segment tree). This will help for having the correct values when iterating elements in incomplete blocks. Suppose previous value was prev and my new value is val. We need to iterate each “complete” bucket. Suppose for a bucket we know how many functions from it contain position pos. Formally, we need to count functions f(i) from a bucket such as L* <= pos <= R*. For all those functions, we’ll have to erase prev and add val. Let’s denote number of functions from bucket which contain position pos by x. Then, it can be showed that bucket’s value is modified by adding x * (val - prev) (for each function which contains position pos, we remove prev and add val, in total whole bucket modifies by x * (val - prev) ).

It remains a single detail to handle: we need to know, for each position and for each bucket, how many functions from that bucket contain that position (value x from above). Let’s define matrix x[bucket][pos] = how many functions from the bucket contain position pos. How to do this in a reasonable time?

Let’s iterate over all buckets. Suppose we’re solving now bucket B. It will contain some functions which say: f(x0, y0) = all positions between x0 and y0 appear one more time in the bucket B. So, we need to increase x**[x0], x**[x0 + 1], …, x**[y0 - 1], x**[y0] by 1. If the increase is done in O(1) time plus O(n) at final, complexity becomes O(n * sqrt(n)). How do to this?

The problem reduced to: given M queries of form (x0, y0), increase all elements from all positions from x0 to y0 by 1. The solution is well known. We keep two arrays: A and B. When you get an operation x0, y0, you do:

A[x0] += 1;
A[y0 + 1] -= 1;

Then, you do B* = A[0] + A 1 + … + A* = A* + B[i - 1].

The correct answers will be in array B. We leave as an exercise to proof why this works.

This problem allows multiple solutions. If you have alternative solutions, please share them with us in the comment section!

AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon
To be updated soon


#2

I wrote a solution which takes O(n) time to update and O(1) time to query but it was giving TLE for the last 2 subtasks. Can anyone help me understand why it was giving TLE?


#3

I am getting forbidden error when I try to see setters solution. Looks like I am missing something


#4

The message “Access Denied” is displayed to me when I try to view the Author and Tester’s solutions linked. Please fix?


#5

nishantkumars …linear time complexity is too much for update operation…u need to reduce the complexity…


#6

I’m wondering is there someone who user the limitation in subtask 2 where R - L <= 10?

It would help me if n - m <= 100 for example, but I had no idea how to use the one mentioned above…


#7

I can solve it with complexity O(sqrt(max(N,Q))) per query and O(sqrt(max(N,Q))) per update.

We split all the operations we must perform in sqrt(Q) groups. We solve each group separately. Before starting with the current group we go through all update queries which happened before the group and update the array (in reality - just the updates in the previous group; others have already been counted). Then we extract all numbers which we will need to update in the current group and put 0 in their place in the array (there are at most sqrt(Q) such numbers). Then we answer all the queries in the group without looking at the updates in the group (this can be done in constant time per query if we precompute arrays with preffix sums).

What is left is the ammount updates in our group give. We transform each query [L,R] into two queries [0,R] and [0,L-1]. We go through the sum intervals from left to right. When we are at interval P we will answer queries [0,P]. Assume we have an array which can add number to interval in O(sqrt(N)) and get value at some index in O(1). So, for each sum interval (from left to right) we can add 1 to it and now when we are at interval P we will know how many intervals cover each number ( = how many times we must add the number to the query result). The remaining is simple - just go through all the numbers affected by updates in our group (which are at most sqrt(Q)) and add them with the correct count from the array above.

Array which can add number to interval in O(sqrt(N)) and get value at index in O(1) again is done with sqrt-decomposition.

I guess it won’t be very usefull, but here is my solution - http://www.codechef.com/viewsolution/5351179


#8

As for authur’s solution,I wonder what the i is ? if it is the index of the bucket,how can we know occurrences of pos in range [1,x] , considering the array B is just one dimension,but you must deal with the pos and the x.I need HELP!!!


#9

"We can precompute this factor in O(N*sqrt(N)) space and time.

Thus, we can update this structure in O(sqrt(N)) by traversing through all the chunks and applying +(yfactor)-(prevfactor) at every chunk"

what does this mean???please someone elaborate this


#10

Please explain in detail cant get your solution??


#11

As we are undating only blocks …how would we get correct sum in case of incomplete block since we are not updating the actual functions with the given index ???
please explain…


#12

Can you please elaborate on “No update version”? I am unable to understand the use of segment tree in that.


#13

Can someone, please, post the test data for Task #2 (i.e. first test of the Sub-Task3)? This is the only test that I’m receiving WA. I’ve already tried many, many things and many, many random tests but I’m not able to find my mistake… I would really appreciate this specific test. Thanks a lot.


#14

you can solve this problem with sqrt-decomposition on queries + persistent segment tree :slight_smile:
My solution: https://www.codechef.com/viewsolution/17543787


#15

Anyone whose solution is failing for first test case of third subtask: Use unsigned long long instead of long long int whenever computing sum.


#16

i tried an O(q log(n)sqrt(q)) solution that i couldn’t get to run in time. To know how many times a particular x occurs in range of functions [m,n], i used a persistent segment tree with pre-computation nlogn .
After every sqrt(q) queries i updated my prefix sum array.For each query i just visited all the updates within that chunk of queries. So, query was O(sqrt(q)log(n)) , while update was O(1).


#17

yes, just keep a segment tree for the value of all functions so that you can query the sum of functions [m,n]. Also store the index of all functions starting from any given index in the original array.
On updating index x, you only need to update the functions that start from either x-1,x-2…,x-10 and ending at or after x. There can be O(n) such functions for a given x, but since x is unique total complexity will stay qlogn.


#18

Great, thanks for an answer, I misunderstood the x will be distinct part, I thought elements in A are distinct and it didn’t help me, suprisingly :smiley:


#19

Although I didn’t use ‘all x are distinct’ constraint, I used the R-L<=10 part to keep a vector of vectors where vector* stores occurrences of index i in the intervals array. Then I divided the queries into square root(q) segments and for each segment, I applied brute force. For all queries of type 2 in a segment, I iterated over all queries of type 1 before it and checked which queries of type 1 affect the current type 2 query. For this, I binary searched in the vector* part of the index x of type 1 query to find no. of occurrences of this index in range [m,n] of type 2 query.


#20

I feel that, if x are not distinct it won’t fit, I need to think more abouot this. Thanks for you answer :wink: