ES242. Data Structures and Algorithms I. Week 02 Lab
ES242. Data Structures and Algorithms I.
Lab Quiz 2
There are n people partaking in a project X. The capability value of the ith person is denoted as C[i]. The manager of the project has proposed the following algorithm to calculate the capability of the group (to undertake project X):
On each turn, choose two people, x and y, with capabilities C[x] and C[y] respectively (with C[x] <= C[y]). A unity procedure is followed:
- If the two have same capability value, remove both.
- Else, person
xis removed, and capability of person y changes toC[y]-C[x]
It is obvious that at the end at most one person shall remain. The capability value of the person is stated as the capability value of the group. If no person remains, capability value of the group is taken as 0.
You have the find the minimum possible capability value of the group.
Note that the choice of people for the unite procedure directly affects the final capbility value.
Input Format
The first line contains an integer n.
The next line contains n space-separated integers representing C[]
Output Format
Return the minimum possible capability value of the group according to the mentioned algorithm
Sample I/O
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Bangalore has n locations, and m bidirectional roads between them. The goal is to construct new roads so that there is a route between any two cities.
Your task is to find out the minimum number of roads required.
Input
The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,...,n.
After that, there are m lines describing the roads. Each line has two integers a and b: there is a road between those cities.
A road always connects two different cities, and there is at most one road between any two cities.
Output
Print an integer k: the number of required roads.
Constraints
- 1 \leq n \leq 10^5
- 1 \leq m \leq 2⋅10^5
- 1 \leq a,b \leq n
Sample I/O
Sample Input
Sample Output
After all the dropouts, there are n people left in ES242. The class has students from across different batches and disciplines, so some people know each other while others do not.
You want spread a rumor about whether ES242 will be repeated in the next semester. Students who are friends with each other will share any information they get. To get student i to start spread a rumor, you have to pay them in by buying c[i] samosas at Aadhya. Once someone is bribed, s/he tells it to all her/his friends, and they start spreading the rumor to their friends (for free), and so on.
You want everyone to catch the rumor. What is the minimum number of samosas you need to buy?
Take a look at the notes if you think you haven’t understood the problem completely.
Input
The first line contains two integer numbers n and m (1 \leq n \leq 10^5, 0 \leq m \leq 10^5) — the number of students in the class and the number of pairs of friends.
The second line contains n integer numbers c[i] –— the amount of samosas i-th student asks to start spreading the rumor.
Then m lines follow, each containing a pair of numbers (x[i], y[i]) which represent that characters x[i] and y[i] are friends (1 \leq x[i], y[i] \leq n, x[i] \neq y[i]). It is guaranteed that each pair is listed at most once.
Output
Print one number — the minimum number of samosas you have to buy to spread the rumor fully.
Sample I/O
Sample Input
Sample Output
Sample Input
Sample Output
Note
In the first example the best decision is to bribe the first student (he will spread the rumor to fourth student, and the fourth one will spread it to student). You also have to bribe the second and the third students, so they know the rumor.
You are playing a decision making game where the output can be either 1 or 0.
Given a N X N matrix, the objective of the game is to predict if it’s possible to reach from a given source to a destination in less than or equal to k moves.
Some constraints are as follows:
You can only move to adjacent positions in
1move.You can only move diagonally across the matrix.
Given the value of n, and the maximum moves k, determine if you can fulfill the requirement: can you reach from source to destination in less than k moves?
Input Format
The first line contains an integer n.
The second line contains an integer k, denoting the maximum number of moves you can make.
The third line contains two space-separated integers, i and j. An entry i j denotes i as the x-coordinate and j as y-coordinate of the source location.
The fourth line contains two space-separated integers, m and n. An entry m n denotes m as the x-coordinate and n as y-coordinate of the destination.
Output Format
Return 1 if you can reach from source to destination in less than k moves. Else, return 0.
Sample I/O
Sample Input 1
Sample Output 1
You are a student in a university U.
You can only register in a certain program A, if the following condition is met:
You have registered for all courses with the course IDs [0,1... num_courses-1]
If there exists at least one i in range [0,1... num_courses-1] for which you cannot register, then you cannot register from the program.
Some constraints are as follows:
Some courses may have prerequisite courses. For example if
iis a prerequisite of course IDj, then you must register foribeforejYou can not repeat a course, you can only register for a course one.
Given the value of num_courses, and the prerequisite requirements, determine if you can fulfill the requirement: can you register for A (can you register for all the courses in range num_courses)?
Input Format
The first line contains an integer num_courses.
The second line contains an integer num_prerequisites, denoting the number of prerequisites or conditions you have to fulfil.
The next num_prerequisites lines contain 2 space-separated integers i and j. An entry i j denotes course j is a prerequisite for course i.
Output Format
Return YES if you can register for program A. Else, return NO.
Sample I/O
Sample Input 1
Sample Output 1
