At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
Sorry I havent done combinatorics in years. Let's see if someone else can put some light here.
@ganeshie8 can you help me out here? having really hard time to get started. :/
xD so much reading
if u break it down and ask me a particular question on it, maybe i can help uq
i can only help with the second part as I am unsure of the first
Well for the first group, i checked 6 times. 0 times for the 2nd group. 4 times for the last group.
yes, i understand how the split works.
okay sooo dooo ittttttttttt
that gives me 12.
i mean, 6*
hmm wait okay
uM, I have to submit this hw by 12 am and it's 10:40pm. Is it ok if Ganeshie chips in too? He said he was familiar with this problem. :/
okay that is what ur doing
can u delete stuff its lagigng me
okay ill just show u >_>
which stuff? comments?
nvm its fine now
there can be a total of k infected in the first group itself
so u will perform binary search on the group n/k, k times in worst case scenario
each time removing 1 sameple
this is an upper bound
but its kinda weird to see this because its not really even possible, u wont even do this many things if u are finding samples like that
Oh kk. So that, formula works?
yes its just an upper bound
there are multiple upper bounds u can find, its just what s the closest upperbound
i advise u to find a better one
just make sure atleast that park makes sense
so it's a ceiling function?
oh um that shud be n/k
u are doing binary search on each group, and at most ud have to do binary search k times on a single group
wait, isn't upper bound supposed to be in theta format?
in big O notation?
can u show some work or attempts
What do you mean? And also, shouldn't the coefficient in front of the summation be n/k and not just k?
cause initially i thought there should be no coefficient. But if there is going to be any, and based on your explanation that there are n/k groups and we're iterating through them each time, i thought it should be n/k
think about this case
N samples and N-1 infections
or N samples and N infections u dont know that there were N infections
so for each group, ud have to perform N/K binary searches
so for K groups ull perform N/k binary searches on elements N/k as they decrease by 1 every time
OOO. gotchya gotchya.
And why not just use a celing bracket instead of R for rounding up? is that just your convention? just wondering.
So wait, in the diagram yu drew, that implies 2 possible upper bounds. But there can only be one answer though.
i dunno the symbol for ceiling lol
that'd be the symbol for ceiling. those brackets flipped downwards would be floor.
But um, my question still persists. Can we have 2 aanswer for upper bound? i thought, only one answer can exist.
ya there are like multiple answers for an upper bound
liek 2<3 also 2<4 2<10.... its just what is the closest possible upper bound
i mean do u get this so far?
u can make it a better function of k u see
this covered alll the worst possible cases for K