How to find a corner test case for this problem?

Правка en3, от hhpuss12, 2024-02-19 17:26:50

Given an array of n elements a[1], a[2], ... , a[n] (0 <= a[i] <= 9). There are k constraints of 2 types that the array must satisfy:

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

You should find any array that satisfy all k constraints (it is guaranteed to exist at least one). 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)