Color Grid algorithm
I just came across a problem on a website that I am trying to solve now. Here's the problem.
You are given an N×N grid. Each cell has the color white (color 0) in the beginning.
Each row and column has a certain color associated with it. Filling a row or column with a new color V means changing all the cells of that row or column to V (thus overriding the previous colors of the cells).
Now, given a sequence of P such operations, calculate the sum of the colors in the final grid. Operations can be like COL 1 6 meaning, Fill Col 1 with 6. Likewise for rows.
Fairly simple problem in my opinion but my solution don't seem to be accepted. Clearly I am missing something. Here's what I have tried so far. Initialize a flag for each row and column with false(not filled). Keep a track of number of col and rows filled. Now start with the last operation(from reverse).
If its an operation on column, check if that col was previously filled before, ie., check the flag of that column. If it wasn't, check the number of rows filled. Now sum = sum + (N - rows_filled) * (Number to be filled in the column). Update flag of the column to true implying filled. Increment column-filled by one . If the column was filled before, continue to next operation. The same logic applies to row operations as well. This goes on until number of rows filled = number of columns filled = N or until all operations are processed.
Can anyone help me find out, what is wrong with this logic? If you have a better approach to this problem, do share as well.
The problem is that Integer only handles 32bit integers, so your computation overflows.
Note that:
(576055795*10)%2**32 = 1465590654
Long handles 64bit integers so works correctly.
It looks like you're trying to solve the [IOI] Color Grid problem at HackerRank. Since the contest has ended already, I suppose it's OK to discuss solutions.
You need to play closer attention to the constraints for this problem:
1 <= N <= 6000 # Grid size
1 <= P <= 400000 # Number of paint operations
Notice that P is potentially many times larger than N, in which case nearly all of the paint operations will have zero effect on the end result, because they will be painted over in subsequent operations on the same row or column.
If you try to calculate the consequences of each operation, your code will time out before reaching a solution. Instead, you should concentrate on disregarding operations that have no net effect.
You could do this by, for example, memorizing the last operation performed on each row and column, and only calculating the effects of these operations after you've exhausted all the input data.
(And as @Peter de Rivaz pointed out, you have to add up the cell values in a 64-bit accumulator to avoid overflows.)
链接地址: http://www.djcxy.com/p/63842.html上一篇: 从左列到右列找出矩阵的最大总和路径？
下一篇: 颜色网格算法