Sammmmmmm's blog

By Sammmmmmm, history, 6 months ago, In English

Given an array of n integers. In 1 operation you can swap 2 adjacent elements a[i] and a[i + 1] if and only if a[i] + a[i + 1] <=

k. Count the number of possible arrays that can be created using a series of operations (possibly none). Two arrays a and b are

considered different if there exists an index i so that a[i] != b[i]

N <= 1e5

K <= 1e9

Ai <= 1e9

Thanks!

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

»
6 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it
correct me if i'm wrong
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it is wrong
    Consider this array

    K=10, arr = [3,100,2]

    your algorithm will give 2 permutations, but actual answer is 1
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you are correct. i misread the problem please verify the edit part. Thanks!

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

    [1, 10, 2, 10, 3, 10], k: 5
    the answer here is one since you can't swap any two adjacent element, but the B array will be: 1,2,3, which the number of permutations are 6

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

      yes, you are correct i misread the problem i have corrected it can you please verify it again

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

        Bro, I typed all that s**t as a solution, and u explained it in 2 sentences, yes it's indeed correct.

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

why downvotes this is a good question

»
6 months ago, # |
Rev. 5   Vote: I like it +1 Vote: I do not like it

I have this solution:(the indexing for the array is one based):

If too long to read: https://codeforces.net/blog/entry/129493?#comment-1149165 simplifies it
EDIT: Now that I think about it, there exist a more clever and cleaner way to implement this approach, but I wrote the first thing that came to mind, so if you wanna read it:

Although the part for calculation the permutations is indeed required, even if u use the other clever implementation. So yes that might be helpful

Detailed solution, also talked about details way of implementation
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need to have a multiset, have 3 variables: mn, mx, and length, while advancing the new vertex, if the new_mn - new_mx <= k, the length gets incremented.
    otherwise, the answer gets multiplied by (length! / (all those cnt factorials)). which may help the complexity to lose some constant factor

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

      Also, keeping the dominator and numerator in 2 different variables all the time and calculating the mod division only once is a good performance boost

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Bro this comment section turned into a place for specialists(everyone who commented was spec)