## 11540 - Sultan's Chandelier

Moderator: Board moderators

NewSuperconductor
New poster
Posts: 1
Joined: Fri Dec 26, 2008 1:53 am

### 11540 - Sultan's Chandelier

Hi,
I'm solving this problem using DP taking care not to count some arrangement more than once. The problem statement was not very clear but what I understood is that the children of each sub tree can be rotated through all cyclic permutations and we will still have the same tree. I wrote a java solution according to this understanding but I'm getting WA, so if anybody can tell whether I understand the problem correctly, and in this case can anybody provide any tricky case because I ran out of test cases I can verify by hand.
This is my code

Code: Select all

``````import java.io.*;
import java.util.*;
public class Chandelier {
static String s;
static int[][] a=new int[150][150];
static int[][] dpe=new int[150][150];
static long[] dp=new long[150];
static long[] pans=new long[150];
static long num,mod=1000000007;
public static long modPow(long a,long k){
if(k==0)
return 1;
if(k%2==0)
return modPow((a*a)%mod,k/2);
return (modPow((a*a)%mod,k/2)*a)%mod;
}
public static long divMod(long a,long b){
return (a*modPow(b,mod-2))%mod;
}
public static int parse(int current,int i,int j){
i++; j--;
if(i>=j)
return 1;
int count=0,nodes=0,nxt=current+1,m=i,ans=1;
for(int k=i;k<j;k++){
if(s.charAt(k)=='['){
count++; nodes++;
}
else if(s.charAt(k)==']')
count--;
if(count==0){
k++;
ans+=parse(nxt,m,k);
a[current][0]++;
a[current][a[current][0]]=nxt;
nxt+=nodes;
m=k+1;
nodes=0;
}
}
return ans;
}

public static int equal(int m,int n){
if(a[m][0]!=a[n][0])
return 0;
if(a[m][0]==0)
return 1;
if(dpe[m][n]!=-1)
return dpe[m][n];
int N=a[m][0];
for(int i=0;i<N;i++){
boolean flag=true;
for(int j=1;j<=N&&flag;j++)
if(equal(a[m][j],a[n][(i+j-1)%N+1])==0)
flag=false;
if(flag)	return dpe[m][n]=1;
}
return dpe[m][n]=0;
}

public static long f(int m){
if(a[m][0]==0)
return num;
if(dp[m]!=-1)
return dp[m];
int N=a[m][0];
pans[0]=1;
for(int i=1;i<=N;i++){
pans[i]=(pans[i-1]*f(a[m][i]))%mod;
}
int i;
for(i=1;i<N;i++){
boolean flag=true;
for(int j=1;j<=N&&flag;j++){
int k=(i+j-1)%N+1;
if(equal(a[m][k],a[m][j])==0)
flag=false;
}
if(flag){
break;
}
}
int d=i;
long ans=pans[i];
for(int j=2*i;j<=N;j+=i)
if(N%j==0){
long temp=(pans[j]-pans[d]+mod)%mod;
d=j;
temp=(temp*i)%mod;
temp=divMod(temp,j);
ans=(ans+temp)%mod;
}
return dp[m]=(ans*num)%mod;
}
public static void main(String[] args)throws IOException{
for(int w=1;w<=t;w++){
s=temp[0]; num=Integer.parseInt(temp[1].trim());
int n=parse(0,0,s.length());
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
dpe[i][j]=-1;
Arrays.fill(dp,-1);
for(int i=n-1;i>=0;i--)
f(i);
System.out.println("Case #"+w+": "+f(0));
for(int i=0;i<n;i++)
a[i][0]=0;
}
}
}
``````

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 11540 - Sultan's Chandelier

For the testcase

Code: Select all

``[[[],[]]],[],[[],[]]``
how many transformations do we have? I would have said 4: identity, 2 rotations of the bottommost

Code: Select all

``[[],[]]``
subtrees and the product of the latter two transpositions. Thus we have one permutation with 8 disjoint cycles (colors^8),
two permutations with 1 two-cycles and 6 one-cycles (2*color*color^6), one perm with 2 two-cycles and 4 one-cycles (colors^2*colors^4),
thus

Code: Select all

``(colors^8 + 2colors^7 + colors^6)/4 = [colors = 2] = 144.``

lambda
New poster
Posts: 3
Joined: Tue Jan 20, 2009 2:20 pm

### Re: 11540 - Sultan's Chandelier

why 4 permutations? I use the uva toolkit to check your case: [[[],[]]],[],[[],[]] 2, and it returns ans 192, not 144. what does it mean?
can u write down the 4 permutations? I've been doing this problem for a whole day and just get wa. help~
I don't know if I misunderstand the problem, can u provide the answers for the following cases? :
[],[[],[]] 2
[[],[]],[] 2
[[[]]],[[[]]],[[[]]] 2
thx a lot.

lambda
New poster
Posts: 3
Joined: Tue Jan 20, 2009 2:20 pm

### Re: 11540 - Sultan's Chandelier

I've made a mistake. I know why 4 permutation now.
but after I fixed the bug of my code, I got RE, why? how many nodes are there mostly?