Problem Statement
Fox Ciel is going to walk through an unpaved road to meet her friend. The road is one-dimensional. It is separated into N parts numbered from 0 to N-1, where part 0 is Ciel's current part and part N-1 is her destination part.
Ciel will perform her trip tomorrow. Unfortunately today it is raining, so tomorrow some parts of the road will be muddy. You are given a vector <int> road containing N elements. The probability that the i-th part of the road will be muddy tomorrow is road[i]/100.
Ciel can walk along the road using any combination of strides with lengths 1 and 2. If she is at part i, a stride of length 1 will move her to part i+1 and a stride of length 2 will move her to part i+2 (skipping part i+1). If there are many ways to reach part N-1 from part 0, Ciel will choose the one among them where the number of visited muddy parts is minimal.
Return the expected number of muddy parts that she will visit tomorrow.
Definition
Class:
MuddyRoad
Method:
getExpectedValue
Parameters:
vector <int>
Returns:
double
Method signature:
double getExpectedValue(vector <int> road)
(be sure your method is public)
Notes
-
Assume that events "i-th part of the road will be muddy tomorrow" are totally independent.
-
Ciel has very good sight, so when starting her trip at part 0, she is already able to see for each part whether it is muddy or not.
Constraints
-
road will contain between 2 and 50 elements, inclusive.
-
Each element of road will be between 0 and 100, inclusive.
-
The first element and the last element of road will be 0.
Examples
0)
{0, 60, 60, 0}
Returns: 0.36
There can be four different states of the road tomorrow:
.... with probability = 0.16, 0 steps to muddy parts
.M.. with probability = 0.24, 0 steps to muddy parts
..M. with probability = 0.24, 0 steps to muddy parts
.MM. with probability = 0.36, 1 step to muddy parts
(Here, '.' represents a non-muddy part and 'M' represents a muddy part.)
Thus, the expected number of steps is 0*0.16+0*0.24+0*0.24+1*0.36=0.36.
1)
{0, 50, 50, 50, 50, 0}
Returns: 0.5625
2)
{0, 0, 100, 100, 100, 100, 100, 100, 0, 0, 100, 0}
Returns: 3.0
3)
{0, 12, 34, 56, 78, 91, 23, 45, 67, 89, 0}
Returns: 1.7352539420031923
4)
{0, 50, 50, 100, 50, 100, 50, 50, 100, 66, 0}
Returns: 2.288125
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Ironically this 500 problem took me less time than 250 problem. However, my score is too low!
#include <vector>
using namespace std;
class MuddyRoad
{
public:
double getExpectedValue(vector<int> road)
{
double result = 0.0;
vector<bool> roadState;
initRoadState(road.size(), roadState);
do
{
double probability = calculateRoadStateProbability(road, roadState);
int step = calculateMuddyStep(roadState);
result += (double)step * probability;
}
while (generateRoadState(roadState));
return result;
}
private:
void initRoadState(int size, vector<bool>& roadState)
{
for (int i = 0; i < size; i ++)
{
roadState.push_back(false);
}
}
bool generateRoadState(vector<bool>& roadState)
{
int i;
for (i = 1; i < roadState.size() - 1; i ++)
{
if (!roadState[i])
{
roadState[i] = true;
return true;
}
else
{
roadState[i] = false;
}
}
return false;
}
double calculateRoadStateProbability(const vector<int>& road, const vector<bool>& roadState)
{
int i;
double result = 1.0;
for (i = 1; i < road.size() - 1; i ++)
{
if ((road[i] == 0 && roadState[i]) || (road[i] == 100 && !roadState[i]))
{
return 0.0;
}
if (roadState[i])
{
result *= (double)road[i]/100.0;
}
else
{
result *= (double)(100 - road[i])/100.0;
}
}
return result;
}
int calculateMuddyStep(const vector<bool>& roadState)
{
int pos = 0;
int counter = 0;
while (pos < roadState.size() - 2)
{
if (roadState[pos + 1] && roadState[pos + 2])
{
// no choice! muddy!
counter ++;
pos += 2;
}
else
{
if (!roadState[pos + 2])
{
pos += 2;
}
else
{
pos += 1;
}
}
}
return counter;
}
};
/************************************************************************************************************************
The following is just a simple demo of "dynamic programming"-- a improvement of common recursion.
The story is very simple. In "starcraft" or "warcraft", you have "workers" which collect foods and which also
consumes when you recruit more of them because the more workers, the more food they collect.
Now, you are given n workers at beginning with "price" food to consume if you recruit one worker and your
goal is to collect "neededFood", the question is how much round you can finish, assuming each round
one worker bring in one food.
***********************************************************************************************************************/
#include <string>
#include <iostream>
#include <map>
using namespace std;
struct Worker
{
int worker;
int food;
};
struct WorkerComp
{
bool operator()(const Worker& left, const Worker& right) const
{
if (left.food < right.food)
{
return true;
}
if (left.food > right.food)
{
return false;
}
return left.worker < right.worker;
}
};
typedef map<Worker, int, WorkerComp> WorkerMap;
class FoodCollecting
{
private:
WorkerMap workerMap;
int doGather(long long neededFood, long long currentFood, int n, int price)
{
if (currentFood >= neededFood)
{
return 0;
}
int ret = 1000;
for (int i = 0; i*price <= currentFood; i ++)
{
int nextFood= currentFood-i*price+n+i, nextWorker= n+i;
Worker worker;
worker.worker = nextWorker;
worker.food = nextFood;
WorkerMap::iterator it = workerMap.find(worker);
int temp;
if (it != workerMap.end())
{
temp = it->second;
}
else
{
temp = 1 + doGather(neededFood, nextFood, nextWorker, price);
workerMap[worker] = temp;
}
if (temp < ret)
{
ret = temp;
}
}
return ret;
}
public:
int gather(long long neededFood, int n, int price)
{
return doGather(neededFood, 0, n, price);
}
};
