JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - New Recipes Counting permutations of certain type
 Counting permutations of certain type | Reply Hello,This is my first post here and I really need some help with this.I know this problem might be silly for many of you :) but I couldn't solve it, so need your help.I am given 2 integers1st one: N, I have to consider all permutations of numbers from 1 to N2nd one: M, I have to count only those of the set of permutations in which no sum of adjacent numbers are dividable by MExample:Input: 3 3Output: 2The set of all permutations is1. 1 2 32. 1 3 23. 2 1 34. 2 3 15. 3 1 26. 3 2 1But I can take only 2 and 4 because all the others have adjacent numbers whose sum is dividable by 3. So the output is 2.The maximum value of N is 14 and for M is 30Is there any efficient way of doing this??Please note that, I know how to generate all the permutations and get the result using bruteforce. But given the constraints, this will take hours if not days. But some teams solved it on a single attempt in a local contest and I'm really out of ideas here.Please help..
 Subject Author Date Counting permutations of certain type Tafhim Aug 31, 2013 at 8:44 AM EDT Re: Counting permutations of certain type dimkadimon Sep 19, 2013 at 3:20 AM EDT Re: Counting permutations of certain type rit2012008 Dec 13, 2014 at 10:47 AM EST Re: Counting permutations of certain type shpendktester Jan 30, 2016 at 7:38 AM EST
 Forums TopCoder Cookbook Algorithm Competitions - New Recipes Counting permutations of certain type Previous Thread  |  Next Thread