hhpuss12's blog

How to find a corner test case for this problem?
By hhpuss12, history, 10 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?

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

»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

misread

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone has an answer yet?

→ Reply
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

What is the use of given array 'a' or we have to find 'a'?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry for my mistake, I've just edited the statement.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a O(nk²logk) solution, but I don't think so it's optimal, we can do it in better speed. Coming to corner cases I think test cases with suffled size of l-r in 2nd query might take much time I think

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Amazing! Can you show me your solution? And what do you mean by "test cases with shuffled size of l-r"? Do you have an example cause I've tried a lot (I tested it for nearly 100 times with different k and l-r sizes) and it still runs pretty fast?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My solution is: create an empty array and update every first query position with inf. Later store all 2nd queries in set with respect to there size. Create a Boolean array of size n, initially all are false then process with set that update first non-visited position in l-r and decrease all other l-r where this position in between them by 1. Repeat this for all Time complexity:O(nk²logk) And I think your solution is pretty clear for this problem, hence it's working fast. IDK apart from that

      → Reply