LIFE_GOES_ON's blog

By LIFE_GOES_ON, history, 4 years ago, In English

Please anyone help me with this 98A - Помогите Василисе Премудрой . I do not understand how the solution of editorial is approached.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

:(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it
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