COPS - Editorial

@sidharth14163 just check for a case
1
1 2 1
100
your first condition of breaking the loop is wrong .
hope it would be clear :slight_smile:

Did this with hashing :slight_smile:
This loop takes care of all possible boundary conditions.

for(i=0 to m)
{
input val:
for(j = max(val-x*y,0) ;j<=min(val+x*y,100);j++)
arr[j]++;
}

Now just check how many entries of arr are 0.

2 Likes

Why am I getting wrong answer?Here is the link CodeChef: Practical coding for everyone

1 Like

test_cases = gets.to_i
test_cases.times do
m, x, y = gets.strip.split(" “).collect(&:to_i)
prod = x * y
all_houses = (1…100).to_a
cops_houses = gets.strip.split(” ").collect(&:to_i)
searchable_houses = []
cops_houses.each do |el|
searchable_houses += ((el - prod)…el).to_a + (el…(el + prod)).to_a
end
safe_houses = all_houses - searchable_houses
puts safe_houses.length
end

My code isnt working despite correct logic. Pls help.

https://www.codechef.com/viewsolution/13138859

where to ask questions?

1 Like

I just made a boolean array with 100 elements. For each cop position I checked ±20 positions and then counted how many false positions there were. I’m pretty sure it’s a better solution since you don’t have to check every house.

1 Like

somebody please help!! i dont get what wrong in my code(python). please…
https://www.codechef.com/viewsolution/15429435

Well,the question and explanation in the example do not correlate .The question says in a straight line,a cop in a house can go left or right but not both whereas the explanation uses the range on either sides makig it a Simpler problem

6 Likes

guyz here is a very easy solution in c++,go through it

#include

#include
using namespace std;
struct dis
{
int max,min;

};
int main() {
int t,m,x,y,p;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>m>>x>>y;
p=x*y;
int a[m];
int safe=0,h=0;

for(int j=0;j<m;j++)
{
    cin>>a[j];
}
sort(a,a+m);
dis b[m];
int s,d;
for(int j=0;j<m;j++)
{
    s=a[j]-p;// min
    d=a[j]+p; //max
    if(d>=100)
    {b[j].max=100;}
    else
    b[j].max=d;

     if(s<=1)

    {b[j].min=1;}
    else
    b[j].min=s;
}
for(int j=0;j<m-1;j++)
{
    if(b[j].max==100)
    {
        break;
    }
    if(b[j+1].min>b[j].max)
    {
        h=b[j+1].min-b[j].max-1;
        safe=safe+h;
    }
}
safe=safe+(b[0].min-1)+(100-b[m-1].max);
cout<<safe<<endl;

}

return 0;

}

2 Likes

Better one I guess,never tried though

  1. Hash the cop houses,better than Sorting(simply compensating the 400 bytes(sizeof(int)*100) for computing speed).
  2. Consider the fact that Total Distance traveled by any cop is Distance=Number_Of_Houses_per_minute times Total_Time.
  3. For any cop house consider that range inclusive [cop_house-Distance,cop_house+Distance] to be cop houses.
  4. If there are any more left houses that is not included in the range,those are the best houses for the thief to hide.

Note:-

  • For 100th cop house exclude right boundary.
  • Step 4 can we achieved by some math directly for houses that aren’t in the range.

Please Correct Me If I’m Wrong,Happy To Learn :slight_smile:

1 Like

Is the time complexity correct?

Under faster solution its written - “Let us can create a sorted array of houses of cops.” Wouldn’t creating a sorted array contribute O(nlogn) to the total time? How is it just O(100*logn)

1 Like

@keertika32 I think you made an error in the inner for loop that is iterating from j=0 to j=4. Can you explain why you did that?

I have used prefix sum or something is better than that?

I have used prefix sum or something is better than that?

There is a relatively obvious answer which for speed doesn’t depend on the number of houses at all and doesn’t involve populating an array with likely-redundant entries. Sort the cop houses - O(N\log N) - then step through these - O(N) - to find the safe ranges.


lim = 100
for _ in range(int(input())):
    # input
    m,x,y = map(int, input().split())
    cops = sorted( map(int, input().split()) ) # read and sort
    # process
    rng = x*y        # the range of each cop
    hse = 1          # the next available house safe from the cops reviewed so far
    safe = 0         # count of safe houses
    for cop in cops:
        if cop-rng > hse:
            # there is a gap in cop coverage
            safe += cop-rng-hse 
        hse = cop+rng+1 # current cop cannot reach this
    if hse<=lim:
        # some safe houses at the end too
        safe += lim-hse+1
    # report
    print(safe)

what is wrong with this??
https://www.codechef.com/viewsolution/21204870

Well, You may have a look at my code

variable m denotes the product, left holds the house number till we have checked and covered, and 100+m+1 is added to check for houses in the end, like 100, 99 …

Rest code is self-explanatory (java)

https://www.codechef.com/viewsolution/15431189

(Solved this for you)

Please UPVOTE…

Feel free to ask anything

1 Like

If problem related then here , Else than on discuss

My code isnt working despite correct logic. Pls help.
https://www.codechef.com/viewsolution/24481962