[Solved] Algorithm Homework7-Grade Sort

You are given the midterm exam scores for all students in all of NYU campuses. The scores are natural numbers no greaterthan 100.To report the midterm grades, you need to display all the scores in ascending order.InputThe first line contains one integer N. N is the total number of grades, 1 N 4,000,000.In the next line, there are N integers indicating the grades.OutputPrint a line with N space separated integers. These integers are the grades of the midterm sorted in ascending order.Warning: This problem may have potentially very large input/outpu. Use fast IO operations, please.Example 1Input:450 60 100 90Output:50 60 90 100Example 1Input:699 92 93 92 93 91Output:91 92 92 93 93 99Page 1/1Jacobs LadderThe World Tree is a towering tree standing in the center of the endless Cloud Sea. The fabled paradise Elysium is said tobe located at the top of the World Tree. The exterior of the World Tree is covered in thick growths of wood, while the interioris a high-tech ladder with n rungs.Poppi can use rocket jumping to climb the ladder, but she cannotskip any rungs. Initially Poppi is on the ground. Initial strength ofthe rocket is set to k. As long as her jumps are strictly smallerthan k, her rockets strength remains at k. If her jump is everequal to k, the strength decreases by 1. The rocket cannot beused to propel her to the height greater than k.For example let the height of the rungs from the ground be 2, 7, 8,12, 14 respectively and the initial strength of the rocket be k be 5.Her jumps are:1. Jumped 2 feet from the ground to the 1st rung (ground to 2),k remains 5.2. Jumped 5 feet for the next rung (2 to 7). So, k decreases to4.3. Jump 1 feet for the 3rd rung (7 to 8). So, k remains 4.4. Jump 4 feet for the 4rd rung (8 to 12). So, k decreases to 3.5. Jump 2 feet for the 5rd rung (12 to 14). So, k remains 3.Since the rockets with the greater strength cost more, Poppi asksyou for help in figuring out the minimum initial strength k for the rocket sot that she can reach the top rung.InputThe first line contains 1 integer: a positive n (0 < n 10^5) giving the number of rungs in the ladder.The next line contains n space separated integers, r1, r2, , rn(1 r1 < r2 < < rn 10^7), denoting the heights of therungs from the ground.OutputPrint the minimum value of k as described above.Example 1Input:52 7 8 12 14Output:5Page 1/1Polar BearDue to global warming, the sea level is rising.Mr. Panda is a polar bear who lives at the Bamboo Island. He is worried about flooding. Some low lying parts of BambooIsland will be under water if the sea levels continue to rise. Mr. Panda hates swimming so it is a bad news for him.Mr. Panda has a topographic map of the Bamboo Island.Bamboo Island has a rectangular shape, and can bedivided into a n by m grid. The elevation of the each field atgrid point (i,j) is Aij. The soil at Bamboo Island is porous,and the water can freely flow through it. Thus, if the sealevel is no less than Aij, then the field at grid point (i,j) willbe flooded.Adjacent un-flooded fields (i.e., sharing common edge)create safe areas. Mr. Panda is interested in the number ofdistinct safe areas for a given sea level.An example of 35 map is given on the right. Numbersdenote the elevation of the Ai,j as described above. Floodedfields are shaded. There will be1 safe area when the sea level is 0,1 safe area when the sea level is 1,2 safe areas when the sea level is 2,2 safe areas when the sea level is 3,1 safe area when the sea level is 4 (not shown in the image),and no safe areas when the sea level is 5 (not shown in the image).InputThe first line contains two numbers n and m separated by a single space, the dimensions of the Bamboo Island, where 1 <=n,m <= 1000.Next n lines contain m integers from the range [1, 10^9 ] separated by single spaces, denoting the elevations of therespective fields.Next line contains an integer T, 1 <= T <= 10^5, the number of sea levels that Mr. Panda is interested in.The last line contains T integers ti, separated by single spaces, such that 0 <= t1 <= t2 <= . . . <= tT 1 <= tT <= 10^9. The ith integer denotes the sea level of the i-th query.OutputOutput a single line consisting T numbers ci separated by single spaces, where ciis the number of safe areas when the sealevel is equal to tiExampleInput:3 53 3 3 2 43 5 3 1 43 3 3 2 451 2 3 4 5Output:1 2 2 1 0Page 1/1Unique SubarrayA subarray is the sequence of consecutive elements in an array. A unique subarray is a subarray in which all elements areunique (i.e., no repeated values). Given an array, your task is to calculate the maximum length of a unique subarray.For example [4, 3, 2, 2, 1], the maximum length of of a unique subarray is 3. The unique subarray is [4,3,2]. [3,2,2,1] is asubarray of length 4, but since 2 appears twice in this subarray, it is not a unique subarray.InputThe 1st line contains an integer n (1 <= n <= 10^6), specifying the length of the array.The following line contains n integers, in range [1, 10^9], denoting the elements of the array.OutputThe maximum length of a unique subarray.Example 1Input:54 3 2 2 1Output:3Example 2Input:61 1 1 1 1 1Output:1Page 1/1APS HomeworkDaru is weary of the time-consuming APS homework. As a super hacker, he developed an AI called Amadeus to help himsolve his homework problems automatically.There are N problems for this week. It takes ai seconds for Amadeus to solve the i-th problem. Since Daru is a superhacker, he has broken into Gradescope to figure out how long it takes Gradescope to evaluate each submission. He knowsthat it takes bi seconds for Gradescope autograder to evaluate and accept the correct solution for the i-th problem. (Daru isnot interested in cheating by also downloading all the test cases from Gradescope since its not cool and he knows that thiswould violate the academic integrity policies).Amadeus can not work on multiple problems simultaneously. It will follow an order given by Daru to solve problems. OnceAmadeus solves a problem, it submits the solution to Gradescope and continues to the next problem.It takes no time to submit a solution and Gradescope is able to evaluate multiple solutions at the same time. The solution forthe i-th problem will be accepted in exactly bi seconds after it is submitted to Gradescope. Amadeus always produces acorrect solution, so Gradescope always accepts after the first submission.Daru wants to find an order of problems to minimize the time necessary for all problems to be accepted on Gradescope.Can you help him to figure out the optimal order?InputThe first line contains one integer N. N is the number of problems in homework, 1 N 1000.The i-th line of the following N lines contains a pair of integers ai and bi(1 ai, bi 10000), as described above.OutputOutput one number followed by a newline. The total number of seconds that it takes Amadeus to solve, submit and getaccept verdict for all the problems when the order of the problems is optimal. (Note, that there may be multiple orders thatresult in the same time. Since you only report on the time, the actual order is irrelevant.)Example 1Input:32 12 53 2Output:8The optimal order is to do the 2nd problem first, then solve the 3rd problem and leave the 1st problem to solve at the end.The solution for the 1st problem will be accepted at time 5 (Amadeus starts at 5) + 2 + 1 = 8.The solution for the 2nd problem will be accepted at time 0 + 2 + 5 = 7.The evaluation for the 3rd problem will be accepted at time 2 + 3 + 2 = 7,Hence the total number of seconds consumed from start to end is 8