Could somebody share their test generator for challenge? The 4-th test set is confusing me: the way it is described:
“After generating the triples, try again if any of them have equal elements.”
seems to run very long for me. Even checking right after each triple seems to take forever. So instead I did some weird search:
“After generating each triple, if the triple has equal elements, try again and add +1 to count_mistakes. Start again from scratch if count_mistakes > 64.”
Now it generated the test fast, but it felt like my local 4-th type tests were somehow very different still compared to the one visible test of 4th type. (sometimes very different scores)
How do you know there is a 4th type test included in the 3 visible test files. Following up, how do you separate the score for only the 4th type test file?
If the test case is of 4-th type, solve it as best as I can.
If the test case is of another type, first solve it, and then append random operations until a total of 10000 operations have been made.
Since such a solution scored 22700 points, I made the conclusion that 4-th type existed and I scored 2700 on it.
But this looked wrong, as all my local tests were making 4000+ operations (why only 2700?! how is this possible?! :D)
Oh that’s interesting. Maybe it’s a case of infinite monkeys typing a Shakespearean soliloquy It’s possible that the test generated by the problem setter is a rare case where your algorithm works pretty well. How many tests did you try?
“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: CodeChef: Practical coding for everyone).
This score 85533 means that both tests of 4th type scored ~ 5533/2 = 2766.5.
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?
Wait, random shuffle?! I thought “Add the values in the three registers (in a fixed order) to the list L.” would mean the registers don’t get shuffled and just the value of third register is used every time. (exactly the same as pwild: CodeChef September Long Challenge 2019 - Codeforces)
Well, the scores make perfect sense now, thanks! I just think this random shuffle should’ve been explicitly mentioned in the problem statement - very unexpected.
Wait, I think there is more difference besides the random shuffle: I think you add all 3 registers as one tuple, then make 3 moves, then add another tuple with all 3 registers?!
In this case, wouldn’t a solution be:
set the registers to be equal to the first tuple
for each next tuple, try all possibilities of the next 3 moves in O(60^3)
Wouldn’t that give a solution for 4th type that uses only ~300 operations?
How I filled in the blanks for your generator: LzGXTn - Online C++0x Compiler & Debugging Tool - Ideone.com
And here is above solution that seems to solve using only ~300 op: http://ideone.com/cxHcHH
But it fails when submitting online Anyway is this supposed to be a valid approach? I’m doing something different again?!
During the contest, I made the same mistaken interpretation as pwild as to what case 4 was; I thought it was the same register R over time (so first test triple is [R(t=0), R(t=1), R(t=2)], then the next triple is [R(t=3), R(t=4), R(t=5)] and so on). andres96 is correct that with the given generator, a simple 60**3 search would suffice for every triple after the first. In fact, because many possible operations within the 3 alloted could cancel each other out (like two xors), my local testing has many instances where only 1 or 2 operations are required. Thus, I get scores in the 230-260 range. I have submitted a modified version to the practice room version of the challenge problem to take advantage, but scores aren’t being calculated so that I can prove that this is working.