Блог пользователя LIFE_GOES_ON

Автор LIFE_GOES_ON, история, 4 года назад, По-английски

Please anyone help me with this 98A - Help Victoria the Wise . I do not understand how the solution of editorial is approached.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

:(

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Writing editorial is difficult for me too.

set<string> ans
string S(input)
For Each of 720 permutations
    string tmp = "ZZZZZZ"
    For Each of 24 rotations
        tmp = min(tmp, rotation(permutation(S)))
    Next
    ans.insert(tmp)
Next
print ans.size()
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится
Main code

Link to AC submission

Take a cube and label it as follows.
Up, down : 0, 1
Front, Back : 2, 3
Left, Right : 4, 5

Now, we have 3 different kinds of rotations, each rotation has one of the above pairs fixed and the remaining ones complete some circles.

Say we have {1, 2, 3, 4} as an array. Then one rotation gives {2, 3, 4, 1}. Similarly, the positions for rotation as per the above notation are {0, 2, 1, 3}, {0, 4, 1, 5}, {2, 4, 3, 5}.

It is obvious that only 3 rotations are possible and 4th rotation gives us the original array.

So here's what I did :

  • Sort the initial string

  • Go through its permutations

  • Rotate each of its permutations along each of the 3 axes up to a maximum of 3 times(64 in total)

  • See if at least one of them already exists in the set

  • If it doesn't then increase the answer by 1

  • Push all the rotations of the current permutation into a set