12761  Blue Chips
Moderator: Board moderators
Re: 12761  Blue Chips
i can not understand the problem statement..
anybody please explain the statement....
anybody please explain the statement....

 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!
Re: 12761  Blue Chips
I have time limit exceeded in my solution how I can solve this problem?

 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!
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[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((id)<0)
{
pre=n(di);
}
else
{
pre=id;
}
if((i+d)>(n1))
{
next=(n(i+1))*(1);
}
else
{
next=i+d;
}
x[i]=y[next]+y[pre];
}
x[0]=y[d]+y[nd];
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
Reason: Added code blocks
Re: 12761  Blue Chips
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 problembrianfry713 wrote:You can solve this using matrix multiplication.

 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

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

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 12761  Blue Chips
http://en.wikipedia.org/wiki/Exponentiation_by_squaring
http://en.wikipedia.org/wiki/Matrix_multiplication
http://en.wikipedia.org/wiki/Matrix_multiplication
Check input and AC output for thousands of problems on uDebug!