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!!!

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:

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

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:

int Damage(int n, int a[],int p)
  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:
CODE

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Problem 1: What will be the output of the following C code:

int fun(char *x){
char *ptr=x;
while(*ptr!=0)ptr++;
return (ptr-x);
}
int main(){
char str[30]="This is PDS test";
printf("%d",fun(str));
}

(a) 4 (b) 16
(c) 17 (d) 30



Problem 2: What will the following code print:

int main(){
int array[4]={20,18,16,14};
int *ptr=array;
printf("%d,%d",*ptr+2,*(ptr+2));
}

(a) 16,16 (b) 20,16
(c) 22,16 (d) 22,22



Problem 3: Which of the following line will give an error if we declare array A, B, C as:

int *A,*B,C[10];

(a) A=B;. (b) B=A+10;
(c) B=C+20; (d) C=B+30;


Problem 4: What will be the output of the following C code:

int main(){
int arr[3]={1,2};
int i;
for(i=0;i<3;i++){
printf("%d ");
}
}

(a) compilation error
(b) 1 2 0
(c) runtime error
(d) 1 2 garbage-value
(e) 1 2 3


Solution 1: (b) 16

Solution 2: (c) 22,16

Solution 3: (d) C=B+30;

Solution 4: (b) 1 2 0



Additional task for viewers:
Try to figure out why the outputs were so.






Happy Coding!!!

Problem:
We have an array arr[0 . . . n-1]. We should be able to
(1) Find the sum of elements from index l to r where 0 <= l <= r <= n-1

(2) Change value of a specified element of the array to a new value x. We need to do arr[i] = x where 0 <= i <= n-1.

Solution:
We can solve this problem using different datastructures. The main purpose of this problem is to introduce some datastructures which are useful to find optimized solutions in many cases.

Prefix Array:
Given an array arr[] of size n, its prefix sum array is another array prefixSum[] of same size such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] … arr[i].

void precompute(int prefixSum[])
prefixSum[0]=arr[0]

for i=1 to n-1 prefixSum[i]=prefixSum[i-1]+arr[i]

int rangesum(int l,int r,int prefixSum[])
if(l=0)
return prefixSum[r]
else
return prefixSum[r]-prefixSum[l-1]

void update(int i,int x,int prefixSum [],int arr[])
int diff = x-arr[i]
for j=i to n-1
prefixSum[j]=prefixSum[j]+diff
arr[i] = arr[i] + diff

Time complexity of range sum query is O(1)
and update query is O(n)

Binary Indexed Tree:
DETAILS
Binary Indexed tree or Fenwick tree takes O(logn) complexity for both range sum operation and update operation.
Compared with segment tree , binary indexed tree requires less space and is easier to implement.

Segment Tree:
DETAILS
Segment tree also performs both range sum operation and update operation in O(logn) time.

Square Root Decomposition:
DETAILS
The key concept of this technique is to decompose given array into small chunks specifically of size sqrt(n).
The time complexity of range sum query is O(sqrt(n)) in worst case.
The time complexity of update query operation is O(1).

Solve different problems using these datastructures to become proficient in applying them in various competitive programming problems.

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Jump Game

Difficulty level : Medium


Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Hint / Solution Link :
SOLUTION

Microsoft Interview Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.


Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]


Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?


Solution:
SOLUTION

"What are the algorithms required to solve all problems (using C++) in any competitive coding contest?"
Answered by Mostafa Saad Ibrahim, ACM ICPC World Finalist, Problem Setter

Here is my helper list. It lists most of needed algorithms/concepts.Some elements are not algorithms (e.g. Fake, States/Concerns) and little repetitions.

But 1 final advice: Initially, Given great attention to thinking skills rather than the knowledge. This is helpful for both competitions and your future. To do so, make sure you are so good in adhocks, where no algorithms are required, just pure thinking.

Asked in Amazon Interview

Find Longest Palindrome in a String : Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

NOTE: Required Time Complexity O(n^2).

Example:
Input:
1
aaaabbaa

Output:
aabbaa

Solution:
https://www.linkedin.com/feed/update/urn:li:activity:6594490601763364864

Problem : Merge Intervals
Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.


Solution:
SOLUTION

Elevator Problem

A building has floors numbered 0 through n≤10^18. There is a single elevator with four buttons: "go to floor 0", "+a floors", "+b floors", and "+c floors". We have a,b,c≤ 10^6. Compute the number of unreachable floors.


Solution:

This feels like a number theory problem, but trying to solve it by GCDs and casework will not lead to success. Instead, treat it as a graph theory problem. First, note that if you can reach floor x, you can reach all floors of the form x+k*a. Hence, for each remainder modulo a all we need is the smallest reachable x with this remainder. These can be found by using Dijkstra’s shortest path algorithm on a graph with a nodes. The nodes are the remainder classes, and from each node there are two edges, corresponding to +b and +c.

The stunning thing about this problem is the asymmetry of the solution: you are treating one button differently from the other two.

Credits : Michal Forišek on Quora, scientist, competitive programmer

Adobe Interview:
Credits : GFG

Problem:
Find Minimum Number of Platforms Required for a Railway/Bus Station

Given arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits.
We are given two arrays which represent arrival and departure times of trains that stop

Examples:
Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
There are at-most three trains at a time (time between 11:00 to 11:20)

Solution:
SOLUTION

Dynamic Programming playlist by Chirayu Jain

https://www.youtube.com/playlist?list=PLtBICreuIvuuVifFHcHvIUR6elWTy1K5v

Some links for Competitive Programming Resources :

1. https://github.com/kothariji/competitive-programming

2. https://github.com/kunal-kushwaha/Competitive-Programming-Resources

List of awesome learning resources :


https://www.topcoder.com/thrive/articles/List%20of%20awesome%20learning%20resources

The Ultimate Topic List (with Resources, Problems and Templates) - Codeforces
https://codeforces.com/blog/entry/95106