How to find a corner test case for this problem?

Правка en6, от hhpuss12, 2024-02-20 19:54:39

You should find one array a of length n: a[1], a[2], ... , a[n] that satisfy k given constraints of 2 types:

1 x i : a[i] should not be x

2 x l r : there is at least one a[i] = x such that l <= i <= r

It is guaranteed to exist at least one, if there are multiple, you can output any. k <= 200 and n should be fairly small like under 20, tell me if you could still solve it for larger n

I've come up with this problem recently and for some reasons my backtracking solution runs fast as hell for any test cases that I've generated randomly and I've not come up with any better solution or tests. Can someone show me a corner test case to kill backtracking or maybe this is the best way to solve this problem?

Теги backtracking

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский hhpuss12 2024-02-20 19:54:39 2 Tiny change: 'not be x\n2 x l r ' -> 'not be x\n\n2 x l r '
en5 Английский hhpuss12 2024-02-20 19:53:10 173
en4 Английский hhpuss12 2024-02-20 19:04:17 47
en3 Английский hhpuss12 2024-02-19 17:26:50 6
en2 Английский hhpuss12 2024-02-19 17:26:15 9 (published)
en1 Английский hhpuss12 2024-02-19 17:25:32 810 Initial revision (saved to drafts)