Dr.Milota
BAN USERHere is a dp solution and a brute force solution. You can improve the DP solution by talking out the total array and reducing the other matrices to a pair of vectors that you swap on every cycle.
#include <iostream>
#include <vector>
using namespace std;
#include <stdint.h>
int count(char *s)
{
int c = 0;
int state = 0;
int i = 0;
while(s[i] != 0)
{
switch (state)
{
case 0: // last letter was con
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
{
state = 1;
}
break;
case 1: // last was vowle
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
{
if (s[i - 1] == s[i])
{
c++;
state = 2;
}
}
else
{
state = 0;
}
break;
case 2: // in a sequence
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
{
if (s[i - 1] != s[i])
{
state = 1;
}
}
else
{
state = 0;
}
break;
}
i++;
}
return c;
} //----------------------------------------------------------------------------------------------------------------
int test_all_string_r(int n, int k, char *s, int l)
{
if (l == n)
{
//cout << s;
int x = count(s);
if (x == k)
{
//cout << " *\n";
return 1;
}
else
{
//cout << "\n";
return 0;
}
}
int sum = 0;
for (char c = 'A'; c <= 'Z'; c++)
{
s[l] = c;
sum = sum + test_all_string_r(n, k, s, l + 1);
}
return sum;
}//----------------------------------------------------------------------------------------------------------------
int test_all_string(int n, int k)
{
char *s = new char[n + 1];
s[n] = 0;
int out = test_all_string_r(n, k, s, 0);
delete[] s;
return out;
}//----------------------------------------------------------------------------------------------------------------
void dump(const vector<vector<uint64_t>> &in)
{
for (int y = 0; y < in[0].size(); y++)
{
for (int x = 0; x < in.size(); x++)
{
cout << in[x][y] << " ";
}
cout << "\n";
}
}
uint64_t dp_cont_2(int n, int k) // n > 1 and k > 0
{
vector<vector<uint64_t>> end_consonant(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> end_vowel_set(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> end_single_vowel(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> total(n + 1, vector<uint64_t>(k + 1, 0));
end_consonant[1][0] = 26 - 5; // any of the consonants
end_single_vowel[1][0] = 5; // any of the vowels
total[1][0] = 26;
for (int ni = 2; ni <= n; ni++)
{
for (int ki = 0; ki <= k; ki++)
{
end_consonant[ni][ki] = total[ni - 1][ki] * (26 - 5); // ways of doing it with one less letter and then we add a new consonant at the end
uint64_t ec = end_consonant[ni][ki];
end_single_vowel[ni][ki] = end_single_vowel[ni - 1][ki] * 4 + // add a different vowel
end_vowel_set[ni - 1][ki] * 4 + // add a different vowel
end_consonant[ni - 1][ki] * 5; // add any vowel
uint64_t esv = end_single_vowel[ni][ki];
if (ki > 0)
{
uint64_t d = end_single_vowel[ni - 1][ki - 1];
end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki] + d;
}
else
{
end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki];
}
end_vowel_set[ni][ki] = ((ki > 0) ? end_single_vowel[ni - 1][ki - 1] : 0) + // k went up so we need to have i-1
end_vowel_set[ni - 1][ki]; // add a vowel after eithe a uneque v and a set of vs
uint64_t evs = end_vowel_set[ni][ki];
total[ni][ki] = end_consonant[ni][ki] + end_vowel_set[ni][ki] + end_single_vowel[ni][ki]; // total ways with one less letter
uint64_t t = total[ni][ki];
}
}
cout << "--------end_consonant---------------------------------------\n";
dump(end_consonant);
cout << "--------end_vowel_set---------------------------------------\n";
dump(end_vowel_set);
cout << "--------end_single_vowel---------------------------------------\n";
dump(end_single_vowel);
cout << "--------total---------------------------------------\n";
dump(total);
cout << "-----------------------------------------------\n";
return total[n][k];
}
int _tmain(int argc, _TCHAR* argv[])
{
cout << "(1, 0) " << test_all_string(1, 0) << '\n';
cout << "(1, 1) " << test_all_string(1, 1) << '\n';
cout << "(2, 0) " << test_all_string(2, 0) << '\n';
cout << "(2, 1) " << test_all_string(2, 1) << '\n';
cout << "(3, 1) " << test_all_string(3, 1) << '\n';
cout << "(4, 2) " << test_all_string(4, 2) << '\n';
cout << "(5, 2) " << test_all_string(5, 2) << '\n';
cout << dp_cont_2(5, 2);
return 0;
}
If you are allowed to change the string you are given you can sort it and then looking for duplicates can be done in O(n); so the total is O(nlog(n)) for the sort;
If you cannot do that you must search the whole string for each letter you run across. Of course you can double the speed by only looking forward from where you are.
this will cost you O(n^2)
for(int i =0; i < len-1; i++)
{
for(int j = i+1; j < len; j++)
{
if(input[i] == input[j]) return false;
}
}
return true;
#include "stdafx.h"
#include <math.h>
#include <iostream>
using namespace std;
#define STEPS 4
#define BUDGET 7
int _tmain(int argc, _TCHAR* argv[])
{
float p[STEPS + 1][BUDGET + 1]; // Probability that it worked on a particular step with a particular budget
int used[STEPS][BUDGET]; // machines used
float r[STEPS] = { .99f, .8f, .9f, .4f }; // Probability that a step works
int c[STEPS] = { 2, 2, 5, 2 }; // cost of a machine
int i, s;
for (s = 0; s <= BUDGET; s++) // for all amounts you spend
{
p[0][s] = 1.0f; // if you have not run any steps the prob is 1
}
for (i = 1; i <= STEPS; i++) // init the 0 spent colum
{
p[i][0] = p[i - 1][0] * r[i - 1];
}
for (i = 1; i <= STEPS; i++)
{
for (s = 1; s <= BUDGET; s++)
{
int nm = s / c[i - 1]; // number of extra machines we could get
float best = 0;
used[i - 1][s - 1] = 0;
for (int mi = 0; mi <= nm; mi++)
{
float sp = 1.0f - powf((1.0f - r[i - 1]), mi + 1); // step probability
int leftover = s - mi * c[i - 1];
float total_prob = p[i - 1][leftover] * sp; // probability so far
if (best < total_prob)
{
best = total_prob;
used[i - 1][s - 1] = mi; // set number of machines used at this stage
}
}
p[i][s] = best;
cout << used[i - 1][s - 1] << " " << best << endl;
}
cout << i << "---------------------------------------------------------------------" << endl;
}
int out[STEPS];
int left = BUDGET - 1; // need an offset becas used array index starts at 0
for (i = STEPS-1; i >= 0; i--) // get the result in reverse order
{
out[i] = used[i][left]; // save number of machines
int cost = used[i][left] * c[i]; //How much did they cost
left = left - cost; //how much do you have left
}
// Print the number of extra machines best employed for each step in the correct order
for (i = 0; i < STEPS; i++)
{
cout << out[i] << " ";
}
}
Here is a slightly improved version without cutoffs hopefully
- Dr.Milota October 26, 2017