Hi guys ! Please explain this problemproblem with its solution . Thanks in advance !!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hi guys ! Please explain this problemproblem with its solution . Thanks in advance !!
Название |
---|
You have an NxN grid with M elements scattered around inside of it, you're asked to move the least number of elements such that each cell in the grid have at most one element and all the elements are arranged in a way such that they form a rectangle
Solution:
First: what are the dimensions of said rectangle?
We can see that they are the divisors of M which are at most pairs, don't forget swapping width and hight
Second: which elements to move?
If we were to assume that our rectangle will occupy some arbitrary rectangle inside the grid, then the number of moves needed to rearrange the elements such that they would occupy that area is equal to E where E is number of empty squares in the rectangle
Third: which rectangle to pick?
The constrains are good enough for us to brute force all of them
We will do partial sums over 2D array of elements where grid[x][y] contains sum of empty squares in the rectangle designated by (1, 1)&(x, y)
With partial sums we can find number of empty squares anywhere in O(1) time
We have about rectangles, let's try every possible top-left point for each of them, no more than N2 points in worst case
So our solution will run in time
First lets change the statement, you are given the dimension (x,y) of the required rectangle (x * y = M). To solve this problem you can put the upper left corner of the rectangle in every cell of the given matrix and check how many cubes are inside of it. Suppose there are C cubes, then obviously the answer is M - C for this rectangle. Be careful with towers of cubes.
Having solved this problem, you can try all possible rectangles with dimensions (x,y) such that x * y = M and keep the one that requires the least amount of moves.
Thanks for this much clear explanation .