Help - Codeforces

LIFE_GOES_ON's blog

Help

By LIFE_GOES_ON, history, 6 years ago, In English

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

LIFE_GOES_ON
6 years ago
4

Comments (4)

Write comment?

LIFE_GOES_ON

6 years ago, hide # |

→ Reply

bloodoath

6 years ago, hide # ^ |

+18

Someone will come to help you, even if they don't, you know bro, LIFE_GOES_ON

→ Reply

Nachia

6 years ago, hide # |

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()

→ Reply

sankalp_

6 years ago, hide # |

← Rev. 2 →

+11

Main code

vector<string> rotation(string str) {
    int n = str.length();

    vector<string> ans;
    REP(i, n)
        ans.pb(str.substr(i)+str.substr(0, i));

    return ans;
}

int rot[3][4] = {{0, 2, 1, 3}, {0, 4, 1, 5}, {2, 4, 3, 5}};

string oneRotate(string str, int axis, int times) {
    string tmp = "";
    for(int x : rot[axis])
        tmp += str[x];

    int idx = 0;
    string rotated = tmp.substr(times)+tmp.substr(0, times);
    for(int x : rot[axis])
        str[x] = rotated[idx++];

    return str;
}

string rotate(string str, int i, int j, int k) {
    str = oneRotate(str, 0, i);
    str = oneRotate(str, 1, j);
    str = oneRotate(str, 2, k);

    return str;
}

//Main function
int main() {
    IOS;
    TIE;

    string str;
    cin>>str;
    sort(all(str));

    int ans = 0;
    set<string> s;
    do {
        bool flag = true;
        vector<string> v;
        REP(i, 4)
            REP(j, 4)
                REP(k, 4) {
                    string cur = rotate(str, i, j, k);
                    if(s.find(cur) != s.end())
                        flag = false;
                    v.pb(cur);
                }

        for(auto foo : v)
            s.insert(foo);

        ans += flag;
    }
    while(next_permutation(all(str)));

    cout<<ans<<endl;

    return 0;
}

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

→ Reply