@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
Did this with hashing
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.
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.
where to ask questions?
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.
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
guyz here is a very easy solution in c++,go through it
#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;
}
Better one I guess,never tried though
- Hash the cop houses,better than Sorting(simply compensating the 400 bytes(sizeof(int)*100) for computing speed).
- Consider the fact that Total Distance traveled by any cop is Distance=Number_Of_Houses_per_minute times Total_Time.
- For any cop house consider that range inclusive [cop_house-Distance,cop_house+Distance] to be cop houses.
- 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
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)
@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)
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
If problem related then here , Else than on discuss
My code isnt working despite correct logic. Pls help.
https://www.codechef.com/viewsolution/24481962