Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

LovesProgramming's blog

Super Hard Uber OA Problem | Count good permutations | July
By LovesProgramming, history, 4 hours ago, In English

How to solve this problem asked in Uber OA :-

You can assume N walls with distinct heights.

You are given an array A. A[i] denotes how many walls can be viewed if you stand after the i'th wall

Example array of walls :- [5 4 2 3 1]

A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 3 (You can view 5 , 4 , 3 -> if you stand after 3 and observe.) A[5] = 4

Given an array A ; find the count of permutations possible of size "N" ("N" walls with distinct heights from 1 to N)

Input :- A : [1 2 3 1 2]

Output :- 4

[4 3 2 5 1]

[4 3 1 5 2]

[4 2 1 5 3]

[3 2 1 5 4]

Tried many ways couldn't find any that works.

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

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

Auto comment: topic has been updated by LovesProgramming (previous revision, new revision, compare).

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is kind of similar to 1946E - Girl Permutation Let’s choose the biggest index i such that a[i] = 1,then p[i] = N.We divide the array into two parts: [1,i-1] and [i+1,N].There are $$$C_{N-1}^{i-1}$$$ ways to do that. Now let’s solve the left part(right part is similar). Assume the segment is [L,R], again we choose the biggest index i such that a[i] = 1 && L <= i <= R.then p[i] is the largest number in the segment,again we divide the segment into two parts:[L,i-1] and [i+1,R]. There are $$$C_{R-L}^{L}$$$ ways to do that. If the size of segment is 1 then just return 1.

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In your initial statement you said (i-1)C(n-1) ways; but there is only 1 way to divide:-

    (1,i-1) and (i+1,n)

    What am I getting wrong

    Thankyou

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let’s see your example A : [1 2 3 1 2]. First we choose a[4] = 1, we have $$$C_4^3$$$ = 4 ways to divide the array.for subarray [1,2,3] we choose a[1] = 1 and we have $$$C_2^0$$$ = 1 ways to divide.left part is empty.the contribution is 1.for the right part [2,3] we should choose the biggest index i such that a[i] = 2(since we know there is a element in the left of the segment that is larger than all the element in this part.In this case it is p[1]).then we choose a[2] and divide the segment again.the left part is empty and the right part contains only a[3].both contributions are 1.And the last segment is a[5] and the contribution is 1 too.So we have the answer = 4.

      → Reply
    • »
      »
      »
      3 hours ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      The ways to divide the array means you choose some elements for the left part and leave other elements for the right part.there is $$$C_{N-1}^{i-1}$$$ ways to choose the numbers.which number you choose doesn’t matter.

      → Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    expected rating of the problem ??

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Was this actually asked for an Uber interview or is it from some site that tries to get clicks by claiming it was from Uber?

→ Reply