ENGLISH - why does this method not pass?

My submission https://www.codechef.com/viewsolution/28661698 for ENGLISH fails 6 out of the 20 cases, but I cannot see why. Can anyone advise?

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?

Consider example

  1. aaddaa
  2. aayyaa
  3. aaypyaa
  4. aazzaa

In this if we create that successive beauty array , it will be
[ 4,9,4,0]

So , if I understood your method , it will give answer as 9+0 = 9 .

So , here it is considering only pair (2,3)

But maximum answer will be 13 as (1,4),(2,3) which is 4+9 = 13

Do tell me if I understood your method wrong or anything is wrong with this example.

1 Like

Can anyone please tell what’s wrong with for this submission also?

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 https://www.codechef.com/viewsolution/28966892 please.

This method actually works and it won’t give TLE

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)))

Hi @kapil255075

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
1
281
osjxapwnyzerinsugboiipgaeyzaq
osjxapwnyzerinsugboiipgaeyzaqumibiakv
osjxapwnyzerinsugb
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaoh
o
osjxapwnyzerinsugboiipgaeyzaqu
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowa
osjxapwnyzerinsugboiipgaey
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxs
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsa
osjxapwny
osjxapwnyzerinsugboiipgaeyzaqumibi
osjxapwnyzerinsu
osjxapwnyzerinsugboiipgaeyz
osjxapwnyzerinsugboiipgaeyzaqumibiak
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhq
osjxapwnyzeri
osjx
osjxapwnyzerinsugboiipgaeyzaq
osjxapwnyzerinsug
osjxapwnyzerinsug
osjxapwnyzerinsugboiipgaeyzaqu
osjxapwnyzer
os
osjxapwny
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohx
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsa
o
osjxapwnyzerinsugboiipgaeyzaqumib
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapwnyzerinsugboiipga
osjxapwnyzerinsug
osjx
osjxapwnyzerinsugb
o
osjxapwnyzerinsugboii
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxow
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaoh
osjxapwnyzerins
osjxapwnyzerinsugboiipgaeyzaqumib
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohx
osjxapwnyzerinsugboiipgaeyzaq
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxow
o
osjxapwnyzerinsugboiipgaeyzaq
osjxapwnyzerins
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowao
osjxapwnyzerinsugboiipgaeyzaqumibiakv
o
osjxapwnyzerinsugboiipgaeyzaqumibiak
osjxapwnyzerin
osjxapwnyzerinsugboiipg
osjxapwnyzerinsug
osjxapwnyzer
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohx
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowa
osjxapwnyzerinsugboiipga
osjxapwnyzerinsugboiipgaeyzaqumibiak
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsa
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowao
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapwnyzerinsug
osjxapwnyzerinsugboiipgaeyzaqumibiak
osjxapwnyzerinsugboiipgaeyzaqumibi
osjxapwny
osjxapwnyzerinsugboiipgaeyzaqum
osjxapwnyzerinsugboiipgae
osjx
osjxapwnyzerinsugboiipgaeyzaqumib
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapwnyzerinsugboiipgaeyzaqumibi
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxo
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxow
osjxapwn
osjxapwnyzerinsugboiipgaeyz
o
osjxapwnyzerinsu
osjxapwnyzerinsugboiipgae
osjxapwnyzerinsug
osjxa
osjxapwnyzerinsugboii
osjxapwnyzerinsugboiipgaeyzaqumibia
osjxapwnyzerinsugboiipgaeyzaq
osjxapwnyzerinsugboiipgaeyzaqumi
osjxapwnyzerinsugboiipgaeyzaqumibia
osjxapwnyzerinsugboiipgaeyzaqumibiakvx
osjxapwnyzerinsugboiipgaeyzaq
osjxapwnyzerinsugboiipga
osjxapwnyzerinsu
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsas
osjxapwnyzerinsugboiipgaeyzaqumibiakvx
osjxapwnyzerinsugboiipgaeyzaqu
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsa
osjxapwnyzerinsugboi
osjxapwny
osjxapwnyzerinsugboii
osjxapwnyzerinsugboiipg
osjxapwn
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxo
osjxapwnyzerinsugboiipgaeyzaqumi
osjxapwnyzerinsugboiipgaeyzaq
osjxapwnyzerinsugb
osjxapwnyzerinsugboi
osjxapwn
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhq
osjxa
osjxapwnyzerinsugboiipgae
osjxapwn
osjxapwnyzerinsugboiipgaeyza
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxo
osjxapwnyzerinsugboiipgaeyzaqumibiakv
osjxapwnyzerinsugboiipgaeyzaqum
osjxapw
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxo
osjxapw
osjxap
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqx
osjxapwnyzerinsugboiipg
osjxapwnyzeri
osjxapwnyze
osjx
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowao
osjxapwnyzerinsugb
osjxapwnyzerinsug
osjxapwnyzerinsugboiipgae
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxo
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxow
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohx
osjxapwnyzerinsugboi
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhq
osjxapwnyzerinsugboiipg
osjxapwnyzerinsu
osjxapwnyzerin
osjxapwnyzerinsugboiipgae
osjxapwnyz
osjxapw
osjxapwnyzerinsug
osjxapwnyzerinsugboiipg
osjxapwnyzerinsugboiipgaeyzaqumibiak
osjxapwnyzerinsugboiipgaeyza
osjxapwnyze
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowao
osjxapwnyzerinsugboiipga
osjxapwnyzerinsugboiipgaeyzaqumibiakv
osjxapwnyzerinsug
osjxapwnyzerinsugb
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsas
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxs
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapwnyzerinsugboiipgaeyzaqu
osjxapw
osjxapwnyz
osj
osjxapwnyzerinsugb
osjxapwnyzerinsugboiipgaey
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapwnyzerinsugboiipgaeyza
osjxapwnyzerinsugboiipgaey
osjxapwnyzerinsugboiip
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxow
osjxapwnyzerinsugboiip
osjxapwnyzerinsugb
osjx
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapw
osjxapwnyze
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxs
osjxapwnyzerinsugboiipga
osjxapwny
osjxapwnyze
osjxapwnyzerinsugboii
osjxapwnyzerinsugboi
osjxapwnyzerinsugboiipg
osjxapwn
os
osjxapwnyzerinsugboiipgaeyzaqumibiakv
osjxapwnyzerinsugboiipgaeyza
osjxapwnyzerinsugboiipgaeyzaqu
osjxapwnyzerinsugboiipgaeyzaqumibiak
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxow
osjxapwnyzerinsugboiipgae
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapwnyzerinsugboiipg
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsas
osjxapwnyzerinsugboiipgaeyzaqumibi
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaoh
o
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohx
osjxapwnyzerinsugboii
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowa
osjxapwnyze
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhq
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxs
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowao
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowao
osjxapwnyzerinsugb
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsas
osjxapwnyzerinsugbo
osjxapwnyz
osjx
osjxapwnyze
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqx
os
osjxapwnyzerinsugboiipgaeyzaqumibi
osjxapwnyzerinsugboiipg
osjxapwnyzerinsugboiipgaeyzaqumibi
osjxapwnyzer
osjxapwnyzerinsugboiipgaeyzaqumibi
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqx
osjxapwnyzerinsu
osjxapwnyzerinsugboiipgaeyzaqumi
osjxapwnyzerinsugboiipgaeyz
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaoh
osjxapwnyzerinsu
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqx
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhq
osjxa
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxo
osj
osjxapwnyzerinsugboiipgaeyza
osjxapwnyzerinsugbo
osjxa
osjxapwnyzerinsugboiipgaeyzaqum
osjxapwnyze
osjxapwnyz
osjxapwn
osjxapwnyzerinsugboii
osjxapwnyzerinsu
osjxapwnyzerinsugboiipg
osjxapwnyzerins
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowao
osjxapwnyzeri
osjxapwnyzerinsugboiipg
osjxapwnyzerinsugb
osjxapwnyzerin
osjxapwnyzerinsugbo
osjxapwny
osjxapwnyzerinsugboiipgaeyzaq
osjxapwnyzerinsugboiipgaeyzaqum
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxow
osjxapwnyzerinsugboiipgaeyzaqumi
osjxapwnyzerinsugboiipgaeyzaqumibiakvxh
osjxapwnyzerinsugboiipgae
osjxapwnyzer
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsas
osjxapwnyzerinsugb
osjx
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsas
osjxapwnyzerinsugboii
osjxapwnyzerinsu
osjxapwnyzerinsugboiipgaeyza
osjxapwnyzerinsugb
osjxapwnyzerinsugbo
osjxapwnyzer
osjxapwnyzerinsu
osjxapwnyzerinsugboiipgaeyzaqumibiak
osjxapwnyzerinsugboii
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowa
osjxapwnyzerinsugboiip
osjxapwnyzerinsugboiipg
osjxapwnyzerinsugboiipgaeyzaqumi
osjxapwnyzerinsugboiipga
osjxapwnyz
osjxapwnyzerinsugboiipgaeyzaq
osjxapwnyzerinsugboiipgaeyzaqumibiakv
osjxapwnyzerinsugbo
osjxa
o
osjxapwnyzerinsugboiipgaeyzaq
osjxap
osjxapwnyzerinsugboiipgaeyzaqumibiak
osjxapwnyzer
osjxapwnyzerinsugboiipgaeyzaqumibiakv
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowa
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxo
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowaohxsa
osjxapwny
osjxapwnyzerinsugboiipgaeyza
osjxapwnyzerinsugboiipgaeyzaqumibiakvxhqxowao
Here are the responses
correct response: 108890
incorrect response: 108891

Hope this was helpful. :slight_smile:

Thanks a lot @raisinten.

Even I had done this testing and found the answers deflected by 1 always.

Still couldn’t figure out.

P.S. Got partial as well without using a trie.

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

1 Like

Thank you, this explains perfectly why my method is wrong.

My last reply is to thank vitz_6 for his explanation