artemis
BAN USERFor 1 to 50
Using DP
1. Initialize dp[0] to dp[6] = 1 {Since these can be reached in 1 dice roll} and all dp[7] to dp[50] = INT_MAX (high number)
2. Ladders will have 2 endpoints : Starting Cell and Ending Cell of which obviously ending cell will be greater.
Sort all the ladders in ascending of their starting cell.
3. For i = 1 to 6
4.Check if there is a ladder with starting cell i. Say ending cell of such a ladder is e. If so make dp[e] = 1;
5. For i = 7 to 50
6. max = INT_MAX (some very high value)
7. For j = i to j = i-6
8. if max < dp[j]+1 then max = dp[j]+1;
9. if dp[i] > max dp[i] = max;
10. Check if there is a ladder with starting cell i. Say ending cell of such a ladder is e. If so make dp[e] = dp[i]+1;
11. dp[50] is the minimum number of dice rolls required to reach 50.
If there are ladders on top of another ladder, example: ladder1 from cell 9 to cell 12 and ladder2 from cell 12 to 25.
In this case repeat Step 4 and Step 10 till there are no more ladders.
Step 10:
10a. flag = 0, s = i;
10b. while flag == 0
10c. Check if there is a ladder with starting cell s. Say ending cell of such a ladder is e. If so make dp[e] = dp[s];
and set s = e;
10d. If there is no such ladder then flag = 1;
@sonesh To your 1st point..yes it will work..First the algo gets the pattern abc, then finds it right in the beginning of the main string.
To your 2nd point: what I mean was for each patter it is O(n)..of course it depends how many substrings need to be matched
@Prashant..yes, exactly what I meant.
@siva..searching in binary tree and binary search tree are different, because BST has the property of left node<root and right node>root, whereas in case of heap we if the element we are searching for < root then it can be in either left/right subtree.
Also, I will add..this was a theory question, so it may not be possible...but I am not sure.
This is O(n) solution
1. Read a pattern i.e substr within *. For example *abc*def*.doc* The first pattern is abc.
2. Use KMP algorithm to find if pattern exists in string and get starting and ending index of where the pattern occurs in the main string.
3. Read the next pat,
Use KMP again,
if it does not exist then no,
if it exists then check if starting index of this pattern is after the ending index of previous pattern. If so then continue with next pattern. Else no.
First for each row, add k consecutive elements (use DP here)
1. Take another matrix B[m][n-k+1], temp = 0
2. for j = 0 to j < m
3. for i = 0 to i < k
temp = temp+A[j][i]
4. B[j][0] = temp
5. for j = 0 to j < m
6. a = k+1
7.for i = 1 to n-k+1
8. B[j][i] = B[j][i-1]+A[j][a]-A[j][a-k]
9. a++;
this takes O(mn+mk) i.e O(mn)
Similarly, now using B[][] find the sum of consecutive k elements, but this time columnwise (using DP as done above) takes another O(mn).
After this we will get the sum of each kxk submatrix possible. A single scan can be done to obtain the maximum one(O(m-k+1)(n-k+1))
Total time is then O(mn).
Will this do?
Considering 'max sum' means subarray with maximum sum and also that this subarray is composed of alternate numbers(since two numbers should not be adjacent to each other) here is the solution I have in mind.
Split the array into two.
First array has all elements at even index, 2nd array has elements in odd index.
Then apply largest contiguous subarray sum method to both.
Return the higher one as the result
yes it should be equal to..Thanks for pointing that out.
I hope this works fine for all.
1. left = 0, mid = 0, right = n
2. while mid <= right
3. if arr[mid] == 0 swap arr[left] and arr[mid], then mid++; left++;
4. if arr[i] == 1 mid++;
5. if arr[i] == 2 swap arr[mid] and arr[right], then right--;
geeksforgeeks will have more details.
Use Dutch Flag Algo:
1. left = 0, mid = 0, right = n
2. while mid < right
3. if arr[mid] == 0 swap arr[left] and arr[mid], then mid++;
4. if arr[i] == 1 mid++;
5. if arr[i] == 2 swap arr[mid] and arr[right], then right--;
geeksforgeeks will have more details.
Eg: aabbccccddddeee
1. Scan the string once to get the count for each alphabet (use hashing). We get a=2, b=2,c=4,d=4,e=3. While doing this scan also maintain a max and min. So we get max = 4, min = 2.
2. diff = max - min and chars_red=0, prev=0 (stores previous value of chars_red)
Now create an array of size max (arr[max]) and assign values to it in this way:
First a = 2. so arr[2]++, then b=2, so arr[2]++..so on
So at the end, arr[] ={0,0,2,1,2}
3. while(char_red <=n)&&(diff != 0) do this :
if(arr[max]!=0)
{
prev = chars_red;
chars_red+=arr[max];
diff--;
max--;
}
4. Ans is prev
I guess we can have a similar method to remove elements with minimum frequency and get prev. Then we compare the values obtained from both and return the minimum one
Eg: aabbccccddddeee
1. Scan the string once to get the count for each alphabet (use hashing). We get a=2, b=2,c=4,d=4,e=3. While doing this scan also maintain a max and min. So we get max = 4, min = 2.
2. diff = max - min and chars_red=0, prev=0 (stores previous value of chars_red)
Now create an array of size max (arr[max]) and assign values to it in this way:
First a = 2. so arr[2]++, then b=2, so arr[2]++..so on
So at the end, arr[] ={0,0,2,1,2}
3. while(char_red <=n)&&(diff != 0) do this :
if(arr[max]!=0)
{
prev = chars_red;
chars_red+=arr[max];
diff--;
max--;
}
4. Ans is prev
I guess we can have a similar method to remove elements with minimum frequency and get prev. Then we compare the values obtained from both and return the minimum one
This is O(num_row*num_col) solution and also changes the matrix, so if the matrix is later required then its copy is needed.
For each cell (i,j) in the matrix do the following:
if (a[i][j] == -1) Call find(i,j), count++;
find(i,j) works somewhat like this:
1. for r = i-1, c = j; r = i+1, c= j; r =i, c = c -1 and r = i, c = c+1...for each of these check if arr[r][c] == -1.
If yes then change arr[r][c] to 0 and call find(r,c)
Thus, we recursively find the entire connected component due to i,j using find(i,j) and ncrement count by 1 for each such instance.
I hope this will be helpful. It has time complexity O(k.num_rows) and space complexity O(num_cols)
Basically I find the minimum element k times. And for finding minimum element we just need to check the first (unscanned) element of each row. And then increment it accordingly.
min stores the minimum element.
minOfRows[i] stores the index (i.e column) of row i which is the first unscanned or rather minimum element of that row.
For eg: a[3][4]={{2,5,6,10},{4,8,9,12},{7,15,20,22}};
minOfRows = 0 for all rows.
For 1st iteration:
min = 2 (1st element of the matrix is minimum and last element (bottom right) is the maximum)
minOfRows[0] is incremented by 1;
For 2nd iteration:
We check minimum from among minOfRows[j] column element for each row j. and update min and minOfRows accordingly.
int min = a[0][0];
int minOfRows[rows];
for(i = 0;i < rows;i++)
minOfRows[i] = 0;
minOfRows[0] = 1;
for(i = 1;i < k;i++){
min = INT_MAX;
for(j = 0;j < rows; j++){
if(minOfRows[j] < cols){
if(a[j][minOfRows[j]] < min){
min = a[j][minOfRows[j]];
r = j;
}
}
}
minOfRows[r]++;
}
Actually whatever element the candidate holds at the end (irrespective of its count at the end), will be the majority element(if there exists one)
For eg: {2, 1, 2}
when i = 0, arr[i] = 2, Start with candidate = 2, count = 1;
when i = 1, arr[i] = 1, candidate = 1, count = (1-1)+1 = 0. Since arr[i] != candidate we decrement count, then change candidate element whenever count reaches 0, and then increment count for this new value of candidate.
when i = 2, arr[i] = 2, candidate = 2, count = 1-1+1 = q (similarly)
So at the end candidate = 2 (There will always be a candidate element at the end of the algo)
So, now 2 is the majority element if there exists one in the array. To be sure, just runa scan once again and maintain a counter only for 2. If it is > n/2 then 2 is the answer
So, I guess we can just maintain a singly linked list with an additional tail pointer. Every time an element is used we move it to the end of the list (use the tail pointer to do it in O(1) time) and every time we have to delete we remove the first element (using the head pointer, make the head pointer point to the next)
- artemis October 26, 2012
sure..Problem with tabs in CareerCup makes it difficult to understand for loops.
- artemis January 05, 2013