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

Post by suneast » Sun Feb 27, 2011 3:55 pm

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

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

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

Re: 11926 - Multitasking

Post by sohel » Mon Feb 28, 2011 5:27 am

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

Post by suneast » Mon Feb 28, 2011 6:51 am

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.
:oops: Oooooooops...
how silly I am... :o

thanks sohel so much... :D
I got it now...

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

Re: 11926 - Multitasking

Post by mostafa_angel » Thu Mar 03, 2011 5:00 pm

Hi...
I got WA and I dont how this could be happend... :(
Please help to figure it out , thanks...

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

Post by mostafa_angel » Thu Mar 03, 2011 5:53 pm

i Got AC ... :D

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm
Location: CUET,Chittagong,Bangladesh

Re: 11926 - Multitasking

Post by naseef_07cuet » Wed Mar 09, 2011 1:43 am

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
Location: CUET,Chittagong,Bangladesh

Re: 11926 - Multitasking

Post by naseef_07cuet » Wed Mar 09, 2011 8:52 pm

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

Post by mostafa_angel » Thu Mar 10, 2011 12:33 am

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

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

Re: 11926 - Multitasking

Post by Imti » Fri Apr 22, 2011 4:49 pm

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

Post by suneast » Fri Apr 22, 2011 5:23 pm

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~ :wink:

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

Re: 11926 - Multitasking

Post by andr3s2 » Sun Nov 20, 2011 12:37 am

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
Location: Chittagong, Bangladesh

Re: 11926 - Multitasking

Post by @li_kuet » Thu Dec 27, 2012 12:22 pm

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

Post by Repon kumar Roy » Tue Feb 11, 2014 7:31 pm

Carefully the condition of the loop should be checked :D
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

Post by brianfry713 » Wed Feb 12, 2014 12:07 am

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

Post by vector9x » Sun Jul 06, 2014 9:01 pm

A hard case, a task in conflict with itself:

Code: Select all

0 1
1 100 2
0 0
Correct output is CONFLICT

Post Reply

Return to “Volume 119 (11900-11999)”