PROBLEM LINK:
Setter/Tester/Editorialist: Chandan Boruah
DIFFICULTY:
EASY
PREREQUISITES:
Maths, Brute Force
PROBLEM:
The problem statement states there are a few numbers which can be “magically equal” only if they contain digits in equal count. You need to print the number of ways in which all numbers are “magically equal” in that sense when one of the arrays is rearranged and each index is compared with the other.
QUICK EXPLANATION:
You can do a permutation on the first array, since the constraints are small. Print the number of ways in which all the numbers in each position are equal, by incrementing counter everytime you find such a permutation that satisfies the condition.
EXPLANATION:
You do permutation on the index of the first array, every permutation will create a new arrangement. On each arrangement you can check if the number on the same index are equal, here equal means all digits in the numbers are equal in count. Everytime you meet such an arrangment just increment the counter that will be printed in the end.
SOLUTIONS:
Setter's Solution
using System;
using System.Collections.Generic;
class some
{
public static int[]perm;
public static void Main()
{
int n=int.Parse(Console.ReadLine());
int[]arr1=new int[n];
int[]arr2=new int[n];
string[]ss=Console.ReadLine().Split();
for(int i=0;i<n;i++)arr1[i]=int.Parse(ss[i]);
ss=Console.ReadLine().Split();
for(int i=0;i<n;i++)arr2[i]=int.Parse(ss[i]);
perm=new int[n];
for(int i=0;i<n;i++)
{
char [] a=(arr1[i]+"").ToCharArray();
char [] b=(arr2[i]+"").ToCharArray();
Array.Sort(a);
Array.Sort(b);
arr1[i]=int.Parse(new string(a));
arr2[i]=int.Parse(new string(b));
}
for(int i=0;i<n;i++)perm[i]=i;
int count=0;
while(true)
{
if(perm[0]==-1)break;
bool ok=false;
for(int i=0;i<n;i++)
{
if(arr1[i]!=arr2[perm[i]]){ok=true;break;}
}
if(!ok)count++;
next();
}
Console.WriteLine(count);
}
public static void next()
{
int p=-1;
for(int i=1;i<perm.Length;i++)
{
if(perm[i]>perm[i-1])
{
p=i-1;
}
}
if(p==-1){perm[0]=-1;return;}
int q=-1;
for(int i=perm.Length-1;i>p;i--)
{
if(perm[i]>perm[p])
{
q=i;break;
}
}
if(q==-1){perm[0]=-1;return;}
int temp=perm[p];
perm[p]=perm[q];
perm[q]=temp;
for(int i=p+1,j=perm.Length-1;i<j;i++,j--)
{
temp=perm[i];
perm[i]=perm[j];
perm[j]=temp;
}
return;
}
}
ALTERNATE SOLUTIONS:
EgorK's Solution
using namespace std;
class MagicallyEqualKeteki {
public:
void solve(std::istream& inp, std::ostream& outp) {
Input in(inp);
Output out(outp);
int n = in.readInt();
auto a = in.readArray<string>(n);
auto b = in.readArray<string>(n);
for (int i = 0; i < n; ++i) {
sort(a[i]);
sort(b[i]);
}
sort(a);
sort(b);
map<string, int> m;
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) {
out.printLine(0);
return;
}
m[a[i]]++;
}
longint answer = 1;
for (const auto& p : m) {
for (int i = 1; i <= p.second; i++) {
answer *= i;
}
}
out.printLine(answer);
}
};