Sunil
BAN USERHere is my thinking process.
The open question here is, can any leaf node be a root node ? And the explanation below assumes that leaf node can be a root node.
Let's consider any non-leaf node. This node needs to have at-least one red edge and one black edge, so that path through this node will have alternate red and black edge. Also, it can not have more than one edge of the same color, as any path from that node which involves the edges of the same color will violate the condition.
So, with this what we are looking for is a path through the graph, which touches all the nodes of the graph. And it means that it has only 2 leaf nodes. And only these are the nodes which "may" have the edges of only one color in the original graph.
So following is the algorithm
1. Scan all the nodes, and check if it has edges of only one color.
2. If you get such a node, follow DFS, with alternating color edges, and since the answer is guaranteed to exist, it should result in the path.
3. If we do not find the node with edges of just one color, then choose a random node
4. Try to follow DFS with all the edges in the node.
5. If we do not get the required path, move on to next node. to step 4.
// SpanningTree.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#define NO_EDGE 0
#define RED 1
#define BLACK 2
#define V 5
int FindProbableLeafNode(int graph[V][V]) {
for(int i = 0; i < V; ++i ) {
int color = NO_EDGE;
int j;
for (j = 0; j<V; ++j) {
if(graph[i][j] == NO_EDGE) {
continue;
}
if(color == NO_EDGE) {
color = graph[i][j];
} else if(color != graph[i][j]){
break;
}
}
if(j == V) {
return i;
}
}
return -1;
}
bool checkNode(int newNode, int tree[V][V], int newColor, int currentColor) {
if(newColor == currentColor) {
return false;//New color and old color are same. return false
}
for(int i = 0; i< V; ++i) {
if(tree[newNode][i] != NO_EDGE) {
return false;//Node is already present in the tree;
}
}
return true;
}
bool spanningTreeComplete(int tree[V][V]) {
int i;
for(i =0; i<V; ++i) {
bool vertexPresent = false;
for( int j = 0; j<V; ++j) {
if(tree[i][j] != NO_EDGE) {
vertexPresent = true;
break;
}
}
if(!vertexPresent) {
break;
}
}
if(i<V) {
return false;
}
return true;
}
bool getSpanningTree(int graph[V][V], int tree[V][V], int startNode, int currentColor) {
for(int i = 0; i < V; ++i) {
if(graph[startNode][i] != NO_EDGE) {
if(checkNode(i, tree, graph[startNode][i], currentColor)){
tree[startNode][i] = graph[startNode][i];
tree[i][startNode] = graph[i][startNode];
if(spanningTreeComplete(tree)){
return true;
}
if(getSpanningTree(graph, tree, i, tree[startNode][i])) {
return true;
}
tree[startNode][i] = NO_EDGE;
tree[i][startNode] = NO_EDGE;
}
}
}
return false;
}
void initTree(int tree[V][V]) {
for(int v1 =0; v1 < V; ++v1) {
for(int v2 =0; v2 < V; ++v2) {
tree[v1][v2] = 0;
}
}
}
void printSpanningTree(int tree[V][V]) {
for(int i = 0; i<V;++i) {
for(int j=0;j<V;++j) {
printf("%d ", tree[i][j]);
}
printf("\n");
}
}
bool SpanningTree(int graph[V][V]) {
int val = FindProbableLeafNode(graph);
if(val == -1) {
int i;
//iterate through nodes to find the spanning tree
for(i = 0; i < V; ++i) {
int tree[V][V];
initTree(tree);
if(getSpanningTree(graph, tree, val, NO_EDGE)) {
printSpanningTree(tree);
break;
}
}
if(i == V) {
printf("No spanning tree possible");
}
} else {
int tree[V][V];
initTree(tree);
if(getSpanningTree(graph, tree, val, NO_EDGE)) {
printSpanningTree(tree);
} else {
printf("No spanning tree possible");
}
}
return true;
}
int _tmain(int argc, _TCHAR* argv[]) {
int graph[V][V] = {
{0,2,1,1,1},
{2,0,1,1,1},
{1,1,0,1,2},
{1,1,1,0,1},
{1,1,2,1,0}
};
SpanningTree(graph);
getchar();
return 0;
}
#include "stdafx.h"
#include <vector>
using namespace std;
int getMaxSlices(const vector<int> & pies, int numberOfPeople) {
int totalSlices = 0;
auto itr = pies.cbegin();
while(itr != pies.cend()) {
totalSlices += *itr;
++itr;
}
int maxSlices = totalSlices /numberOfPeople;
while(maxSlices > 0) {
auto itr = pies.cbegin();
int peopleWhoGotSlices = 0;
while(itr != pies.cend()) {
peopleWhoGotSlices += *itr / maxSlices;
++itr;
}
if(peopleWhoGotSlices >= numberOfPeople) {
return maxSlices;
}
--maxSlices;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> pies;
pies.push_back(8);
pies.push_back(10);
pies.push_back(12);
pies.push_back(14);
pies.push_back(16);
for(int i =1; i<=20;i++) {
int maxSlices = getMaxSlices(pies, i);
printf("%d\n", maxSlices);
}
getchar();
return 0;
}
// RangePaint.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
class Cost {
public:
Cost(int begin, int end, float cost) :_begin(begin), _end(end), _cost(cost) {
}
int getBegin() {
return _begin;
}
int getEnd() {
return _end;
}
float getCost() {
return _cost;
}
private:
int _begin;
int _end;
float _cost;
};
float findMinCost(int begin, int end, const std::vector<Cost *>& costs) {
float * cumulativeCost;
cumulativeCost = new float[end-begin];
for (int i = begin; i<end;i++) {
cumulativeCost[i] = -1;
}
std::vector<Cost *>::const_iterator itr = costs.cbegin();
while (itr != costs.cend())
{
float startCost = 0;
if((*itr)->getBegin() > begin){
if(cumulativeCost[(*itr)->getBegin() - begin] == -1) {
itr++;
continue;
}
startCost = cumulativeCost[(*itr)->getBegin() - begin];
}
for (int j = (*itr)->getBegin(); j <(*itr)->getEnd(); ++j) {
if( j - begin >= 0 && j < end && ( cumulativeCost[j - begin] == -1 || cumulativeCost[j - begin] > (startCost + (*itr)->getCost())) ) {
cumulativeCost[j - begin] = startCost + (*itr)->getCost();
}
}
++itr;
}
return cumulativeCost[end - begin - 1];
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<Cost *> costs;
costs.push_back(new Cost(0,5,10));
costs.push_back(new Cost(0,4,1));
costs.push_back(new Cost(0,2,5));
costs.push_back(new Cost(2,5,1));
//costs.push_back(new Cost(1,4,10));
//costs.push_back(new Cost(2,5,6));
float minCost = findMinCost(0, 5, costs);
printf("Min Cost = %f", minCost);
getchar();
return 0;
}
// travel.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <queue>
enum BitType{
eEmpty,
ePath,
eSensor,
eVisited,
eInvalid
};
class Sensor{
public:
Sensor(int x, int y, int radius) : _x(x), _y(y), _radius(radius) {
}
bool hitTest(int x, int y) {
int h = _x - x;
int v = _y - y;
if(v*v + h*h <= _radius* _radius){
return true;
}
return false;
}
private:
int _x, _y;
int _radius;
};
class Bitmap{
public :
Bitmap(int width, int height) : _width(width), _height(height) {
_buffer = new char [_width * _height];
if(_buffer != NULL) {
memset(_buffer, eEmpty, _width *_height);
}
}
void setBit(int x, int y, BitType bitType) {
if(_buffer == NULL || x<0||y<0 || x>=_width || y>=_height)
return;
_buffer [y * _width + x] = bitType;
}
BitType getBit(int x, int y) {
if(_buffer == NULL || x >= _width || x < 0|| y >= _height || y < 0) {
return eInvalid;
} else {
return (BitType)_buffer[y * _width + x];
}
}
void printBitmap() {
for(int y = 0; y < _height; ++y){
printf("|");
for (int x =0; x < _width; ++x) {
if(_buffer[x + y * _width] == eEmpty){
printf(" ");
} else if(_buffer[x + y * _width] == ePath) {
printf("-");
} else if(_buffer[x + y * _width] == eSensor) {
printf("S");
} else if(_buffer[x + y * _width] == eVisited) {
printf(" ");
}
}
printf("|\n");
}
}
int getWidth() {
return _width;
}
int getHeight() {
return _height;
}
private :
int _height;
int _width;
char * _buffer;
};
class Node {
public :
Node(int x, int y, Node * parent) : _x(x), _y(y), _parent(parent) {
}
int getX(){
return _x;
}
int getY() {
return _y;
}
Node * getParent() {
return _parent;
}
void addChild(Node * child) {
_childs.push_back(child);
}
void addChildsInQueue(std::queue<Node *> &queue) {
std::vector<Node *>::iterator itr = _childs.begin();
while(itr != _childs.end()){
queue.push(*itr);
++itr;
}
}
private:
int _x;
int _y;
Node * _parent;
std::vector<Node *> _childs;
};
class Terrain {
public:
Terrain(Bitmap *bitmap, std::vector<Sensor *> & sensors) :_bitmap(bitmap), _sensors(sensors) {
}
~Terrain(){
std::vector<Sensor *>::iterator itr = _sensors.begin();
while(itr != _sensors.end()) {
delete (*itr);
}
_sensors.erase(_sensors.begin(), _sensors.end());
delete _bitmap;
}
void traversePath() {
if(_bitmap == NULL) {
return;
}
for(int y = 0; y < _bitmap->getHeight(); ++y){
for (int x =0; x < _bitmap->getWidth(); ++x) {
std::vector<Sensor *>::iterator itr = _sensors.begin();
while(itr != _sensors.end()) {
if((*itr)->hitTest(x,y)) {
_bitmap->setBit(x,y, eSensor);
}
++itr;
}
}
}
std::queue<Node *> queue;
Node * root = new Node(-1,-1,NULL);
for(int y = 0; y < _bitmap->getHeight(); ++y) {
if(_bitmap->getBit(0, y) == eEmpty) {
Node * node = new Node(0,y,root);
_bitmap->setBit(0,y, eVisited);
queue.push(node);
root->addChild(node);
}
}
Node * destination = NULL;
while(!queue.empty()){
Node * node = queue.front();
if(_bitmap->getBit(node->getX() + 1, node->getY()) == eEmpty){
Node *child = new Node (node->getX() + 1, node->getY(), node);
_bitmap->setBit(node->getX() + 1, node->getY(), eVisited);
queue.push(child);
node->addChild(child);
if(node->getX() +1 == _bitmap->getWidth() -1) {
destination = child; //We reached the right side. So break
break;
}
}
if(_bitmap->getBit(node->getX(), node->getY() + 1) == eEmpty){
Node *child = new Node (node->getX(), node->getY() + 1, node);
_bitmap->setBit(node->getX(), node->getY() + 1, eVisited);
queue.push(child);
node->addChild(child);
}
if(_bitmap->getBit(node->getX(), node->getY() - 1) == eEmpty){
Node *child = new Node (node->getX(), node->getY() - 1, node);
_bitmap->setBit(node->getX(), node->getY() - 1, eVisited);
queue.push(child);
node->addChild(child);
}
queue.pop();
}
while(destination != NULL) {
_bitmap->setBit(destination->getX(), destination->getY(), ePath);
destination = destination->getParent();
}
while(!queue.empty()) {
queue.pop();
}
_bitmap->printBitmap();
//Delete the tree
queue.push(root);
while(!queue.empty()){
Node * node = queue.front();
node->addChildsInQueue(queue);
delete node;
queue.pop();
}
}
private:
Bitmap * _bitmap;
std::vector<Sensor *> _sensors;
};
int _tmain(int argc, _TCHAR* argv[])
{
Bitmap * bitmap = new Bitmap(20, 20);
std::vector<Sensor *> sensors;
sensors.push_back(new Sensor(4, 4, 4));
sensors.push_back(new Sensor(11, 11, 4));
sensors.push_back(new Sensor(15, 15, 4));
sensors.push_back(new Sensor(14, 5, 4));
Terrain terrain(bitmap, sensors);
terrain.traversePath();
getchar();
return 0;
}
// BigNumber.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
class BigNumber {
public :
BigNumber(const std::vector<char> & input);
void increment();
void print();
private:
std::vector<int> _digits;
};
BigNumber::BigNumber(const std::vector<char> &input){
std::vector<char>::const_iterator itr = input.cbegin();
while(itr != input.cend()){
_digits.push_back(*itr - '0');
++itr;
}
}
void BigNumber::increment(){
std::vector<int>::reverse_iterator itr = _digits.rbegin();
int carry = 0;
do{
if(itr == _digits.rend()) {
_digits.insert(_digits.begin(),1);
break;
}
(*itr)++;
if(*itr > 9){
*itr = 0;
carry = 1;
} else {
carry = 0;
}
++itr;
} while(carry);
}
void BigNumber::print(){
std::vector<int>::const_iterator itr = _digits.cbegin();
while(itr != _digits.cend()){
printf("%d", *itr);
++itr;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char input1[] = {'9','9','9','9','9','9','9','9','9','9','9','9','9','9','9','9','9','9'};
std::vector<char> input(&input1[0], &input1[0] + 18);
BigNumber bigNumber(input);
bigNumber.print();
printf("\n");
bigNumber.increment();
bigNumber.print();
getchar();
return 0;
}
// MaxPrefix.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
//#include <vector>
#include <queue>
using namespace std;
struct Comparator;
class Node {
public:
friend Comparator;
Node(int value, int initiaIndex);
bool operator < (const Node & rhs);
//private:
int _value;
int _initialIndex;
};
Node::Node(int value, int initiaIndex) : _value(value), _initialIndex(initiaIndex){
}
struct Comparator
{
bool operator()(Node * i, Node * j){
if(i->_value > j->_value){
return true;
} else if(i->_value == j->_value) {
return i->_initialIndex > j->_initialIndex;
}
return false;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
priority_queue<Node *, std::vector<Node *>, Comparator> minHeap;;
minHeap.push(new Node(-3,0));
minHeap.push(new Node(0,1));
minHeap.push(new Node(2,2));
minHeap.push(new Node(4,3));
minHeap.push(new Node(10,4));
minHeap.push(new Node(-4,5));
minHeap.push(new Node(6,6));
minHeap.push(new Node(2,7));
minHeap.push(new Node(8,8));
minHeap.push(new Node(9,9));
minHeap.push(new Node(4,10));
int maxPrefix = 0;
while(minHeap.size() > maxPrefix){
Node * node = minHeap.top();
minHeap.pop();
if(minHeap.size() - node->_initialIndex > maxPrefix){
maxPrefix = minHeap.size() - node->_initialIndex;
}
}
printf("%d", maxPrefix);
getchar();
return 0;
}
#include "stdafx.h"
#include <vector>
void shiftBits(unsigned long number, int shiftStartIndex, int shiftEndIndex) {
if(shiftStartIndex < 0){
return;
}
if (( (1 << shiftStartIndex) && number )== 0){
return;
}
for(int i = shiftStartIndex; i < shiftEndIndex - 1; ++i) {
unsigned long mask = ~(1 << i);
number = number & mask;
number = number | ( 1 << (i + 1) );
printf("%d ", number);
shiftBits(number, shiftStartIndex - 1, i + 1);
}
}
void insertBits(int bitCount){
unsigned long number = 0;
printf("%d ", number);
for(int i = 0; i< bitCount;++i) {
number = number | (1 << i);
printf("%d ", number);
shiftBits(number, i, bitCount);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int bits;
scanf_s("%d", &bits);
insertBits(bits);
getchar();
getchar();
return 0;
}
when n = 10, p = 6, then meeting point will be 12. Similarly, when n = 10 p = 6 meeting point will be 14, and so on.
- Sunil July 19, 2016So here is the formula.
meeting point = n + (p - n % p).