Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Naim_Hasan's blog

By Naim_Hasan, 4 weeks ago, In English,

https://toph.co/arena?contest=mirror-nstu-ice-fest-regional-2020#!/p/beauty-factor

Above problem has almost same pattern as problem described below.

You are given an Array of integer numbers. You have to answer Q query.

For each query you will be given 3 integer- L, R, K; [ 1'based indexing ]

The answer is if you sort the Array elements from index L to R, then what will be the sum of first K element of the Array? { You can't sort the range [L , R] permanently ] }.

Example:

Array = { 8, 7, 6, 5, 4, 3, 2, 1 };

Lets answer 2 query.

Query 1: 5 8 3 Answer : 21 [ Because K < L, so sorting didn't affect our answer ]

Query 2: 5 8 6 Answer : 27 [ If we perform sort, then first 6 elements will be 8 7 6 5 1, so ans is 27 ]

{ I just learned Merge_Sort_Tree data structure and this problem came to mind. Type_1 query can be answered with prefix_sum algorithm. But how to handle Type_2 query? }

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide the link to the problem?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually the problem pop up in my mind while learning merge_sort_tree. As each node store a range in sorted order, so i was thinking is it possible to answer for a sorted range without performing sort on real array elements.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You could binary search the ending element in the L,R range in a merge sort tree, where each node has sorted elements and prefix sums. Complexity would be log(n) * log(n) * log(max_element) per query.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I figured out that if R <= K, than sorting also doesn't affect the answer just like type_1 query. I got bellowed idea while thinking and walking- Lets say L < K < R means K is somewhere between [L,R]. Now add prefix_sum from 1 to L-1 to the answer. Now we have to find answer for range [L,K]. Here i got confused how to handle this part because after sorting some element of actual array range [L,K] may not be present if we sort range [L,R].

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can be done online using persistent segment tree in O(log(n)) for a query or offline using usual segment tree with sorting queries

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

You have no reason to know any algorithms harder than DFS. Really.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Ouch! True but sometimes people just wanna learn something new instead of focusing purely on increasing their rating I guess?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Didn't get it. Um_nik

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Your rating is below 1220 for more than a year, which means that you are struggling to solve problems on basic logic skills, ifs and fors. You shouldn't know words "merge sort tree". I don't, for example.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, you are right. I still got confused when try to solve A,B from Div_2 and Div_3. Actually my thinking level is still low, so i am trying to focus on problems with fixed data structure and algorithm. [ It was a pleasure to get attention from an LGM ]

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    You have no reason to have high rating either ;)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think we can solve this by using the solution to SPOJ's KQUERY problem as a subroutine.

You can turn each query into 2 parts:

  1. What is the kth element of the subarray?
  2. What is the sum of elements less than X in the subarray?

The first can be answered using the solution for the KQUERY problem. The second can be answered offline using a range tree like fenwick tree or segment tree.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Understood the 2nd part. Each node in Merge_Sort_Tree will keep 2 array. One for storing elements in sorted order and second is for prefix_sum. Now we can perform binary search on 1st array to see if current element is less than X or not. If yes, we can add the range_sum to our answer from 2nd array. [ This problem has the exact same pattern as i explained. Now i have to learn how to handle type_1 query from your comment. Thanks for your time.