197 - Cube

[epsilon0]

(way) down this board i saw someone say the output had to be sorted but it doesn't say so in the problem...

also, is there a trick to solve this problem faster? since the judge allows 600 seconds, i suppose not.... but i still got TLE

[Ivor]

if you read it the topic carefully, Ivan (if I remeber it correctly) also mentioned that the output does not have to be sorted. Elsewise why's the yellow checkmark for? And why do you think there's 600 seconds of time limit?? Take a look at the rank -- you'll see a time beyond 9 minutes!! And if you look at the date, you'll see that it was after the introduction of the ten seconds limit.

And there is a way of solving it very quickly, but I ain't gonna share it.

Happy solving,
Ivor

[Ivan Golubev]

Yes, I've firstly wrote that output must be sorted (because I forget about correction program) but then I've corrected this -- output need not to be sorted.

About speed-up -- you need to calculate all possible assemblies only once. So, short algorithm:
1. Fix part 'a' to translation only and generate all possible assemblies (480 variants).
2. Rotate each of these assemblies (24 ways to rotate cube) to get all possible states when part 'a' isn't fixed (so, total 11520 variants).
3. Now easily search this array to match with input and output correct 480 strings.

Part 1 can be precomputed and submitted in the source code, part 2 & 3 won't take too much time, so you can easily AC in less than a second.

[Jan]

I am getting WA, but not understanding why. Is there any trick? Can anybody resubmit the problem just to be sure that the judge is correct?
Thanks.

[mf]

I've resubmitted my old solution, and it gets accepted.

[Jan]

Thanks mf. Got accepted.