Name123's blog

By Name123, history, 4 years ago, In English

Given an array A that is a permutation of n numbers [1-n]. Find the number of subarrarys S that meets the following condition max(S) — min(S) = length(S) — 1.

Example 1:

Input: [4, 3, 1, 2, 5] Output: 10 Explanation: subarrays that meets the condition are [4] [3] [1] [2] [5] [4 3] [1 2] [3 1 2] [4 3 1 2] [4 3 1 2 5]

There are 10 subarray that meets the condition, so the answer should be 10.

Is there a better than O(n^2) solution?

  • Vote: I like it
  • -20
  • Vote: I do not like it

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

https://codeforces.com/blog/entry/70503?locale=en

Can you please specify the source?

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

This problem is being asked a record third time

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

you should for every number i from 1 to n calculate that:

0!+1!+2!+.....+(n-i)!;

And then get sum of all this calculation.

for every i you should store in an array D that:

D[i] = 0!+1!+2!+....+i!

how can you calculate an array D?

d[0] = 1;

 for i from 1 to n:

      d[i] = d[i-1]*i;

And then:

for i from 1 to n:

     ans += D[n-i]

print ans;
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How have you come up with this thing?

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

    I am not getting correct answer with this approach

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

(n-i)!*(i+1)!*(n-i) where i should be from 0 to n-1 will give you the correct answer for n=1 ->1 n=2 ->6 n=3 ->32 n=4 ->180 ans so on