Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Programming Assignment
Instructions
? Submit the soft-copy of your program to Learn@PolyU
? You can only submit one program file (either C++ or Java or Python),
and the filename must follow the format below.
Language
C++
Java Python
Problem
Filename format mainStudentID.cpp mainStudentID.java mainStudentID.py
Filename example
main10987654d.cpp main10987654d.java main10987654d.py
Section 1:
Input: Output:
An array A[0..n–1] (of comparable elements)
The total number of pairs (i, j) such that i < j and A[i] > A[j].
In this problem, the input can be an array of integers or an array of strings.
(1.1) Comparisonforstrings
We use the lexicographical order to compare strings. Let s[x] denote the x-th letter of the string s.
Given two strings s[0..sL–1] and r[0..rL–1], s>r holdsif
? risaprefixofs(i.e.,rL<sLand?p=0..rL-1s[p]=r[p]) OR ? there exists a position k such that s[k]>r[k] and ?p=0..k-1 s[p]=r[p]
Examples:
? charge > balance ? balance > bal
? bbbbbb > bbbbba
(1.2) Examplesfortheproblem Input
Output Explanation
5 5 pairs satisfy the requirement:
(0,1), (2,3), (2,5), (3,5), (4,5).
5 5 pairs satisfy the requirement: (0,1), (2,3), (2,5), (3,5), (4,5).
Example for an array of integers Example for an array of strings
A[0..6] =
| 31 | 24 | 85 | 76 | 93 | 50 | 93 |
A[0..6] =
| “charge” | “balance” | “wind” | “thunder” | “zoo” | “mile” | “zoo” |
p. 1
Section 2: Input and Output Format
Here are samples of the input file and the output of your program.
Sample input file “file1.txt” The output on screen (stdout)
integer
7
31
24
85 76 93 50 93
5
Sample input file “file2.txt” The output on screen (stdout)
string
7
charge
balance
wind
thunder
zoo
mile
zoo
5
The format of the input file is as follows:
? the 1st line shows the type (either integer or string), ? the 2nd line shows the number of elements,
? each subsequent line shows an element.
The number of elements is in the range 1.. 10000000.
For integers, the elements are in the range 1..10000000.
For strings, the elements have length at most 20 and contain lower-case letters only.
We will run your program by a command line like:
Language
C++ (after compilation) Java (after compilation) Python
Command line
./mainStudentID input123.txt
java mainStudentID input123.txt python mainStudentID.py input123.txt
where the argument “input123.txt” is an example of the input filename. Your program should only output the result number.
Please follow the above output format and DO NOT print any extra information.
p. 2
Section 3: Hints
(3.1) Comparisonsforstrings
You are allowed to use operator or standard library function (e.g., in C++, Java, Python) to perform lexicographic comparison for string. Examples:
? C++: https://cplusplus.com/reference/string/string/compare/
? Java: https://docs.oracle.com/javase/tutorial/java/data/comparestrings.html
? Python: https://docs.python.org/3/library/stdtypes.html#comparisons Please test them before using them in your program.
(3.2) Hintsforprogramming
? Use a large enough integer type (e.g., long) to prevent “integer overflow” in counting.
? A simple program is to use nested for-loops. Its time complexity is O(n2). It is acceptable for
small input file but too slow for large input file.
? If you wish to obtain higher marks, try to use the “divide-and-conquer” approach in your
program. It is possible to achieve the time complexity O(n log n) time.
? Some programming tricks can be used to speedup your program by a constant factor.
p. 3
Section 4: Grading Criteria
(4.1) Namingconventions,compilationandexecutioncommands
? Before submission, rename your program to mainStudentID.cpp,
OR mainStudentID.java, OR mainStudentID.py,
e.g., main10987654d.cpp e.g., main10987654d.java e.g., main10987654d.py
? [C++ and Java only] Make sure that you can compile your program using the command: g++ mainStudentID.cpp -o mainStudentID
OR javac mainStudentID.java
o No marks will be given if your program cannot be compiled.
? We will run your program by a command line like: ./mainStudentID input123.txt
OR java mainStudentID input123.txt
OR python mainStudentID.py input123.txt where the argument “input123.txt” is an example of the input filename.
Make sure that you can execute the above commands on the COMP apollo server successfully. Otherwise, no marks will be given. The current versions on apollo are as follows:
g++ (GCC) 4.8.5, javac 1.8.0_20, Python 2.7.5
(4.2) Testfilesforgrading