fork download
copy 
  1. /*
  2. 	----IIT(ISM) Dhanbad----
  3. 	Author: Siddhant Choudhary
  4.  
  5. 	--samsumg coding test--
  6.  
  7. 	Q.There is a large plot with various sinkholes present. 
  8. 	Since one sinkhole can combine with another sinkhole, it is required to get
  9. 	at most one sinkhole while occupying the plot. You have to find the maximum 
  10. 	square-area formed with at most one sinkhole present.
  11. 	If there are two plots with the same area then print the one with 
  12. 	lesser sinkhole present otherwise if the sinkholes are also same then print
  13. 	anyone. For each case, you have to print the bottom leftmost coordinate and 
  14. 	top rightmost point. Please keep in mind that the plot starts with (1, 1).
  15.  
  16. 	Time limit= 1sec and Memory limit– 256Mb
  17.  
  18. 	Input: First line will give the number of test cases. For each test case, we
  19. 	will be given the size of the plot matrix N x M (where 1<=N, M<=1000). Next
  20. 	line will give the number of sinkholes present in the matrix K (1<=K<=N+M). 
  21. 	Next, K-lines will give the coordinates of the sinkholes.
  22.  
  23. 	Output: For each test case, you have to print the number of the test case
  24. 	and the coordinates of the resultant square.
  25. 	i.e. #i xb yb xt yt (ith test case, xb=bottomost left x-coordinate, 
  26. 	yb=bottomost  left y-coordinate, xt= topmost right x-coordinate,
  27. 	yt= topmost right y-coordinate)
  28.  
  29.   *	time complexity of my approach = O(n*m*log(min(m,n))) *
  30. */
  31.  
  32. #include <iostream>
  33. using namespace std;
  34.  
  35. #define INT_MAX 100000;
  36.  
  37. int xb,yb,xt,yt;
  38.  
  39. int fun(int dp[][1001], int N, int M, int k){
  40. 	int msum = INT_MAX;
  41. 	for(int i=0; i<=N-k; i++){
  42. 		for(int j=0; j<=M-k; j++){
  43. 			int sum = dp[i+k][j+k]-dp[i+k][j]-dp[i][j+k]+dp[i][j];
  44. 			if(sum < msum){
  45. 				msum = sum;
  46. 				if(msum <=1){
  47. 					xb = i+k;
  48. 					yb = j+1;
  49. 					xt = i+1;
  50. 					yt = j+k;
  51. 				}
  52. 			}
  53. 		}
  54. 	}
  55. 	return msum;
  56. }
  57.  
  58. int main() {
  59. 	ios_base::sync_with_stdio(0);
  60. 	cin.tie(0);
  61. 	/* input */
  62. 	int N,M;
  63. 	cin>>N>>M;
  64. 	int A[N][M];
  65. 	for(int i=0; i<N; i++){
  66. 		for(int j=0; j<M; j++){
  67. 			A[i][j]=0;
  68. 		}
  69. 	}
  70. 	int K;
  71. 	cin>>K;
  72. 	for(int i=0; i<K; i++){
  73. 		int x,y;
  74. 		cin>>x>>y;
  75. 		A[x-1][y-1]=1;
  76. 	}
  77.  
  78. 	int dp[1001][1001]; /* dp[i][j] = sum of submatrix top-left(0,0) to bottom-right(i,j) */
  79. 	for(int i=0; i<1001; i++){
  80. 		for(int j=0; j<1001; j++){
  81. 			dp[i][j]=0;
  82. 		}
  83. 	}
  84. 	for(int i=1; i<=N; i++){
  85. 		for(int j=1; j<=M; j++){
  86. 			dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+A[i-1][j-1];
  87. 		}
  88. 	}
  89. 	/* applying binary search */
  90. 	int l=1, r=min(M,N);
  91. 	int ones;
  92. 	while(l<r){
  93. 		int mid = (l+r)/2;
  94. 		ones = fun(dp,N,M,mid);
  95. 		//if no. of ones > 1 means we need to decrease the submatix size 
  96. 		if(ones >1){
  97. 			r = mid;
  98. 		}
  99. 		//else increase the submatrix size
  100. 		else{
  101. 			l = mid+1;
  102. 		}
  103. 	}
  104. 	/* output */
  105. 	cout<<xb<<" "<<yb<<" "<<xt<<" "<<yt<<endl;
  106. 	return 0;
  107. }
Success #stdin #stdout 0.01s 7468KB
comments (?)
stdin
copy 
6 6
4
1 1
3 3
4 4
6 6
stdout
copy 
3 4 1 6
https://ideone.com/nVjQrp
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!