# Codeforces: Dasha & Nightmares

so I got started with competitive programming about a day ago and I got stuck on the first random question I tried on codeforces. It's called Dasha and Nightmares.

Problem Description: The problem involves finding the number of unique nightmares formed by concatenating pairs of given words. A nightmare is defined as a string with an odd length, exactly 25 different letters, and each letter occurring an odd number of times. The task is to determine the count of distinct nightmares resulting from different word pair concatenations, considering the constraints provided.

Here is my solution for the problem:

#include <iostream>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int main() {

// IO optimization
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);

// main
int num_words;
std::cin >> num_words;

std::string words[num_words];
unsigned int presence_flags[num_words] = {0};
unsigned int parity_flags[num_words] = {0};

for (int i=0; i<num_words; i++) {
std::cin >> words[i];

// calculating flags
for (int j=0; j<words[i].length(); j++) {
short pos = words[i][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++) {
int word_length = words[i].length() + words[j].length();
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';

return 0;
}


Now, it passes the first 2 test cases, however on the 3rd test case, it exceeds the time limit of 4 seconds. What am I doing wrong here and how can I make it faster? I found out about some of the IO optimisations and pragma tricks today but even with those I can't execute under 4 seconds.

• Ahoy! I added the programming-challenge tag, since the problem comes from codeforces question. From the tag wiki: "Always include a sufficient description of the problem to be solved - while a link to the challenge is welcome, the review request needs to be complete when the challenge site is unavailable.". Can you please edit the post to include enough information for that? Commented Nov 2, 2023 at 6:04
• @SᴀᴍOnᴇᴌᴀ I added the problem description Commented Nov 2, 2023 at 6:09

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?

1. you allocate the vector for those strings; and then…
2. you read in all the strings into the vector (while scanning); and then…
3. 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!

• hey thx a lot for replying. so I fixed the part where I was storing every single string and replaced it with a single string and a word length vector. However, the runtime is still exceeding 4 seconds. Also, I had a question about one of your suggestions - you said i need at most 1 bit for odd/even, 26 bits to see which letters were seen odd times and 1 bit to check if used by nightmare. However, wont I need another 26 bits to keep track of which letters were present? For instance, if the following 26 bits represent odd letters seen: 100101000..., Commented Nov 4, 2023 at 10:51
• continuing from the above comment, the first 1 indicates the letter was seen an odd number of times, but the 0 after that could mean that either the letter was seen an even number of times or it wasn't seen at all. Wouldn't I need to keep track of this? Commented Nov 4, 2023 at 10:52
• You actually don’t need a separate bit to encode “seen”, because “seen an odd number of times” ⊢ “seen” (where “⊢” means “logically implies”). You can’t be seen an odd number of times without being seen! You are correct that 0 would mean either “seen an even number of times” or “not seen”… but you don’t care which, because in either case, the string fails. And, ultimately, all you care about is whether the string passes or fails… not why.
– indi
Commented Nov 4, 2023 at 19:26
• Oh, also, if you’re still getting timeouts after removing the string vector, the new most likely culprit is now that second loop, which is a loop of loops. Consider that for every word, you are checking for a nightmare with every other word not checked yet… even though half of them will yield a string with an even length. That’s twice the work you need to do. That’s why I suggested separating the odd-length and even-length words.
– indi
Commented Nov 4, 2023 at 19:26