How to find a corner test case for this problem?

Revision en3, by 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?

Tags backtracking

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English 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 English hhpuss12 2024-02-20 19:53:10 173
en4 English hhpuss12 2024-02-20 19:04:17 47
en3 English hhpuss12 2024-02-19 17:26:50 6
en2 English hhpuss12 2024-02-19 17:26:15 9 (published)
en1 English hhpuss12 2024-02-19 17:25:32 810 Initial revision (saved to drafts)