agent3889's blog

By agent3889, 6 years ago, In English,

I saw this problem in codechef, can anyone tell me what is the approach to solve this problem. ?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

EDIT: misunderstood the problem

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

    This is interesting. You just solved the longest increasing subsequence problem in O(n) ? Care to explain how?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My mistake, I thought subsequence meant consecutive, thanks for correcting me.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        No problem.

        On a sidenote, my solution to OP's problem has complexity O(t * n * log10000) using segment tree.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          so what is the solution for the problem ?

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ok, well I reduced the problem to the following one:

            You are given an array of integers and a number of queries. Each query is of the form a, b.

            The query means — Find out the maximum element in the range [a, b]. Also find out the number of occurences of the maximum element in that range.

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              sorry but it is not clear to me :( can you please describe it a little more ?

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

Thank you very much , good answers ....

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

so no one ??

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    this problem almost the same as find longest increasing sub-sequence.

    in longest increasing sub-sequence problem the dp states is dp[i] which represent the length of longest increasing sub-sequence from using only numbers from 1 to i and i'th element must be included , and it's calculated like this dp[i]= max ( dp[j] + 1) for all j<i and Array[j]<Array[i]

    this is O(N^2) and it is easy to reduce it to O(N log N) using data structures, however this only calculates the length of longest increasing sub-sequence , how to count how many sub-sequences are there?

    it is very simple let cnt[i] represent the number of sub-sequences which satisfy the conditions of dp[i] then to calculate cnt[i] do the following while you iterate over j to calculate dp[i]:

    if you find j such that dp[j]+1>dp[i] then make the value of cnt[i] equal to cnt[j]

    if you find j such that dp[j]+1==dp[i] then add to cnt[i] the value of cnt[j]

    if you find j such that dp[j]+1<dp[i] ignore it.

    now let's back to your problem , to solve it you need little bit change to dp states so it will become dp[i][0] represent longest mountain-sequence while it's in increasing part of it

    and dp[i][1] represent longest mountain-sequence while it's in decreasing part of it

    now it's your exercise to continue solving the problem based on my explanation of longest increasing sub-sequence problem