11540 - Sultan's Chandelier

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11540 - Sultan's Chandelier

Post by NewSuperconductor »

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{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int t=Integer.parseInt(br.readLine());
		for(int w=1;w<=t;w++){
			String[] temp=br.readLine().split(" ");
			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

Post by serur »

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

Post by lambda »

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

Post by lambda »

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?

Post Reply

Return to “Volume 115 (11500-11599)”