Re: [algogeeks] RR Scheduling
You can solve this problem using Binary Indexed Trees.
(copied from spoj forum)
On Mon, Mar 21, 2011 at 3:09 PM, Terence technic@gmail.com wrote:
In this problem, sum can be as large as 5*10^9.
Try breaking the whole interval into several stages (no more than 2*N),
each with a fixed amount of tasks.
Then in each stage, the schedule is a simple loop: A B C D E A B C D E A B
...
Process each stage in O(1) time, then the total time complexity is O(N).
On 2011-3-21 17:32, saurabh singh wrote:
using scanf and printf and still tle,I am not pretty sure how malloc or new
arrays can speed up execution?
On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal sm14it...@gmail.comwrote:
use scanf n printf instead of cin n cout,
malloc array of structures after reading value of n if working in c else
use new in cpp
rest i guess...is ok
On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal ankitsamb...@gmail.com
wrote:
I worked on this problem but cud not get a more efficient algo than
yours.
Plz get back 2 me if u find a better algo.
On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma
akshatasharm...@gmail.com wrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#includeiostream
#includestdio.h
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cinn;
struct process prss[5];
for(long i=0;in;i++)
{
scanf(%ld,prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;in;i++)
printf(%ld\n,prss[i].elapsed_time);
return 0;
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sanchit Mittal
Second Year Undergraduate
Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards,
chinna.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] RR Scheduling
In this problem, sum can be as large as 5*10^9.
Try breaking the whole interval into several stages (no more than 2*N),
each with a fixed amount of tasks.
Then in each stage, the schedule is a simple loop: A B C D E A B C D E A
B ...
Process each stage in O(1) time, then the total time complexity is O(N).
On 2011-3-21 17:32, saurabh singh wrote:
using scanf and printf and still tle,I am not pretty sure how malloc
or new arrays can speed up execution?
On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal sm14it...@gmail.com
mailto:sm14it...@gmail.com wrote:
use scanf n printf instead of cin n cout,
malloc array of structures after reading value of n if working in
c else use new in cpp
rest i guess...is ok
On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal
ankitsamb...@gmail.com mailto:ankitsamb...@gmail.com wrote:
I worked on this problem but cud not get a more efficient algo
than yours.
Plz get back 2 me if u find a better algo.
On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma
akshatasharm...@gmail.com mailto:akshatasharm...@gmail.com
wrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#includeiostream
#includestdio.h
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cinn;
struct process prss[5];
for(long i=0;in;i++)
{
scanf(%ld,prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;in;i++)
printf(%ld\n,prss[i].elapsed_time);
return 0;
}
--
You received this message because you are subscribed to
the Google Groups Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the
Google Groups Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sanchit Mittal
Second Year Undergraduate
Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups Algorithm
Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] RR Scheduling
If i understand correctly, the requirement is to write a scheduler.
You can refer to O'REilly 's understanding the linux kernel.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Mar 20, 2011 at 3:54 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#includeiostream
#includestdio.h
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cinn;
struct process prss[5];
for(long i=0;in;i++)
{
scanf(%ld,prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;in;i++)
printf(%ld\n,prss[i].elapsed_time);
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] RR Scheduling
use scanf n printf instead of cin n cout,
malloc array of structures after reading value of n if working in c else use
new in cpp
rest i guess...is ok
On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal ankitsamb...@gmail.comwrote:
I worked on this problem but cud not get a more efficient algo than yours.
Plz get back 2 me if u find a better algo.
On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma akshatasharm...@gmail.com
wrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#includeiostream
#includestdio.h
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cinn;
struct process prss[5];
for(long i=0;in;i++)
{
scanf(%ld,prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;in;i++)
printf(%ld\n,prss[i].elapsed_time);
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sanchit Mittal
Second Year Undergraduate
Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] RR Scheduling
using scanf and printf and still tle,I am not pretty sure how malloc or new
arrays can speed up execution?
On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal sm14it...@gmail.com wrote:
use scanf n printf instead of cin n cout,
malloc array of structures after reading value of n if working in c else
use new in cpp
rest i guess...is ok
On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal ankitsamb...@gmail.comwrote:
I worked on this problem but cud not get a more efficient algo than yours.
Plz get back 2 me if u find a better algo.
On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma
akshatasharm...@gmail.com wrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#includeiostream
#includestdio.h
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cinn;
struct process prss[5];
for(long i=0;in;i++)
{
scanf(%ld,prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;in;i++)
printf(%ld\n,prss[i].elapsed_time);
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sanchit Mittal
Second Year Undergraduate
Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] RR Scheduling
U have to use Some Advanced Data Structures for this problem
:P
On Mon, Mar 21, 2011 at 3:02 PM, saurabh singh saurab...@gmail.com wrote:
using scanf and printf and still tle,I am not pretty sure how malloc or new
arrays can speed up execution?
On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal sm14it...@gmail.com wrote:
use scanf n printf instead of cin n cout,
malloc array of structures after reading value of n if working in c else
use new in cpp
rest i guess...is ok
On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal ankitsamb...@gmail.com
wrote:
I worked on this problem but cud not get a more efficient algo than
yours.
Plz get back 2 me if u find a better algo.
On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma
akshatasharm...@gmail.com wrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#includeiostream
#includestdio.h
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cinn;
struct process prss[5];
for(long i=0;in;i++)
{
scanf(%ld,prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;in;i++)
printf(%ld\n,prss[i].elapsed_time);
return 0;
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sanchit Mittal
Second Year Undergraduate
Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] RR Scheduling
u tokin of any kinda tree?
On Mon, Mar 21, 2011 at 7:36 PM, radha krishnan
radhakrishnance...@gmail.com wrote:
U have to use Some Advanced Data Structures for this problem
:P
On Mon, Mar 21, 2011 at 3:02 PM, saurabh singh saurab...@gmail.com
wrote:
using scanf and printf and still tle,I am not pretty sure how malloc or
new
arrays can speed up execution?
On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal sm14it...@gmail.com
wrote:
use scanf n printf instead of cin n cout,
malloc array of structures after reading value of n if working in c else
use new in cpp
rest i guess...is ok
On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal ankitsamb...@gmail.com
wrote:
I worked on this problem but cud not get a more efficient algo than
yours.
Plz get back 2 me if u find a better algo.
On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma
akshatasharm...@gmail.com wrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#includeiostream
#includestdio.h
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cinn;
struct process prss[5];
for(long i=0;in;i++)
{
scanf(%ld,prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;in;i++)
printf(%ld\n,prss[i].elapsed_time);
return 0;
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sanchit Mittal
Second Year Undergraduate
Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sanchit Mittal
Second Year Undergraduate
Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] RR Scheduling
I worked on this problem but cud not get a more efficient algo than yours.
Plz get back 2 me if u find a better algo.
On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma
akshatasharm...@gmail.comwrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#includeiostream
#includestdio.h
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cinn;
struct process prss[5];
for(long i=0;in;i++)
{
scanf(%ld,prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;in;i++)
printf(%ld\n,prss[i].elapsed_time);
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
