nahnahinin
Junior Member
Lại nháp là ra nhé các thím, nghĩ nát óc không ra đâu ![sweat :sweat: :sweat:](https://data.voz.vn/styles/next/xenforo/smilies/popopo/sweat.png?v=01)
![sweat :sweat: :sweat:](https://data.voz.vn/styles/next/xenforo/smilies/popopo/sweat.png?v=01)
Xịn vãi, Q4 no idea luôn.
bài này vẽ hình chia case siêu dễ, chẳng cần nghĩ vẹo gì, nhìn theo hình để code.Xịn vãi, Q4 no idea luôn.
Có 2 người a/e VN xong Q4, người anh em là phungtienminh hay nguyenquocthao thếbài này vẽ hình chia case siêu dễ, chẳng cần nghĩ vẹo gì, nhìn theo hình để code.
Lúc đầu em nghĩ ác lắm, 10ph sau ngồi vẽ hình ra code 20ph là xong![]()
em không để location, acc clone để cày cho đẹpCó 2 người a/e VN xong Q4, người anh em là phungtienminh hay nguyenquocthao thế![]()
Thi xong bác guide ae cách nháp vớibài này vẽ hình chia case siêu dễ, chẳng cần nghĩ vẹo gì, nhìn theo hình để code.
Lúc đầu em nghĩ ác lắm, 10ph sau ngồi vẽ hình ra code 20ph là xong![]()
Ý tưởng là thử hết combinations của 3 hình chữ nhật ko bị overlap với nhau đúng ko fence
class Solution {
public int[] minimumArea(int[][] grid, int li, int ri, int lj, int rj) {
int minI = grid.length, maxI = -1;
int minJ = grid[0].length, maxJ = -1;
int count = 0;
for (int i = li; i <= ri; i++) {
for (int j = lj; j <= rj; j++) {
if (grid[i][j] == 1) {
minI = Math.min(minI, i);
maxI = Math.max(maxI, i);
minJ = Math.min(minJ, j);
maxJ = Math.max(maxJ, j);
count++;
}
}
}
return new int[]{minI, maxI, minJ, maxJ, count};
}
int calArea(int[] area) {
return (area[1]-area[0]+1)*(area[3]-area[2]+1);
}
public int minimumSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] bound = minimumArea(grid, 0, m-1, 0, n-1);
int minI = bound[0];
int maxI = bound[1];
int minJ = bound[2];
int maxJ = bound[3];
int count = bound[4];
int ans = Integer.MAX_VALUE;
for (int i = minI; i < maxI; i++) {
var area1 = minimumArea(grid, minI, i, minJ, maxJ);
if (area1[4] >= count-1) {
continue;
}
for (int ii = i+1; ii < maxI; ii++) {
var area2 = minimumArea(grid, i+1, ii, minJ, maxJ);
if (area1[4] + area2[4] >= count) {
continue;
}
var area3 = minimumArea(grid, ii+1, maxI, minJ, maxJ);
ans = Math.min(ans, calArea(area1) + calArea(area2) + calArea(area3));
}
for (int j = minJ; j < maxJ; j++) {
var area2 = minimumArea(grid, i+1, maxI, minJ, j);
if (area1[4] + area2[4] >= count) {
continue;
}
var area3 = minimumArea(grid, i+1, maxI, j+1, maxJ);
ans = Math.min(ans, calArea(area1) + calArea(area2) + calArea(area3));
}
}
for (int i = minI+1; i <= maxI; i++) {
var area1 = minimumArea(grid, i, maxI, minJ, maxJ);
if (area1[4] >= count-1) {
continue;
}
for (int j = minJ; j < maxJ; j++) {
var area2 = minimumArea(grid, minI, i-1, minJ, j);
if (area1[4] + area2[4] >= count) {
continue;
}
var area3 = minimumArea(grid, minI, i-1, j+1, maxJ);
ans = Math.min(ans, calArea(area1) + calArea(area2) + calArea(area3));
}
}
for (int j = minJ; j < maxJ; j++) {
var area1 = minimumArea(grid, minI, maxI, minJ, j);
if (area1[4] >= count-1) {
continue;
}
for (int jj = j+1; jj < maxJ; jj++) {
var area2 = minimumArea(grid, minI, maxI, j+1, jj);
if (area1[4] + area2[4] >= count) {
continue;
}
var area3 = minimumArea(grid, minI, maxI, jj+1, maxJ);
ans = Math.min(ans, calArea(area1) + calArea(area2) + calArea(area3));
}
for (int i = minI; i < maxI; i++) {
var area2 = minimumArea(grid, minI, i, j+1, maxJ);
if (area1[4] + area2[4] >= count) {
continue;
}
var area3 = minimumArea(grid, i+1, maxI, j+1, maxJ);
ans = Math.min(ans, calArea(area1) + calArea(area2) + calArea(area3));
}
}
for (int j = minJ+1; j <= maxJ; j++) {
var area1 = minimumArea(grid, minI, maxI, j, maxJ);
if (area1[4] >= count-1) {
continue;
}
for (int i = minI; i < maxI; i++) {
var area2 = minimumArea(grid, minI, i, minJ, j-1);
if (area1[4] + area2[4] >= count) {
continue;
}
var area3 = minimumArea(grid, i+1, maxI, minJ, j-1);
ans = Math.min(ans, calArea(area1) + calArea(area2) + calArea(area3));
}
}
return ans;
}
}
Chuẩn rồi, tính hết combination độ phức tạp là O(n^2). Sau đó trong mỗi hình nhỏ thì dùng lại code bài 3 để tính, cái đó O(n^2) nữa. Tổng hợp là O(n^4). n = 30 nên vẫn pass,Ý tưởng là thử hết combinations của 3 hình chữ nhật ko bị overlap với nhau đúng ko fenceimplement ăn bọ quá
Tính ra t làm y chang ntn luôn đó,
Sáng 3Q 30ph ăn rank 11k đây fencehôm qua em 3Q 20p 1 bọ thì rank 11k, nay 3Q 1h25' 6 bọ thì rank 6k![]()
Xem cái trừ 30₫ ở đâu thế?Sáng 3Q 30ph ăn rank 11k đây fencebị trừ 30 điểm
Hên chứ ko xuống làm vozliz luôn rồi
via theNEXTvoz for iPhone
Xem cái trừ 30₫ ở đâu thế?
ko nhé bác, mới check ac thằng bạn guardian rank 1k2 , rating 2k2 ko biến đổi gì lắmMấy bác cho e hỏi tầm rank 900-1500 thì gần guardian nó có cộng k mấy bác, em làm contest thường trong khoảng rank này. Giờ rating e tầm 2k hơn xíu tính hè cày cho trâu hẳn r đánh contest tiếp với dạo này cũng bận thi cử quá![]()