Page 1 of 2
11926 - Multitasking
Posted: Sun Feb 27, 2011 3:55 pm
by suneast
Oh, my god ! I need help...
this problem isn't seems hard ...
but in fact I can't figure out how to solve it excepted for brute force, which directly cause me getting TLE
I know
Code: Select all
for any two ONE-TIME task, we can use O(n^2) brute force to check whether they are intersect with each other
for a ONE-TIME task and a REPEAT task , we can use O(n*m) brute force to check whether they are intersect with each other, using format
ONE-TIME = [a1, b1 ]
REPEAT = [a2 + k*REP, b2+k*REP]
if there exist a valid k, b2+k*REP >=a1 && a2+k*REP<=b1 , they are intersect
But what about two REPEAT task ?
I can't figure out any format or have another ideas...
anyone gives me some hints plz....
Thx in advance
Re: 11926 - Multitasking
Posted: Mon Feb 28, 2011 5:27 am
by sohel
I just maintained a boolean array of size 10^6 and for each task marked the corresponding indices. When there is any conflict, I just stopped altogether. With this approach, you will just need 10^6 comparisons - which is small enough to pass the time limit.
Re: 11926 - Multitasking
Posted: Mon Feb 28, 2011 6:51 am
by suneast
sohel wrote:I just maintained a boolean array of size 10^6 and for each task marked the corresponding indices. When there is any conflict, I just stopped altogether. With this approach, you will just need 10^6 comparisons - which is small enough to pass the time limit.
Oooooooops...
how silly I am...
thanks sohel so much...
I got it now...
Re: 11926 - Multitasking
Posted: Thu Mar 03, 2011 5:00 pm
by mostafa_angel
Hi...
I got WA and I dont how this could be happend...
Please help to figure it out , thanks...
this is my code :
Re: 11926 - Multitasking
Posted: Thu Mar 03, 2011 5:53 pm
by mostafa_angel
i Got AC ...
Re: 11926 - Multitasking
Posted: Wed Mar 09, 2011 1:43 am
by naseef_07cuet
I am little bit confused about the overlapping process. Can anyone help me?
Re: 11926 - Multitasking
Posted: Wed Mar 09, 2011 8:52 pm
by naseef_07cuet
Why wrong answer?? Can anyone give me some i/o. Here is my code:
Code: Select all
#include<iostream>
using namespace std;
bool con[1000009];
int main()
{
long rw[10000],w[10000],i,j,k,l,n,m,e[10000],s[10000],flag,iv,t;
while(1)
{
flag=0;
memset(con,false,sizeof(con));
memset(rw,0,sizeof(rw));
memset(w,0,sizeof(w));
scanf("%ld%ld",&n,&m);
if(n==0 && m==0)
break;
for(i=0;i<n;i++)
{
scanf("%ld%ld",&s[i],&e[i]);
}
for(j=0;j<m;j++)
{
scanf("%ld%ld%ld",&s[i+j],&e[i+j],&iv);
}
for(k=0;k<n;k++)
{
for(l=s[k];l<e[k];l++)
{
if(con[l]==true)
{
flag=1;
printf("CONFLICT\n");
break;
}
con[l]=true;
}
if(flag==1)break;
}
if(flag==0)
for(k=n;k<m+n;k++)
{
t=s[k];
while(t<1000000)
{
for(j=t;j<e[k];j++)
{
if(con[j]==true)
{
flag=1;
printf("CONFLICT\n");
break;
}
con[j]=true;
}
t=t+iv;
e[k]+=iv;
if(flag==1)
break;
}
if(flag==1) break;
}
if(flag==0)
printf("NO CONFLICT\n");
}
return 0;
}
Re: 11926 - Multitasking
Posted: Thu Mar 10, 2011 12:33 am
by mostafa_angel
I am little bit confused about the overlapping process. Can anyone help me?
I think you learn an open range and close range of numbers in R
open range = (0 ,20)
close range = [0 , 20]
and if a = (0 , 1) and b = (1 ,2)
the Subscription of a and b is NULL but if
a = (0 , 1] and [1 , 2)
the Subscription of a and b is 1,
in this question all the ranges are Open
Re: 11926 - Multitasking
Posted: Fri Apr 22, 2011 4:49 pm
by Imti
Can anybody say me what should be the output for following cases:
Re: 11926 - Multitasking
Posted: Fri Apr 22, 2011 5:23 pm
by suneast
Imti wrote:
hi,
here is the output from my ac code
hope I'm help to U...
p.s this problem is quite easy if you are brave enough to solve it using brute force~
happy coding~
Re: 11926 - Multitasking
Posted: Sun Nov 20, 2011 12:37 am
by andr3s2
Just use a BitSet (and use te function to know if there was a intersection bs.cardinality()) this is very fast.
Re: 11926 - Multitasking
Posted: Thu Dec 27, 2012 12:22 pm
by @li_kuet
Few test case :
Code: Select all
2 1
2 5
7 9
5 7 4
2 0
2 5
4 6
2 0
2 5
5 6
2 1
2 5
7 10
5 7 4
0 0
Output :
Code: Select all
NO CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
Re: 11926 - Multitasking
Posted: Tue Feb 11, 2014 7:31 pm
by Repon kumar Roy
Carefully the condition of the loop should be checked
Re: 11926 - Multitasking
Posted: Wed Feb 12, 2014 12:07 am
by brianfry713
Input:
Code: Select all
1 1
999900 999901
99900 199800 100000
0 0
Output should be CONFLICT
Re: 11926 - Multitasking
Posted: Sun Jul 06, 2014 9:01 pm
by vector9x
A hard case, a task in conflict with itself:
Correct output is CONFLICT