MOHSINGRAM

I. Gadgets of Tomishu Score: 1 CPU: 1s Memory: 1200MB Little Tomishu likes numbers. But he likes electronic gadgets (mobile, tablet, phablet, laptop and so on) more than numbers. His parents are trying to keep him engaged with numbers. So, they asked him to write down all the numbers of n length, consisting of only 0 and 1, and without any neighboring 1s. For example, if n = 3, he is supposed to write: 000, 001, 010, 100 and 101. Of course, Tomishu will write the numbers in increasing order. For each of the numbers, his parent will reward him with one of the k types of gadgets. Find out the number of ways he can get the gadgets. Two ways will be different if he received different gadget for the ith number for some i. For example, for n = 3, if there are k = 2 types of gadgets (say mobile and laptop), he can get the gadgets in 2 * 2 * 2 * 2 * 2 = 2 5  = 32 ways. Since the answer can be quite big for the given  n  and  k , you will also be given  M . You...

H. An Interesting Game Score: 1 CPU: 8s Memory: 1200MB Let’s play a game. You might like it. You are given an array of  N  integers. All the numbers are distinct and between  [1...N] . The rule of the game is simple. You will be given two integers, let’s call them  L, R (1 ≤ L ≤ R ≤ N) . You need to find out the length of the largest contiguous sub-array of the given permutation in which every value is between  L  and  R  inclusive. You will be given many queries like this for the given array. You win if you can answer all the queries perfectly and in time. Can you win this game? Input The first line has an integer  T  (The number of test scenarios,  1≤ T ≤ 5 ). Then T test cases follow. Each test had two integers at the first line  N, Q (1 ≤ N, Q ≤ 100000) . Then the next line contains a permutation of positive integers between  1...N . The next  Q  lines contain pairs of integers:  L ...

G. Repeater Score: 1 CPU: 4s Memory: 1200MB Hello soldier, welcome to the military base Ground Zero. The enemies are planning to attack our base. Right now, they are camping in the jungle near our camp for the night. We must destroy them before the sunrise. Now there are  N  enemy vehicles in a straight line. The distance of the vehicles are  d 1 , d 2 , d 3 , d 4 ,,, d n . The distances are all positive integers between 1 to  M . For all practical purpose, you can think of our base and all the vehicles are dots in a straight line. Now the enemy doesn’t know about our secret weapon the repeater. The repeater is a powerful weapon with which can destroy the enemy vehicles. When firing the repeater, we can choose a parameter  R  and the repeater will first destroy everything at exactly  R distance away, then it will destroy everything in  2R  distance, then  3R, 4R  until all the multiples of  R  less than...

F. Counter RMQ Score: 1 CPU: 1s Memory: 1200MB You must have heard about the Range Minimum Query (RMQ) problem. If you haven’t, here is a definition: Given an array  A[1 … n]  of n integers, the range minimum query  RMQ(l, r) (1 ≤ l ≤ k ≤ r ≤ n)  returns the value of the minimal element in the specified sub-array  A[l … r] . Imagine a program that takes a series of RMQ queries and prints the answers. Is it possible to recover the original sequence? Yes, you are right, it’s not possible for most of the cases, for different possible input arrays  A , there could be the same set of answers for a given set of  RMQ  queries. Why don’t we try finding one such array  A ? Given  n , (the length of  A ) and  q  RMQ queries and their answers in  l r RMQ(l, r)  format, print any array that produces the answer. For the purpose of this problem, we assume  A[i]  will be positive and less than or equa...

E. Bigger Picture Score: 1 CPU: 3s Memory: 1200MB In our country, sometimes organizers organize competition keeping a “big picture” in mind. They don’t care about the fairness of a competition. They just see that “lots of people got aware.” And that’s a great achievement for them while a good participant’s morale may get hurt by the unfairness but that gives the least amount of headache to the organizers. So, let’s organize a competition ourselves with a bigger picture in mind. There are n rooms in the competition arena. We are given the number of participants in each room. If we are to choose the first, we will look for the room with the maximum number of participants, in the case of more than one such room, we choose the room with the minimum id among the ones with maximum number of participants. After choosing the room, we randomly remove one participant from that room. Then we proceed on in the similar fashion until we rank all the participants. For example, suppose ther...

D. Double Trouble Score: 1 CPU: 1s Memory: 1200MB Camden is an evil town with  N  zones and  (N - 1)  tunnels in between the zones. The newly elected mayor of Camden ensured that every zone is reachable from all the other zones through these tunnels. You may wonder why it is being called ‘evil’. Well, people say that every zone of Camden offers some level of trouble. Depending on this level, each zone is categorized to be either Minder (less trouble) or Meer (more trouble). And now say hello to Mr. Milo, who will be moving to Camden very soon, thanks to his new job! He was wiki-ing about Camden while he freaked out as he learned about the extreme risk of getting into trouble in the town he is relocating to. Fortunately, his office is going to be in a Minder zone, and before going to sleep, he decided that by all means he is going to live in a Minder zone as well. But that night he had a nightmare that even though he was living in a Minder zone, on his d...

C. Grid Construction Score: 1 CPU: 3s Memory: 1200MB Alice have a  n*m  sized grid. The grid is divided into  n  rows and  m  columns.  Cell(x,y)  denotes the cell of the grid located in x-th row and y-th column. Alice is building wooden blocks in the grid. Each cell will contain one block and each of the blocks will contain a lowercase letter. Before starting construction, Alice has drawn a blueprint of the grid in her notebook. Alice will construct the grid in row-major order. That means, first she will complete the first row from left to right, then the second row and so on. Suppose the current block she is building must contain the letter  c . Now she has two choices: If this is the first time she is building a block which contains the letter  c , she will buy a brand-new block which costs  k  dollars. If there is already another block in cell  (x, y)  which contains the letter  c , she...

B. Wrong Solution Score: 1 CPU: 1s Memory: 1200MB Given a list of stock values, where the i-th element is the value of the stock on the i-th day. Find the maximum money you can earn by buying and selling stocks, given that you can buy or sell (not both) only one stock on a particular day. However, you can have multiple stocks with you at any point of time. You have to buy a stock before you can sell it. Example: stock_prices[] = {2,4,6,8,10},Optimal solution would be {(1,5), (2,4)} (1-based indexing), which means : buy a stock on day 1 and sell that on day 5. buy a stock on day 2, and sell it on day 4. This way you can earn: 10 + 8 – 2 - 4 = 12. For this problem, someone has submitted the following code. The idea of the code is given briefly (initially all the stocks are unmarked): Find the day X where the stock value on day X is the maximum among all the days not yet marked. Choose the rightmost one in case of tie. Find the day Y where Y is before X (Y < X) a...

A. A Directed Graph Score: 1 CPU: 1s Memory: 1200MB Some people often ask what is the real-life usage of algorithm. There are tons of such usages and one popped up in the following real life scenario. One day Alpha, Beta and Gamma went for dinner. When the bill came, we saw Alpha is charged with 23 takas, Beta with 21 takas and Gamma with 24 takas. So, Alpha gave 20 takas to Beta and Beta does not mind paying 3 takas out of his pocket for Alpha. Other than these 3 takas, Beta will pay for himself and also for Gamma. So, Beta gave 100 takas to Gamma and asked Gamma to pay to the restaurant boy. However, after a while, Beta said- “Hey Alpha, why don’t you pay for Gamma today. And for my meal, here is the 20 takas, I guess you won’t mind paying the rest.” Alpha agreed to the proposal (and paid the restaurant) and Beta took the 100 takas back from Gamma. Now the question is, after all these transactions how much money was spent by each one of Alpha, Beta and Gamma. I guess yo...

F. Process and Resources Score: 1 CPU: 1s Memory: 1200MB In operating systems, one of the major concerns is about process and resource management. Now you are to find whether a given process can be assigned to a given resource. In this problem, there will be two types of queries, Query type 1: You will be given a process id (pid) and a resource id (rid). If the resource is already free (initially all resources are free), then output ‘Y’ and the resource will be hold by this process. Otherwise output ‘N’ (even if the resource is already held by this process). Query type 2: You will be given a resource id. If the resource is already free output ‘F’, otherwise output the pid of the process which holds the resource and free the resource. Input The first line of the input file contains the number of test case T (1 <= T <= 25). Each test case starts with the number of query Q (1 <= Q <= 100000). Each of Q lines starts with the query typ...

E. Large vs Small Score: 1 CPU: 1s Memory: 1200MB You will be given a list of numbers. After reading each number, you have to print the largest number you have still read divided by smallest number you have still read. Output For each X, print one line of output, “Case Y: Z”. Where Y is the position of X in input and Z is the result of the division rounded to two digit after decimal. Sample Input Output 5 4 3 2 6 1 Case 1: 1.00 Case 2: 1.33 Case 3: 2.00 Case 4: 3.00 Case 5: 6.00

D. Box Sorting Score: 1 CPU: 1s Memory: 1200MB You are constantly getting threats from your mom to tidy up your desk. On top of your desk, there are lots and lots of cubic boxes of various sizes (You are a collector of boxes?!). Each box can contain one other box, which has size strictly smaller than itself. You have to put the boxes one inside of another in such a configuration that there are minimum number of boxes on the table. Input Input will start with the number of test cases, T (T ≤ 100). Following that will be the number of boxes, N (0 < N ≤ 100,000). The following N integers will denote the length of one side for each box, X (0 < X ≤ 2^30 ). Output For each test case, print one line of output, “Case Y: Z”. Where Y is the number of test case and Z is the minimum number of boxes on the table. Sample Input Output 2 5 1 5 4 2 3 2 5 5 Case 1: 1 Case 2: 2

C. Stick to Triangle Score: 1 CPU: 1s Memory: 1200MB You are given a stick of length N. You want to break it in three pieces such that it can form a triangle. In how many distinct triangles can you make? Two triangles are equal if all the side length is same when sorted in ascending order of length. So (1, 3, 2) is same to (3, 1, 2) because their side lengths are same is we sort them which is (1, 2, 3). But (1, 3, 4) is not same with (1, 2, 3). Suppose the lengths of three pieces are X, Y, Z respectively. Following constraints should be maintained: X, Y, Z > 0. X, Y, Z is an integer. X + Y + Z = N A triangle with zero area is considered a valid triangle. For example if N = 14, then there are 7 triangles: (1, 6, 7), (2, 5, 7), (2, 6, 6), (3, 4, 7), (3, 5, 6), (4, 4, 6), (4, 5, 5). Input First line will give you the number of test cases, T (T<=100). Then each line will have an integer N (0< N <= 300000). Output For each case print one line ...