This question was recently asked in Samsung "Code The Next" contest hosted on hackererth.
Boogle, the software giant developed a mobile operating system named Ambroid. As we all know, in order to unlock an Ambroid device, one needs to draw a pattern connecting the given dots. The developers of Ambroid OS want this pattern unlock to be more secure. So they are wondering, in how many ways, can we draw a pattern by connecting dots.
Given N points (dots) in the co-ordinate system, find and return the number of ways in which, we can draw a pattern by connecting dots.
A pattern is a sequence of distinct dots where two adjacent dots in the sequence are connected by a line segment and should satisfy following conditions.
- A pattern should connect at least two dots.
- While connecting two dots A and B, suppose there is a dot C which has not yet been connected and lies on the line segment joining A and B, then you cannot connect A and B without connecting C in between, that is, pattern A-C-B and pattern B-C-A are valid but the patterns A-B or B-A are not valid as C has not yet been connected.
Input 2<=N<=16 0<=x,y<=200
I only know the obvious n! solution. Any solution with better time complexity is appreciated.
Auto comment: topic has been updated by GODOF_Shinobi (previous revision, new revision, compare).
I believe that since the bounds on N are so low, a bitmask dynamic programming (2^n * n^2) can solve this problem. Your state would be dp[current_point][mask], where the mask would represent whether or not a point has already been visited (for example, the mask 0101 would say that the 0th and 2nd points have been visited, while the 1st and 3rd points have not been visited). In your dp, given that you are currently on point P with mask M, you can try all other possible points to reach next (as long as they are valid and haven't been visited yet). Once you reach the mask where all the bits are 1's (a value of 2^n — 1), then you have made a successful pattern.