Test cases to prove the solution will TLE

general
, ,
1

In the recently concluded Long challenge, in the problem “CLONEME”, I wrote an optimal brute force solution. The solution is as follows :

  • I stored the prefix sum, sum of square and sum of cubes of elements in an array.
  • Check if the 2 subarrays are permutation of each other or not. For this simply check if the sum, sum of squares, sum of cubes etc are exactly same are not.
  • Now, we need to deal with one mismatch only. Now, I found the difference of sum and sum of sqaures of 2 subarrays. If only one element mismatches(let them be a and b, then we have the following equations :

S_1 - S_2 = a - b and {S_1}^2 - {S_2}^2 = a^2 - b^2.

Then a + b = \frac{{S_1}^2 - {S_2}^2}{S_1 - S_2} i.e. {S_1}^2 - {S_2}^2 should be divisble by S_1 - S_2.

Also, if S_1 == S_2, this means atleast 2 elements differ as, there not permutation as assured by the prefix sums checked above.

  • Now, using difference in sum of cubes in the 2 subarrays, I confirm again if the 2 elements I found are valid out. i.e if the difference of the sum of cubes of 2 subarrays is exactly equal to the difference of the cube of the 2 numbers found.

  • If all the above methods fails, I simply do a brute force algorithm, i.e. construct the 2 subarrays, sort them and then check if they mismatch at one position only.

I had tried to construct test cases such that my solution TLE, but was unsuccessful. Can someone here would like to challenge my solution for the problem ?

Remember, that almost all the queries should be different as I should cache the previous queries answer which is generally used and such test cases are avoided by making problem. (i.e. if you find a particluar query for which my solution will execute the brute force solution, then do not give the same query again and again in the test case).

Happy coding :slight_smile:

2 Likes
2

An extra comment regarding the solution. After the above process, we can’t skip the brute force solution as the element we may have found may differ in the position in sorted array (if the question was about check if the subarrays differ in 1 position without any sorting i.e. they are almost permutation, then we could have brute force and simply answered as “YES” i.e. O(1) per query) ). For example let the 2 number found the above process are 1 and 4, and the subarrays be [1, 3] and [3, 4]. then the ans is “NO”.

3

This is not at all the correct approach.
Since there are many arrays whose sum, sum of squares and sum of cubes are equal.

Consider the query on below two subarrays:
i) 1 4 6 7 10 11 13 16
ii) 2 3 5 8 9 12 14 15

Your solution will give answer “YES”. Clearly this is not the answer.

I have seen this approach in many solutions, Am i missing anything?

2 Likes
4

Here we go: input.txt

Generator:https://ideone.com/QFoYPb

Output of time command:

chaitanya@cpu:/tmp$ time ./sol < input.txt > /dev/null

real	1m23.091s
user	1m22.396s
sys	    0m0.564s
2 Likes
5

i don’t know whether your code fails for some test cases or not,but your approach was pretty awesome.From this post i came to know that we should try to do the question using various techniques.

6

With the given A array and queries(generated randomly), there is a high chance that none of your if statements satisfies.

7

So overall you need to get the cases having atleast one difference but produces Yes as output to get the above method to tle (and with distinct queries)

Eg: 1 2 3 4 6 1 2 3 4 7

Queries like:

  • 5 5 10 10
  • 4 5 9 10
  • 3 5 8 10
  • …

This could easily make it n^2*logn


[1]

There should have been strong cases that had majority tests having 1 element difference. But it looks like weak test cases.

  [1]: http://ideone.com/NH4aIi
2 Likes
8

@sanket_markan, you are right, my solution is wrong. But many a times, it is tough to generate random test cases against hashing based solution. They can be hacked only after seeing the solution.

9

@fallandrise, you are correct. My solution will TLE for this test case. But the solution takes, 2.3129 sec on my machine (with -O2 optimisation, without -O2 also, it takes 11.328 sec). I would recommend you to use clock() to measure more accurate time for your solution, instead of “time” whose value can vary sometimes largely due to other operations going on. (Also, I think you ran my solution without any flags while compilation, which is also such a large difference in timing reported).

1 Like
10

@vsp4, this was exactly I was looking for. Thank you for providing the test case.

11

Oh yeah, I didn’t compile with O2 flag. And thanks for suggestion.

12

Hey @fallandrise, i’ve seen your answers giving test cases and execution times on many threads, what tool you’re using for generation and analysis ?

13

The “time” and “clock()” almost returns the same time. which is around 6 seconds in my system with O2 flag. perhaps it depends largely on system as well as other processes(% of cpu got and so on).

1 Like
14

@godslayer12 For generating the test cases, this is my thought process – I go through the code and look for time complexity of the solution and any un-handling of any edge cases(corner cases) and so on. If I find any, I create tests for that. But if I couldn’t, I write a generator to generate the test cases(which are completely random) to see if the solution fails.

Previously I used to do this on topcoder practice rooms(where we can hack other inefficient and wrong solutions) while I was practising. And that’s where I learnt this skill.

1 Like
15

Frickin awesome dude!! Seriously awesome!!

16

@godslayer, you can also find my testcase generators here. For checking the time, you can check this out.

1 Like
17

@likecs For generating tests, I prefer python because it is pretty easy to write the generator and it happened to me many times that while I was stress testing my code, python tests were able to catch the error(s) in my code than tests generated using C++. Anyway it’s up to the user to choose the language but I just wanted to share my experience and opinion.

2 Likes
18

Hey thanks both of you.

19

I have a doubt

  1. If S1==S2 and (S1^2!=S2^2 or S1^3!=S2^3) that means we have at least 2 elements different so ans is NO.
  2. If S1!=S2 or S1^2!=S2^2 or S1^3!=S2^3 that means they are not permutation of each other, so answer is to be calculated using brute force.
  3. If all they are same that means they are permutation of each other so YES.

I understood this part( please correct if wrong) but for the 1 mismatch case the two conditions you stated

  1. S1-S2 = a-b and S1^2-S2^2 = a^2-b^2 I did not get this. This means that S1+S2 = a+b (if S1-S2 != 0) but that is not true is it? because a and b are elements and S1 and S2 are sum.

Can you please explain this.

I guess you are using brute force every time you come to know that its type of at least 1 mismatch. Am I right ?

20

For a better hashing method, instead of using sum of cubes, use prefix product.

To reverse the prefix product for a subarray product, use Fermat’s little theorem for modular multiplicative inverses.

Feel free to ask questions if you don’t understand this approach.