gimli
BAN USERI think this is the correct solution, but can you also explain this. I am not very familiar with this programming language, but seems like you are filling the server with tasks going in descending order of capacity. If you fail to fit a task at any stage, you back track and try next server until you either find a solution or run out of all servers to try.
- gimli August 05, 2014Here is the code using backtracking. I have not bothered for boundary cases, but they can be incorporated as well. Following give some idea.
#include <iostream>
#include <set>
using namespace std;
template<typename T, typename U>
class Point
{
public:
Point(T x, U y);
bool operator== (const Point& other) const;
bool operator!= (const Point& other) const;
bool operator< (const Point& other) const;
bool operator<= (const Point& other) const;
bool operator>= (const Point& other) const;
T m_x;
U m_y;
};
template<typename T, typename U>
Point<T, U>::Point(T x, U y)
: m_x(x),
m_y(y)
{}
template<typename T, typename U>
bool Point<T, U>::operator== (const Point& other) const
{
return m_x == other.m_x && m_y == other.m_y;
}
template<typename T, typename U>
bool Point<T, U>::operator!= (const Point& other) const
{
return !(*this == other);
}
template<typename T, typename U>
bool Point<T, U>::operator< (const Point& other) const
{
if (m_x < other.m_x) return true;
else if (m_x == other.m_x)
return m_y < other.m_y;
else return false;
}
template<typename T, typename U>
bool Point<T, U>::operator<= (const Point& other) const
{
return (*this < other) || (*this == other);
}
template<typename T, typename U>
bool Point<T, U>::operator>= (const Point& other) const
{
return !(*this < other) || (*this == other);
}
template<typename T, typename U>
static bool PathExists(const Point<T, U>& o, const Point<T, U>& x, const set< Point<T, U> >& w,
set< Point<T, U> >& checked,
T tRange[2],
U uRange[2],
T tUnit,
U uUnit)
{
if (o == x) return true;
if (w.find(o) != w.end()) return false;
bool checkPath = true;
if ((o.m_x - tUnit) >= tRange[0])
{
Point<T, U> newO(o.m_x - tUnit, o.m_y);
if (checked.find(newO) == checked.end())
{
checked.insert(newO);
checkPath = PathExists(newO, x, w, checked, tRange, uRange, tUnit, uUnit);
if (checkPath) return true;
}
}
if ((o.m_x + tUnit) <= tRange[1])
{
Point<T, U> newO(o.m_x + tUnit, o.m_y);
if (checked.find(newO) == checked.end())
{
checked.insert(newO);
checkPath = PathExists(newO, x, w, checked, tRange, uRange, tUnit, uUnit);
if (checkPath) return true;
}
}
if ((o.m_y - uUnit) >= uRange[0])
{
Point<T, U> newO(o.m_x, o.m_y - uUnit);
if (checked.find(newO) == checked.end())
{
checked.insert(newO);
checkPath = PathExists(newO, x, w, checked, tRange, uRange, tUnit, uUnit);
if (checkPath) return true;
}
}
if ((o.m_y + uUnit) <= uRange[1])
{
Point<T, U> newO(o.m_x, o.m_y + uUnit);
if (checked.find(newO) == checked.end())
{
checked.insert(newO);
checkPath = PathExists(newO, x, w, checked, tRange, uRange, tUnit, uUnit);
if (checkPath) return true;
}
}
return false;
}
int main()
{
int range[] = { 1, 7 };
Point<int, int> start(1, 1);
Point<int, int> end(7, 7);
set< Point<int, int> > ws;
ws.insert(*(new Point<int, int>(1, 2)));
ws.insert(*(new Point<int, int>(2, 2)));
ws.insert(*(new Point<int, int>(2, 3)));
ws.insert(*(new Point<int, int>(2, 4)));
ws.insert(*(new Point<int, int>(3, 5)));
ws.insert(*(new Point<int, int>(4, 1)));
ws.insert(*(new Point<int, int>(4, 5)));
ws.insert(*(new Point<int, int>(4, 6)));
ws.insert(*(new Point<int, int>(4, 7)));
ws.insert(*(new Point<int, int>(5, 1)));
ws.insert(*(new Point<int, int>(5, 3)));
ws.insert(*(new Point<int, int>(5, 4)));
ws.insert(*(new Point<int, int>(6, 1)));
ws.insert(*(new Point<int, int>(6, 6)));
ws.insert(*(new Point<int, int>(7, 2)));
ws.insert(*(new Point<int, int>(7, 3)));
ws.insert(*(new Point<int, int>(7, 4)));
ws.insert(*(new Point<int, int>(7, 5)));
set< Point<int, int> > checked;
checked.insert(start);
if (PathExists(start, end, ws, checked, range, range, 1, 1))
{
cout << "YaY, Found!" << endl;
}
else
{
cout << "Not found :(" << endl;
}
return 0;
}
I implemented it using KMP longest prefix finding approach.
Basically, I am finding the longest prefix of all substrings of the given string, which is proper suffix of the substring.
More clearly, for any substring s[i] ... s[j], I find the longest prefix s[i] ... s[k] which is proper suffix of s[i] ... s[j].
When, I have computed all such values, I go over them and check if the prefix found is a repeating string (it is, if the length of prefix is atleast half the length of the substring considered), and return the longest one.
Since I have to find for all strings, the running time is O(n^2). Is there any better time complexity? I am think maybe I can use the result of pi[0][x] ... pi[i-1][x] while computing pi[i][x], but having thought through it.
static string FindLongestRepeationgSubstring(string s)
{
int n = s.length();
int pi[n][n];
for (int i = 0; i < n; ++i)
pi[i][i] = i - 1;
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
int k = pi[i][j-1];
while (k >= i && s[j] != s[k+1]) k = pi[i][k];
if (s[j] == s[k+1]) k++;
pi[i][j] = k;
}
}
for (size_t i = 0; i < n; ++i)
{
for (size_t j = i; j < n; ++j)
{
cout << pi[i][j] << " ";
}
cout << endl;
}
int ls = -1;
int le = -1;
int l = 0;
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n; ++j)
{
int tempL = pi[i][j] - i + 1;
if ((pi[i][j] >= j - tempL) && tempL > l)
{
l = tempL;
ls = i;
le = pi[i][j];
}
}
}
if (l > 0)
return s.substr(ls, l);
else
return "";
}
You missed a minute detail, when you introduced the minority person to the majority person, the counter is zero, but the current guess also changes to the next person which is the majority person.
Since we are assuming that data ensures there is always a majority person, we need not check if this guess is correct (it has to be), otherwise we would have introduced this person with everyone else to confirm it is from majority.
We define
S[i][j] to be the minimum number of operations required to convert substring a[i] .. a[j] into RPN.
Now we have the following recursive formulation of S[i][j]
S[i][j] =
min { (0, if i == j & a[i] is an operand),
(1, if i == j & a[i] is an operator [either delete it or replace with operand, both have same cost, if they would have been different we would have chosen the minimum]),
(S[i][j-1] + 1, [just delete a[j] and convert a[i] .. a[j-1] into RPN]),
(min_(i<=k<j-1){S[i][k] + S[k+1][j-1]}, if a[j] is an operator [if we convert S[i][k] and S[k+1][j-1] into RPN, and just use the operator a[j] we have a valid RPN, minimize over all such k]),
min{
(min_(i<=k<j-1){S[i][k] + S[k+1][j-1]} + 1, if a[j] is an operand [if we convert S[i][k] and S[k+1][j-1] into RPN, and convert a[j] into operator we have a valid RPN, minimize over all such k]),
(min_(i<=k<j){S[i][k] + S[k+1][j]} + 1, if a[j] is an operand [if we convert S[i][k] and S[k+1][j] into RPN, and insert an operator we have a valid RPN, minimize over all such k])
}
}
Keep a queue of characters which you have found till now in the text which are in the map as well. While queuing, decrease the count in the map, while dequeuing increase the count in the map.
Here is when we queue and dequeue:
Queue Q
foreach character in text
if map[character] > 0
Q.Enqueue[character]; map[character]--;
if (Q.size == requiredLength) return Q.ToString();
else
while(Q.front() != character)
map[Q.Dequeue]++;
Q.Dequeue; Q.Enqueue[character];
Isn't writing number to pre-allocated buffer same as writing number in stringbuf of stringstream? In stringstream case, the buffer resizing is handled automatically, which will not be as bad as creating string for each number.
Also, I think, string size can be computed as:
long count = 0;
int multiplier = 1;
int rem = 0;
int digits = 1;
while (n > 10)
{
rem += (n%10)*multiplier; // this will calculate the remaining highest digit numbers in range [1,n]
count += 9*multiplier*digits; // number of 'digits' digits number is 9*multiplier (1 digit -> 9, 2 digit -> 90, so on)
n = n/10;
multiplier *= 10;
digits++;
}
count += ((n-1)*multiplier + rem)*digits;
count += (n-1); // for commas
The simple O(n^2) is evident where each delegate is made to greet every other and hence checked if it belong to the majority party.
There is an elegant O(n) algorithm: Go through all delegates. Keep a counter and current guess for delegate of majority party, for each delegate the guessed delegate meet with smile, increase the counter and for each stare decrease the counter. When counter is zero, update the guess with the next delegate that you pick (at initialization, the first delegate is the guess).
When you have gone through all delegates, confirm that the delegate that you have chosen is indeed the one from majority party (this check not required if question ensures that there is a majority party)
For correctness of O(n) algorithm, search for 'Finding majority element in an array'
Here is the solution in C++. Quite straightforward, and true the stack size would be O(n.size)
First call is PrintStrings("", n, 0, n.size)
const char phonePad[][5] =
{
{'1', ' ', '\0', '\0', '\0'},
{'3', 'a', 'b', 'c', '\0'},
{'3', 'd', 'e', 'f', '\0'},
{'3', 'g', 'h', 'i', '\0'},
{'3', 'j', 'k', 'l', '\0'},
{'3', 'm', 'n', 'o', '\0'},
{'4', 'p', 'q', 'r', 's'},
{'3', 't', 'u', 'v', '\0'},
{'4', 'w', 'x', 'y', 'z'},
{'1', '+', '\0', '\0', '\0'}
};
static void PrintStrings(std::string prefix, int n[], int startIndex, int size)
{
const char* optionsStr = &phonePad[n[startIndex]][0];
int options = atoi(optionsStr);
for (int optionIndex = 1; optionIndex < 1 + options; ++optionIndex)
{
std::string newPrefix = prefix + phonePad[n[startIndex]][optionIndex];
if (startIndex == size - 1)
{
printf("%s\n", newPrefix.c_str());
}
else
{
PrintStrings(newPrefix, n, startIndex + 1, size);
}
}
}
Sorry mistakes in code.
Here is corrected:
int A[m][n];
int i = m-1;
int j = n-1;
for(;i >= 0 && j >= 0; i--, j--)
{
if ( i == m-1 && j == n-1)
{
A[i][j] = 0;
}
else
{
A[i][j] = A[i+1][j] + A[i][j+1];
}
for (int k = i-1; k >= 0; k--)
{
if ( j == n-1)
{
A[k][j] = A[k+1][j];
}
else
{
A[k][j] = A[k+1][j] + A[k+1][j+1];
}
}
for (int k = j-1; k >= 0; k--)
{
if ( i == m-1)
{
A[i][k] = A[i][k+1];
}
else
{
A[i][k] = A[i][k+1] + A[i+1][k+1];
}
}
}
|_13_|_4_|_1_|
|_09_|_3_|_1_|
|_03_|_2_|_1_|
|_01_|_1_|_0_|
For example, the array above has 13 paths from top-left corner to bottom-right corner. In each node, i have listed number of paths from that node to the bottom-right corner.
So, it can be seen easily it can be done in O(n^2) time.
Here is the sample code:
int A[m][n];
int i = m-1;
int j = n-1;
for(;i >= 0 && j >= 0; i--, j--)
{
if ( i == m-1 && j == n-1)
{
A[i][j] = 0;
}
else
{
A[i][j] = A[i+1][j] + A[i][j+1];
}
for (int k = i-1; k >= 0; k--)
A[k][j] = A[k+1][j+1];
for (int k = j-1; k >= 0; k--)
A[i][k] = A[i+1][k+1];
}
Start from the root of say BST1, and search for its correct position in other tree BST2. Let this be node x, now if root of BST1 lies to the right of x, then attach the root as well as whole right sub-tree at this node, and perform the same operation with left sub tree as BST1.
Thus, we will do a search (O(lg n)) in BST2 O(lg m) time which is the height of BST1.
Hence complexity is O(lg m . lg n).
Only the parallel chords is not the answer. For instance, with 6 points, we can draw a hexagon and select any group of alternate edges, thus drawing 3 non-intersecting chords.
The number can be found using the following recursion I think:
T(n) = 2n x T(n-1)
The logic behind above recursion is that we can choose any two adjacent points, then any non-intersecting set of (n-1) chords on rest 2n-2 points, will form set of n non-intersecting chords with a chord using these two point, hence on 2n points.
The above recursion can be solved to give T(n) = 2^(n-1) x n!
Repcarlaapepin, Area Sales Manager at Atmel
Hello, I am Carla and I live in San Bernardino, USA. I am working as a bookkeeper in a library ...
This will not work because in max-flow problem you could divide the flow from a job node to multiple worker nodes, but this is not allowed in the problem. You cannot have half the job running on one server and other half on other server.
- gimli August 05, 2014