12761 - Blue Chips

All about problems in Volume 127. 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
zain
New poster
Posts: 2
Joined: Sat Oct 18, 2014 1:15 am

Re: 12761 - Blue Chips

Post by zain » Sat Oct 18, 2014 1:19 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12761 - Blue Chips

Post by brianfry713 » Tue Oct 21, 2014 9:50 pm

You can solve this using matrix multiplication.
Check input and AC output for thousands of problems on uDebug!

abedalg
New poster
Posts: 4
Joined: Fri Oct 24, 2014 9:40 am

Re: 12761 - Blue Chips

Post by abedalg » Fri Oct 24, 2014 9:43 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12761 - Blue Chips

Post by brianfry713 » Fri Oct 24, 2014 9:22 pm

Post or send me your code.
Check input and AC output for thousands of problems on uDebug!

abedalg
New poster
Posts: 4
Joined: Fri Oct 24, 2014 9:40 am

Re: 12761 - Blue Chips

Post by abedalg » Sat Oct 25, 2014 9:39 pm

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;
}
Last edited by brianfry713 on Tue Oct 28, 2014 11:16 pm, edited 1 time in total.
Reason: Added code blocks

yasin1989
New poster
Posts: 1
Joined: Sun Oct 26, 2014 9:52 am

Re: 12761 - Blue Chips

Post by yasin1989 » Sun Oct 26, 2014 10:03 am

brianfry713 wrote: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
New poster
Posts: 2
Joined: Tue Oct 28, 2014 9:22 pm

Re: 12761 - Blue Chips

Post by myaccount92 » Tue Oct 28, 2014 9:37 pm

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12761 - Blue Chips

Post by brianfry713 » Tue Oct 28, 2014 11:55 pm

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.
Check input and AC output for thousands of problems on uDebug!

abedalg
New poster
Posts: 4
Joined: Fri Oct 24, 2014 9:40 am

Re: 12761 - Blue Chips

Post by abedalg » Wed Oct 29, 2014 5:13 am

 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12761 - Blue Chips

Post by brianfry713 » Wed Oct 29, 2014 9:07 pm

Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 127 (12700-12799)”