hhpuss12's blog

By hhpuss12, history, 3 months ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +24
  • Vote: I do not like it