Aggressive cow | SPOJ
ฝัง
- เผยแพร่เมื่อ 20 ก.ย. 2024
- This video explains a very interesting problem from sphere online judge (SPOJ) which is the aggressive cow problem. I have shown proper insights and intuitions for solving this problem. First i have explained the problem statement using proper examples and then i have shown a simple approach to solve and also explained intuition for improving the time complexity further. I have shown the solution using binary search and have shown an example on how to solve it. Finally, at the end of the video, i have explained the code for this problem. As usual, CODE LINK along with some RELATED VIDEOS are present below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...
RELATED VIDEOS:-
Search in rotated sorted array: • Search in rotated sort...
First bad version: • First bad version | Le...
U r the best ......Now whenever I have a doubt in a questio..... I just search "(Question name) by tech dose" and TH-cam gives me ur video
Thanks :)
One of the toughest problems explained very effectively.
Best video on youtube 1⃣
☺️
Sir your explanation for these programming problems is just awesome. (P.S. - I never posted any comment before this on any youtube video, your hardwork made me to express myself and Show how thankfull i am.)
Thanks honest :)
One of the best coding question Channel. Your explanation is very simple and easy to understand. Thank you
One of best coding channel.
I am really amazed by your hard work and making programming more accessible to tier n cities.
Thanks bro :)
For those not able to understand it, this problem is actually quite similar to "Allocate Minimum Number of Pages" problem on gfg. There we had to minimise the maximum value, and here we have to maximise the minimum value. The approach and logic is very similar
Yes you are right Allocate minimum number of pages, Painters Partition Problem and Aggressive cow problem is similar to each other
kab se samjhna tha aap ne itne easy way me samjha diya thanks alot
Welcome :)
Excellent explanation better than most videos keep up the good work
Thanks :)
I was not clicking on this video because it was the longest one. But finally watched this one till end after quitting others in the first 1 min.
Really nice. Thanks.
Welcome :)
if perfect explanation exists......! Hats off to you sir.
how could you get such intution (applying binary search on it) plz reply bhai
Great video. Quality is more important than quantity when it comes to these types of videos!
Thanks :)
Why is the low starting initialized with 0 and not ( arr[1]-arr[0] ) in sorted array as this would give the lowest possible answer in search space?
1st cow will definitely be at 1st position. You can try submitting in SPOJ with your logic as well.
Did it worked
What is SPOJ and AGGRCOW? Does it signifies something very important?
Best explanation!
Thank you for the solution
Welcome
why mid=(low+high+1)/2 instead of (low+high)/2
What is SPOJ and AGGRCOW? Does it signifies something very important?
Why position of first cow is always fixed,why it is always placed at first index?
Great explanation as compares to others on this problem on you tube.
hey lad, can you explain me code in prolog?
there is exercise: "list has to include months. define a predicate that will show one month before and after that you typed in. use append/3".
solution is:
month( X, M1, M2) :-
append( _, [M1,X,M2 | _],
[jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec]).
can you explain me why we use anonymous variables and lists here? i dont really get it :/
This is simple man. Let's say X=Jun. The entire list of months you gave at the end will be matched with your anonymous and other variables. So, first anonymous variable will be a list from Jan to Apr. M1=May, M2=July and last anonymous variable is a list containing aug to Dec. what's the confusion? It's better to use anonymous variable for the part you don't really care about. It just takes in any data (just like auto keyword in c++).
one doubt: why are you taking mid as (low+high+1)/2 instead of (low+high)/2 or low+(high-low)/2
to take care of even-odd cases
if low and high are int and of order 10^9, then low + high will overflow the int range and the answer will be garbage, whereas low+(high-low) /2 will always work.
great explanation bro !!
But one question
why you use mid =(low+high+1)/2 instead of mid = low+(high-low)/2
same doubt here
You can use that too. Mine got accepted there at the spoj using low+(high-low)/2.
Both are same thing right,
low+(high-low)/2=
low -(low/2)+(high/2)=
( low+high)/2
@@abin_4857 yes all are same but u should try to avoid using (low+high)/2,as if both low and high are huge numbers then their sum may lead to overflow
@@abin_4857 Aree mere bhai, pehla comment thoda dhyan se dekh kya likha hua hai😂 , usne likha hai mid= (low+high+1)/2 , aur aap hume (low+high)/2 samjha rhe ho 😅
why mid is (low+high+1)/2, it should be (low + high)/2 right.
I think there is bug low should be equal to mid not mid +1, we can not discard mid itself, since it may well be the first element for which it is true. This is why moving the lower bound to mid is as aggressive as we can do without introducing bugs
yes, u r right but to improvise this issue sir has used variable "best", not to miss the best possible answer.
Hope it helps.
Java code for AgressiveCows:github.com/RajeshAatrayan/InterviewPreparation/blob/master/src/BinarySearch/Aggressivecows.java
Boy....u r good... : )
: )
giving the wrong answer for below logic (updating the answer only when the cnt == c) , but we have to update the ans when the cnt == cows only not when the c>n
why this was not working
if(cnt == c)
{
best = mid;
low = mid+1;
}
else uf (cnt > c)
{
low = mid+1;
}
else
{
high = mid-1;
}
Best explanation bro.Thanks a lot
Welcome :)
why is low =1 ? Should'nt it be 0???
Try with 0 and N-1
@@techdose4u Yeah it's working with 0 and high = pos[n-1] - pos[0]
Great solution buddy
Thanks
14:35 gap should be 3 and mid =4 so i think you are right in the video
👍🏼
no words to define hard work..
Thanks
if i devide the stall by cows then i get equal gap which will be max gap.
Great Explanation!👍
Thanks 😊
What is SPOJ and AGGRCOW? Does it signifies something very important?
best explanation. Thanks a lot!
What is SPOJ and AGGRCOW? Does it signifies something very important?
Good explanation.
Thanks
Nicely explained
Thanks :)
Can you make a video on Google Foobar challenge???
This is the first time I am hearing this 😅 I will search and see it.
@@techdose4u A pop up will appear on the browser when you search stuff related to computer science.
There are other hacks to activate it but I've never tried those.
I read on Quora about it. Some challenges are given 🤔
Sir this is data structures or any other language🤔
?? Dint get your question!
This problem is from data structures or not
@@aviligondagowtham1153 Loda Structure
plz upload video on problem like this
I understand the need. I was bored from leetcode challenge and its consistently easy questions. You will see very good questions in future (but due to corona I committed to leetcode challenge and now there are many people who requested to continue in may). When I start going office, I won't be making daily videos and you will see only important videos. Making multiple videos in a day is next to impossible 😅 I hope you understand my position.
@@techdose4u i am talking about after leet code challenge .ya sir we can understand your situations.you putting so much effort . God bless you
I will continue with good problems after leetcode challenge. You guys keep suggesting good problems. My list of videos to be made is very long now. I am processing them one by one. Today's problem was also requested by someone.
Why low = 0 ? According to me low= arr[0]...pls tell
Arr[0] will always be 1 because 1st cow always takes first position. You can even take low=1. There will be no problem. I took 1 extra for safety.
@@techdose4u got it...thanks sir
👍
is normal to do not be able to solve this problem ? because i feel that my level will not grow up
This is not a normal binary search. You can learn this and solve painters partition problem using same technique.
Bro in code low must be a[0] isn't it??
Yes , it will be.
Thank you
Welcome
why low and high are 0 and a[n-1] respectively? Won't low be minimum gap(in this case min gap = 1) and high gap = a[n-1]-a[0]?
Yes you can take that as well. But 0 to a[n-1] is only 1 value larger. So no worries.
awesome.
:)
Thanks bro
You have said that in april it's not possible to make video for iterative merge sort . Can you please make a video of iterative merge sort in this month
Yea sure......I will try to include in on weekend.
Where are you stuck in iterative merge sort? It is simple only. Just like recursive.
@@techdose4u in MERGESORT function if you saw geeksforgeeks tutorial for this. Basically we know what is going to happen but I can't come up intuitively like if we forget this question solution after reading this then how to proceed and all. One more reason I said this because there is no tutorial for this on YT (like you explain) and in blogs we see someone's solution which you also know that it is undigestable so that's why I put this question forward.
Why are we taking mid = (low+high+1)/2 ? I tried with the standard mid = low + (high-low)/2 and it gave WA on SPOJ.
Edit :
I think we can use mid = low + (high-low)/2, but the think thats causing the issue is line no. 32 of code we can't take best directly , we must use something like best = max(best,mid); Then it will work fine for all cases.
What is SPOJ and AGGRCOW? Does it signifies something very important?
I tried this problem , but I was getting WA , because i took `high` as accumulate(arr , arr+ n , 0 ) , i.e , sum of all elements . This is wrong . I watched this video then I realized It should be the highest element in the array . Thanks for this video .
#include
using namespace std ;
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL) ;
#define endl '
'
#define f(i , k , n ) for(int i = k ; i < n ; ++i )
bool isPossible(int a[] , int n , int c , int minDis) {
int lastPos = a[0] ;
int cows = 1 ;
for(int i = 1 ; i < n ; ++i ) {
if ( a[i] - lastPos >= minDis ) {
cows++ ;
lastPos = a[i] ;
if ( cows == c ) return true ;
}
}
return false ;
}
int minDistance(int a[] , int n , int c ) {
sort(a , a+n ) ;
int low = 0 , high = a[n-1] ;
int mid ; int ans = 0 ;
while(low > t;
while (t-- ) {
int n , c ; cin >> n >> c ;
int a[n] ;
f(i , 0 , n ) cin >> a[i] ;
cout
Welcome :)
Sir my doubt is if every time we get some difference value > gap and we can place all cows, that time the minimum value won't be equal to gap right?
Basically why are we doing >=gap and not just = gap
What is SPOJ and AGGRCOW? Does it signifies something very important?
Am I the only one who feeling dumb here?
What happened ?
@@techdose4u Well, I found this concept difficult to understand, but everyone in this comment section seems to understand it rather easily.
That's the reason I felt dumb, lol
Ohh...actually this is easy once you get my idea 😅
Your voice sounds familliar 🤔 🤔 🤔
Really!! 😂
extermeley bad explanation....totaly messed with gap values