How to solve D?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
2 | maomao90 | 163 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
How to solve D?
Name |
---|
What a interesting problem that is.
...
If you have odd number in a[i][j], transfer 1 to a[i+1][j] or a[i][j+1], whichever is eligible
Just do this for each i <= n & j <= m, where n and m are dimensions of the matrix
stefdasca How your idea will work to this test?
3 3
2 3 2
2 2 2
2 2 3
That 1 from (1,2) will go to (2,2), (3,2) and (3,3), where it will be added to a[3][3] which is 3, therefore making all matrix full with even elements
The thing is that if sum of elements in a matrix is even, we can make it have just even elements by doing this strategy, because eventually, all 1's resulting from odd numbers will end up in some other square, situated in a bigger line and bigger column
If sum of elements is odd, we can do the same strategy too, but we will have exactly one odd element, because odd sum can't be formed by only even elements
I was at today's ABC, and i got AC on first try, using this idea
why adding all the non-zero numbers and put it to any one cell (let's say, the bottom right (h,w)) doesn't work? with this any odd number will paired with another odd number and make it even, and even+even still even, so the number of even number will be all cell (because we make all 0 except cell (h,w)) plus -1 if cell (h,w) is odd
give counter example pls, i cant find any..
EDIT: misread the problem, changed above algo to move one coin from all cell with odd number of coins to any one cell (mine to (h,w)) is accepted
You can move only one coin in a single operation. Moving two or more coins from the same cell is forbidden.