PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

Permutations solution: Facebook hacker cup 2013 Round 2

(1 votes, average: 5.00 out of 5)

February 17, 2013 by puzzler Leave a Comment

From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the third question(Carried 45 marks out of 100) for the Round 2 of 2013 hacker cup. only top 100 contestants will be moved to Round 3.

Problem Statement

In this problem you need to count number of possible permutations p of the first N integers, given N-1 constraints of the form pi < pj.

Input

The first line contains an integer T, T ≤ 20, followed by T test cases. Each test case begins with an integer N, N ≤ 1000, which is the number of integers in the permutation. The next N – 1 lines each contain a single constraint in the following format: “i sign j“, where 0 ≤ i, j ≤ N – 1 and sign is either “<” or “>“, which denotes whether the i-th element of the permutation should be less than or greater than the j-th element.

It is guaranteed that it is not possible to partition indices into two disjoint sets A and B such that there is no constraint involving elements from both A and B.

Output

For each test case, output one single line with the number of permutations that satisfy all the constraints, following the output format shown in the example. The answer may be very large, so you should give the result modulo 1000000007.

Example Input

5
2
0 < 1
3
0 < 1 2 > 1
5
0 < 2
1 < 2
2 < 3
2 < 4
4
0 < 1
0 < 2
0 < 3 6 0 > 1
1 > 2
2 > 3
3 > 4
4 > 5

Example Output

Case #1: 1
Case #2: 1
Case #3: 4
Case #4: 6
Case #5: 1

Solution

I will just give the hint as of now, think of using graph and dfs.
There is a neat solution by Niyaj(ranked 45 in round 2).

  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments
Next Puzzle
3 SUM problem

Checkout more Interview Questions Tags: Algorithm, Facebook Hacker Cup, Interview, Java, Solved Puzzles, Very Difficult

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Osmos Solution: Google codejam 2013 Round 1B
  • Find a pythagorean triplet from an array
  • Objective Questions set C/C++ – Part 5
  • Magic Trick Solution – Google Code Jam 2014
  • Minesweeper Master Solution – Google Code jam 2014
  • Find all non duplicate pairs that sum to S
  • Reverse a link list without using another
  • Average speed of train
  • Beautiful Strings solution: Facebook hacker Cup 2013 Qual Round
  • Fair and Square Solution: Google codejam 2013 Qual Round

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2023 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▲
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous