Discussion on Introduction to Representation Theory Challenge

Sort by

recency

|

3 Discussions

|

6 years ago+ 1 comment

It appears that I'm the only one that has solved this problem using C, atleast according to the leaderboard. Basically it is just to implement an inverse discrete fourier transform (as kogoro_akechi suggest and quite nicely ) and since the parameter limits are not that severe m<=2000 you can get away with a naive implementation (as kogoro_akechi has in his solution) wich has timecomplexity O(m^2) in all cases. I thought that was booring and decide, since it is an advanced problem, to implement a generalized fast fourier transform that exploits the periodicity of the exp(2pi*l*t/k) to reduce the computational complexity to O(m*log(m)) in best case and O(m*m) in the worst case (which is if m is a prime number). Here after follow my C implementation:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <complex.h>
#include <assert.h>
#include <math.h>

const double PI = acos(-1);

size_t smallest_prime_factor(size_t number)
{
	if (number%2 == 0)
		return 2;
	size_t factor;
	for (factor = 3;
	     factor <(sqrt(number)+1);
	     factor+=2)
	{
		if (number % factor == 0)
			return factor;
	}
	return number;
}

void partition_array(double complex *elements,
		     double complex *help_array,
		     size_t num_elements,
		     size_t num_partitions)
{
	size_t num_elements_partition = num_elements/num_partitions;
	size_t write_index;
	size_t read_index;
	for (write_index = 0;
	     write_index < num_elements;
	     write_index++)
	{
		read_index = (write_index/num_elements_partition)+
			(write_index%num_elements_partition)*num_partitions;
		help_array[write_index] = elements[read_index];
	}
	memcpy(elements,
	       help_array,
	       sizeof(double complex)*num_elements);
	
}


void combine_partitions(double complex *elements,
			double complex *help_array,
			size_t num_elements,
			size_t num_partitions)
{
	const double complex exponent_prefactor = -I*(2*PI)/num_elements;
	size_t num_elements_partition = num_elements/num_partitions;
	size_t write_index;
	size_t read_index;
	for (write_index = 0;
	     write_index < num_elements;
	     write_index++)
	{
		double complex accumulator = 0;
	        size_t partition_index;
		for (partition_index = 0;
		     partition_index < num_partitions;
		     partition_index++)
		{
			double complex factor = cexp(exponent_prefactor * write_index * partition_index);
			read_index = num_elements_partition*partition_index+
				(write_index % num_elements_partition);
			accumulator+=factor*elements[read_index];
		}
		help_array[write_index] = accumulator/num_partitions;
	}
	memcpy(elements,
	       help_array,
	       sizeof(double complex)*num_elements);
}

void inverse_fourier_transform(double complex *elements,
			       double complex *help_array,
			       size_t num_elements)
{
	if (num_elements == 1)
		return;
	size_t num_partitions = smallest_prime_factor(num_elements);
	size_t num_elements_partition = num_elements/num_partitions;
	partition_array(elements,
			help_array,
			num_elements,
			num_partitions);
	size_t partition_index;
	for (partition_index = 0;
	     partition_index < num_partitions;
	     partition_index++)
	{
		double complex *partition = elements+partition_index*num_elements_partition;
		inverse_fourier_transform(partition,
					  help_array,
					  num_elements_partition);
	}
	combine_partitions(elements,
			   help_array,
			   num_elements,
			   num_partitions);
}

int main()
{
	size_t n,m;
	scanf("%ld %ld\n",
	      &n,&m);
	double complex *traces =
		(double complex*)malloc(sizeof(double complex)*m);
	double complex *trace_help =
		(double complex*)malloc(sizeof(double complex)*m);
	size_t i;
	for (i = 0; i<m; i++)
	{
		double real_part,imaginary_part;
		scanf("%lg %lg",
		      &real_part,
		      &imaginary_part);
		traces[i] = real_part+I*imaginary_part;
	}
	inverse_fourier_transform(traces,trace_help,m);
	for (i = 0; i<m; i++)
	{
		double complex eigenvalue = cexp(I*((2*PI)/m)*i);
		size_t num = creal(traces[i])+0.5;
		size_t j;
		for (j = 0; j<num; j++)
			printf("%0.10lf %0.10lf\n",
			       creal(eigenvalue),
			       cimag(eigenvalue));
	}
	

	free(traces);
	free(trace_help);
	return 0;
}

7 years ago+ 0 comments

Essentially, this is more about finite Fourier transforms (although you could argue that this counts as representation theory of finite abelian groups).

Our matrix fulfils the identity A^k = 1. Therefore all eigenvalues must fulfill this equation as well.

We conclude the eigenvalues are of the form exp(2pi*I*t/k) where t goes from 0 to k-1 and I is the imaginary unit. Say the eigenvalue exp(2pi*I*t/k) has multiplicity a_t.

The trace of a matrix is the sum of all its eigenvalues, and taking powers of a matrix has the effect that the eigenvalues are taken to this power as well.

So, A^j has the eigenvalue exp(2pi*I*j*t/k) with multiplicity a_t and its trace is:

tr(A^j) = sum (t = 0 to k-1) a_t * exp(2pi*I*j*t/k)

This is actually just the discrete Fourier transform of the function taking t to a_t. Therefore, we want the inverse Fourier transform of the function taking j to tr(A^j). Call the latter f_j.

The inverse transform is given by:

a_t = 1/k * sum (t = 0 to k-1) f_j * exp(-2pi*I*j*t/k).

I know that a_t is an integer, so I just calculate the real part of this sum and do some rounding with this result. Furthermore, I modded out k from j*t - the result of exp(...) is the same but errors due to big arguments are less probable to occur.

Then I print the eigenvalue exp(2pi*I*t/k) simply a_j times (my code calculates the occurrences of exp(-2pi*I*t/k) but this just reverses the order of the eigenvalues).

By the way - the number n is not needed for the calculations.

Here is my code:

cout.precision(7);

    double x ;
    
    vector<double> real ;
    vector<double> imag ;
    
    double PI = 3.14159265358979 ;
    
    int k, n ;
    
    cin >> n >> k  ;
    
    double a,b ;
    
    for(int i = 0 ; i < k ; i++){
        cin >> a >> b ;
        real.push_back(a) ;
        imag.push_back(b) ;
    }
    
    for(int i = 0 ; i < k ; i++){
        double sumreal = 0 ;
        
        for(int j = 0 ; j < k ; j++){
            int modded = (i*j) % k ; //
            sumreal = sumreal + real[j]*cos(2*modded*PI/k) - imag[j]*sin(2*modded*PI/k) ;
        }
        
        sumreal = sumreal/k + 0.5 ;
        
        int howmany ;
        
        howmany = sumreal ;
        
        double x = cos(2*i*PI/k) ;
        double y = -sin(2*i*PI/k) ;
        
        for(int l = 0 ; l < howmany ; l++){
            cout << fixed << x << " " << y << endl ;
        }
        
    }

7 years ago+ 0 comments

I've been thinking about this problem for a while and I don't really know how to start. I've been trying the 'hard way' because I don't know anything about representation theory... Can anyone give me a hint or some reading material about representation theory that could help me? Thanks!

No more comments

Sort by

|

3 Discussions

|

Cookie support is required to access HackerRank