0
Your rating: None

CodeChef submission 61418 (C++ 4.0.0-8)

CodeChef submission 61418 (C++ 4.0.0-8) plaintext list. Status: AC, problem E5, contest . By srihari (Srihari), 2009-07-31 00:45:58.
  1. #include<cstdio>
  2. #include<algorithm>
  3.  
  4. #define CATALANSIZE 31
  5.  
  6. using namespace std;
  7.  
  8. long long derivedCatalanNumbers[CATALANSIZE][CATALANSIZE];
  9.  
  10. inline void initializeDerivedCatalanNumbers() {
  11. 	derivedCatalanNumbers[1][1] = derivedCatalanNumbers[1][0] = derivedCatalanNumbers[0][0] = 1L;
  12. 	int i, j;
  13. 	for (i=2; i<CATALANSIZE; ++i) {
  14. 		derivedCatalanNumbers[i][i] = 1L;
  15. 		for (j=i-1; j>0; --j) {
  16. 			derivedCatalanNumbers[i][j] = derivedCatalanNumbers[i][j+1] + derivedCatalanNumbers[i-1][j-1];
  17. 		}
  18. 		derivedCatalanNumbers[i][0] = derivedCatalanNumbers[i][1];
  19. 	}
  20. }
  21.  
  22. int prefix[CATALANSIZE];
  23.  
  24. struct state {
  25. 	int ind;
  26. 	int maxLen;
  27.  
  28. 	bool operator<(const state& other) const {
  29. 		return ((maxLen < other.maxLen) || ((maxLen == other.maxLen) && (ind < other.ind)));
  30. 	}
  31. };
  32.  
  33. state states[CATALANSIZE];
  34. inline void resetStates(int m) {
  35. 	for (int i=0; i<m; ++i) {
  36. 		states[i].maxLen = 0;
  37. 	}
  38. }
  39.  
  40.  
  41. int numbersSmallerThanButNotInPrefix[CATALANSIZE];
  42. inline void resetNumArray(int n) {
  43. 	for (int i=0; i<n; ++i) {
  44. 		numbersSmallerThanButNotInPrefix[i] = i;
  45. 	}
  46. }
  47.  
  48. int main() {
  49. 	initializeDerivedCatalanNumbers();
  50.  
  51. 	int T;
  52. 	scanf("%d", &T);
  53.  
  54. 	int n, m;
  55.  
  56. 	int i, j;
  57. 	int maxLen;
  58.  
  59. 	for (int t=0; t<T; ++t) {
  60. 		scanf("%d%d", &n, &m);
  61. 		resetNumArray(n);
  62. 		for (i=0; i<m; ++i) {
  63. 			scanf("%d", &prefix[i]);
  64. 			for (j=prefix[i]; j<n; ++j) {
  65. 				numbersSmallerThanButNotInPrefix[j]--;
  66. 			}
  67. 		}
  68.  
  69. 		// find all longest decreasing subsequences in the prefix
  70. 		resetStates(m);
  71. 		for (i=0; i<m; ++i) {
  72. 			states[i].ind = prefix[i];
  73. 			maxLen = 0;
  74. 			for (j=0; j<i; ++j) {
  75. 				if (states[i].ind < states[j].ind) {
  76. 					if (states[j].maxLen > maxLen) {
  77. 						maxLen = states[j].maxLen;
  78. 					}
  79. 				}
  80. 			}
  81. 			states[i].maxLen = maxLen+1;
  82. 		}
  83. 		sort(states, states+m);
  84.  
  85. 		// no decreasing subsequence in prefix
  86. 		if ((m==0) || (states[m-1].maxLen == 0)) {
  87. 			printf("%lld\n", derivedCatalanNumbers[n-m][0]); // SOLUTION
  88. 			continue;
  89. 		}
  90. 		// 3+ sized decreasing subsequence already in prefix.
  91. 		if (states[m-1].maxLen > 2) {
  92. 			printf("0\n"); // SOLUTION
  93. 			continue;
  94. 		}
  95. 		for (i=m-1; i>=0; --i) {
  96. 			// 2-size decreasing subsequence in prefix has a
  97. 			// 100 % chance of completing trio in the suffix
  98. 			if ((states[i].maxLen == 2) && (numbersSmallerThanButNotInPrefix[states[i].ind-1] > 0)) {
  99. 				printf("0\n"); // SOLUTION
  100. 				break;
  101. 			}
  102. 			
  103. 			if (states[i].maxLen == 1) {
  104. 				// SOLUTION
  105. 				printf("%lld\n", derivedCatalanNumbers[n-m][numbersSmallerThanButNotInPrefix[states[i].ind-1]]);
  106. 				break;
  107. 			}
  108. 		}
  109. 		// shouldn't have come here empty handed in the first place..
  110. 		// i.e. (i > 0) always as solution should have been found.
  111. 		if (i < 0) abort() ; // SIGABRT
  112. 	}
  113.  
  114. 	return 0;
  115. }
  116.

Comments