In the recently concluded Long challenge, in the problem "CLONEME", I wrote an optimal brute force solution. The solution is as follows :
$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.
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

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? answered 14 Jun '17, 20:15
@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)

Here we go: input.txt chaitanya@cpu:/tmp$ time ./sol < input.txt > /dev/null answered 14 Jun '17, 20:19
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)
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)
Oh yeah, I didn't compile with O2 flag. And thanks for suggestion.
(14 Jun '17, 20:50)
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)
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)
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 unhandling 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)
Frickin awesome dude!! Seriously awesome!!
(14 Jun '17, 21:06)
1
@godslayer, you can also find my testcase generators here. For checking the time, you can check this out.
(14 Jun '17, 21:07)
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)
Hey thanks both of you.
(14 Jun '17, 21:25)
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:
This could easily make it n^2*logn There should have been strong cases that had majority tests having 1 element difference. But it looks like weak test cases. answered 14 Jun '17, 20:30
@vsp4, this was exactly I was looking for. Thank you for providing the test case.
(14 Jun '17, 20:49)

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. answered 14 Jun '17, 20:24

I have a doubt
I understood this part( please correct if wrong) but for the 1 mismatch case the two conditions you stated 1. S1S2 = ab and S1^2S2^2 = a^2b^2 I did not get this. This means that S1+S2 = a+b (if S1S2 != 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

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. answered 15 Jun '17, 13:05

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