Help on set problem - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	Um_nik	3396

#	User	Contrib.
1	Um_nik	164
2	cry	160
2	maomao90	160
4	-is-this-fft-	159
5	atcoder_official	158
5	awoo	158
7	adamant	155
8	nor	154
9	maroonrk	152
10	Dominater069	149

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

from collections import defaultdict, deque

UD = 0 # Up-Down, lamp is vertical
LR = 1 # Left-Right, lamp is horizontal

n, r, k = map(int,input().split()) 
idxToPt = defaultdict(tuple)
for i in range(k):
    ptX, ptY = map(int, input().split())
    idxToPt[i + 1] = (ptX, ptY)
g1 = {i: [] for i in range(1, k + 1)}
g2 = {i: [] for i in range(1, k + 1)}

for i in range(1, k + 1):
    for j in range(i + 1, k + 1):
        x1, y1 = idxToPt[i]
        x2, y2 = idxToPt[j]
        # same x coordinate: check y coordinate for UD conflict
        if x1 == x2:
            if abs(y1 - y2) <= 2 * r:
                g1[i].append(j)
                g1[j].append(i)
        if y1 == y2: # same y coordinate: check x coordinate for LR conflict
            if abs(x1 - x2) <= 2 * r:
                g2[i].append(j)
                g2[j].append(i)

def bfs(start):
    color[start] = 0
    q = deque([start])
    while q:
        current = q.popleft()
        # assert color[current] != -1 # will cause runtime error if false
        if color[current] == UD:
            for neighbor in g1[current]:
                if color[neighbor] == -1:
                    color[neighbor] = LR # 1 - color[current] also works
                    q.append(neighbor)
                elif color[neighbor] == UD: # can't have both UD in graph 
                    return False
        else: # color[current] is 1
            for neighbor in g2[current]:
                if color[neighbor] == -1:
                    color[neighbor] = UD
                    q.append(neighbor)
                elif color[neighbor] == LR: # can't have both LR in graph 2
                    # print(current, neighbor)
                    return False
    return True

color = [-1] * (k + 1)
for i in range(1, k + 1):
    if color[i] == -1:
        res = bfs(i)
        if not res:
            # print(color)
            print(0)
            exit()
print(1)

Any help would be appreciated!

Comments (1)

Write comment?

Neko1i3

3 months ago, # |

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).

→ Reply

MutedSolace's blog