sonthaile2002's blog

By sonthaile2002, history, 5 weeks ago, In English,

You are given an array a of n integers (n <= 1e5, a [i] <= 1e5) and m (m <= 1e4) the query has the form (x, y) meaning that finding the xth largest value is made by y consecutive numbers in array a. please help me solve this problem? Thanks. And sorry because of my poor English.

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

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

Can you give me an example?

Lets say a ={1.2.3.4.5}

and query: (2,3)

What should the answer be?

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

    9

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

      you mean 2+3+4 = 9?(a[1]+a[2]+a[3])

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

        yes

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it -10 Vote: I do not like it

          (i'm not very experienced programmer)

          a simple idea is that you create a sliding window of length y(if you don't know what is sliding window click here) and store the values from the sliding window in a vector/array(i will call it sums) then sort that array and take the sums[x-1](if you are using starting index 0) or sums[x] if you are using starting index 1)

          if you need code tell me

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

            That surely would work !

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

              Yeah,but its a bit slow the time complexity is O(n*m*log(m)) where n is size of given array and m the size of the array created with the help of the sliding window(m = n-x)

              so my algorithm is close to O((n^2)*log(n))(a bit faster than that) which is very close to O(n^2)

              in conclusion my algorithm will work for n < 10^4

»
5 weeks ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

If I will met this problem in contest I will write in this way

Let's create some array $$$b$$$ where we save pair {$$$ a[i], i $$$} to sort them and save every position of element which largest one in array, and after that we can create simple segment sum tree, and answer for every query $$$x$$$ is position of element and $$$y$$$ is position of element + $$$y$$$ — 1

Upd2: My approach is wrong, I am solving problem for finding x th largest number and add y consecutive numbers

Upd: There is the approach https://ideone.com/7to9IH

Time complexity $$$O(n + mlog(n))$$$

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

    Your solution is actually incorrect on testcase

    2
    5 2
    1
    1 2
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      I think now this works https://ideone.com/7to9IH

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

        Nope.

        3
        3 2 1
        1
        1 2
        

        Please explain a little more on your solution, so I can understand.

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

          Isn't the answer 4?

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it -6 Vote: I do not like it

            The answer can't be 4 because the only possible values are 3 + 2 = 5 and 2 + 1 = 3.

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

              Oh, my bad, I am solving problem for finding x th largest number and add y consecutive numbers.

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

If TL is high enough there is a $$$O(n \cdot m)$$$ solution. For each query just calculate the needed sums and use k-th statistics which works in $$$O(n)$$$.

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

Can you provide link to the problem?