First I store each each word spliced with its reverse, for example ‘card’ is stored as ‘cdarradc’. Then I sort these alphabetically, so that the most beautiful combinations will be those of adjacent words.
Then I create an array of beauties, by comparing the first characters of each word with that after. The beauty is (floor ( (number of characters the same) / 2) ) squared. A dummy value of zero is added to the end.
As each word may be used only once, adjacent beauties in the array cannot be used. I loop through the beauties choosing the best combinations. For example, if successive beauties are 1 25 36 25 9 0 then 25 + 25 is chosen because it is larger than 1 + 36 + 9.
Does anyone have any idea why this algorithm fails?
I thought of doing the same first. The only difference being when I calculate the successive beauties, I insert those in a max heap with the pair of their indices.
Keep popping elements off the heap and if the pair of popped element is (2,3), remove the pair (1,2) and (3,4) plus add another beauty pair (1,4).
Since I wasn’t sure if it would’ve given TLE (insertion and deletion takes O(log N) plus calculating new beauty pair may take O(|S|)), so I just built a trie and ran a dfs at the max possible depths.
Can somebody please help me in finding out what is wrong in my submission for english it is not passing testcases 1 and 6 link for code is CodeChef: Practical coding for everyone please.
Yes , insertion and deletion will add extra O(logN) but calculating new beauty can be done as
Beauty ((1,4)) = min( Beauty((1,2)),Beauty((2,3)),Beauty((3,4)))
I’ve incorporated a random testcase generator into my program which compares your program’s response with mine. It stops only when there is a mismatch and prints both the correct and incorrect responses.
Here's the code
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define what_is(x) cout << #x << " is: " << x << endl;
#endif
#ifdef _WIN32
#define gc getchar
#else
#define gc getchar_unlocked
#endif
template<class T>
T read()
{
T data;
cin >> data;
return data;
}
///////////////////////////////////////////////////////////
// NOT MINE BEGIN
bool comperator(pair<long long int, vector<int> > a , pair<long long int, vector<int> > b)
{
return a.first>b.first;
}
// NOT MINE END
class Solver
{
// NOT MINE BEGIN
int greatest_beauty_2(const vector<string>& words)
{
int n = words.size();
const vector<string>& a = words;
map<pair<int,long long int> , vector<int>> mp;
hash<string> gethash;
for(int i=0;i<n;i++)
{
string pre,suf,tmp;
pre = a[i][0];
suf = a[i][a[i].size()-1];
tmp = pre+'$'+suf;
long long int has = gethash(tmp);
mp[{pre.size(),has}].push_back(i);
for(int j=1;j<a[i].size();j++)
{
pre += a[i][j];
suf += a[i][a[i].size()-1-j];
tmp = pre + '$' + suf;
has = gethash(tmp);
mp[{pre.size(),has}].push_back(i);
}
}
vector < pair<long long int , vector<int>> > vec;
for(auto i:mp)
{
long long int tmp = i.first.first;
tmp = tmp*1ll*tmp;
vec.push_back({tmp,i.second});
}
sort(vec.begin(),vec.end(), comperator);
bool flag[n+5];
for(int i=0;i<n+5;i++)
flag[i] = false;
long long int ans = 0;
for(int i=0;i<vec.size();i++)
{
vector<int> v1;
for(int j=0;j<vec[i].second.size();j++)
{
if(!flag[vec[i].second[j]])
v1.push_back(vec[i].second[j]);
}
int ln = v1.size()/2;
ans += vec[i].first*1ll*ln;
for(int j=0;j<2*ln;j++)
flag[vec[i].second[j]] = true;
}
return ans;
}
// NOT MINE END
vector<pair<vector<string>, uint64_t> > test_cases;
uint64_t beauty;
// combines 2 characters into an int by appending
// one character to the other and filling the rest with 0
static int combine(const char& char_1, const char& char_2)
{
return ((char_1) | (char_2 << 8));
}
int greatest_beauty(const int& id, const vector<string>& words)
{
// Initially, we're gonna group the words
// into equivalence classes under the relation:
// first id_th and last id_th character of the
// words are equal
// we're gonna store the number of words that are
// too small for id in variable `extra`
unordered_map<int, vector<string> > groups;
int extra = 0;
// adding words to map
for(const auto& word : words)
{
const auto word_size = word.size();
if(id < word_size)
{
// inserting word
groups
[
combine
(
word[id],
word[word_size - id - 1]
)
]
.emplace_back(word);
}
else
{
// word is too small to fit :(
++extra;
}
}
// After the groups are formed we're gonna assume
// that `greatest_beauty` returns the number of extra
// words that couldn't be paired in each group and
// accumulate the return values in extra.
// Also, if a group contains only 1 element, we add that
// to extra.
// feedforward
for(const auto& group : groups)
{
if(group.second.size() > 1)
{
extra += greatest_beauty(1 + id, group.second);
}
else
{
extra += group.second.size();
}
}
// Now we have the quantity of words that couln't be
// paired up. If you look closely, you'll infer that
// all these extra words have one thing in common:
// the longest common prefix/suffix in all these words
// are `id` in length(coz that's how we grouped them)!
// Now, we find the maximum number of pairs we can form
// using these words, i.e., floor(extra / 2). We can now
// add the contribution of these pairs to `beauty` and
// return number of remaining unpaired words.
// backpropagation
const auto num_pairs = extra >> 1;
beauty += (uint64_t) num_pairs * id * id;
const auto remaining = extra - (num_pairs << 1);
return remaining;
}
public:
void ingest()
{
test_cases.resize(read<int>());
for(auto& test_case : test_cases)
{
auto& words = test_case.first;
words.resize(read<int>());
for(auto& word : words)
{
word = read<string>();
}
}
}
void solve()
{
for(auto& test_case : test_cases)
{
beauty = 0;
greatest_beauty(0, test_case.first);
test_case.second = beauty;
}
}
void solve_incorrect()
{
for(auto& test_case : test_cases)
{
test_case.second = greatest_beauty_2(test_case.first);
}
}
bool check(const vector<string>& words)
{
beauty = 0;
greatest_beauty(0, words);
const auto& mine = beauty;
const auto& not_mine = greatest_beauty_2(words);
if(mine != not_mine)
{
spit(words, mine, not_mine);
return false;
}
return true;
}
void spit() const
{
for(const auto& test_case : test_cases)
{
cout << test_case.second << "\n";
}
}
void spit(const vector<string>& words, const int& mine, const int& not_mine) const
{
cout << "1\n"; // for number of test cases
cout << words.size() << "\n";
for(const auto& word : words)
{
cout << word << "\n";
}
// Comment this if you don't want the responses
cout << "\n";
cout << "correct response: " << mine << "\n";
cout << "incorrect response: " << not_mine << "\n";
}
};
class random_test_case_generator
{
vector<string> random_strings;
string plz_mek_random_string_of_size(const int& SOME_SIZE)
{
const string VALID_CHARS = "abcdefghijklmnopqrstuvwxyz";
random_device rd; // obtain a random number from hardware
mt19937 eng(rd()); // seed the generator
uniform_int_distribution<int> distribution(0, VALID_CHARS.size() - 1);
ostringstream oss;
for (size_t i = 0; i < SOME_SIZE; ++i)
{
oss << VALID_CHARS[distribution(eng)];
}
string your_random_string = oss.str();
return your_random_string;
}
public:
random_test_case_generator()
{
random_device rd; // obtain a random number from hardware
mt19937 eng(rd()); // seed the generator
uniform_int_distribution<> distribution(1, 500); // define the range
const auto& number_of_strings = distribution(eng);
random_strings.resize(number_of_strings);
}
vector<string> now_give()
{
// reference: https://stackoverflow.com/questions/7560114/random-number-c-in-some-range
random_device rd; // obtain a random number from hardware
mt19937 eng(rd()); // seed the generator
uniform_int_distribution<> distr(1, 50); // define the range
for(auto& random_string : random_strings)
{
const auto SOME_SIZE = distr(eng);
random_string = plz_mek_random_string_of_size(SOME_SIZE);
}
return random_strings;
}
};
int main()
{
ios_base::sync_with_stdio(false);
// Uncomment this for the correct response my program produces
// Solver english;
// english.ingest();
// english.solve();
// english.spit();
// Uncomment this for the incorrect response your program produces
// Solver english;
// english.ingest();
// english.solve_incorrect();
// english.spit();
// Uncomment this for generating another testcase
// (don't forget to tune the lower and upper bounds
// @ lines 291 and 304)
// Solver english;
// for(;;)
// {
// random_test_case_generator generator;
// const auto& words = generator.now_give();
// if(not english.check(words))
// {
// break;
// }
// }
return 0;
}
Here's a random testcase for which a mismatch occurs
I used the same approach, solution was accepted.
I calculated the beauties in the same way (considering adjacent elements in sorted array of spliced strings), and then pushed all those values into a priority queue (stored the beauty along with the indices (in the beauty array) of the strings which produced that beauty). After popping a value from the heap and adding its beauty to the result, we also need to push the first un-chosen element to the left and the first un-chosen element to the right of the pair which we just used.
For example, if the beauty array is [9, 25, 25, 9], after choosing 25 + 25 (whose indices are 1 and 2 in the beauty array), you’d also need to consider choosing indices 0 and 3, which would not have been considered previously as we’d only considered adjacent elements.
For finding the first un-chosen left element and the first un-chosen right element in the beauty array, I used an algorithm similar to the findset(x) routine in DSU. My solution
