Help on set problem - Codeforces

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

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

5 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