I am not going to do a full review; I just happened to stumble across this while passing by. I will merely give a very, very brief overview, and some guidance that might help.
As you’ve noticed, “tricks” like de-syncing IOstreams and using optimization pragmas, while they do help, don’t really make that big a difference (usually). Whenever you really want performance improvements, there are no shortcuts; you have to rethink the design.
An easy place to start is to look for the most expensive operations in your code, and ask… do you really need them?
Before going any further, I have to point out that this code is not legal C++:
std::string words[num_words];
unsigned int presence_flags[num_words] = {0};
unsigned int parity_flags[num_words] = {0};
The reason that appears to be working is because you are using some kind of compiler extension there. But it’s wrong.
The correct thing to do is to use vectors:
auto words = std::vector<std::string>(num_words);
auto presence_flags = std::vector<unsigned int>(num_words, 0u);
auto parity_flags = std::vector<unsigned int>(num_words, 0u);
Now, at a glance, the most expensive thing in your entire program is that vector of strings. That vector could be huge—the upper limit is 2 × 10⁵. And each string could potentially be large, though it’s not clear to me what the upper limit is. At the very least, it is not unreasonable to assume that the strings could easily be large enough to require allocation (that is, not small enough to allow the small string optimization). So that means you could have on the order of 20,000 allocations… and allocations are not cheap.
Now, if you need ’em, you need ’em… but… do you need ’em?
Look at your code carefully:
- you allocate the vector for those strings; and then…
- you read in all the strings into the vector (while scanning); and then…
- you use the string lengths to calculate the total word length.
Did you catch that?
You allocate and then read in (and scan) all those strings… and then never actually use them again!!!
All you use are their lengths!!!
🤯
In fact, you only need a single string: one to read to each word into, one at a time, while you scan it… then discard it and read in the next one over it. In other words, my very minor modification to your program would be this:
auto main() -> int
{
// IO optimization
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr); // Note: NULL is bad, use nullptr
std::cout.tie(nullptr);
// main
int num_words;
std::cin >> num_words;
// auto words = std::vector<std::string>(num_words); // Don't need strings!!!
auto word_lengths = std::vector<std::string::size_type>(num_words); // Just need lengths!
auto word = std::string{}; // (but do need one string to hold one word at a time)
unsigned int presence_flags[num_words] = {0};
unsigned int parity_flags[num_words] = {0};
for (auto i = int{}; i < num_words; ++i)
{
std::cin >> word;
word_lengths[i] = word.length(); // The length is all we need!
// calculating flags
// Note: j is being used to store word lengths... but those are *NOT*
// ints. They are std::string::size_type.
for (auto j = std::string::size_type{}; j < word_lengths[i]; ++j)
{
short pos = word[j] - 'a';
// presence
presence_flags[i] |= (1 << pos);
// parity
parity_flags[i] ^= (1 << pos);
}
}
int num_nightmares = 0;
// checking all word combinations
for (int i = 0; i < num_words; ++i)
{
for (int j = i + 1; j < num_words; ++j)
{
auto word_length = word_lengths[i] + word_lengths[j]; // Note: not int!
if (word_length % 2 == 1 && word_length > 24)
{
unsigned int combined_presence = presence_flags[i] | presence_flags[j];
unsigned int missing_positions = combined_presence ^ 0b11111111111111111111111111;
bool is_25_letters = (missing_positions & (missing_positions-1)) == 0;
if (is_25_letters)
{
unsigned int combined_parity = parity_flags[i] ^ parity_flags[j];
bool is_occur_odd = (combined_presence ^ combined_parity) == 0;
if (is_occur_odd)
++num_nightmares;
}
}
}
}
std::cout << num_nightmares << '\n';
}
(Other than replacing the string vector with a vector holding just the string lengths, I fixed a few bugs due to type issues. For example, strings lengths are not ints, so trying to jam them into an int (like in int word_length = words[i].length() + words[j].length();) could cause UB. But this is almost exactly your code, except for that string vector.)
By not creating tens of thousands of strings… that alone will probably solve your time-limit exceeded issue.
But this is just the tip of the iceberg. I strongly urge you to stop, take a step back, and rethink the problem.
Consider this: for each string pair \$s_i\$ and \$s_j\$, the only information you need is:
- whether the length of the concatenation is odd… which is a single bit of information
- whether each of the letters is seen an odd number of times… and I assume there are 26 letters, so that is 26 bits of information
- whether the number of letters seen an odd number of times is 25… that would take 25 bits, but that is 25 out of the 26 bits we already have from previous item; and
- whether \$i\$ or \$j\$ has been used in a “nightmare” before… which is a single bit of information.
That is a shockingly small amount of information you actually need! You certainly don’t need to store 20,000 strings! You literally only need 28 bits for each word:
- 1 for whether the word length is odd
- 26 to keep track of whether each letter was seen an odd number of times; and
- 1 for whether it has already been used in a “nightmare”.
And then you just need to do some simple bit tests to find all the “nightmare” pairs, and only ones that are “different”.
Two final tips:
First, the only way the length of a concatenated string can be odd is if the lengths of the two words are odd and even. If both are odd, the length of their concatenation is even. If both are even, the length of their concatenation is even. Therefore, if you separate the odd-length and even-length strings, you halve the amount of checking you need to do for each pair.
And, finally: XOR is your friend!
