10128 - Queue

[maxagaze]

I am really stuck here, and wondered if any of you kind people could see mercy to me and gime me a hint on this problem.

Up until now the only soultion I have been able to come up with is a brute-force'ish iteration over most permutaions of a set of n integer (0..n) and checking everyone if they may be part of the total solution set.

Any hint/help will be greatly Appreciated

--
Maxagaze

[rjhadley]

How does everyone solve this problem so quickly?

I've tried backtracking, but it is way too slow. My method is:
(a) decide how many people, L, should be to the left of the tallest person
(b) split the people into to the L to the left of the tallest person and thus, the remaining N - L - 1 people are to the right of the tallest person
(c) independently choose P of the L (from above) to be able to see left and R of the N - L - 1 (from above) to be able to see right, then count how many ways the remaining L - P people on the left can be placed around the P without blocking their view. Likewise place the N - L - 1 - R remaining people on the right. I then add the product of how many ways their are for each to my total. (i.e. Product Rule).

Any suggestions on a faster way would be appreciated. Thanks.

[little joey]

I must shamefully confess that I precalculated the 13*13*13 array of answers and stored it in the code...

But I doubt if it is to be considered cheeting; many real life programs work this way if solution space is small and calculations are time consuming.

[Adrian Kuegel]

My solution is similar to rjhadleys, but I use divide and conquer. I use a function solve that returns number of permutations of n persons with v visible from front, r visible from back or v visible from front and arbitrary many visible from back or arbitrary many visible from front and r visible from back. If I would have memorised these results, I wouldn't have that slow time of 0.210 seconds. Probably it is also possible to calculate these values bottom up with DP.

[rjhadley]

Thanks Adrian! I switched from a backtracking approach to a dynamic programming approach and that solved it in 0.094 seconds.

(I think I was mislead by Skiena & Revilla's Programming Challenges, which lists this as a backtracking problem).

[sohel]

My approach is quite similar to the mentioned algorithm.

I ran a loop from P to (1+N-R) which indicates the position of the tallest person. Then for each side I calculated the number of permutaion considering any arbitrary value and then multiplied with ncr.
My recursive function includes ncr and factorials.

The above approach took 0.90 seconds.
Then with a bit of memoization it came down to 0.23 seconds.

[stalf]

Hello there,
I've been trying to solve this problem for a while, but i couldn't figure out how to achieve any results...
As far as i've understood, the idea is to find the range of places where the tallest person can be, and then loop through it calculating how many ways people can stay in front and behind him in order to have P and R people seen from front and back respectively.
What I don't understand is: don't i need further information on who is taller than who?
i tried this code:
1) loop i from P to 1+N-R
1.1) combinations += combination(i,P)*combination(N-i,R)

I know this ain't right, but can't figure out why or how to make it right..
any help is appreciated

[mak(cse_DU)]

My solution was a DP,Memoization.

my recursion was like
fun(L,pre,mask){

memo[L][pre][mask] // it is memoization

};

And initial call was: cout<<fun(L,-1,0);

here pre is negative for first call.

But I am AC.!!!!!!!!!!!!!! Need Explanation.

Thanks in advance.

Note: The tallest person is always n(Middle man).

[koalo]

Does anyone has an accepted backtracking solution as the Skiena & Revilla's Programming Challenges suggests?

With DP it was relatively easy, but with backtracking the complexity seems to be far too large.
For example the number of all permutations for 12 persons and 4 being larger than their predecessor is in the range of 10G - so even with very clever pruning I don't see a chance.

Please correct me if I am wrong.

Greetings,
koalo

[Hikari9]

There is a formula for this problem using math ( I derived it using combinatorics )

After tedious calculations, I found out that the answer is just the equation

• F(n,p,q) = abs( stirling( n-1, p+q-2 ) ) * nCr( n, p+q-2 ) )

where abs(x) is absolute value,
stirling(n,k) is the stirling number of first kind,
and nCr(n,k) is number of combinations.

and of course, constraints should be p, q should be positive and 1 < p+q <= n, or else answer is 0.

note that stirling(n,k) is a recursive function defined as

• stirling( 0, 0 ) = 1
  stirling( 1, 0 ) = 0
  stirling( 0, 1 ) = 0
  stirling( n, k ) = stirling( n-1, k-1 ) - ( n-1 ) * stirling( n-1, k ) , 1 < k <= n

while we have the combination function nCr(n,k) is defined as

• nCr( n, k ) = n! / ( k! * (n-k)! )

I know that there are other easier formulas for this problem, but I hope this helps