CS3334 - Data Structures
Lab 1
Outline
• CS Online Judge – User Guidance
• Simple Exercises about Linked list and Stack
• Two OJ problems (755 and 815)
Access
• http://acm.cs.cityu.edu.hk/oj2/
• CSLab VPN is required
§ automatic settled on all CS Lab computers
§ CSLab VPN connection:
https://cslab.cs.cityu.edu.hk/services/cslab-vpn-sonicwall
• User Account
§ Need activation your account. The account activation email
has sent to your registration email (from CityU CS OJ
Administrator <[email protected]>)
§ contact TA Mr. Jiacheng HUANG if you have not received
email
(provide your student id and email address)
• TA/Helper:
Search Problems
• Browse Problems
– or use problem id: http://acm.cs.cityu.edu.hk/oj2/index.php/p/755
• Search Problems
– tag ‘CS3334_2024_Fall’
Submit Code
• Check Problem Statement
• Submit
– compiler
– paste code
Example problem OJ1
Verdict Information
q In Queue (QU): your submission code is in the queue, to
be compiled.
q Compile Error (CE): The server could not compile your
submission code. Of course, warning messages are not
error messages.
mostly it is caused by syntax errors:
$ variable not defined,
$ variable type not match,
$ need include library
q Accepted (AC): OK! Your program is correct!
q Presentation Error (PE): Your program outputs are correct
but are not presented in the correct way.
Check for spaces line breaks, ‘ ’, ‘\n’, ‘comma’...
Verdict Information
q Wrong Answer (WA): output is not correct.
$input format,
$special case, any tricky test case?
q Runtime Error (RE): Your program failed during the execution.
$ index overflow, a[-1], a[n+1].
$ Stack/memory overflow, endless recursions, self call
q Time Limit Exceeded (TLE): Your program is not finished in required
time.{time complexity, infinite loop, waiting for input,}
q Memory Limit Exceeded (MLE): Your program tried to use more
memory than allowed.
static memory (array size) + memory for stack/queue during execution
q Output Limit Exceeded (OLE): Your program output too much than
expected. {infinite loop}
Input/Output
//example //read line-by-line
#include <iostream> string linestr;
#include <sstream> while ( getline(cin, linestr) )
#include <string>
using namespace std;
//read from string
int main(){
string input = “Hello World";
string inputstr, outputstr;
stringstream myStream(input);
cin >> inputstr;
outputstr = inputstr + " Hello"; myStream >> str1 >> str2;
cout << outputstr << endl;
return 0; Note: space and line breaks will be
} automatically ignored when reading.
Input/Output
• End of Input
while (cin >> str){
// output result
}
• Output Format (check problem statement)
– for each test case, output the result in one line
while (cin >> caseinput1 >> caseinput2)
cout << caseinput1 + caseinput2 << endl;
Exercise 1 Manipulate List
Given a singly linked list, complete a function
insert(i, d) which inserts a new node with data d at position i of a Singly Linked List.
For example, ”7 5 3 1” with i=1, d=2 will become -> ”7 2 5 3 1 " )
If i is larger than the current list size, we do nothing.
void List::insert(int i, int d)
class List
{
{
...
class ListNode public:
}
{ List( String );
public:
List();
ListNode( int );
ListNode( int, ListNode *); int size();
ListNode *get_Next() ... //various member functions
…
private:
private:
int data; ListNode *first;
ListNode *next; string name;
}; }
Exercise 2 Manipulate List
Given a singly linked list, complete a function
reverse(i, j) which reverses elements from i-th element to j-th element(i,j inclusive).
For example, ”0 1 2 3 4 5” with i=1, j=3 will become -> ”0 3 2 1 4 5" )
void List::reverse(int i, int j)
{
...
} class List
{
class ListNode public:
{
List( String );
public:
ListNode( int ); List();
ListNode( int, ListNode *); int size();
ListNode *get_Next() ... //various member functions
…
private: private:
int data; ListNode *first;
ListNode *next; string name;
};
}
Exercise 3 Stack
Given a stack, complete a function
delete(d) which removes all occurrences of an item d in a stack.
For example, ”5 2 3 5 4” (4 is on top) with d = 5 will become -> ”2 3 4" ) (4 is on
top)
// Stack.h
#include “stdlib.h”
{ void Stack::delete(int d)
public class Stack
{
{
public: ...
Stack(); }
bool IsEmpty();
bool IsFull();
void push(int);
int pop();
int top();
private:
…
// maybe array or linked based implementation
};
}
755 Stock Market
Description
Sherlock is a mad data scientist. Recently he drew a histogram using a dataset
with size N from stock market showing the stock price on each day. Those days
are consecutive. Can you help him find out the rectangle of the maximum area
in the corresponding histogram?
755 Stock Market
Input
The first line of input is an integer T (1 <= T <= 10) representing the number of
test cases. Each test case will follow the format shown below:
The first line: An integer N showing the number of days in the dataset.
The second line: N integers p1, p2, ..., pN showing stock prices on each day.
(1 <= N<= 100000, 1 <= pi <= 100000).
Output
For each case, print a single line containing the maximum area of the rectangle in the
histogram.
755 Stock Market
Sample Input Sample Output
2 12
6 12
345238
7
6254516
815 Sorting
Description
For a given permutation of 1 … n, noting it as P, you need to insert the number in
P into a set S one by one, i.e. P1, P2, …, Pn-1, Pn.
After the insertion of each number,
you need to find the largest number in S that is smaller than the inserted
number and the smallest number in S that is larger than the inserted number.
Initially, two integers 0 and n+1 has already been inserted into S so that the
results always exist.
815 Sorting
Input
The input contains multiple test cases.
The first line of the input contains an integer T, indicating the number of test
cases.
For each test case, the first line contains a positive integer n. The second line
contains n integers, separated by spaces, the i-th integer of which denotes Pi.
Output
For each test case, print n lines, each line contains two integers separated by a
space, the i-th line of which denotes the result required after the insertion of the
i-th number.
The first integer of a result represents the largest number in S that is smaller
than the inserted number and the second one represents the smallest number
in S that is larger than the inserted number.
815 Sorting
Sample Input Sample Output
2 06
5 16
15243 15
2 25
12 24
03
13
Constraint
1 <= n <= 105
It is guaranteed that P is a permutation of 1 … n.
