Algoflux Qualifiers

general
1

How to solve 5th problem ?

4 Likes
2

This question has two parts:
Part1- Precomputing i * (sum of different prime factors of A[i]) for all i and store in another array (say arr[]). This is pretty basic and can be done using Sieve.
Part2- Using a data structure to answer queries of the form l,r,k.
For this maintain a segtree whose leaf nodes contain values of arr[i].
Now, sort the queries with respect to k in increasing order.
After answering a query moving to next query involves updating all leaf nodes to 0 whose A[i] value is less than equal to k of the new query, and then answering range query(l,r).
Total no. of updates is atmost n and queries q. So total complexity of part2 is O( nlogn + qlogn ).

3 Likes
3

Pre requisites : Sieve , offline query , FenwickTree or SegmentTree

The sum of prime factors can be precomputed using a sieve for numbers less than 10^7
Lets call that S[i]

We need a data structure which supports 2 operations:

  1. sum of all values which are greater than a index K , query(K)

  2. increment the value at a particular index , update(i , val)

The basic idea is to process the queries offline . That is we won’t be solving the queries as and when they come . We will iterate each index in the array and process each endpoint in that index .

Let ans[j] store the answer to the j^{th} query

When we are in the i^{th} index of the array

  1. For each query j whose left endpoint is i , ans[j] = query(K)

  2. update(S[A[i]] , i * S[A[i]])

  3. For each query j whose right endpoint is i , ans[j] = query(K) - ans[j]

You can visualize it as something similar to prefix sums

My Solution :


[1]

Complexity : $O((N + Q)log R)$ , $R$ = maximum sum of prime factors , for $N = 10^7 , R = 9999991$ 



I made a really trivial mistake while implementing a Fenwick Tree , so I wasn't able to submit during contest . I was able to fix it only after the contest. 


  [1]: https://www.codechef.com/viewsolution/12677829
2 Likes
4

I have a doubt. According to the solution given by @grey_code we will have to check for updates on leaf nodes after each query. So how would we do that ? wouldnt it take O(n) time ?

5

sort w.r.t k in decreasing order? I think it should be increasing order and then for each A[i]<=k update A[i]=0; Am i right ?

6

Yes you are right, will edit my answer.

7

Thanks.Your approach is very simple.Marked your answer as accepted :slight_smile:

8

Thanks for writing detailed solution :slight_smile: +1

9

No, as we do not check for all n leaf nodes to update. We know that leaf nodes that have been previously updated to 0 will remain 0. Only update new nodes less than equal to k in a new query. We can have sorted order of leaf nodes in some other array, and update each leaf node at most once.