11926 - Multitasking

[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

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

[suneast]

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]

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

[mostafa_angel]

i Got AC ...

[naseef_07cuet]

I am little bit confused about the overlapping process. Can anyone help me?

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

[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

[Imti]

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]

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]

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

[@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

[Repon kumar Roy]

Carefully the condition of the loop should be checked

[brianfry713]

Input:

Code: Select all

1 1
999900 999901
99900 199800 100000
0 0

Output should be CONFLICT

[vector9x]

A hard case, a task in conflict with itself:

Code: Select all

0 1
1 100 2
0 0

Correct output is CONFLICT