## 11926 - Multitasking

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### 11926 - Multitasking

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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11926 - Multitasking

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.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 11926 - Multitasking

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

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

### Re: 11926 - Multitasking

Hi...
I got WA and I dont how this could be happend...

this is my code :

Code: Select all

``````the code is deleted...
``````
Last edited by mostafa_angel on Thu Mar 03, 2011 6:05 pm, edited 1 time in total.

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

### Re: 11926 - Multitasking

i Got AC ...

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm

### Re: 11926 - Multitasking

I am little bit confused about the overlapping process. Can anyone help me?
If you have determination, you can do anything you want....

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm

### Re: 11926 - Multitasking

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

``````
If you have determination, you can do anything you want....

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

### Re: 11926 - Multitasking

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

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 11926 - Multitasking

Can anybody say me what should be the output for following cases:

Code: Select all

``````2 0
3 4
1 6
2 0
3 4
3 4
``````

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 11926 - Multitasking

Imti wrote: hi,
here is the output from my ac code

Code: Select all

``````CONFLICT
CONFLICT
``````
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~

andr3s2
New poster
Posts: 1
Joined: Sun Nov 20, 2011 12:32 am

### Re: 11926 - Multitasking

Just use a BitSet (and use te function to know if there was a intersection bs.cardinality()) this is very fast.

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 11926 - Multitasking

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

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 11926 - Multitasking

Carefully the condition of the loop should be checked
Last edited by Repon kumar Roy on Wed Feb 19, 2014 6:47 pm, edited 1 time in total.

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

### Re: 11926 - Multitasking

Input:

Code: Select all

``````1 1
999900 999901
99900 199800 100000
0 0
``````
Output should be CONFLICT
Check input and AC output for thousands of problems on uDebug!

vector9x
New poster
Posts: 3
Joined: Sun Jul 06, 2014 8:57 pm

### Re: 11926 - Multitasking

A hard case, a task in conflict with itself:

Code: Select all

``````0 1
1 100 2
0 0
``````
Correct output is CONFLICT