Since I am very new to “algorithm” world and neither have enough knowledge nor IQ to solve harder questions, I am trying to solve TopCoder DIV II – Level I questions. They are usually very easy to solve. They do not need any special algorithm knowledge, basic coding approach does work.
I will try to explain some of the questions that i solved. I start with the TimeTravellingCellar problem. You can find the problem statement here.
Well if you look at the constraints, you realize that you can solve problem by brute force approah. However i came up with a different and a better solution.
It is clear that in order to find the answer, we need to find to find the max profit and the min decay. By using this simple realization, we can solve the problem in O(N) time. Implementation is even easier than the realization, as it only involves finding maximum and minimum. The only trick is that you cannot time travel in the same cellar, meaning if the cellar with the highest profit contains the lowest decay, you should ignore the cellar with the highest profit while finding the lowest decay profit.
I have implemented my solution in C++.
int max(vector<int> profit)
{
int place=0;
int maxi = 0;
for(int i = 0; i<profit.size();i++)
{
if(profit[i] > maxi)
{
maxi = profit[i];
place = i;
}
}
return place;
}The above function simply returns the index of the max element. It is easy to calculate that this code runs in O(N) time.
int min(vector<int> profit,int aa)
{
int place=aa;
int maxi = 10001;
for(int i = 0; i<profit.size();i++)
{
if(profit[i] < maxi)
{
if(i != aa)
{
maxi = profit[i];
place = i;
}
}
}
return place;
}Well this is the same as findMax function. The only trick is that I pass the index of max profit element in order to ignore it while finding the lowest decay element. Nothing special.
And in the actual function, I simply substract the lowest decay from the highest profit value. The code as a whole looks like this:
#include <vector>
#include <set>
using namespace std;
class TimeTravellingCellar
{
public:
int max(vector<int> profit)
{
int place=0;
int maxi = 0;
for(int i = 0; i<profit.size();i++)
{
if(profit[i] > maxi)
{
maxi = profit[i];
place = i;
}
}
return place;
}
int min(vector<int> profit,int aa)
{
int place=aa;
int maxi = 10001;
for(int i = 0; i<profit.size();i++)
{
if(profit[i] < maxi)
{
if(i != aa)
{
maxi = profit[i];
place = i;
}
}
}
return place;
}
int determineProfit(vector<int> profit, vector<int> decay)
{
int maxi = max(profit);
int mini = min(decay,maxi);
return profit[maxi] - decay[mini];
}
};After submitting the solution, I have found a bug in my program. Consider the situation: profit = { 888, 889, 100 }, decay = { 100, 1, 97 }. Let’s simulate what my program will do: It will find position of max element which is 889, then it will find position of min element. However, while finding the min element, it will return 97 due to ignoring second cellar. Finally it will return the answer as 889 – 97. However, this is not the best situation. The best profit we can get is 888 – 1. This situation happens when the lowest decay and highest profit is at the same cellar. This bug can be easily solved by a if statement, so I will not correct it now.
As you see, even the easiest problems can contain painful corner cases. If you find a bug in my solution, feel free to inform me.
PS: Sorry for the bad indentation. WP and Copy-Paste are responsible for this!
