You are not logged in. Please login at www.codechef.com to post your questions!

×

Test cases to prove the solution will TLE

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 :)

asked 14 Jun '17, 19:35

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

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".

(14 Jun '17, 19:41) likecs6★

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?

link

answered 14 Jun '17, 20:15

sanket_markan's gravatar image

6★sanket_markan
361
accept rate: 100%

@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.

(14 Jun '17, 20:41) likecs6★

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

link

answered 14 Jun '17, 20:19

fallandrise's gravatar image

4★fallandrise
2628
accept rate: 20%

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

(14 Jun '17, 20:28) fallandrise4★
1

@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).

(14 Jun '17, 20:46) likecs6★

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

(14 Jun '17, 20:50) fallandrise4★

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 ?

(14 Jun '17, 20:53) godslayer121★
1

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).

(14 Jun '17, 20:54) fallandrise4★
1

@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.

(14 Jun '17, 21:01) fallandrise4★

Frickin awesome dude!! Seriously awesome!!

(14 Jun '17, 21:06) vijju123 ♦♦5★
1

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

(14 Jun '17, 21:07) likecs6★
2

@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.

(14 Jun '17, 21:23) fallandrise4★

Hey thanks both of you.

(14 Jun '17, 21:25) godslayer121★
showing 5 of 10 show all

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

Code

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

link

answered 14 Jun '17, 20:30

vsp4's gravatar image

6★vsp4
1.2k138
accept rate: 28%

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

(14 Jun '17, 20:49) likecs6★

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.

link

answered 14 Jun '17, 20:24

hruday968's gravatar image

4★hruday968
1.7k210
accept rate: 14%

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 ?

link
This answer is marked "community wiki".

answered 15 Jun '17, 12:20

vishesh_345's gravatar image

1★vishesh_345
2567
accept rate: 8%

edited 15 Jun '17, 12:34

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.

link

answered 15 Jun '17, 13:05

liaojh's gravatar image

5★liaojh
1825
accept rate: 7%

edited 15 Jun '17, 13:08

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,424
×365
×33

question asked: 14 Jun '17, 19:35

question was seen: 717 times

last updated: 15 Jun '17, 13:08