## 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

zain
New poster
Posts: 2
Joined: Sat Oct 18, 2014 1:15 am

### Re: 12761 - Blue Chips

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

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

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 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

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;
unsigned long int y;
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=y[d]+y[n-d];
for ( int r = 0;r != n; r++)
{
y[r]=x[r];
}

}
unsigned long int min =x;
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

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

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

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

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

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