2. (20 points) Alice writes n distinct integers on a blackboard, and picks a positive integer...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
2. (20 points) Alice writes n distinct integers on a blackboard, and picks a positive integer K. She then allows Bob to make moves, each of which consist of the following steps. 1. Identify two integers x and y on the blackboard which differ by at most K, i.e. |xy|K. 2. Erase the smaller of the two chosen integers. Bob's task is to make moves in this way until he is no longer able to do so. Note that in some cases, Bob may be unable to make even a single move. Design an algorithm which runs in O(n log n) time and finds the longest sequence of moves. If there are several sequences of maximum length, you may find any of them. 2. (20 points) Alice writes n distinct integers on a blackboard, and picks a positive integer K. She then allows Bob to make moves, each of which consist of the following steps. 1. Identify two integers x and y on the blackboard which differ by at most K, i.e. |xy|K. 2. Erase the smaller of the two chosen integers. Bob's task is to make moves in this way until he is no longer able to do so. Note that in some cases, Bob may be unable to make even a single move. Design an algorithm which runs in O(n log n) time and finds the longest sequence of moves. If there are several sequences of maximum length, you may find any of them.
Expert Answer:
Related Book For
Posted Date:
Students also viewed these programming questions
-
The Energetic Company needs to make plans for the energy systems for a new building. The energy needs in the building fall into three categories: (1) electricity. (2) heating water, and (3) heating...
-
answer the question clearly You are building a flight-control system for which a convincing safety case must be made. Would you assign the tasks of safety requirements engineering, test case...
-
This question concerns lexical grammars. (a) Tree Adjoining Grammars contain two types of elementary tree. (i) What are these trees called? [1 mark] (ii) If one were building a grammar for English...
-
a. How could aspirin be synthesized, starting with benzene? b. Ibuprofen is the active ingredient in pain relievers such as Advil®, Motrin®, and Nuprin®. How could ibuprofen be...
-
What are the advantages and disadvantages of a four-jaw independent chuck versus a three-jaw chuck?
-
Eddie's Precision Machine Shop is insured for \(\$ 700,000\). The present yearly insurance premium is \(\$ 1.00\) per \(\$ 100\) of coverage. A sprinkler system with an estimated life of 20 years and...
-
1. ETHICS Lee McNeely told Hardee's officials that he was interested in purchasing multiple restaurants in Arkansas. A Hardee's officer assured him that any of the company-owned stores in Arkansas...
-
The outstanding capital stock of Edna Millay Corporation consists of 2,000 shares of $100 par value, 8% preferred, and 5,000 shares of $50 par value common. Instructions Assuming that the company has...
-
Topic: Valuation of Securities To what extent do you agree or disagree with the following statement on a scale of 1 to 5 where 1 = strongly disagree and 5 = strongly agree. Please explain your...
-
No- State Insurance Company has made the following estimate of auto damage for several groups of potential customers who own cars worth $10,000. There are an equal number of customers in each group....
-
x3 +x + 2xy dy The solution of the differential equation dx = 0 is: x2 + 1 A) y = (x + 1)[1In /x2 + 1+ c] B) y = (x + 1)[[n(x + 1) + c] !! C) y = (x + 1); In(x + 1) + xc] D) y = (x + 1)[, In /x + 1 +...
-
_____ is a combination of job satisfaction, ability, and a willingness to perform for the organization at a high level and over an extended period of time.
-
Briefly describe the controls that should exist over use of removable storage media in a mainframe computer environment.
-
Why must care be taken if removable storage media is sent to an outside organization for cleaning and repair?
-
_____ is the failure of an employee to report to the workplace as scheduled.
-
Briefly explain the file librarian's responsibilities with respect to backup storage media in a mainframe computer environment. What responsibilities do microcomputer users have with respect to...
-
Wynn Farms reported a net operating loss of $160,000 for financial reporting and tax purposes in 2021. The enacted tax rate is 25%. Taxable income, tax rates, and income taxes paid in Wynn's first...
-
Juanita owns a home in Richardson, TX. She purchases a Homeowners Policy (HO-3) from Farm State Ins. Co. The policy provides $100,000 in liability coverage (coverage E) and $5,000 in Med Pay coverage...
-
If E[X] = 1 and Var(X) = 5, find (a) E[(2 + X)2]; (b) Var(4 + 3X).
-
Use Theoretical Exercise 8 to prove that /Z Ft Ft
-
Suppose in Problem 72 that the two teams are evenly matched and each has probability 12 of winning each game. Find the expected number of games played. Problem 72 Two athletic teams play a series of...
-
On the Internet, locate "Corruption and Related Matters: An Annotated Bibliography" by the Independent Commission Against Corruption, especially the Chapters on White Collar Crime and Workplace...
-
Go to the AICPA's Antifraud Resource Center and search for forensic accounting topics. Read some of the material listed. Search for material dealing with litigation support. What type of forensic...
-
Go to the Association of Certified Fraud Examiners web site and locate the 2008 Report to the Nation on Occupational Fraud and Abuse (The 2008 Wells Report). a. The cases in this study generated...
Study smarter with the SolutionInn App