iroodaz
BAN USERI suggest using fast exponentiation technique (exponentiation by squaring) for the whole number portion. We can utilize the same technique for the decimal portion; however, this time every time we move one digit forward in base 2 representation of the decimal portion, we calculate the square root of the previous step using babylonian method, or any other efficient method.
- iroodaz April 16, 2014Thank you very much for the analysis ninhnnsoc, and also thanks for the paper on the average path length.
Hahaha, I could not digest the proof; however, the good news is, we can use what they proved :-D
I think, as you said, it is okay to assume the sub-graph is a random graph with p = ( (N^2) - E)/N^2 where E is the number of the edges with cost B. However, have got no idea if the graph is scale-free as I couldn't understand the definition in the Wikipedia article :-(
In addition, I totally agree with you on maximum step count; therefore, the O(m.N) upper bound seems correct. By the way, the 2-way BFS idea is great and maybe even necessary.
I'm not sure if there is a better algorithm than BFS for finding a shortest path, because at any node we probably have no information about our distance from the target node.
Thanks again for your research and analysis.
Hi ninhnnsoc.
If A<B, what you said is correct, but first of all note that we cannot store the edges with cost A, and second, during the interview, probably you'd need to prove that doing this would work, because we have O(n^2) edges with cost A and BFS is runs linear in number of edges. My initial intuition is that, when n grows, the length of the path becomes incredibly short; therefore, the algorithm would run in O(n) anyway. I cannot formally proof why it would work, though.
A DP solution without using recursions. A technique similar to non-recursive DFS is used. A 1xN table is used as a stack. For memoization part, I have put two variables in every node to keep track of the largest independent set in the subtree rooted at that node. One for the case that, that node is included in the set, and another one for the case that, that node is not included in the set.
#include <iostream>
using namespace std;
#define mp make_pair
#define nodeID first
#define state second
typedef pair<int, int> pi;
const int BLACK = 0;
const int GREY = 0;
int max(int a, int b) { return (a < b ? b : a); }
class Node{
int id;
int childCount;
int chosenBestSet;
int notChosenBestSet;
int *children;
public:
int getChildCount()
{
return childCount;
}
int getChildIdAt(int i)
{
return children[i];
}
int getChosenBest()
{
return this->chosenBestSet;
}
int getNotChosenBest()
{
return this->notChosenBestSet;
}
void setChosenBest(int val)
{
this->chosenBestSet = val;
}
void setNotChosenBest(int val)
{
this->notChosenBestSet = val;
}
};
int solve(int numOfNodes, pi *stk, Node* nodes, int root)
{
int top = 0;
stk[top] = mp(root, BLACK);
while (top >= 0)
{
int topElemId = stk[top].nodeID;
Node *curNode = &(nodes[topElemId]);
int childCnt = curNode->getChildCount();
int topElemState = stk[top].state;
if (topElemState == GREY)
{
int chBestCnt = 0, notChBestCnt = 0;
for (int i = 0; i < childCnt; i++)
{
Node curChild = nodes[curNode->getChildIdAt(i)];
chBestCnt += curChild.getNotChosenBest();
notChBestCnt += max(curChild.getChosenBest(), curChild.getNotChosenBest());
}
curNode->setChosenBest(chBestCnt);
curNode->setNotChosenBest(notChBestCnt);
top--;
continue;
}
stk[top].state = GREY;
if (childCnt == 0)
{
curNode->setChosenBest(1);
curNode->setNotChosenBest(0);
top--;
continue;
}
for (int i = 0; i < childCnt; i++)
{
int childId = curNode->getChildIdAt(i);
stk[++top] = mp(childId, BLACK);
}
}
return max(nodes[root].getChosenBest(), nodes[root].getNotChosenBest());
}
Hey buddy. Unfortunately, this algorithm won't work. Consider this testcase:
Servers: 7 9
Tasks: 3 3 3 7
This solution will first assign the first two tasks to the first server and the third task to the second server. After that, we won't have enough server capacity for the fourth task; therefore, it will return false. However, if we assign the first three tasks to the second server, and the last task to the first server, we have a valid assignment.
As the number of servers and the number of tasks is not so big, we can use backtracking to solve it, and use memoization technique (dynamic programming) to keep track of previously visited configurations and to have a better running time by pruning duplicate sub-trees.
Here is my implementation in C++:
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#define mp make_pair
using namespace std;
int tmp1[10], tmp2[10];
struct srtArray{
int n;
int *ary;
srtArray(int N)
{
n = N;
ary = new int[n];
}
void srt()
{
sort(ary, ary + n);
}
bool operator < (const srtArray& that)const
{
int i;
for (i = 0; i < n && that.ary[i] == ary[i]; i++);
if (i == n)
return false;
return ary[i] < that.ary[i];
}
};
set < pair<int, srtArray> > seen;
int remCap[10];
int totalTaskCount,serverCount;
int tasksCapacity[10];
vector < pair<int, int> > answer;
bool solve(int curtask)
{
if (curtask == totalTaskCount)
return true;
srtArray *curarray = new srtArray(serverCount);
for (int i = 0; i < serverCount; i++)
curarray->ary[i] = remCap[i];
curarray->srt();
if (seen.find(mp(curtask,*curarray)) != seen.end())
return false;
for (int i = 0; i < serverCount; i++)
{
if (remCap[i] >= tasksCapacity[curtask])
{
remCap[i] -= tasksCapacity[curtask];
if (solve(curtask + 1))
{
answer.push_back(mp(curtask + 1, i + 1));
return true;
}
remCap[i] += tasksCapacity[curtask];
}
}
seen.insert(mp(curtask, *curarray));
return false;
}
bool startSolving(int sCount,int *sCap,int tCount,int *tCap)
{
totalTaskCount = tCount;
for (int i = 0; i < tCount; i++)
tasksCapacity[i] = tCap[i];
serverCount = sCount;
for (int i = 0; i < sCount; i++)
remCap[i] = sCap[i];
return solve(0);
}
int main()
{
int n, t;
int *sCap = new int[10];
int *tCap = new int[10];
while (cin >> n >> t)
{
seen.clear();
answer.clear();
for (int i = 0; i < n; i++)
cin >> sCap[i];
for (int i = 0; i < t; i++)
cin >> tCap[i];
if (startSolving(n, sCap, t, tCap))
{
cout << "Possible!\n";
for (int i = 0; i < answer.size(); i++)
cout << answer[i].first << " -> " << answer[i].second << endl;
}
else
cout << "Impossible\n";
cout << endl;
}
}
Thanks Eugene :-)
Could you please provide a small example for the case with 5 distinct values rather than 4?
I've actually used an array in my other post here.
Unfortunately, I have read the solution in the pdf and what comes next is not my solution:
First of all, observe that we are only interested in maximum and minimum of a given slicing to check its validity. This said, the problem is solved if we can find a way for handling maxima and minima efficiently. From here on, I will only explain how to handle the maximum (the minimum is pretty similar). Suppose the first pointer goes forward one step and points to element X. Now we have two types of numbers in the slicing. The ones that are smaller than X and the ones that are larger than or equal to X. Let us focus on the smaller ones. We can see that those numbers are never going to be the maximum. The proof is by contradiction and is pretty straightforward, so I'll skip it. Now, suppose that we have the numbers in the slicing in non-increasing order. When we want to add X, we discard the smaller ones and the append X to end of the list; therefore, we maintain the non-increasing order. Another interesting property we have is that the numbers in the set are in order of their appearance in the original array, because we always append the new one to end of the list. This property, helps us in advancing the second pointer. Right before every step of the second pointer, we simply check the first element of the list and if it is the element that the second pointer is currently pointing to, we remove it from the list, before advancing the second pointer.
We can see that, maintaining a list like the above is going to cost us O(n) total amount of time, because every element is inserted and removed at most once. Here is an implementation of the list using STL list.:
#include <iostream>
#include <list>
using namespace std;
class myDataStructure{
private:
list < pair<int, int> > maxima, minima;
public:
void insert(int value, int position)
{
while (maxima.size() && maxima.back().first < value)
maxima.pop_back();
maxima.push_back(make_pair(value, position));
while (minima.size() && minima.back().first > value)
minima.pop_back();
minima.push_back(make_pair(value, position));
}
void remove(int position)
{
if (maxima.front().second == position)
maxima.pop_front();
if (minima.front().second == position)
minima.pop_front();
}
int maxMinDifference()
{
int mx = maxima.front().first;
int mn = minima.front().first;
return mx - mn;
}
};
C++ implementation for the algorithm described in my other post: ( O(n) running time )
#include <iostream>
#include <algorithm>
using namespace std;
class myDS{
private:
int mx, mn, distinctCount;
pair<int, int> ary[4];
public:
myDS()
{
for (int i = 0; i < 4; i++)
ary[i].first = ary[i].second = -1;
distinctCount = 0;
}
void insert(int x)
{
int emptySlot = -1;
for (int i = 0; i < 4; i++)
{
if (ary[i].second > 0)
{
if (ary[i].first == x)
{
ary[i].second++;
return;
}
continue;
}
emptySlot = i;
}
ary[emptySlot].first = x;
ary[emptySlot].second = 1;
if (distinctCount>0)
{
mx = max(mx, x);
mn = min(mn, x);
}
else
mx = mn = x;
distinctCount++;
}
void remove(int x)
{
bool isThisTheFirstOne = true;
for (int i = 0; i < 4; i++)
{
if (ary[i].first == x && ary[i].second>0)
{
if (ary[i].second == 1)
{
ary[i].first = ary[i].second = -1;
distinctCount--;
}
else
{
ary[i].second--;
}
}
if (ary[i].second > 0)
{
if (isThisTheFirstOne)
{
mx = mn = ary[i].first;
isThisTheFirstOne = false;
}
else
{
mx = max(mx, ary[i].first);
mn = min(mn, ary[i].first);
}
}
}
}
bool isGood()
{
return ((mx - mn) <= 2);
}
};
long long numberOfGoodSlices(int n, int *ary)
{
int ptr1 = 0, ptr2 = 0, mx, mn;
long long ans = 0ll;
myDS *mds = new myDS();
mds->insert(ary[0]);
while (ptr1 < n)
{
if (mds->isGood() )
{
ans += (ptr1 - ptr2) + 1;
ptr1++;
if (ptr1 < n)
mds->insert(ary[ptr1]);
}
else
mds->remove(ary[ptr2++]);
}
return ans;
}
Hi everyone.
First of all, I should point out that if we want to know all those pairs, we cannot do better that n-squared. Consider an array of all 1's. For this array we have to print out all pairs as the answer. So, printing alone would take quadratic amount of time. This said, from now on, I am assuming that we are only interested in the number of those pairs.
As the OP has said, we can solve this problem in O(n). I will give a hint, and start coding myself. However, let's analyze and see an O(nlogn) solution, which itself leads to the O(n) solution.
The algorithm that I am going to describe, utilizes a two-pointer approach. That is, two pointers are going to traverse the array. These pointers are going to show us a valid slicing. We are going to advance the first pointer until the slicing becomes invalid. After that we are going to advance the second pointer until we have a valid slicing, again. We are going to do this routine until the first pointer gets out of range.
Here is the algorithm.
1. Point both pointers to the first element.
2. Answer <= 0
3. While first pointer is in range:
a. If current slicing is valid, then:
1. Answer <= Answer + (Number of elements between two pointers, inclusive)
2. Advance the first pointer one step
b. Else, current slicing is not valid:
1. Advance the second pointer one step
4. Return Answer
For the moment, let's not worry about the running time of the validity check and find out if the algorithm counts all valid pairs.
We can prove this by contradiction. Suppose there is a valid pair, say (A,B), that we do not count when the first pointer points to B. That is, when the first pointer reaches B, the second pointer is pointing to an element after A. This can only happen when the second pointer points to A and the first pointer is pointing to an element C(A<C<B), and the slicing (A,C) is not valid (so the second pointer goes forward one step and we miss (A,B) when we reach B). However, a situation like this is impossible, because if (A,C) is not valid the difference between the maximum and the minimum in (A,C) is more than two; therefore, the difference between the maximum and the minimum in (A,B) is going to be at least equal to that of (A,C), because (A,C) is contained in (A,B). This shows that we are not going to miss a valid pair.
Let's go back to validity check. As we are going to do this check n times we should be able to do it in O(logn). We can do this check in O(logn) by using a balanced binary search tree like Red-Black Tree. This tree contains all elements in the slicing between the pointers. In each iteration, we compare the maximum (O(logn) ) and the minimum (O(logn) ) of the tree, to see if a slicing is valid. If we have a valid slicing, we increment the first pointer and insert the element that it points to, in the tree. If the slicing is not valid, we delete the element that the second pointer points to from the tree, and the increment the second pointer.
Here is my implementation of the algorithm in C++. I have used STL map as the balanced tree:
#include <iostream>
#include <map>
using namespace std;
long long numberOfGoodSlices(int n, int *ary)
{
int ptr1 = 0, ptr2 = 0, mx, mn;
long long ans = 0ll;
map <int, int> mp;
map <int, int> ::iterator it;
mp[ary[0]] = 1;
while (ptr1 < n)
{
mx = mp.rbegin()->first;
mn = mp.begin()->first;
if ( (mx - mn) <= 2 ) //we are in good shape :)
{
ans += (ptr1 - ptr2) + 1;
ptr1++;
if (ptr1 < n)
{
it = mp.find(ary[ptr1]);
if (it == mp.end())
mp[ary[ptr1]] = 1;
else
it->second++;
}
}
else
{
it = mp.find(ary[ptr2++]);
it->second--;
if (!(it->second))
mp.erase(it);
}
}
return ans;
}
Hint for linear solution: We never have more than 4 distinct values in the tree. I'm going to code this one, too and post it here.
Cheers!
Hey everyone. My solution is the same as the majority of you. Here is my implementation in C++, using priority_queue class in STL. Note that, we should push (-1 * value) in the pqueue, because we want to have a min-heap but the priority_queue class implements a max-heap.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
string findnexthighest(string ipt)
{
priority_queue <char> pq;
int swplace = -1;
for (int i = ipt.size() - 1; i > 0; i--)
{
pq.push(-1 * ipt[i]);
if (ipt[i] > ipt[i - 1])
{
swplace = i - 1;
break;
}
}
if (swplace < 0)
return ipt;
pq.push(-1 * ipt[swplace]);
int curplace = swplace + 1;
int cur;
while (true)
{
cur = -1 * pq.top();
pq.pop();
if (cur>ipt[swplace])
{
ipt[swplace] = cur;
break;
}
ipt[curplace++] = cur;
}
while (!pq.empty())
{
cur = -1 * pq.top();
pq.pop();
ipt[curplace++] = cur;
}
return ipt;
}
The running time of the algorithm is proportional to running time of the sorting algorithm used. Note that we have only digits here, so we can use counting sort to have a linear running time.
- iroodaz April 11, 2014
Could you provide more info on swapping definition? Are we only allowed to put a car in the empty slot in each step?
- iroodaz April 16, 2014