Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

MutedSolace's blog

By MutedSolace, history, 5 weeks ago, In English

problem link: https://open.kattis.com/problems/illumination

I think this problem simplifies down to putting k elements into 2 sets given conditions in the format of either:
1. x and y cannot both be in set 1
2. x and y cannot both be in set 2
where set 1 represents lamps oriented vertically and set 2 represents lamps oriented horizontally.

So far I have tried a bfs bipartite-like approach but it's getting WA on TC 9/43:

My Code

Any help would be appreciated!

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This looks to me like a standard 2-SAT problem. Every lamp has to be either horizontal or vertical, if one lamp is horizontal then some other lamps in the same row must be vertical and vice versa. If you worry about TLE then you could do the full binary tree trick (1903F - Babysitting).