a7mads3ed's blog

By a7mads3ed, history, 4 years ago, In English,

How can I solve Problem 275A ? http://codeforces.com/problemset/problem/275/A

  • Vote: I like it
  • -1
  • Vote: I do not like it

4 years ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

Consider a simpler problem:

Every time you press a light only the light pressed will be toggled.

Now it is obvious that if a light is pressed event number of times it will be in it's initial state (ON).

Now to solve the initial problem:

Let pressed[3][3] be the initial matrix and toggled[3][3] the matrix of total lamp presses.

In the beginning pressed[][] = toggled[][].

Now if pressed[i][j] != 0 then we have to add pressed[i][j] to toggled[i][j + 1], toggled[i][j - 1], toggled[i - 1][j] and toggled[i + 1][j]. Now we are left with the first, much simpler problem.

But be careful when handling edge lamps.

My solution (see how I handle edge lamps): http://codeforces.com/contest/275/submission/20742578

I hope I helped you.

  • »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is the same idea, but with different implementation. well, just consider it as another reference, haha :)


    Hope this helps :)

  • »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot, Buddy!