Introduction to Representation Theory Discussions | Mathematics | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Combinatorics
  4. Introduction to Representation Theory
  5. Discussions

Introduction to Representation Theory

  • tordjarv
     + 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;
}