marina.gupshpun
BAN USERi'd improve findHeight by
1.add
if(height[tree[i]] !=-1)
height[i]+=height[tree[i]];
2.remove
if (height[i] != -1)
return height[i];
O(n) time & O(n) space:
1. build max-heap
2.init count = 0 && n = max_int;
while count<n : delete max from the heap + update n by max value, update count.
^^add edge (t_sum, T)
- marina.gupshpun May 29, 2015Nice idea, but I think we need to
add T and t_sum nodes and edge (T,t_sum) with w(T,t_tag) = sum of all tasks needs
add edges( t_i, t_sum) with w(t_i, t_sum) = need of task i
add edges (S, s_j) with w(S, s_j) = capacity of server j
and add edges(t_i, s_j) if capacity of server j is >= need of task i
improved version with less calls:
void PrintRec(int base, int N)
{
printf("%d\n", base);
for (int i = 0; i < 10; i++)
{
int newBase = base * 10 + i;
if(newBase <= N)
PrintRec(newBase, N);
else
break;
}
}
void Print(int N)
{
for (int i = 1; i < 10; i++)
PrintRec(i, N);
}
Distance to A[i-1][j-1] or A[i+1][j+1] is at least distance to A[i][j] +2.
Directly we can calculate only distance to A[i-1][j] , A[i+1][j], A[i][j-1] , and A[i][j+1].
I'd run while...for each switch case.
- marina.gupshpun May 06, 2015#include <stdio.h>
#include <iostream>
#include <thread>
#include <mutex>
std::mutex evenMutex, oddMutex;
int nextEven = 0, nextOdd = 1;
int nMax = 100;
void printOdd()
{
while(nextOdd <= nMax && nextEven <= nMax)
{
oddMutex.lock();
std::cout << nextOdd << std::endl;
nextOdd +=2;
evenMutex.unlock();
}
}
void printEven()
{
while(nextOdd <= nMax && nextEven <= nMax)
{
evenMutex.lock();
std::cout << nextEven << std::endl;
nextEven +=2;
oddMutex.unlock();
}
}
int main()
{
evenMutex.unlock();
oddMutex.lock();
std::thread t1(printOdd);
std::thread t2(printEven);
t1.join();
t2.join();
std::cout << "Press Enter to continue ..." << std::endl;
std::cin.get();
return 0;
}
#include <stdio.h>
#include <iostream>
#include <thread>
#include <mutex>
std::mutex evenMutex, oddMutex;
int nextEven = 0, nextOdd = 1;
int nMax = 100;
void printOdd()
{
while(nextOdd <= nMax && nextEven <= nMax)
{
oddMutex.lock();
std::cout << nextOdd << std::endl;
nextOdd +=2;
evenMutex.unlock();
}
}
void printEven()
{
while(nextOdd <= nMax && nextEven <= nMax)
{
evenMutex.lock();
std::cout << nextEven << std::endl;
nextEven +=2;
oddMutex.unlock();
}
}
int main()
{
evenMutex.unlock();
oddMutex.lock();
std::thread t1(printOdd);
std::thread t2(printEven);
t1.join();
t2.join();
std::cout << "Press Enter to continue ..." << std::endl;
std::cin.get();
return 0;
}
#include <stdio.h>
#include <iostream>
#include <thread>
#include <mutex>
std::mutex evenMutex, oddMutex;
int nextEven = 0, nextOdd = 1;
int nMax = 100;
void printOdd()
{
while(nextOdd <= nMax && nextEven <= nMax)
{
oddMutex.lock();
std::cout << nextOdd << std::endl;
nextOdd +=2;
evenMutex.unlock();
}
}
void printEven()
{
while(nextOdd <= nMax && nextEven <= nMax)
{
evenMutex.lock();
std::cout << nextEven << std::endl;
nextEven +=2;
oddMutex.unlock();
}
}
int main()
{
evenMutex.unlock();
oddMutex.lock();
std::thread t1(printOdd);
std::thread t2(printEven);
t1.join();
t2.join();
std::cout << "Press Enter to continue ..." << std::endl;
std::cin.get();
return 0;
}
flag is unsafe shared resource...
- marina.gupshpun April 14, 2015
How about a variation of Prim algorithm:
- marina.gupshpun April 18, 20161.start with an arbitrary edge and add to ST. Let assume that it's black.
2
2.1. add to ST all red edges that cross a cut and respect the restriction (adjacent edges to edges that were added in the previous iteration)
2.2. add to ST all black edges that cross a new cut and respect the restriction
3.repeat until there is no edges that cross a new cut and respect the restriction