fork download
copy 
  1. import java.util.Random;
  2.  
  3. public class Subrectangle {
  4. 	public int minMissed(String S) {
  5. 		int N = S.length();
  6. 		boolean[] isBlack = new boolean[N];
  7. 		for(int i = 0; i < N; ++i)
  8. 			isBlack[i] = S.charAt(i) == '#';
  9. 		int first_black = 0;
  10. 		while(first_black < N && !isBlack[first_black]) ++first_black;
  11. 		if(first_black == N) return 1;
  12. 		int last_black = N - 1;
  13. 		while(!isBlack[last_black]) --last_black;
  14. 		int answer = -1;
  15. 		for(int b = 1; b <= N; ++b)
  16. 			for(int w = 0; w <= N; ++w) {
  17. 				int added = 0;
  18. 				for(int i = first_black; i <= last_black;) {
  19. 					if(w == 0 && !isBlack[i]) {
  20. 						added = -1;
  21. 						break;
  22. 					}
  23. 					int need = b;
  24. 					while(need > 0 && i < N && isBlack[i]) {
  25. 						--need;
  26. 						++i;
  27. 					}
  28. 					added += need;
  29. 					if(i > last_black) break;
  30. 					need = w;
  31. 					while(need > 0 && i < N && !isBlack[i]) {
  32. 						--need;
  33. 						++i;
  34. 					}
  35. 					added += need;
  36. 				}
  37. 				if(added == -1) continue;
  38. 				int W = b + w;
  39. 				int start = first_black % W;
  40. 				if(start + b > W)
  41. 					added += W - start;
  42. 				int area = S.length() + added;
  43. 				if(area % W != 0)
  44. 					added += W - area % W;
  45.  
  46. 				if(answer == -1 || added < answer)
  47. 					answer = added;
  48. 			}
  49. 		return answer;
  50. 	}
  51.  
  52. 	boolean containsSubsequence(String A, String B) {
  53. 		int j = 0;
  54. 		for(int i = 0; i < A.length(); ++i)
  55. 			if(j < B.length() && A.charAt(i) == B.charAt(j))
  56. 				++j;
  57. 		return j == B.length();
  58. 	}
  59.  
  60. 	// brute force
  61. 	int slow(String S) {
  62. 		for(int area = 1; ; ++area)
  63. 			for(int H = 1; H <= area; ++H) if(area % H == 0) {
  64. 				int W = area / H;
  65. 				for(int r1 = 0; r1 < H; ++r1)
  66. 					for(int r2 = r1; r2 < H; ++r2)
  67. 						for(int c1 = 0; c1 < W; ++c1)
  68. 							for(int c2 = c1; c2 < W; ++c2) {
  69. 								String A = "";
  70. 								for(int row = 0; row < H; ++row)
  71. 									for(int col = 0; col < W; ++col) {
  72. 										if (r1 <= row && row <= r2 && c1 <= col && col <= c2)
  73. 											A += '#';
  74. 										else
  75. 											A += '.';
  76. 									}
  77. 								if(containsSubsequence(A, S))
  78. 									return area - S.length();
  79. 							}
  80. 			}
  81. 		// unreachable
  82. 	}
  83. }
  84.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:3: error: class Subrectangle is public, should be declared in a file named Subrectangle.java
public class Subrectangle {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/Zk5mi0
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

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!