Problem 1: You have n lists, each consisting of m integers sorted in ascending order. Merging these lists into a single sorted list will take time:
(a) O(nm log m) (b) O(mn log n)
(c) O(m + n) (d) O(mn)
Problem 2: A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex?
(a) 3 (b) 0
(c) 5 (d) 4
Problem 3: When a user submits a query, a search engine does the following. For every webpage that has been visited by the search engine, it computes a score indicating how relevant that page is to the query. Finally, it reports the pages with the top k scores on the screen, for a number k specified by the user. A good data structure for accumulating the scores and ranking them is:
(a) a queue (b) a heap
(c) a stack (d) a binary search tree
Problem 4: A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?
Solutions:
Answer 1: b) O(mn log n)
We can merge two sorted lists of size k and l in time
O(k +l). We begin by merging the lists in pairs to generate n/2 lists of size 2m each. To generate a list of size 2m we require O(m+m) time. Therefore to generate n/2 list the time required will be O(mn). If we repeat this, we get n/4 lists of size 4m each, again in total time O(mn). Thus, in O(log n) rounds, we converge to a single sorted list. Each round takes time O(mn), so the total time is O(mn log n).
Another strategy to achieve complexity O(mn log n) is to build a min-heap of size n, consisting the first element in each of the n lists. We then extract the minimum element from the heap to the output and replace it in the heap with the next element from the list from which the minimum came. Thus, it takes time O(log n) to generate each element in the output and there are O(mn) output elements in all, so the overall time
is O(mn log n).
Answer 2: d) 4
The number of odd degree vertices in any graph is even. Since we already have four
vertices of odd degree, the degree of the last vertex cannot be 3 or 5. It cannot be 0 either, since there is one vertex with degree 7, which means that it is a neighbour to all the other vertices, which implies that there is no isolated vertex in the graph. Thus the only possible degree of the last vertex is 4.
Answer 3: b) a heap
Let n be the number of pages visited by the search engine at the time a query is submitted. Assume that it takes constant time to compute the relevance score for each page w.r.t. a query. Then it takes O(n) time to compute the relevance scores, a further O(n) time to build a heap of n relevance scores, and O(k·log n) time for k delete-max operations to return the top k scores.
Answer 4: For every path from u to v, w is always present. Now, the no of nodes from the remaining 7 nodes (10 nodes -{u,v,w}) can be choosen in 7Ci ways and for each of the choosen i vertices, these nodes can be travelled in (i+1)! ways ( i+1 because we are including the w vertex also, along with the i vertices). Thus the total no of ways are:
=(7C0).(1!) + (7C1).(2!) + (7C2).(3!) + (7C3).(4!) + (7C4).(5!) + (7C5).(6!) + (7C6).(7!) + (7C7).(8!)
=95901.
Happy Coding!!!!
(a) O(nm log m) (b) O(mn log n)
(c) O(m + n) (d) O(mn)
Problem 2: A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex?
(a) 3 (b) 0
(c) 5 (d) 4
Problem 3: When a user submits a query, a search engine does the following. For every webpage that has been visited by the search engine, it computes a score indicating how relevant that page is to the query. Finally, it reports the pages with the top k scores on the screen, for a number k specified by the user. A good data structure for accumulating the scores and ranking them is:
(a) a queue (b) a heap
(c) a stack (d) a binary search tree
Problem 4: A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?
Solutions:
Answer 1: b) O(mn log n)
We can merge two sorted lists of size k and l in time
O(k +l). We begin by merging the lists in pairs to generate n/2 lists of size 2m each. To generate a list of size 2m we require O(m+m) time. Therefore to generate n/2 list the time required will be O(mn). If we repeat this, we get n/4 lists of size 4m each, again in total time O(mn). Thus, in O(log n) rounds, we converge to a single sorted list. Each round takes time O(mn), so the total time is O(mn log n).
Another strategy to achieve complexity O(mn log n) is to build a min-heap of size n, consisting the first element in each of the n lists. We then extract the minimum element from the heap to the output and replace it in the heap with the next element from the list from which the minimum came. Thus, it takes time O(log n) to generate each element in the output and there are O(mn) output elements in all, so the overall time
is O(mn log n).
Answer 2: d) 4
The number of odd degree vertices in any graph is even. Since we already have four
vertices of odd degree, the degree of the last vertex cannot be 3 or 5. It cannot be 0 either, since there is one vertex with degree 7, which means that it is a neighbour to all the other vertices, which implies that there is no isolated vertex in the graph. Thus the only possible degree of the last vertex is 4.
Answer 3: b) a heap
Let n be the number of pages visited by the search engine at the time a query is submitted. Assume that it takes constant time to compute the relevance score for each page w.r.t. a query. Then it takes O(n) time to compute the relevance scores, a further O(n) time to build a heap of n relevance scores, and O(k·log n) time for k delete-max operations to return the top k scores.
Answer 4: For every path from u to v, w is always present. Now, the no of nodes from the remaining 7 nodes (10 nodes -{u,v,w}) can be choosen in 7Ci ways and for each of the choosen i vertices, these nodes can be travelled in (i+1)! ways ( i+1 because we are including the w vertex also, along with the i vertices). Thus the total no of ways are:
=(7C0).(1!) + (7C1).(2!) + (7C2).(3!) + (7C3).(4!) + (7C4).(5!) + (7C5).(6!) + (7C6).(7!) + (7C7).(8!)
=95901.
Happy Coding!!!!
Hello Everyone!!
Problem Link: PROBLEM
Question
An archeologist seeking proof of the presence of extraterrestrials in the Earth’s past, stumbles upon a partially destroyed wall containing strange chains of numbers. The left-hand part of these lines of digits is always intact, but unfortunately the right-hand one is often lost by erosion of the stone. However, she notices that all the numbers with all its digits intact are powers of 2, so that the hypothesis that all of them are powers of 2 is obvious. To reinforce her belief, she selects a list of numbers on which it is apparent that the number of legible digits is strictly smaller than the number of lost ones, and asks you to find the smallest power of 2 (if any) whose first digits coincide with those of the list.
Thus you must write a program such that given an integer, it determines (if it exists) the smallest exponent E such that the first digits of 2^E coincide with the integer (remember that more than half of the digits are missing).
Input
It is a set of lines with a positive integer N not bigger than 2147483648 in each of them.
Output
For every one of these integers a line containing the smallest positive integer E such that the first digits
of 2^E are precisely the digits of N, or, if there is no one, the sentence ‘no power of 2’.
Sample Input
1
2
10
Sample Output
7
8
20
Explanation
Input 1
2^7 = 128
input 2
2^8=256
input 3
2^20=1048576
Solution:
EDITORIAL
Pseudocode:
CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
Problem Link: PROBLEM
Question
An archeologist seeking proof of the presence of extraterrestrials in the Earth’s past, stumbles upon a partially destroyed wall containing strange chains of numbers. The left-hand part of these lines of digits is always intact, but unfortunately the right-hand one is often lost by erosion of the stone. However, she notices that all the numbers with all its digits intact are powers of 2, so that the hypothesis that all of them are powers of 2 is obvious. To reinforce her belief, she selects a list of numbers on which it is apparent that the number of legible digits is strictly smaller than the number of lost ones, and asks you to find the smallest power of 2 (if any) whose first digits coincide with those of the list.
Thus you must write a program such that given an integer, it determines (if it exists) the smallest exponent E such that the first digits of 2^E coincide with the integer (remember that more than half of the digits are missing).
Input
It is a set of lines with a positive integer N not bigger than 2147483648 in each of them.
Output
For every one of these integers a line containing the smallest positive integer E such that the first digits
of 2^E are precisely the digits of N, or, if there is no one, the sentence ‘no power of 2’.
Sample Input
1
2
10
Sample Output
7
8
20
Explanation
Input 1
2^7 = 128
input 2
2^8=256
input 3
2^20=1048576
Solution:
EDITORIAL
Pseudocode:
N=inputCode:
T=floorl(log10(N)+2)
A=log2(N)+T*log2(10)
B=log2(N+1)+T*log2(10)
while(ceill(A)>=B)
T=T+1
A=log2(N)+T*log2(10)
B=log2(N+1)+T*log2(10)
print ceill(A)
CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
For enhancing the book reading, school distributed story books to students as part of the Children’s day celebrations.
To increase the reading habit, the class teacher decided to exchange the books every weeks so that everyone will have a different book to read. She wants to know how many possible exchanges are possible.
If they have 4 books and students, the possible exchanges are 9. Bi is the book of i-th student and after the exchange he should get a different book, other than Bi.
B1 B2 B3 B4 - first state, before exchange of the books
B2 B1 B4 B3
B2 B3 B4 B1
B2 B4 B1 B3
B3 B1 B4 B2
B3 B4 B1 B2
B3 B4 B2 B1
B4 B1 B2 B3
B4 B3 B1 B2
B4 B3 B2 B1
Find the number of possible exchanges, if the books are exchanged so that every student will receive a different book.
Solution
We have to apply derangement formula here.
DERANGEMENTS
Count Derangements :
SOLUTION
Happy Learning
To increase the reading habit, the class teacher decided to exchange the books every weeks so that everyone will have a different book to read. She wants to know how many possible exchanges are possible.
If they have 4 books and students, the possible exchanges are 9. Bi is the book of i-th student and after the exchange he should get a different book, other than Bi.
B1 B2 B3 B4 - first state, before exchange of the books
B2 B1 B4 B3
B2 B3 B4 B1
B2 B4 B1 B3
B3 B1 B4 B2
B3 B4 B1 B2
B3 B4 B2 B1
B4 B1 B2 B3
B4 B3 B1 B2
B4 B3 B2 B1
Find the number of possible exchanges, if the books are exchanged so that every student will receive a different book.
Solution
We have to apply derangement formula here.
DERANGEMENTS
Count Derangements :
SOLUTION
Happy Learning
Wikipedia
Derangement
In combinatorial mathematics, a derangement is a permutation of the elements of a set in which no element appears in its original position. In other words, a derangement is a permutation that has no fixed points.
Problem:
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by either you or any of your friends, so you can complete as many tasks as possible in parallel, on the same day.
Some tasks depend on others: for instance, you cannot purchase foreign exchange till you have bought your ticket. If task B depends on task A, you can start B only after you complete A. A set of tasks with no pending dependencies can be completed in parallel.
You are given a list of n such tasks to be completed, where each task comes with a set of other tasks that it depends on. The set of tasks is feasible: there are no circular dependencies. You want to compute the minimum number of days needed to complete all the tasks, given the constraints.
Solutions:
Construct a graph in which the tasks are the vertices and there is an edge (i, j) if task i must be completed before starting task j. This is a directed graph without cycles, so it is a directed acyclic graph (dag). Any path (suppose v1->v2->v3->.....->vk of length k) of tasks would take a minimum of k days to complete because each edge in the path describes a dependency. Hence, the problem is one of finding the longest path in a dag.
In any dag, there must be some vertex with no incoming edge (indegree 0). Any vertex of indegree 0 represents a task that has no pending dependencies and can hence be immediately completed. Once it is completed, we can remove it from the graph and operate on the tasks that remain.
The algorithm is thus the following.
• Initialize a counter c to 0.
• While the dag is not empty
– Remove all vertices of indegree 0
– Recompute indegrees of remaining vertices
– Increment c
The final value of c is the answer we seek.
The complexity of this algorithm depends on how we represent the graph. For G = (V, E) let |V | = n and |E| = m. If we use an adjacency matrix, for each vertex we remove, we have to scan a row of the matrix to determine which indegrees to decrement, so it will take time O(n^2). If we use adjacency lists, for each vertex we delete, we can scan its list of outgoing edges and directly decrement indegrees for its outgoing neighbours. Across the n vertices we delete, we scan each of the m edges once, so the overall time is O(n + m).
Happy Coding!!!
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by either you or any of your friends, so you can complete as many tasks as possible in parallel, on the same day.
Some tasks depend on others: for instance, you cannot purchase foreign exchange till you have bought your ticket. If task B depends on task A, you can start B only after you complete A. A set of tasks with no pending dependencies can be completed in parallel.
You are given a list of n such tasks to be completed, where each task comes with a set of other tasks that it depends on. The set of tasks is feasible: there are no circular dependencies. You want to compute the minimum number of days needed to complete all the tasks, given the constraints.
Solutions:
Construct a graph in which the tasks are the vertices and there is an edge (i, j) if task i must be completed before starting task j. This is a directed graph without cycles, so it is a directed acyclic graph (dag). Any path (suppose v1->v2->v3->.....->vk of length k) of tasks would take a minimum of k days to complete because each edge in the path describes a dependency. Hence, the problem is one of finding the longest path in a dag.
In any dag, there must be some vertex with no incoming edge (indegree 0). Any vertex of indegree 0 represents a task that has no pending dependencies and can hence be immediately completed. Once it is completed, we can remove it from the graph and operate on the tasks that remain.
The algorithm is thus the following.
• Initialize a counter c to 0.
• While the dag is not empty
– Remove all vertices of indegree 0
– Recompute indegrees of remaining vertices
– Increment c
The final value of c is the answer we seek.
The complexity of this algorithm depends on how we represent the graph. For G = (V, E) let |V | = n and |E| = m. If we use an adjacency matrix, for each vertex we remove, we have to scan a row of the matrix to determine which indegrees to decrement, so it will take time O(n^2). If we use adjacency lists, for each vertex we delete, we can scan its list of outgoing edges and directly decrement indegrees for its outgoing neighbours. Across the n vertices we delete, we scan each of the m edges once, so the overall time is O(n + m).
Happy Coding!!!
Problem: Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as many complete matches as possible during the week. Suppose there are n such matches scheduled during the coming week and you know the starting and finishing time for each match.
Describe an efficient algorithm to compute the following: for each match, what is the next match whose starting time is strictly later than the finishing time of the current match?
Solution: We can accumulate information about the matches in the order in which they appear in the TV schedule. Hence, we can assume that the starting times and ending times of the matches are recorded in two arrays B[1..n] and E[1..n], where B[i] and E[i] are the beginning and ending time, respectively, of match i and B is sorted in ascending order. For each match i, we use binary search in B to find the earliest match j such that E[i] ≤ B[j] and set Next[i] = j. We do n binary searches, so this takes time O(n log n).
Happy Coding!!!!
Describe an efficient algorithm to compute the following: for each match, what is the next match whose starting time is strictly later than the finishing time of the current match?
Solution: We can accumulate information about the matches in the order in which they appear in the TV schedule. Hence, we can assume that the starting times and ending times of the matches are recorded in two arrays B[1..n] and E[1..n], where B[i] and E[i] are the beginning and ending time, respectively, of match i and B is sorted in ascending order. For each match i, we use binary search in B to find the earliest match j such that E[i] ≤ B[j] and set Next[i] = j. We do n binary searches, so this takes time O(n log n).
Happy Coding!!!!
Forwarded from Strange
Problem 1: Let A be an array of n integers, sorted so that A[1] ≤ A[2] ≤ · · · ≤ A[n]. You are given a number x. The aim is to find out if there are indices k and l such that A[k] + A[l] = x. Design an algorithm for this problem that works in time O(n).
Problem 2: Let A be array of n integers that is assumed to be sorted. You are given a number x. The aim is to find out if there are indices k, l and m such that
A[k] + A[l] + A[m] = x. Design an algorithm for this problem that works in time O(n^2).
Solution 1: Consider the two endpoints A[1] and A[n].
• If A[1] + A[n] > x, A[n] is useless since it cannot be paired with any number to achieve the sum—any sum A[i] + A[n], i > 1, will be greater than or equal to A[1] + A[n] since A[i] ≥ A[1].
• Likewise, if A[1] + A[n] < x, A[1] is useless since it cannot be paired with any number to achieve the sum.
Hence, we start with two pointers left and right, with left = 1 and right = n initially. At each stage, we check the sum A[left] + A[right]. If this sum exceeds x, we decrement right and if this sum is less than x we increment left. Eventually, either left and right meet and there is no solution, or we find the indices k and that we are looking for.
This takes a single scan of A, so the overall time is O(n).
Solution 2: Suppose we fix the first index k = 1. Then the problem reduces to finding l and m in 2, 3, . . . , n such that A[l] +A[m] = x−A[1]. This can be solved in time O(n)
by the solution 1 discuss earlier in this post. . We vary k from 1, 2, . . . , n−3, and check for l and m in k+1, k+2, . . . , n such that A[l] + A[m] = x − A[k]. This takes time (n−1) +(n−2) + (n−3) + · · · · · · · + 1 = O(n^2).
Happy Coding!!!!
Problem 2: Let A be array of n integers that is assumed to be sorted. You are given a number x. The aim is to find out if there are indices k, l and m such that
A[k] + A[l] + A[m] = x. Design an algorithm for this problem that works in time O(n^2).
Solution 1: Consider the two endpoints A[1] and A[n].
• If A[1] + A[n] > x, A[n] is useless since it cannot be paired with any number to achieve the sum—any sum A[i] + A[n], i > 1, will be greater than or equal to A[1] + A[n] since A[i] ≥ A[1].
• Likewise, if A[1] + A[n] < x, A[1] is useless since it cannot be paired with any number to achieve the sum.
Hence, we start with two pointers left and right, with left = 1 and right = n initially. At each stage, we check the sum A[left] + A[right]. If this sum exceeds x, we decrement right and if this sum is less than x we increment left. Eventually, either left and right meet and there is no solution, or we find the indices k and that we are looking for.
This takes a single scan of A, so the overall time is O(n).
Solution 2: Suppose we fix the first index k = 1. Then the problem reduces to finding l and m in 2, 3, . . . , n such that A[l] +A[m] = x−A[1]. This can be solved in time O(n)
by the solution 1 discuss earlier in this post. . We vary k from 1, 2, . . . , n−3, and check for l and m in k+1, k+2, . . . , n such that A[l] + A[m] = x − A[k]. This takes time (n−1) +(n−2) + (n−3) + · · · · · · · + 1 = O(n^2).
Happy Coding!!!!
Hello Everyone!!
Problem Link: TOWER
Question
There are N cities in Magic land arranged as a one dimensional array. For simplicity we can assume an array of size N as N cities. The king of Magic land is now installing new 4G internet towers in various cities. Let us consider the array is A1 , A2 , A3 , A4 ,......, AN. Now, consider the following statement:
If Ai is equal to 0 then it means there is no tower in the city.
If Ai is equal to k (k is a positive integer), then there is a tower in ith city and the range of the tower is k. It means the city from A max ( 1 , i - k ) to A min ( N , i + k ) will get the internet connection.
Suppose, A5 = 1 , then A4 , A5 and A6 will get the internet connection even if there is no tower in A4 or A6.
The installation of towers is over now. The king wants to know how many cities are there without internet connection.
Input
•The first line contains an integer N denoting the number of cities
•The second line contains N spaced seperated integers denoting A1 , A2 , A3 , . . . . . . , AN
Output
•The one and only line contains an integer denoting the number of cities without any internet connections
Constraints
•1 ≤ N ≤ 106
•0 ≤ Ai ≤ 109
Sample Input 1
4
0 0 1 0
Sample output 1
1
Sample Input 2
7
0 2 0 0 0 0 1
Sample output 2
1
Explanation
For sample input 1 :
There is only one tower in city 3 whose range is 1. City 2 , 3 and 4 gets the internet connection from this tower but city 1 doesnot get it hence the output is 1.
For sample input 2:
There is a tower at city 2 whose range is 2. City 1 , 2 , 3 and 4 gets the internet connection from this tower. Similarly city 6 and 7 get internet connection from the tower at city 7. But city 5 doesnot get internet connection at all. Hence the output is 1.
Solution:
EDITORIAL
Pseudocode:
CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
Problem Link: TOWER
Question
There are N cities in Magic land arranged as a one dimensional array. For simplicity we can assume an array of size N as N cities. The king of Magic land is now installing new 4G internet towers in various cities. Let us consider the array is A1 , A2 , A3 , A4 ,......, AN. Now, consider the following statement:
If Ai is equal to 0 then it means there is no tower in the city.
If Ai is equal to k (k is a positive integer), then there is a tower in ith city and the range of the tower is k. It means the city from A max ( 1 , i - k ) to A min ( N , i + k ) will get the internet connection.
Suppose, A5 = 1 , then A4 , A5 and A6 will get the internet connection even if there is no tower in A4 or A6.
The installation of towers is over now. The king wants to know how many cities are there without internet connection.
Input
•The first line contains an integer N denoting the number of cities
•The second line contains N spaced seperated integers denoting A1 , A2 , A3 , . . . . . . , AN
Output
•The one and only line contains an integer denoting the number of cities without any internet connections
Constraints
•1 ≤ N ≤ 106
•0 ≤ Ai ≤ 109
Sample Input 1
4
0 0 1 0
Sample output 1
1
Sample Input 2
7
0 2 0 0 0 0 1
Sample output 2
1
Explanation
For sample input 1 :
There is only one tower in city 3 whose range is 1. City 2 , 3 and 4 gets the internet connection from this tower but city 1 doesnot get it hence the output is 1.
For sample input 2:
There is a tower at city 2 whose range is 2. City 1 , 2 , 3 and 4 gets the internet connection from this tower. Similarly city 6 and 7 get internet connection from the tower at city 7. But city 5 doesnot get internet connection at all. Hence the output is 1.
Solution:
EDITORIAL
Pseudocode:
n=number of citiesCode:
A=array
n,A=input
for i = 0 to n-1
if Ai>0
Ai++
Leftc[n]
Rightc[n]
c=0
for i=0 to n-1
c=c-1
c=max(c,A[i])
Rightc[i]=c
c=0
for i=n-1 to 0
c=c-1
c=max(c,A[i])
Leftc[i]=c
count=0
for i=0 to n-1
if(Leftc[i]==0 && Rightc[i]==0)
count++
print count
CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
Question:
Take an input array, say A and print the maximum value of x
where x = |(A[i] – A[j]) + (i – j)| .
Constraints:
Max array size: 20000
Time limit: 0.1s
Time limit is a major factor in this question.
Hint:
https://imgur.com/0jhFcBi
Solution Approach:
https://imgur.com/5xc5AO2
Complete Solution:
https://imgur.com/abadlKe
Happy Learning
Take an input array, say A and print the maximum value of x
where x = |(A[i] – A[j]) + (i – j)| .
Constraints:
Max array size: 20000
Time limit: 0.1s
Time limit is a major factor in this question.
Hint:
https://imgur.com/0jhFcBi
Solution Approach:
https://imgur.com/5xc5AO2
Complete Solution:
https://imgur.com/abadlKe
Happy Learning
Imgur
Discover the magic of the internet at Imgur, a community powered entertainment destination. Lift your spirits with funny jokes, trending memes, entertaining gifs, inspiring stories, viral videos, and so much more from users.
Question
Given an array of strings with R, G & B as characters. Sort the array such that all R comes first, followed by Gs & followed by Bs.
Do it in O(n) time complexity.
For eg. array is:
I/P: G G R B R B B G R B R
O/P: R R R R G G G B B B B
Read Solution:
DNF algorithm
Happy Learning
Given an array of strings with R, G & B as characters. Sort the array such that all R comes first, followed by Gs & followed by Bs.
Do it in O(n) time complexity.
For eg. array is:
I/P: G G R B R B B G R B R
O/P: R R R R G G G B B B B
Read Solution:
DNF algorithm
Happy Learning
problem: You are given an array A of size n. You are told that A comprises three consecutive runs – first a run of ’a’s, then a run of ’b’s and finally a run of ’c’s. Moreover, you are provided an index i such that A[i] = b. Design an O(log n) time algorithm to determine the number of ’b’s (i.e.,
length of the second run) in A.
Solution: We will use modified binary search to find the first occurrence of 'b'. In the similar manner we will find the last occurrence of 'b'. The final answer is (last occurrence - first occurrence +1).
Now, to find the first occurrence we have to check that if the current element is 'b' and the element before this current element is 'a'. If yes, then we got our first occurrence else we search on the right segment if the current element is 'a', else we search in the left segment.
Pseudo Code:
In the similar manner we can find the last occurrence. If the current element is 'b' and the next element is 'c' then it is the last occurrence of 'b'. Else we search on the left segment if the current element is 'c'. Otherwise we search the right segment.
Pseudo Code:
Happy Coding!!!
length of the second run) in A.
Solution: We will use modified binary search to find the first occurrence of 'b'. In the similar manner we will find the last occurrence of 'b'. The final answer is (last occurrence - first occurrence +1).
Now, to find the first occurrence we have to check that if the current element is 'b' and the element before this current element is 'a'. If yes, then we got our first occurrence else we search on the right segment if the current element is 'a', else we search in the left segment.
Pseudo Code:
first_occurrence(A[],low,high)
mid=(low+high)/2
if(A[mid]=='b' && A[mid-1]=='a'):
return mid
else if(A[i]=='a'):
return first_occurrence(A,mid+1,high)
else:
return first_occurrence(A,low,mid-1)
In the similar manner we can find the last occurrence. If the current element is 'b' and the next element is 'c' then it is the last occurrence of 'b'. Else we search on the left segment if the current element is 'c'. Otherwise we search the right segment.
Pseudo Code:
last_occurrence(A[],low,high)
mid=(low+high)/2
if(A[mid]=='b' && A[mid+1]=='c'):
return mid
else if(A[i]=='b'):
return last_occurrence(A,mid+1,high)
else:
return last_occurrence(A,low,mid-1)
Happy Coding!!!
Asked in Microsoft Interview
Count ways to express a number as sum of consecutive numbers
Example
Input :15
Output :3
15 can be represented as:
1+2+3+4+5
4+5+6
7+8
Input :10
Output :1
10 can only be represented as:
1+2+3+4
Read solution:
SOLUTION
Happy Learning
Count ways to express a number as sum of consecutive numbers
Example
Input :15
Output :3
15 can be represented as:
1+2+3+4+5
4+5+6
7+8
Input :10
Output :1
10 can only be represented as:
1+2+3+4
Read solution:
SOLUTION
Happy Learning
Codeforces
Represent a number as sum of consecutive numbers
To solve this, we can use the concept of A.P. We know that sum of A.P. is n = (m/2)*(2*a + (m - 1)*d) if n is the sum and m is the number of integers with common difference d in the A.P. In our problem, n is the given number and m is the number of consecutive…
Problem: Give an efficient implementation for a data structure STACK_MAX to support an operation maximum() that reports the current maximum among all elements in the stack. Usual stack operations (createEmpty(), push(), pop()) are also to be supported.
Solution: Instead of an array of integers, we will maintain an array of structure. The structure will comprise of 2 member variables. One that holds current element and the other holds the maximum element uptill now. The prototype is as follows:
We just need to modify the push() function a little bit.
The pseudo code for push function is as follows:
The pop() function remains the same. In the maximum() function we just return s[top].cur_max if the stack is not empty. The time complexity for maximum() function is O(1). The overall space complexity is O(n).
Happy Coding!!!
Solution: Instead of an array of integers, we will maintain an array of structure. The structure will comprise of 2 member variables. One that holds current element and the other holds the maximum element uptill now. The prototype is as follows:
struct Stack{
int cur_element;
int cur_max;
};
Stack s[MAX_SIZE];We just need to modify the push() function a little bit.
The pseudo code for push function is as follows:
push(x,top)
if (top==MAX_SIZE) :
//Stack is full
print("Stack overflow")
else if(top==-1) :
//Stack has no elements
top=0
s[top].cur_element=x
s[top].cur_max=x
else :
top=top+1
s[top].cur_element=x
s[top].cur_max=max(x,s[top-1].cur_max)
return
The pop() function remains the same. In the maximum() function we just return s[top].cur_max if the stack is not empty. The time complexity for maximum() function is O(1). The overall space complexity is O(n).
Happy Coding!!!
Asked in Google Internship Interview :
Find Median from Data Stream
Design a data structure that supports the following two operations:
void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example:
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Hint and solution :
bit.ly/solution-running-median
Happy Learning
Find Median from Data Stream
Design a data structure that supports the following two operations:
void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example:
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Hint and solution :
bit.ly/solution-running-median
Happy Learning
Stack Overflow
Find running median from a stream of integers
Possible Duplicate:
Rolling median algorithm in C
Given that integers are read from a data stream. Find median of elements read so far in efficient way.
Solution I have read: We can use a ...
Rolling median algorithm in C
Given that integers are read from a data stream. Find median of elements read so far in efficient way.
Solution I have read: We can use a ...
Your are given an array of integers and an integer k of window size, you need to find minimum value in this window.
Ex. A: 1 2 3 4 5 6 and k = 3
Then output will be: 1 2 3 4
This question is similar to Maximum of all subarrays of size k
Read Optimal and Brute force solution
SOLUTION
Happy Learning
Ex. A: 1 2 3 4 5 6 and k = 3
Then output will be: 1 2 3 4
This question is similar to Maximum of all subarrays of size k
Read Optimal and Brute force solution
SOLUTION
Happy Learning
GeeksforGeeks
Sliding Window Maximum (Maximum of all subarrays of size K) - GeeksforGeeks
Your All-in-One Learning Portal: GeeksforGeeks is a comprehensive educational platform that empowers learners across domains-spanning computer science and programming, school education, upskilling, commerce, software tools, competitive exams, and more.
Question: A bipartite graph is a (simple) undirected graph G = (V, E) whose vertex set V can be partitioned in two disjoint subsets V1 and V2 such that V = (v1 U V2), no two vertices in V1 are connected by an edge, and no two vertices in V2 are connected by an edge. You are given a connected bipartite graph (V, E), but the sets V1 and V2 are not supplied to you. Design an efficient algorithm to compute V1 and V2. Deduce the running time of your algorithm.
Solution: The given graph is a bipartite graph, we need to figure out all the vertices in the set V1 and V2. We will use bfs ( breadth first search) here. We will maintain a bool variable (let it be named bool_flag) inside every node and then we start to travel the graph. We can choose any vertex as the source vertex here. For simplicity lets choose 1 as the source vertex. We set bool_flag for vertex 1 to 0 and for every adjacent vertex of vertex 1 we set the bool_flag to 1. We then travel all the other nodes and set bool_flag to 1 if its parent's bool_flag is 0 else we set bool_flag to 0 if its parent's bool_flag is 1. Note, since the graph is bipartite hence we will not have any cycle of odd length in the graph, hence if two vertices share an edge then the bool_flag of both of them cannot be the same or in another word, if the bool_flag of one of them is 1 then the other will have 0 as its bool_flag. After the whole process, every vertex will have either bool_flag as 0 or as 1. The vertices having bool_flag as 0 makes up one set and the vertices having bool_flag as 1 makes up another set.
The time complexity for the bfs algorithm is O(V+E).
Note: we can also use dfs for travelling the vertices instead of bfs.
Happy Coding!!!
Solution: The given graph is a bipartite graph, we need to figure out all the vertices in the set V1 and V2. We will use bfs ( breadth first search) here. We will maintain a bool variable (let it be named bool_flag) inside every node and then we start to travel the graph. We can choose any vertex as the source vertex here. For simplicity lets choose 1 as the source vertex. We set bool_flag for vertex 1 to 0 and for every adjacent vertex of vertex 1 we set the bool_flag to 1. We then travel all the other nodes and set bool_flag to 1 if its parent's bool_flag is 0 else we set bool_flag to 0 if its parent's bool_flag is 1. Note, since the graph is bipartite hence we will not have any cycle of odd length in the graph, hence if two vertices share an edge then the bool_flag of both of them cannot be the same or in another word, if the bool_flag of one of them is 1 then the other will have 0 as its bool_flag. After the whole process, every vertex will have either bool_flag as 0 or as 1. The vertices having bool_flag as 0 makes up one set and the vertices having bool_flag as 1 makes up another set.
The time complexity for the bfs algorithm is O(V+E).
Note: we can also use dfs for travelling the vertices instead of bfs.
Happy Coding!!!
Sliding Window Maximum (Maximum of all subarrays of size k)
Given an array and an integer K, find the maximum for each and every contiguous subarray of size k.
Examples:
Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Output: 3 3 4 5 5 5 6
Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Output: 10 10 10 15 15 90 90
We have discussed the brute force and optimal solutions in a previous post.
In this post we focus on the O(n) solution and analyse time complexity of the solution.
Explanation:
We create a Deque Q of size k and maintain the following conditions:
1. Q contains only the useful elements of current window.
2. Q contains the elements in descending order.
Now what are useful elements?
Suppose the array is
{10,5,4,3,1,7,6} and k=6
We start traversing input array from index 0 and as we reach index 4 our deque Q contains
{10,5,4,3,1} as all the elements are useful.
Now after we read 7 at index 5 the elements 5,4,3,1 become useless here.
For any window afterwards if it contains 5,it will also contain 7.As 7 is greater than 5 and we are looking for maximum , 5 is useless.Similiarly 4,3,1 are also useless.
So Q contains {10,7}.
Now our window size is 6. For the next element in the array 10 is outside of the window.So We print 10 and pop it from the Q.
Q contains {7,6}.
We process all array elements one by one and maintain Q to contain useful elements of current window and these useful elements are maintained in descending order. The element at front of the Q is the largest of current window.
Pseudocode:
Suppose 1st k elements of input array are in descending order.So after passing through 1st k elements of input array deque contains k elements.
Let's say each of remaining (n-k) elements will be greater than half of elements present in deque.To insert (k+1)th element we have to make (k/2+1) comparisons and after insertion there will be(k/2) elements in the deque. To insert (k+2)th element we have to make (k/4+1) comparisons and after insertion there will be (k/4) elements in the deque.So to insert all the elements of input array in the deque total number of comparisons will be:
k+((k/2+1)+(k/4+1)+(k/8+1)+......(n-k) terms....)
= (k + k/2 + k/4 + ....(n-k+1) terms.....) +(n-k)
= ( k * (1 - (1/2)^ (n-k+1)) / (1-1/2) ) +(n-k)
= 2 * k * (2 ^ (n-k+1)-1) / (2^(n-k+1)) +(n-k)
≅ 2 * k *(2^(n-k+1)) / (2^(n-k+1)) +(n-k)
≅ 2*k + n - k
≅ n + k
So time complexity of above algorithm is O(n+k) i.e O(n) as (k<=n).
Code:
CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
Given an array and an integer K, find the maximum for each and every contiguous subarray of size k.
Examples:
Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Output: 3 3 4 5 5 5 6
Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Output: 10 10 10 15 15 90 90
We have discussed the brute force and optimal solutions in a previous post.
In this post we focus on the O(n) solution and analyse time complexity of the solution.
Explanation:
We create a Deque Q of size k and maintain the following conditions:
1. Q contains only the useful elements of current window.
2. Q contains the elements in descending order.
Now what are useful elements?
Suppose the array is
{10,5,4,3,1,7,6} and k=6
We start traversing input array from index 0 and as we reach index 4 our deque Q contains
{10,5,4,3,1} as all the elements are useful.
Now after we read 7 at index 5 the elements 5,4,3,1 become useless here.
For any window afterwards if it contains 5,it will also contain 7.As 7 is greater than 5 and we are looking for maximum , 5 is useless.Similiarly 4,3,1 are also useless.
So Q contains {10,7}.
Now our window size is 6. For the next element in the array 10 is outside of the window.So We print 10 and pop it from the Q.
Q contains {7,6}.
We process all array elements one by one and maintain Q to contain useful elements of current window and these useful elements are maintained in descending order. The element at front of the Q is the largest of current window.
Pseudocode:
n=size of array
a=array
a=input
Q=deque //We will store the indices of useful elements in the deque
for i=0 to k-1:
while(!Q.empty() and a[i]>=a[Q.rear()]):
Q.pop_back()
Q.push_back(i)
for i=k to n:
print a[Q.front()]
while(!Q.empty() and Q.front()<=i-k):
Q.pop_front()
while(!Q.empty() and a[i]>=a[Q.rear()]):
Q.pop_back()
Q.push_back(i)
print a[Q.front()]
Time Complexity:Suppose 1st k elements of input array are in descending order.So after passing through 1st k elements of input array deque contains k elements.
Let's say each of remaining (n-k) elements will be greater than half of elements present in deque.To insert (k+1)th element we have to make (k/2+1) comparisons and after insertion there will be(k/2) elements in the deque. To insert (k+2)th element we have to make (k/4+1) comparisons and after insertion there will be (k/4) elements in the deque.So to insert all the elements of input array in the deque total number of comparisons will be:
k+((k/2+1)+(k/4+1)+(k/8+1)+......(n-k) terms....)
= (k + k/2 + k/4 + ....(n-k+1) terms.....) +(n-k)
= ( k * (1 - (1/2)^ (n-k+1)) / (1-1/2) ) +(n-k)
= 2 * k * (2 ^ (n-k+1)-1) / (2^(n-k+1)) +(n-k)
≅ 2 * k *(2^(n-k+1)) / (2^(n-k+1)) +(n-k)
≅ 2*k + n - k
≅ n + k
So time complexity of above algorithm is O(n+k) i.e O(n) as (k<=n).
Code:
CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
Pastebin
#include <deque> #include <iostream> using namespace std; // A Dequeue - Pastebin.com
Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time.
Range update query
Consider an array A[] of integers and following two types of queries.
update(l, r, x) : l is left index, r is right index and x is value to be added i.e add x to all values from A[l] to A[r] (both inclusive).
printArray() : Prints the current modified array.
Solution:
Using Prefix Array:
Take an array pref of same size as input array.Initialize it with 0.
1.Upadate(l,r,x):
Add x to pref[l] and substract it from pref[r+1]
i.e we do pref[l]+=x , pref[r+1]-=x
2.PrintArray():
Take prefix sum of pref array i.e
for i=1 to n-1
pref[i]=pref[i]+pref[i-1]
Now, for all elements of input array
do A[i]=A[i]+pref[i] and print them
Here update range operation is performed in O(1).
printArray is performed in O(n).
Pseudocode:
CODE
Using Difference Array:
Difference array D[i] of a given array A[i] is defined as D[i] = A[i]-A[i-1] (for 0 < i < N ) and D[0] = A[0]
1.Upadate(l,r,x):
Add x to D[l] and substract it from D[r+1]
i.e we do D[l]+=x , D[r+1]-=x
2.printArray():
Do A[0] = D[0] and print it.
For rest of the elements, do A[i] = A[i-1] + D[i] and print them.
update range operation is performed in O(1).
printArray is performed in O(n).
Pseudocode:
CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
Consider an array A[] of integers and following two types of queries.
update(l, r, x) : l is left index, r is right index and x is value to be added i.e add x to all values from A[l] to A[r] (both inclusive).
printArray() : Prints the current modified array.
Solution:
Using Prefix Array:
Take an array pref of same size as input array.Initialize it with 0.
1.Upadate(l,r,x):
Add x to pref[l] and substract it from pref[r+1]
i.e we do pref[l]+=x , pref[r+1]-=x
2.PrintArray():
Take prefix sum of pref array i.e
for i=1 to n-1
pref[i]=pref[i]+pref[i-1]
Now, for all elements of input array
do A[i]=A[i]+pref[i] and print them
Here update range operation is performed in O(1).
printArray is performed in O(n).
Pseudocode:
n=size of arrayCode:
A=array
pref=array
initialize pref with 0
A=input
update(l,r,x):
pref[l]+=x
if(r+1<n)
pref[r+1]-=x
printArray():
for i=1 to n-1
pref[i]=pref[i]+pref[i-1]
for i=0 to n-1
A[i]=A[i]+pref[i]
for i=0 to n-1
print A[i]
print " "
print "\n"
CODE
Using Difference Array:
Difference array D[i] of a given array A[i] is defined as D[i] = A[i]-A[i-1] (for 0 < i < N ) and D[0] = A[0]
1.Upadate(l,r,x):
Add x to D[l] and substract it from D[r+1]
i.e we do D[l]+=x , D[r+1]-=x
2.printArray():
Do A[0] = D[0] and print it.
For rest of the elements, do A[i] = A[i-1] + D[i] and print them.
update range operation is performed in O(1).
printArray is performed in O(n).
Pseudocode:
n=size of array
A=array
D=array
A=input
D[0]=A[0]
for i=1 to n-1
D[i]=A[i]-A[i-1]
update(l,r,x):
D[l]+=x
if(r+1<n)
D[r+1]-=x
printArray():
A[0]=D[0]
for i=1 to n-1
A[i]=A[i-1]+D[i]
for i=0 to n-1
print A[i]
print " "
print "\n"
Code:CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
Pastebin
#include <bits/stdc++.h>using namespace std;int n;int pref[100005]; - Pastebin.com
Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time.
Problem: Let A be an unsorted array of n floating numbers. Propose an O(n) time algorithm to compute the (floating-point) number x (not necessarily an element of A) for which max|A[i] - x| is as small as possible for all 1 <= i <= n. (Here |y| means absolute value of y)
Solution: The problem statement can be interpreted as finding a point x such that it's distance from the farthest point is minimized (since, |A[i] - x| is given which is actually distance between two point). Note: we don't need to minimize distance from every point, we just need to minimize the distance of the point which is farthest to it. So we try to put our x as close to the farthest point. But in doing so the point which is near may go far. So the optimal solution is finding the minimum point in the array A (let it be named MN) and finding the maximum point of A (let it be named MX) and the result is the mid-point of these two points, i.e x=(MN+MX)/2. Note: All other point between MN and MX will have distance lesser hence we do not bother it. We could not get more optimal point than this one. Now, MX and MN can be easily determined by travelling once the array. Hence the time complexity is O(n).
Happy Coding!!!
Solution: The problem statement can be interpreted as finding a point x such that it's distance from the farthest point is minimized (since, |A[i] - x| is given which is actually distance between two point). Note: we don't need to minimize distance from every point, we just need to minimize the distance of the point which is farthest to it. So we try to put our x as close to the farthest point. But in doing so the point which is near may go far. So the optimal solution is finding the minimum point in the array A (let it be named MN) and finding the maximum point of A (let it be named MX) and the result is the mid-point of these two points, i.e x=(MN+MX)/2. Note: All other point between MN and MX will have distance lesser hence we do not bother it. We could not get more optimal point than this one. Now, MX and MN can be easily determined by travelling once the array. Hence the time complexity is O(n).
Happy Coding!!!
Problem: Hamming distance between two string of same length is the number of positions in which the corresponding character of two string differs. For example the hamming distance between "abc" and "abd" is 1 and between "abcd" and "acdb" is 3. Palindromic distance of a string is hamming distance between the string and it's palindrome. Write a recursive function that will compute the palindromic distance of a given string.
Solution: The solution is very simple and straight-forward. We create a function named pallin_dist(char ch[1...n]). We compare the first character and the last character of the string. If the the character doesn't match then we simply set the ans by 1 else we set the ans as 0. We then call pallin_dist(ch[2...n-2]) on ch[2,......,n-2] and increase the ans by the value returned by this function. We then return the ans. Here is the pseudo-code for the function:
Happy Coding!!!
Solution: The solution is very simple and straight-forward. We create a function named pallin_dist(char ch[1...n]). We compare the first character and the last character of the string. If the the character doesn't match then we simply set the ans by 1 else we set the ans as 0. We then call pallin_dist(ch[2...n-2]) on ch[2,......,n-2] and increase the ans by the value returned by this function. We then return the ans. Here is the pseudo-code for the function:
int pallin_dist(char ch[],int start,int end):
if(end==-1): //i.e end of string
return 0
ans=pallin_dist(ch,start+1,end-1)
if (ch[start]==ch[end]):
return ans
else:
return ans+1
Happy Coding!!!
Hello Everyone!!
Problem Link: CHEFWAR
Problem:
Bitland declared war on Chefland and sent an army to fight them, but Chefland defended efficiently and Bitland's army has been reduced to N soldiers. They have no chance of winning the war and do not want to surrender, so they are planning to commit group suicide. Josh, the leader of Bitland's remaining soldiers, has different plans — he wants to survive and somehow escape.
The soldiers are numbered 1 through N; Josh is soldier N. The soldiers are going to stand in a circle in the order 1,2,…,P−1,N,P,P+1,…,N−1. Formally, they are standing in the circle in such a way that if Josh's position is P (1≤P≤N), then for each i (1≤i≤N−2, i≠P−1), soldier i+1 is directly to the right of soldier i, soldier P (if P≤N−1) or 1 (if P=N) is directly to the right of Josh and Josh is directly to the right of soldier P−1 (if P≥2) or soldier N−1 (if P=1); if 2≤P≤N−2, soldier 1 is also directly to the right of soldier N−1. For each i (1≤i≤N−1), soldier i has a sword with power Ai. Josh plans to take a shield with sufficiently high defense power D.
First, the soldiers start to commit group suicide according to the following rules:
Initially, soldier 1 is the attacking soldier.
If the attacking soldier is not Josh, this soldier attacks the soldier that is currently to his right.
When Josh is attacked with power a, the current defense power of his shield decreases by a, and if it becomes negative, Josh dies. When a different soldier is attacked, he does not try to defend and dies immediately. The power of the attacking soldier's sword does not change.
Then, the next living soldier to the right of the current attacking soldier becomes the attacking soldier and the process continues until there is only one soldier left.
It is clear that this way, Josh cannot be the last survivor. However, Chefland's general Chef plans to interrupt this process as soon as there are exactly two living soldiers of Bitland left (Josh wants to be one of them) by attacking them with Chefland's full firepower F. Since this attack is unexpected, both attacked soldiers try to defend independently with the weapons they have. Josh survives if the current defense power of his shield is at least F. Any other soldier survives only if the power of his sword is strictly greater than F. Since Chefland does not attack again, if both Josh and another soldier survive, then the other soldier will kill Josh. Therefore, Josh wants to be the only survivor of Chefland's attack.
Your task is to find the minimum possible value of D such that Josh survives if he chooses his position P optimally (or determine that he cannot survive) and the lowest position P such that Josh survives if he takes a shield with this defense power D.
Input:
• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains N−1 space-separated integers A1,A2,…,AN−1.
• The third line contains a single integer F.
Output:
For each test case, first, print a line containing the string "possible" if Josh can survive or "impossible" if he cannot (without quotes). Then, if he can survive, print a second line containing two space-separated integers P and D.
Constraints:
• 1≤T≤1,000
• 2≤N≤1,000,000
• 1≤Ai≤10,000 for each valid i
• 1≤F≤10,000
• the sum of N over all test cases does not exceed 1,000,005
Example Input:
2
5
12 34 45 5
10
5
10 15 43 20
5
Example Output:
possible
4 100
impossible
Problem Link: CHEFWAR
Problem:
Bitland declared war on Chefland and sent an army to fight them, but Chefland defended efficiently and Bitland's army has been reduced to N soldiers. They have no chance of winning the war and do not want to surrender, so they are planning to commit group suicide. Josh, the leader of Bitland's remaining soldiers, has different plans — he wants to survive and somehow escape.
The soldiers are numbered 1 through N; Josh is soldier N. The soldiers are going to stand in a circle in the order 1,2,…,P−1,N,P,P+1,…,N−1. Formally, they are standing in the circle in such a way that if Josh's position is P (1≤P≤N), then for each i (1≤i≤N−2, i≠P−1), soldier i+1 is directly to the right of soldier i, soldier P (if P≤N−1) or 1 (if P=N) is directly to the right of Josh and Josh is directly to the right of soldier P−1 (if P≥2) or soldier N−1 (if P=1); if 2≤P≤N−2, soldier 1 is also directly to the right of soldier N−1. For each i (1≤i≤N−1), soldier i has a sword with power Ai. Josh plans to take a shield with sufficiently high defense power D.
First, the soldiers start to commit group suicide according to the following rules:
Initially, soldier 1 is the attacking soldier.
If the attacking soldier is not Josh, this soldier attacks the soldier that is currently to his right.
When Josh is attacked with power a, the current defense power of his shield decreases by a, and if it becomes negative, Josh dies. When a different soldier is attacked, he does not try to defend and dies immediately. The power of the attacking soldier's sword does not change.
Then, the next living soldier to the right of the current attacking soldier becomes the attacking soldier and the process continues until there is only one soldier left.
It is clear that this way, Josh cannot be the last survivor. However, Chefland's general Chef plans to interrupt this process as soon as there are exactly two living soldiers of Bitland left (Josh wants to be one of them) by attacking them with Chefland's full firepower F. Since this attack is unexpected, both attacked soldiers try to defend independently with the weapons they have. Josh survives if the current defense power of his shield is at least F. Any other soldier survives only if the power of his sword is strictly greater than F. Since Chefland does not attack again, if both Josh and another soldier survive, then the other soldier will kill Josh. Therefore, Josh wants to be the only survivor of Chefland's attack.
Your task is to find the minimum possible value of D such that Josh survives if he chooses his position P optimally (or determine that he cannot survive) and the lowest position P such that Josh survives if he takes a shield with this defense power D.
Input:
• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains N−1 space-separated integers A1,A2,…,AN−1.
• The third line contains a single integer F.
Output:
For each test case, first, print a line containing the string "possible" if Josh can survive or "impossible" if he cannot (without quotes). Then, if he can survive, print a second line containing two space-separated integers P and D.
Constraints:
• 1≤T≤1,000
• 2≤N≤1,000,000
• 1≤Ai≤10,000 for each valid i
• 1≤F≤10,000
• the sum of N over all test cases does not exceed 1,000,005
Example Input:
2
5
12 34 45 5
10
5
10 15 43 20
5
Example Output:
possible
4 100
impossible
Explanation:
Example case 1: When Josh is at the position P=4, the soldiers' initial powers in clockwise order around the circle, starting with soldier 1, are [12,34,45,D,5] (D denotes Josh). Then, the following happens:
The soldier with power 12 attacks the soldier with power 34 and kills him.
The soldier with power 45 attacks Josh, who defends. The living soldiers' powers are now [12,45,D−45,5] and Josh is the attacking soldier.
Josh does not attack, so the soldier to his right (with power 5) becomes the attacking soldier. He attacks the soldier with power 12 and kills him.
The soldier with power 45 attacks Josh again and Josh defends again.
The soldier with power 5 attacks the soldier with power 45 and kills him.
Now, two soldiers are left: Josh (with a shield with defense power D−90) and the soldier with a sword with power 5. Each of them is attacked with firepower F=10, so the power of Josh's shield drops to D−100 and the other soldier dies.
If Josh survives, his shield's initial power D should be at least 45+45+10=100. For all other positions P, Josh cannot survive.
Example case 2: Regardless of how large D is and which position Josh chooses, after Chefland's attack, a soldier of Bitland other than Josh will always survive. This soldier will then attack Josh until his shield breaks and he dies.
Solution:
EDITORIAL
Pseudocode:
CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
Example case 1: When Josh is at the position P=4, the soldiers' initial powers in clockwise order around the circle, starting with soldier 1, are [12,34,45,D,5] (D denotes Josh). Then, the following happens:
The soldier with power 12 attacks the soldier with power 34 and kills him.
The soldier with power 45 attacks Josh, who defends. The living soldiers' powers are now [12,45,D−45,5] and Josh is the attacking soldier.
Josh does not attack, so the soldier to his right (with power 5) becomes the attacking soldier. He attacks the soldier with power 12 and kills him.
The soldier with power 45 attacks Josh again and Josh defends again.
The soldier with power 5 attacks the soldier with power 45 and kills him.
Now, two soldiers are left: Josh (with a shield with defense power D−90) and the soldier with a sword with power 5. Each of them is attacked with firepower F=10, so the power of Josh's shield drops to D−100 and the other soldier dies.
If Josh survives, his shield's initial power D should be at least 45+45+10=100. For all other positions P, Josh cannot survive.
Example case 2: Regardless of how large D is and which position Josh chooses, after Chefland's attack, a soldier of Bitland other than Josh will always survive. This soldier will then attack Josh until his shield breaks and he dies.
Solution:
EDITORIAL
Pseudocode:
int Damage(int n, int a[],int p)Code:
int s = (n-(p+1)) + ceil(p/2)
int d = 0
if(p%2 != 0)
d = d + a[p]
int last = s
int step = 2
while( last != 1)
if((last-1)%step==0)
if(last<=(n-(p+1))
d = d + a[last+p]
else
d = d + a[2*(k-n+p)+1]
else
last = ((last-1)-(last-1)%step)+1
step = step*2
return d
int n,f
n,f=input
n=n-1
int a[n+1]
a[0] = 0;
for i = 1 to n
a[i]=input
int result[n]
initialize result with -1
for i=0 to n
if(a[i]<=f)
result[i]=damage(n,a,i)
int count=0
for i=0 to n
if(result[i]!=-1)
count=count+1
if(count==0)
print "impossible"
else
int index=n+1
int min_damage=INT_MAX
for i = n to 0
if(result[i] != -1 && result[i]<=min_damage)
index=i
min_damage=result[i]
print "possible\n"
print index+1
print min_damage+f
CODE
For any doubt or correction feel free to contact me:
@saranyanaharoy
Happy Learning
Pastebin
#include <bits/stdc++.h>#define dbg(i,j) cout<<"I am "<<i<<" = "<<endl<<j<<end - Pastebin.com
Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time.