0
Your rating: None
CodeChef submission 136779 (C) 

CodeChef submission 136779 (C) plaintext list. Status: CE, problem SNCK03, contest SNACKDWN. By haymakers (haymakers), 2009-11-21 23:56:45.
  1. /*
  2.  *  perm.cpp
  3.  *  
  4.  *
  5.  *  Created by Mayank Jaiswal on 21/11/09.
  6.  *  Copyright 2009 IIT Kharagpur. All rights reserved.
  7.  *
  8.  */
  9. using namespace std;
  10. //using namespace stdcomb;
  11. #include<iostream>
  12. #include<algorithm>
  13. #include<vector>
  14. #include<set>
  15.  
  16. #define DEBUG false
  17.  
  18.  
  19. void print(set<int> s)
  20. {
  21.   for(set<int> :: iterator p= s.begin(); p!= s.end() ; p++)
  22. 	if(DEBUG)  cout<< *p<< " "; 
  23.   if(DEBUG)  cout<< endl;
  24. }
  25. void print(vector<int> s)
  26. {
  27.   for(int i=0; i<s.size(); i++)
  28. 	if(DEBUG)  cout<< s[i]<< " "; 
  29.   if(DEBUG)  cout<< endl;
  30. }
  31.  
  32.  
  33. //=======================================================
  34. // combination.h
  35. // Description : Template class to find combinations
  36. //=======================================================
  37. // Copyright 2003 - 2006 Wong Shao Voon
  38. // No warranty, implied or expressed, is included.
  39. // Author is not liable for any type of loss through 
  40. // the use of this source code. Use it at your own risk!
  41. //=======================================================
  42. #ifndef __COMBINATION_H__
  43. #define __COMBINATION_H__
  44. namespace stdcomb
  45. {
  46.   
  47.   // Non recursive template function
  48.   template <class BidIt>
  49.   
  50.   inline bool next_combination(BidIt n_begin, BidIt n_end,
  51. 							   BidIt r_begin, BidIt r_end)
  52.   {
  53. 	
  54. 	bool boolmarked=false;
  55. 	BidIt r_marked;
  56. 	
  57. 	BidIt n_it1=n_end;
  58. 	--n_it1;
  59. 	
  60. 	
  61. 	BidIt tmp_r_end=r_end;
  62. 	--tmp_r_end;
  63. 	
  64. 	for(BidIt r_it1=tmp_r_end; r_it1!=r_begin || r_it1==r_begin; --r_it1,--n_it1)
  65. 	{
  66. 	  if(*r_it1==*n_it1 )
  67. 	  {
  68. 		if(r_it1!=r_begin) //to ensure not at the start of r sequence
  69. 		{
  70. 		  boolmarked=true;
  71. 		  r_marked=(--r_it1);
  72. 		  ++r_it1;//add it back again 
  73. 		  continue;
  74. 		}
  75. 		else // it means it is at the start the sequence, so return false
  76. 		  return false;      
  77. 	  }
  78. 	  else //if(*r_it1!=*n_it1 )
  79. 	  {
  80. 		//marked code
  81. 		if(boolmarked==true)
  82. 		{
  83. 		  //for loop to find which marked is in the first sequence
  84. 		  BidIt n_marked;//mark in first sequence
  85. 		  for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2)
  86. 			if(*r_marked==*n_it2) {n_marked=n_it2;break;}
  87. 		  
  88. 		  
  89. 		  BidIt n_it3=++n_marked;    
  90. 		  for  (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3)
  91. 		  {
  92. 			*r_it2=*n_it3;
  93. 		  }
  94. 		  return true;
  95. 		}
  96. 		for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4)
  97. 		  if(*r_it1==*n_it4)
  98. 		  {
  99. 			*r_it1=*(++n_it4);
  100. 			return true;           
  101. 		  }
  102. 	  }
  103. 	}  
  104. 	
  105. 	return true;//will never reach here    
  106.   }
  107.   
  108.   // Non recursive template function with Pred
  109.   template <class BidIt, class Prediate>
  110.   
  111.   inline bool next_combination(
  112. 							   BidIt n_begin, 
  113. 							   BidIt n_end,
  114. 							   BidIt r_begin, 
  115. 							   BidIt r_end,
  116. 							   Prediate Equal)
  117.   {
  118. 	
  119. 	bool boolmarked=false;
  120. 	BidIt r_marked;
  121. 	
  122. 	BidIt n_it1=n_end;
  123. 	--n_it1;
  124. 	
  125. 	
  126. 	BidIt tmp_r_end=r_end;
  127. 	--tmp_r_end;
  128. 	
  129. 	for(BidIt r_it1=tmp_r_end; r_it1!=r_begin || r_it1==r_begin; --r_it1,--n_it1)
  130. 	{
  131. 	  if( Equal( *r_it1, *n_it1) )
  132. 	  {
  133. 		if(r_it1!=r_begin) //to ensure not at the start of r sequence
  134. 		{
  135. 		  boolmarked=true;
  136. 		  r_marked=(--r_it1);
  137. 		  ++r_it1;//add it back again 
  138. 		  continue;
  139. 		}
  140. 		else // it means it is at the start the sequence, so return false
  141. 		  return false;      
  142. 	  }
  143. 	  else //if(*r_it1!=*n_it1 )
  144. 	  {
  145. 		//marked code
  146. 		if(boolmarked==true)
  147. 		{
  148. 		  //for loop to find which marked is in the first sequence
  149. 		  BidIt n_marked;//mark in first sequence
  150. 		  for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2)
  151. 			if( Equal( *r_marked, *n_it2) ) {n_marked=n_it2;break;}
  152. 		  
  153. 		  
  154. 		  BidIt n_it3=++n_marked;    
  155. 		  for  (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3)
  156. 		  {
  157. 			*r_it2=*n_it3;
  158. 		  }
  159. 		  return true;
  160. 		}
  161. 		for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4)
  162. 		  if( Equal(*r_it1, *n_it4) )
  163. 		  {
  164. 			*r_it1=*(++n_it4);
  165. 			return true;           
  166. 		  }
  167. 	  }
  168. 	}  
  169. 	
  170. 	return true;//will never reach here    
  171.   }
  172.   
  173.   
  174.   // Non recursive template function
  175.   template <class BidIt>
  176.   
  177.   inline bool prev_combination(BidIt n_begin, BidIt n_end,
  178. 							   BidIt r_begin, BidIt r_end)
  179.   {
  180. 	
  181. 	bool boolsame=false;
  182. 	BidIt marked;//for r
  183. 	BidIt r_marked;
  184. 	BidIt n_marked;
  185. 	
  186. 	
  187. 	BidIt tmp_n_end=n_end;
  188. 	--tmp_n_end;
  189. 	
  190. 	BidIt r_it1=r_end;
  191. 	--r_it1;
  192. 	
  193. 	for(BidIt n_it1=tmp_n_end; n_it1!=n_begin || n_it1==n_begin ; --n_it1)
  194. 	{
  195. 	  if(*r_it1==*n_it1)
  196. 	  {
  197. 		r_marked=r_it1;
  198. 		n_marked=n_it1;
  199. 		break;
  200. 	  }
  201. 	}  
  202. 	
  203. 	BidIt n_it2=n_marked;
  204. 	
  205. 	
  206. 	BidIt tmp_r_end=r_end;
  207. 	--tmp_r_end;
  208. 	
  209. 	for(BidIt r_it2=r_marked; r_it2!=r_begin || r_it2==r_begin; --r_it2,--n_it2)
  210. 	{
  211. 	  if(*r_it2==*n_it2 )
  212. 	  {
  213. 		if(r_it2==r_begin&& !(*r_it2==*n_begin) )
  214. 		{
  215. 		  for(BidIt n_it3=n_begin;n_it3!=n_end;++n_it3)
  216. 		  {
  217. 			if(*r_it2==*n_it3)
  218. 			{
  219. 			  marked=r_it2;
  220. 			  *r_it2=*(--n_it3);
  221. 			  
  222. 			  BidIt n_it4=n_end;
  223. 			  --n_it4;
  224. 			  for(BidIt r_it3=tmp_r_end; (r_it3!=r_begin || r_it3==r_begin) &&r_it3!=marked; --r_it3,--n_it4)
  225. 			  {
  226. 				*r_it3=*n_it4;              
  227. 			  }
  228. 			  return true;
  229. 			}
  230. 		  }
  231. 		}
  232. 		else if(r_it2==r_begin&&*r_it2==*n_begin)
  233. 		{
  234. 		  return false;//no more previous combination; 
  235. 		}
  236. 	  }
  237. 	  else //if(*r_it2!=*n_it2 )
  238. 	  {
  239. 		++r_it2;
  240. 		marked=r_it2;
  241. 		for(BidIt n_it5=n_begin;n_it5!=n_end;++n_it5)
  242. 		{
  243. 		  if(*r_it2==*n_it5)
  244. 		  {
  245. 			*r_it2=*(--n_it5);
  246. 			
  247. 			BidIt n_it6=n_end;
  248. 			--n_it6;
  249. 			for(BidIt r_it4=tmp_r_end; (r_it4!=r_begin || r_it4==r_begin) &&r_it4!=marked; --r_it4,--n_it6)
  250. 			{
  251. 			  *r_it4=*n_it6;              
  252. 			}
  253. 			return true;
  254. 		  }
  255. 		}
  256. 	  }
  257. 	}  
  258. 	return false;//Will never reach here, unless error    
  259.   }
  260.   
  261.   
  262.   // Non recursive template function with Pred
  263.   template <class BidIt, class Prediate>
  264.   
  265.   inline bool prev_combination(
  266. 							   BidIt n_begin, 
  267. 							   BidIt n_end,
  268. 							   BidIt r_begin, 
  269. 							   BidIt r_end,
  270. 							   Prediate Equal)
  271.   {
  272. 	
  273. 	bool boolsame=false;
  274. 	BidIt marked;//for r
  275. 	BidIt r_marked;
  276. 	BidIt n_marked;
  277. 	
  278. 	
  279. 	BidIt tmp_n_end=n_end;
  280. 	--tmp_n_end;
  281. 	
  282. 	BidIt r_it1=r_end;
  283. 	--r_it1;
  284. 	
  285. 	for(BidIt n_it1=tmp_n_end; n_it1!=n_begin || n_it1==n_begin ; --n_it1)
  286. 	{
  287. 	  if( Equal(*r_it1, *n_it1) )
  288. 	  {
  289. 		r_marked=r_it1;
  290. 		n_marked=n_it1;
  291. 		break;
  292. 	  }
  293. 	}  
  294. 	
  295. 	BidIt n_it2=n_marked;
  296. 	
  297. 	
  298. 	BidIt tmp_r_end=r_end;
  299. 	--tmp_r_end;
  300. 	
  301. 	for(BidIt r_it2=r_marked; r_it2!=r_begin || r_it2==r_begin; --r_it2,--n_it2)
  302. 	{
  303. 	  if( Equal(*r_it2, *n_it2) )
  304. 	  {
  305. 		if(r_it2==r_begin&& !Equal(*r_it2, *n_begin) )
  306. 		{
  307. 		  for(BidIt n_it3=n_begin;n_it3!=n_end;++n_it3)
  308. 		  {
  309. 			if(Equal(*r_it2, *n_it3))
  310. 			{
  311. 			  marked=r_it2;
  312. 			  *r_it2=*(--n_it3);
  313. 			  
  314. 			  BidIt n_it4=n_end;
  315. 			  --n_it4;
  316. 			  for(BidIt r_it3=tmp_r_end; (r_it3!=r_begin || r_it3==r_begin) &&r_it3!=marked; --r_it3,--n_it4)
  317. 			  {
  318. 				*r_it3=*n_it4;              
  319. 			  }
  320. 			  return true;
  321. 			}
  322. 		  }
  323. 		}
  324. 		else if(r_it2==r_begin&&Equal(*r_it2, *n_begin))
  325. 		{
  326. 		  return false;//no more previous combination; 
  327. 		}
  328. 	  }
  329. 	  else //if(*r_it2!=*n_it2 )
  330. 	  {
  331. 		++r_it2;
  332. 		marked=r_it2;
  333. 		for(BidIt n_it5=n_begin;n_it5!=n_end;++n_it5)
  334. 		{
  335. 		  if(Equal(*r_it2, *n_it5))
  336. 		  {
  337. 			*r_it2=*(--n_it5);
  338. 			
  339. 			BidIt n_it6=n_end;
  340. 			--n_it6;
  341. 			for(BidIt r_it4=tmp_r_end; (r_it4!=r_begin || r_it4==r_begin) &&r_it4!=marked; --r_it4,--n_it6)
  342. 			{
  343. 			  *r_it4=*n_it6;              
  344. 			}
  345. 			return true;
  346. 		  }
  347. 		}
  348. 	  }
  349. 	}  
  350. 	return false;//Will never reach here, unless error    
  351.   }
  352.   
  353.   
  354.   // Recursive template function
  355.   template <class RanIt, class Func>
  356.   
  357.   void recursive_combination(RanIt nbegin, RanIt nend, int n_column,
  358. 							 RanIt rbegin, RanIt rend, int r_column,int loop, Func func)
  359.   {
  360. 	
  361. 	int r_size=rend-rbegin;
  362. 	
  363. 	
  364. 	int localloop=loop;
  365. 	int local_n_column=n_column;
  366. 	
  367. 	//A different combination is out
  368. 	if(r_column>(r_size-1))
  369. 	{
  370. 	  func(rbegin,rend);
  371. 	  return;
  372. 	}
  373. 	/////////////////////////////////
  374. 	
  375. 	for(int i=0;i<=loop;++i)
  376. 	{
  377. 	  
  378. 	  RanIt it1=rbegin;
  379. 	  for(int cnt=0;cnt<r_column;++cnt)
  380. 	  {
  381. 		++it1;
  382. 	  } 
  383. 	  
  384. 	  RanIt it2=nbegin;
  385. 	  for(int cnt2=0;cnt2<n_column+i;++cnt2)
  386. 	  {
  387. 		++it2;
  388. 	  } 
  389. 	  
  390. 	  *it1=*it2;
  391. 	  
  392. 	  ++local_n_column;
  393. 	  
  394. 	  recursive_combination(nbegin,nend,local_n_column,
  395. 							rbegin,rend,r_column+1,localloop,func);
  396. 	  --localloop;
  397. 	}
  398. 	
  399.   }
  400.   
  401. }
  402. #endif
  403.  
  404.  
  405. // for use with next_combination examples!
  406. template<class BidIt>
  407. void display(BidIt begin,BidIt end)
  408. {
  409.   for (BidIt it=begin;it!=end;++it)
  410. 	if(DEBUG)  cout<<*it<<" ";
  411.   if(DEBUG)  cout<<endl;
  412. }
  413.  
  414.  
  415.  
  416.  
  417. int perm(int cse, vector<int> list , int prev, vector<int> B )
  418. {
  419.   int count=0;
  420.   if(DEBUG)  printf("\nIn Permutation: ");
  421.   if(DEBUG)  cout<< " list: ";
  422.   for (int i=0; i<list.size(); i++) 
  423. 	if(DEBUG)  cout << list[i]<<" ";
  424.   if(DEBUG)  cout<< " B: ";
  425.   for (int i=0; i<B.size(); i++) 
  426. 	if(DEBUG)  cout << B[i]<<" ";
  427.   if(DEBUG)  printf("cse =%d, prev= %d",cse, prev) ;  
  428.   if(DEBUG)  printf(" B[size]-1=%d\n", B.size()-1);
  429.   
  430.   if(cse==B.size())
  431.   {
  432. if(DEBUG)  printf("cse==B.size()\n");
  433. 	return 1;
  434. 	
  435.   }
  436.   
  437.   int dec= cse%2;
  438.   
  439.   if(dec==0) // increasing
  440.   {
  441. 	if(DEBUG)  printf("in increasing \n");
  442. 	
  443. /*	//inserting in set
  444. 	set<int> listset;
  445. 	for (int i=0; i<list.size(); i++) 
  446. 	  listset.insert(list[i]); 
  447. 	if(DEBUG)  cout<< "set: ";
  448. 	for (set<int> :: iterator p = listset.begin(); p!= listset.end(); p++) 
  449. 	  if(DEBUG)  cout << *p<<" ";
  450. 	if(DEBUG)  cout << endl;
  451. */	
  452. 	
  453. 	vector <int> smallListOptions;
  454. 	for (int i=0; i<list.size(); i++) 
  455. 	  if(list[i]>prev)
  456. 		smallListOptions.push_back(list[i]);
  457. 	
  458. 	if(smallListOptions.size() < B[cse]-1)
  459. 	  return 0;
  460. 	vector<int> smallList;
  461. 	for(int i=0; i<B[cse]-1;i++)
  462. 	  smallList.push_back(smallListOptions[i]);
  463. 	if(DEBUG)  printf("small list :");
  464. 	for(int i=0; i<smallList.size();i++)
  465. 	  if(DEBUG)  cout<< smallList[i]<< " ";
  466. 	if(DEBUG)  cout<<endl;
  467. 	
  468. 	
  469. 	do
  470. 	{
  471. 	  if(DEBUG)  printf("Combinations:");
  472. 	  display(smallList.begin(),smallList.end());
  473.  
  474.  
  475. 	  
  476. 	  set<int> listset;
  477. 	  for (int i=0; i<list.size(); i++) 
  478. 		listset.insert(list[i]); 
  479. 	  
  480. 	  for (int i=0; i<smallList.size(); i++) 
  481. 		listset.erase(smallList[i]);
  482. 	
  483. 	  vector<int> restlist;
  484. 	  for (set<int> :: iterator p = listset.begin(); p!= listset.end(); p++) 
  485. 		restlist.push_back(*p);
  486. 	  
  487. 	if(DEBUG)  printf("restlist: ");  
  488. 	  for (int i=0; i<restlist.size(); i++) 
  489. 		if(DEBUG)  cout<< restlist[i]<< " ";
  490. 	  if(DEBUG)  cout << endl;
  491.  
  492. 	  
  493. 	  
  494. 	  
  495. 	  count += perm(cse+1, restlist, smallList[smallList.size()-1],B);
  496. 	  
  497. 	  
  498. //	  int perm(int cse, vector<int> list , int prev, vector<int> B )
  499.  
  500. 	  
  501. 	  //******************************
  502.  
  503. 	
  504. 	
  505. 	
  506. 	
  507. 	
  508. 	
  509. 	}
  510. 	while(stdcomb::next_combination(smallListOptions.begin (),smallListOptions.end (),smallList.begin (),smallList.end()) );
  511. 	
  512. 	
  513. 	
  514. 	
  515. 	
  516. 	
  517. 	
  518. 	  
  519. 	  
  520. 	  
  521. 	  
  522. 	  
  523. 	return count;
  524.   }
  525.   
  526.   else if(dec==1)   //decreasing
  527.   {
  528. 	
  529. 	
  530. 	
  531. 	
  532. 	
  533. 	
  534. 	
  535. 	
  536. 	if(DEBUG)  printf("in decreasing \n");
  537. 	
  538. 	
  539. 	vector <int> smallListOptions;
  540. 	for (int i=0; i<list.size(); i++) 
  541. 	  if(list[i]<prev)
  542. 		smallListOptions.push_back(list[i]);
  543.  
  544. 	if(DEBUG)  printf("small list :");
  545. 	print(smallListOptions);
  546. 	if(smallListOptions.size() < B[cse]-1)
  547. 	  return 0;
  548. 	vector<int> smallList;
  549. 	for(int i=0; i<B[cse]-1;i++)
  550. 	  smallList.push_back(smallListOptions[i]);
  551. 	if(DEBUG)  printf("small list :");
  552. 	for(int i=0; i<smallList.size();i++)
  553. 	  if(DEBUG)  cout<< smallList[i]<< " ";
  554. 	if(DEBUG)  cout<<endl;
  555. 	
  556. 	
  557. 	do
  558. 	{
  559. 	  if(DEBUG)  printf("Combinations:");
  560. 	  display(smallList.begin(),smallList.end());
  561. 	  
  562. 	  
  563. 	  
  564. 	  set<int> listset;
  565. 	  if(list.size()!=0)
  566. 	  for (int i=0; i<list.size(); i++) 
  567. 		listset.insert(list[i]); 
  568. 	  if(DEBUG)  printf("listset : ");
  569. 	  print(listset);
  570. 	  
  571. 	  if(smallList.size()!=0)
  572. 	  for (int i=0; i<smallList.size(); i++) 
  573. 		listset.erase(smallList[i]);
  574. 	  if(DEBUG)  printf("smallList : ");
  575. 	  print(smallList);
  576. 	  
  577. 	  vector<int> restlist;
  578. 	  for (set<int> :: iterator p = listset.begin(); p!= listset.end(); p++) 
  579. 		restlist.push_back(*p);
  580. 	  if(DEBUG)  printf("restlist : ");
  581. 	  print(restlist);
  582.  
  583. 	  
  584. 	  
  585. 	  
  586. 	  
  587. 	  
  588. 	  count += perm(cse+1, restlist, smallList[0],B);
  589. 	  
  590. 	  
  591. 	  //	  int perm(int cse, vector<int> list , int prev, vector<int> B )
  592. 	  
  593. 	  
  594. 	  //******************************
  595. 	  
  596. 	  
  597. 	  
  598. 	  
  599. 	  
  600. 	  
  601. 	  
  602. 	}
  603. 	while(stdcomb::next_combination(smallListOptions.begin (),smallListOptions.end (),smallList.begin (),smallList.end()) );
  604. 	
  605. 	
  606. 	
  607. 	
  608. 	
  609. 	
  610. 	
  611. 	
  612. 	
  613. 	
  614. 	
  615. 	
  616. 	
  617. 	
  618. 	
  619. 	
  620. 	
  621. 	
  622. 	
  623. 	
  624. 	
  625. 	
  626. 	
  627. 	return count;
  628.   }
  629.   
  630.   
  631.   
  632.  
  633.   
  634. }
  635.  
  636.  
  637.  
  638. int main()
  639. {
  640.   if(DEBUG)  printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
  641.  
  642.   int T;
  643.   cin>> T;
  644.   
  645.   for(int test=1; test<=T ; test++ )
  646.   {
  647. 	int N;
  648. 	int K;
  649. 	cin >> N;
  650. 	cin >> K;
  651. 	vector<int> list ;
  652. 	
  653. 	//input list
  654. 	for (int i=0; i<K; i++)
  655. 	{
  656. 	  int temp;
  657. 	  cin>>temp;
  658. 	  list.push_back(temp);
  659. 	}
  660. 	
  661. 	for (int i=0; i<list.size(); i++)
  662. 	  if(DEBUG)  printf("list[%d]=%d\n",i,list[i]);
  663.  
  664. 	
  665. 	//creating B
  666. 	vector<int> B;
  667. 	for(int i=0; i<K-1; i++)
  668. 	  B.push_back(list[i+1]-list[i]+1);
  669.   
  670. 	for (int i=0; i<B.size(); i++)
  671. 	  if(DEBUG)  printf("B[%d]=%d\n",i,B[i]);
  672.  
  673. 	
  674. 	
  675. //	for (int i=1; i<=N; i++)
  676. //	  list.push_back(i);
  677. 	
  678. 	
  679. 	int count=0;
  680. 	for (int i=1; i<=N; i++)
  681. 	{
  682. 	  list.erase (list.begin(),list.end());
  683. 	  for (int j=1; j<=N; j++)
  684. 	  {
  685. 		if(j!=i)
  686. 		  list.push_back(j);
  687. 	  }
  688. 	  
  689. 	  count += perm(0,list,i ,B);  
  690. 	  if(DEBUG)  printf("COUNT=%d\n",count);
  691. 	}
  692. 	
  693. 	//  printf("Case #%2d :%d\n\n\n",test, count);  
  694. 	printf("%d\n", count);  
  695.   }
  696.   
  697.   
  698.   return 0;
  699. }
  700.  
  701.  
  702.  
  703.  
  704.  
  705.  
  706.  
  707.  
  708. //
  709. //  perm(2,list,4);
  710.

Comments