/sci/ - Science & Math » Thread #12206222

186KiB, 975x477, b91e305101b390a6ae9a13a6476ef7ec.png

View Same Google iqdb SauceNAO

Help with an Algorithm problem

Anonymous Thu 08 Oct 03:13:51 2020 No.12206222 View Reply Original Report

Quoted By: >>12206539

Could anyone help me solve this question or tell me if my response is correct?

I think the accurate count would be 2n - 100 since at most n numbers are being removed from the front and at most n numbers are being removed from the back. 100 are left untouched.

Anonymous

Anonymous Thu 08 Oct 2020 03:36:19 No.12206271 Report

Quoted By: >>12206307

If r is number removed from back, q is number removed from front and c is number of operations. We have

$n-(r+q) = 100$
$c = n+r+q = n+n-100 = 2n-100$

Anonymous

Anonymous Thu 08 Oct 2020 03:46:05 No.12206307 Report

Quoted By:

>>12206271
Thank you so much!

Anonymous

Anonymous Thu 08 Oct 2020 03:55:25 No.12206333 Report

Quoted By: >>12206355 >>12206357

No it's something like 2^100.
Each time you insert x, if x is smaller than the smallest element in Q then Q gets erased down to 1 element.
Whatever the smallest element in Q is there's as many numbers below as above so that means there's 50% chance each insert erases everything and it will take 2^100 inserts to reach a Q length of 100.
With y removals from the front it's 2^(100+y) operations.

Anonymous

Anonymous Thu 08 Oct 2020 04:02:27 No.12206355 Report

Quoted By: >>12206374

>>12206333
You're a fucking moron. We know exactly how many elements were inserted into the queue. Picture this, you insert 100 elements which are equal. How many operations did you use it? It sure as shit ain't $2^100$ .

Anonymous

Anonymous Thu 08 Oct 2020 04:04:06 No.12206357 Report

Quoted By:

>>12206333
>insert element
>50/50 chance that element is smaller than all other elements
nice bait

Anonymous

Anonymous Thu 08 Oct 2020 04:10:52 No.12206374 Report

Quoted By:

>>12206355
No we know the difference between the number inserted and the number removed. 100 = 100+z-z, z can be anything but statistically it's 2^100+y

Anonymous

Anonymous Thu 08 Oct 2020 05:07:52 No.12206539 Report

Quoted By:

>>12206222
You can also think in an amortized way: any number inserted has initially a cost of 2. One for the insertion and one for paying for its own deletion later on. You insert n which makes for 2n and you know just 100 remain so 100 was overpaid; 2n-100.

Anonymous

Anonymous Thu 08 Oct 2020 06:15:22 No.12206660 Report

Quoted By:

Thank you everyone for the responses!

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches