JoyZombie
BAN USER//Solution with Dynamic programming, although, haven't even compiled, idea is like, if replacing one character results into a valid word in dictionary then its a similar subproblem like what's the minimum iterations required from that point onwards.
findMinWays(string str)
{
if (str == endWord) {
return 0;
}
int min=MAX_INT, num=0;
for (int i=0; i<str.length1; i++) {
if ( dict.exists( str.replace(i, endWord[i]) ) ) {
num = findMinWays(str.replace(i, endWord[i]));
if (num < min)
min = num;
}
}
if (min==MAX_INT)
return 0;
return min;
}

JoyZombie
October 28, 2015 #include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left, *right;
};
void findFirstnLastOfLevel(Node* root, vector<pair<unsigned int, unsigned int>>& result, unsigned int level ) {
if (result[level].first == 1)//left for this level not yet found
result[level].first = root>data;
else
result[level].second = root>data;//always overwrite the rightest node
if (root>left != NULL)
findFirstnLastOfLevel(root>left, result, level+1);
if (root>right != NULL)
findFirstnLastOfLevel(root>right, result, level+1);
}

JoyZombie
September 20, 2015 Its very difficult to understand to your logic considering the code, you've provided. Lets say we've 5 stored at 0th index
so arr[0] will give us 5
lets say, we've 10 stored at 5th index
so, temp = arr[arr[temp]] = 10
then, you are setting 1 as :
arr[arr[temp]] = 1 , which will write 1 at index by two more levels of indirection, which doesn't help in anyway, I guess.
But I somewhat understood what you were trying to say, but actually couldn't come up with right algo using that approach,
Can you repost the correct version of what you were trying to do in first place?
This approach is like being greedy at each step and not taking into account minCostThusFar at each step. Hence, it will not give optimal answer all the time.
You can modify your algo by NOT just comparing 'move up' or 'move up and cross'; instead you should compare 'cost of move up + minCostThusFar for same side' and 'cost of move up(other side) + minCostThusFar on other side + cost of crossing'. This will give you optimal result. Applying this technique, you are actually doing Dynamic Programming from Bottomup approach.
@Klaus : If someone plans to use single linked list for purchases then, using a Heap needs some more care in order to do Increasekey operation efficiently because to perform Increasekey, one has to know the index of that node. But it can be done, I guess, efficiently by using some maplike datastructure.
Moreover, [ having many linked lists(each for a product) & not having main linked list ] or [ having a single list ] almost takes same space. So, we are not gaining much out of it.
Not that simple though. 'All stops in a cluster should be at a distance not greater than D'  is difficult to implement by using algorithm of connected components.
Instead, I think, one has to calculate shortest paths of 'all pairs' first and need to keep only those nodes in a cluster which can be accessible via all other nodes(in that cluster) with a distance <= D and spare other nodes for other clusters probably.
bool customFindSubSeq(string ipStr)
{
vector<unsigned int> followedBy(26,0);
unsigned int toCheck = 0;
transform(ipStr.begin(), ipStr.end(), ipStr.begin(), ::tolower);
for (int i=0; i<ipStr.size(); i++) {
int index=(ipStr[i]  'a');
unsigned int tmp = (1<<index);
if (toCheck != 0) {
for (int b=0; (b<32 && ((1<<b)<=toCheck)); b++)
{
if ( (1<<b) & toCheck) {
if ( followedBy[b] & tmp) {
return true;
}
}
}
}
for (int j=0; j<followedBy.size(); j++) {
if (followedBy[j] != 0)
followedBy[j] = tmp;
}
if (followedBy[index] == 0)
followedBy[index] = (1 << 31);
else
toCheck = tmp;
}
return false;
}

JoyZombie
October 26, 2014 Open Chat in New Window
I didn't check your code, but some optimizations are possible like somehow, keep track of solved subproblems as they'll surely be repeated in future recursions. Also, perhaps its not necessary to actually populate whole graph, instead just recurse through one path until we get final score and then, during unwinding store results in some map of pair(score) and a string(possible path). Then, during backtracking, we don't have to recurse again for a subproblem for which a solution is already saved in that map. Also, we don't again recurse for a subproblem whose reverse pair is already saved in map as key but we'll take care while printing the value(string).
 JoyZombie December 02, 2015