1. Homepage
  2. Programming
  3. CSC3100 Data Structures Fall 2023 Programming Assignment 3: Node Distance, Price Sequence

CSC3100 Data Structures Fall 2023 Programming Assignment 3: Node Distance, Price Sequence

Engage in a Conversation
CUHKCSC3100Data StructuresNode DistancePrice SequenceC++JavaPython

CSC3100 Data Structures Fall 2023 Programming Assignment 3 CourseNana.COM

1 Node Distance(40% of this assignment) CourseNana.COM

1.1 Description CourseNana.COM

You are given a tree with n nodes, where each edge in the tree has a corresponding weight denoting the length of each edge. The nodes in the tree are colored either black or white. Your task is to calculate the sum of distances between every pair of black nodes in the tree. Let B = {b1, b2, ...} a set of black nodes, then the answer is formulated as: CourseNana.COM

|B|−1 |B|
Ans= XX dist(bi,bj) CourseNana.COM

i=1 j =i+1
where |B| denotes the number of the black nodes in the tree, and dist(bi,bj) is the length of the simple CourseNana.COM

path from the i-th to j-th black node.
Write a program to calculate the sum of distances on the tree between every pair of black nodes
Ans CourseNana.COM

in the given tree. CourseNana.COM

1.2 Input CourseNana.COM

The first line contains an integer n, representing the number of nodes in the tree.
The second line contains
n space-separated integers {c1,c2,...,ci,...,cn} where ci is either 0 or 1. CourseNana.COM

ci = 1 indicates that the i-th node is black, and ci = 0 indicates that the i-th node is white. CourseNana.COM

The following n 1 lines, {l1, l2, . . . , lp, . . . , ln1}, denoting the structure of the tree follow, each line lp contains 2 integers qp and wp, denoting an edge of length wp between the p + 1-th node and the qp-th node. CourseNana.COM

1.3 Output CourseNana.COM

Output the sum of distances for every pair of black nodes in the tree. CourseNana.COM

Sample Input 1 Sample Output 1 CourseNana.COM

This sample considers a tree with 5 nodes: CourseNana.COM

The 1-st node is white, and 2-, 3-, 4-, 5-th nodes are black.
The length of edge: (2-nd, 1-st): 1, (3-rd, 1-st): 2, (4-th, 3-rd): 2, (5-th, 3-rd): 1.
Ans = ((1 + 2) + (1 + 2 + 2) + (1 + 2 + 1)) + (2 + 1) + 2 + 1 = 18. CourseNana.COM

Sample Input 2 Sample Output 2 CourseNana.COM

9 96 010111111
12
13
CourseNana.COM

22 21 52 53 12 71 CourseNana.COM

Three additional large-scale samples are included in the provided files, namely, A samplecase1.in/.ans, A samplecase2.in/.ans and A samplecase3.in/.ans. CourseNana.COM

Problem Scale & Subtasks CourseNana.COM

For100%ofthetestcases,1n105,1qp1 <p,1wp 1000 CourseNana.COM

Test Case No. 1-4 CourseNana.COM

5-7 8
9 10
CourseNana.COM

Hint CourseNana.COM

Constraints n 100
n 1000 qp = p CourseNana.COM

qp = 1
No additional constraints
CourseNana.COM

It can be proven that the given structure is definitely an unrooted tree. CourseNana.COM

For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Use scanf("%lld",&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input n. And the other operations for long and long long are quite same as int. CourseNana.COM

For Python users, if there occurs a RecusrionError, see here. CourseNana.COM

2 Price Sequence (50% of this assignment) 2.1 Description CourseNana.COM

Mario bought n math books and he recorded their prices. The prices are all integers, and the price sequence is a = {a0 , a2 , ...ai , ..., an1 } of length n (n 100000). Please help him to manage this price sequence. There are three types of operations: CourseNana.COM

BUY x: buyanewbookwithpricex,thusxisaddedattheendofa. CourseNana.COM

CLOSEST ADJ PRICE: output the minimum absolute difference between adjacent prices. CourseNana.COM

CLOSEST PRICE: output the absolute difference between the two closest prices in the entire se- quence. CourseNana.COM

A total of m operations are performed (1 m 100000). Each operation is one of the three mentioned types. You need to write a program to perform given operations. For operations ”CLOSEST ADJ PRICE” and ”CLOSEST PRICE” you need to output the corresponding answers. CourseNana.COM

2.2 Input CourseNana.COM

The first line contains two integers n and m, representing the length of the original sequence and the number of operations. CourseNana.COM

The second line consists of n integers, representing the initial sequence a.
Following that are
m lines, each containing one operation: either BUY x, CLOSEST ADJ PRICE, or CourseNana.COM

CLOSEST PRICE (without extra spaces or empty lines). CourseNana.COM

2.3 Output CourseNana.COM

For each CLOSEST ADJ PRICE and CLOSEST PRICE command, output one line as the answer. CourseNana.COM

Sample Input 1 CourseNana.COM

34
719 CLOSEST_ADJ_PRICE BUY 2 CLOSEST_PRICE CLOSEST_ADJ_PRICE
CourseNana.COM

Sample Input 2 CourseNana.COM

6 12
30 50 39 25 12 19 BUY 4 CLOSEST_PRICE
BUY 14 CLOSEST_ADJ_PRICE CLOSEST_PRICE
BUY 0 CLOSEST_PRICE
BUY 30
BUY 12 CLOSEST_PRICE
BUY 20 CLOSEST_PRICE
CourseNana.COM

Sample Output 1 CourseNana.COM

6 1 6 CourseNana.COM

Sample Output 2 CourseNana.COM

5 7 2 2 0 0 CourseNana.COM

Two additional large-scale samples are included in the provided files, namely, B samplecase1.in/.ans and B samplecase2.in/.ans. CourseNana.COM

CourseNana.COM

Problem Scale & Subtasks CourseNana.COM

For 100% of the test cases, 2 n, m 1 × 105, 0 ai, x 1012 CourseNana.COM

Test Case No. 1-4 CourseNana.COM

5-6 7-9 10 CourseNana.COM

Hint CourseNana.COM

Constraints
n 103,m 103
There is no CLOSEST PRICE operation
ai and x are uniformly distributed at random within the range [0,1012] No additional constraints CourseNana.COM

For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Use scanf("%lld",&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input n. And the other operations for long and long long are quite same as int. CourseNana.COM

For Python users, if there occurs a RecusrionError, see here. CourseNana.COM

Get in Touch with Our Experts

QQ QQ
Wechat WeChat
Whatsapp Whatsapp
CUHK代写,CSC3100代写,Data Structures代写,Node Distance代写,Price Sequence代写,C++代写,Java代写,Python代写,CUHK代编,CSC3100代编,Data Structures代编,Node Distance代编,Price Sequence代编,C++代编,Java代编,Python代编,CUHK代考,CSC3100代考,Data Structures代考,Node Distance代考,Price Sequence代考,C++代考,Java代考,Python代考,CUHKhelp,CSC3100help,Data Structureshelp,Node Distancehelp,Price Sequencehelp,C++help,Javahelp,Pythonhelp,CUHK作业代写,CSC3100作业代写,Data Structures作业代写,Node Distance作业代写,Price Sequence作业代写,C++作业代写,Java作业代写,Python作业代写,CUHK编程代写,CSC3100编程代写,Data Structures编程代写,Node Distance编程代写,Price Sequence编程代写,C++编程代写,Java编程代写,Python编程代写,CUHKprogramming help,CSC3100programming help,Data Structuresprogramming help,Node Distanceprogramming help,Price Sequenceprogramming help,C++programming help,Javaprogramming help,Pythonprogramming help,CUHKassignment help,CSC3100assignment help,Data Structuresassignment help,Node Distanceassignment help,Price Sequenceassignment help,C++assignment help,Javaassignment help,Pythonassignment help,CUHKsolution,CSC3100solution,Data Structuressolution,Node Distancesolution,Price Sequencesolution,C++solution,Javasolution,Pythonsolution,