12761 - Blue Chips

[zain]

i can not understand the problem statement..
anybody please explain the statement....

[brianfry713]

You can solve this using matrix multiplication.

[abedalg]

I have time limit exceeded in my solution how I can solve this problem?

[brianfry713]

Post or send me your code.

[abedalg]

Code: Select all

#include "iostream"
using namespace std;
void process(unsigned long int n,unsigned long int k ,unsigned long int d)
{
	unsigned long int h;
	unsigned long int x[50];
	 unsigned long int y[50];
	for( unsigned long int i=0;i<n;i++)
	{
		cin>>h;
		x[i]=h;
		y[i]=h;
	}
	for( unsigned long int j=0;j<k;j++)
	{
	      for (unsigned long int i = 1;i<n; i++)
          {
			  int next=0,pre=0;
			  if((i-d)<0)
			  {
				  pre=n-(d-i);
				
			  }
			  else
			  {
				  pre=i-d;
			  }
			  if((i+d)>(n-1))
			  {
				  next=(n-(i+1))*(-1);
			  }
			  else
			  {
				  next=i+d;
			
			  }
			  
		      x[i]=y[next]+y[pre];
          }
		   x[0]=y[d]+y[n-d];
          for ( int r = 0;r != n; r++)
          {
		      y[r]=x[r];
          }
		  
	}
	 unsigned long int min =x[0];
	for ( unsigned long int i = 0;i != n; i++)
    {
		x[i]=x[i]%n;
		if(x[i]<min)
		{
		    min=x[i];
		}
    }
	cout<<min<<endl;
	for ( unsigned long int i = 0;i != n; i++)
    {
		//cout<<x[i];
		if(x[i]==min)
		{
			cout<<i+1<<" ";
		}
    }
	cout<<endl;
}
int main()
{
	 unsigned long int t,n,d;
	   unsigned long int k;
	cin>>t;
	for( unsigned long int i=0;i<t;i++)
	{
		cin>>n>>k>>d;
		process(n,k,d);
	}

	return 0;
}

[yasin1989]

You can solve this using matrix multiplication.

please explain in more how we can use matrices multiplication to solve this problem, i tried to apply this idea but i couldn't understand the relevant between matrices multiplication and this problem

[myaccount92]

can you please explane how we can use matrix multiplication to solve this problem

[brianfry713]

abedalg, don't print a space at the end of a line, you are not using matrix multiplication.

The initial state is the array X. The brute force TLE solution is to transform that K times, which would take at least O(K * N) for each test case.

To solve it using matrix multiplication, I first create a N by N graph that has either a 0 or 1 based on the value of D. graph[j] = (i - j <= D || N - i + j <= D)
I then use exponentiation by squaring and matrix multiplication to compute the powers of two for that graph.
Then you can transform the X array K times in O(log K * N * N * N) for each test case.

[abedalg]

 I can't understand these lines can you explain mor about them?
I then use exponentiation by squaring and matrix multiplication to compute the powers of two for that graph.
Then you can transform the X array K times in O(log K * N * N * N) for each test

[brianfry713]

http://en.wikipedia.org/wiki/Exponentiation_by_squaring
http://en.wikipedia.org/wiki/Matrix_multiplication