“How do I know the test is of 4th type?” - Consider the set of all values present in input. If the size of this set is < 3*n-10, then the test is of 4th type. (The value 10 is not special, anything in [0,20] should work with high probability too.)
“How many tests did you try?” - How many do you want me to try? Let’s consider this submission (the one with ~22700 score during contest, now 85533: https://www.codechef.com/viewsolution/26589357).
This score 85533 means that both tests of 4th type scored ~ 5533/2 = 2766.5.
Now, if I run that solution through 100 tests, I get the following scores (sorted the order for convenience): http://ideone.com/fZjzxj
The smallest score out of 100 tests is 3377, total score 466227. I think this proves that:
“With very high probability, my test generator is different from official generator.”
Hence the question - what am I doing differently?
@aryanc403 - thanks!
I modified your generator to not ignore that rule and to output 100 tests of type 4: http://ideone.com/GZnwcv (it also ran infinitely long initially - so I added a similar weird search)
And ran those 100 tests on my code too: http://ideone.com/z7uF5v
Now these tests seem even harder on average - min score 3700, total score over 100 tests 491406.
The search continues: could someone provide a generator where this solution scores ~2700 on average like it does in official tests?
Are the official tests of 4th type wrong (by wrong I mean “not generated using the pseudocode described in problem statement”) or am I doing something dumb?