-
Notifications
You must be signed in to change notification settings - Fork 3
/
index.html
73 lines (73 loc) · 6.22 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>DSA2: PA2: Messy Bookshelves</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.columns{display: flex; gap: min(4vw, 1.5em);}
div.column{flex: auto; overflow-x: auto;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
/* The extra [class] is a hack that increases specificity enough to
override a similar rule in reveal.js */
ul.task-list[class]{list-style: none;}
ul.task-list li input[type="checkbox"] {
font-size: inherit;
width: 0.8em;
margin: 0 0.8em 0.2em -1.6em;
vertical-align: middle;
}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="../../markdown.css" />
</head>
<body>
<header id="title-block-header">
<h1 class="title">DSA2: PA2: Messy Bookshelves</h1>
</header>
<p><img src="https://webstockreview.net/images/bookshelf-clipart-messy-6.jpg" style="height:400px;float:right;margin-left:20px;margin-bottom:20px" /></p>
<p>Professor Pettit’s children have to help clean the house once a week. One of their jobs is to neatly put the books back on the bookshelf. But, alas, being children, they often just throw them on the bookshelf in any order. This makes the bookshelf look quite messy. And that type of messiness is not allowed in the house!</p>
<p>In an effort to determine just <em>how</em> messy the book’s ordering is, Professor Pettit has numbered each book. The books should be in (ascending) sorted order. To see how messy the bookshelf is, one has to count how many, of all possible pairings of books, are out of order (meaning a higher numbered book is before (to the left of) a lower numbered book).</p>
<p>Your job is to write a program to help Professor Pettit determine just how messy his bookshelf is.</p>
<h3 id="input">Input</h3>
<p>The first line of the input will contain a positive integer <span class="math inline"><em>n</em> ≤ 2<sup>10</sup></span>, will be the number of test cases in the input. Each test case consists of exactly two lines. The first line contains the integer number of books, <span class="math inline"><em>b</em> ≤ 2<sup>31</sup></span>. The second line of each test case will contain <span class="math inline"><em>b</em></span> integers, space separated, which is the order the books appear on the shelf. The <span class="math inline"><em>b</em></span> book numbers will always be 1 to <span class="math inline"><em>b</em></span>, with no duplicates of the same book number for a given test case.</p>
<p>All input is provided via standard input.</p>
<h3 id="output">Output</h3>
<p>The output is a single integer per test case, which is how many book pairs are out of ascending sorted order. For any positions <span class="math inline"><em>i</em></span> and <span class="math inline"><em>j</em></span>, such that <span class="math inline"><em>i</em> < <em>j</em></span>, let <span class="math inline"><em>b</em><sub><em>i</em></sub></span> and <span class="math inline"><em>b</em><sub><em>j</em></sub></span> represent the books at positions <span class="math inline"><em>i</em></span> and <span class="math inline"><em>j</em></span>. If <span class="math inline"><em>b</em><sub><em>i</em></sub> > <em>b</em><sub><em>j</em></sub></span>, then that book pair is out of order. Recall that you are guaranteed that <span class="math inline"><em>b</em><sub><em>i</em></sub> ≠ <em>b</em><sub><em>j</em></sub></span> as long as <span class="math inline"><em>i</em> ≠ <em>j</em></span>.</p>
<p>The output, per test case, is the total number of book pairs that are out of order. Note that this number may be greater than <span class="math inline">2<sup>32</sup></span>, so it can not be stored in a 32-bit <code>int</code> variable, but will be less than <span class="math inline">2<sup>63</sup></span>, so it can be stored in a 64-bit <code>long</code> variable.</p>
<p>All output is to be printed to standard output.</p>
<h3 id="requirements">Requirements</h3>
<p>This can be done via two nested for loops, but that yields a <span class="math inline"><em>Θ</em>(<em>n</em><sup>2</sup>)</span> algorithm. Your algorithm must be a <strong>divide and conquer</strong> algorithm, as discussed in class – we are going to check this. You cannot use parallelization – your program will be limited to one thread/process.</p>
<p>Your algorithm must run in <span class="math inline"><em>Θ</em>(<em>n</em> log <em>n</em>)</span> time. We are going to check this with a <em>very</em> large test case provided via standard input. If your algorithm is not <span class="math inline"><em>O</em>(<em>n</em> log <em>n</em>)</span>, Gradescope will time out on your submission. That test case will have an answer that is greater than <span class="math inline">2<sup>32</sup></span>.</p>
<p><strong>You will need to name your recursive function <code>solve()</code> (not <code>Solve()</code>, not <code>solver()</code>, not anything else).</strong></p>
<p><strong>You will need to use a <code>long</code> counter for this program if using Java, as there may be more than 2^32 (the number of values in a 32-bit integer) book pairs that are out-of-order.</strong></p>
<h3 id="example-input">Example Input</h3>
<pre><code>2
4
4 3 2 1
3
1 3 2</code></pre>
<p>This input can be found in the <a href="sample.in">sample.in</a> file.</p>
<h3 id="example-output">Example Output</h3>
<pre><code>6
1</code></pre>
<h3 id="skeleton-code">Skeleton Code</h3>
<p>We have provided skeleton code for this assignment. This code only shows how to read in the input; you have to add the rest.</p>
<ul>
<li><a href="pa2-skeleton.py.html">pa2-skeleton.py</a> (<a href="pa2-skeleton.py">src</a>)</li>
<li><a href="PA2Skeleton.java.html">PA2Skeleton.java</a> (<a href="PA2Skeleton.java">src</a>)</li>
</ul>
<p>You will have to rename them to pa2.py or PA2.java prior to submission. You can run your program as such:</p>
<pre><code>> python3 pa2.py < sample.in
6
1
> javac PA2.java
> java PA2 < sample.in
6
1
></code></pre>
</body>
</html>