-emli-'s blog

By -emli-, history, 6 years ago, In English

How to solve D?

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What a interesting problem that is.

Spoiler
»
6 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    stefdasca How your idea will work to this test?

    3 3

    2 3 2

    2 2 2

    2 2 3

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      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

»
6 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can move only one coin in a single operation. Moving two or more coins from the same cell is forbidden.