Editorial for DMOPC '20 Contest 3 P2 - Bob and Parallel-Ks

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AvaLovelace

For the first subtask, we can use brute force. Iterate through each beat and each pair of singers in $\mathcal{O}(NM^2)$ ~\mathcal{O}(NM^2)~ time, checking if the singers form a parallel- $K$ ~K~ between that beat and the next.

Time complexity: $\mathcal{O}(NM^2)$ ~\mathcal{O}(NM^2)~

For the second and third subtasks, notice that since the notes on a single beat are all distinct, a note can form an interval of $K$ ~K~ with at most one other note on that beat. Additionally, if notes $i$ ~i~ and $j$ ~j~ form an interval of $K$ ~K~, any note higher than $i$ ~i~ can only form an interval of $K$ ~K~ with a note higher than $j$ ~j~.

Hence, for each beat, we can sort the singers in ascending order by note and use a "two-pointers" method to find each pair of notes that form an interval of $K$ ~K~. We can then check if the notes' singers still form an interval of $K$ ~K~ on the next beat; if so, we have found a parallel- $K$ ~K~.

Time complexity: $\mathcal{O}(NM \log M)$ ~\mathcal{O}(NM \log M)~

Comments

1

tortle commented on Feb. 2, 2021, 3:50 a.m.

I think I'm misunderstanding something in the editorial;

it says "a note can form an interval of K with at most one other node on that beat," but in the sample input, beat 1, note 10 is forming parallel-5ths with both note 5 and note 15?

16
cabbagecabbagecabbage commented on Feb. 1, 2021, 10:09 p.m. ← edit 3 →
Hi I'd like to share another solution that is surprisingly simple (and probably not intended?).

To summarize the problem statement, we want to find the number of pairs of horizontally adjacent pairs, where the pairs should take up the same 2 columns and whose corresponding difference is $K$ ~K~.

So when we have 1 horizontally adjacent pair $(x, y)$ ~(x, y)~, we can determine whether it forms a parallel- $K$ ~K~ by asking, "is there another pair that starts in the same column as ' $x$ ~x~' whose numbers are $(x+k, y+k)$ ~(x+k, y+k)~?". (to avoid double counting, we only add, since if there exists a pair $(x-k, y-k)$ ~(x-k, y-k)~ then we will find that parallel- $K$ ~K~ when we repeat the process with that pair)

To do this, we can store every single pair as well as their starting index with an unordered_map - like data structure, by mapping $y+k$ ~y+k~ to umap[startingIndex][x+k]. When we try to find whether a pair $(x+k, y+k)$ ~(x+k, y+k)~ exists, simply check if umap[startingIndex][x+k] == y+k. If so, then we have found a parallel- $K$ ~K~.

However, std::unordered_map is unfortunately slow, and will most likely TLE on test case 31 from my experience. To work around this, we can take advantage of Policy Based Data Structures, specifically gp_hash_table, which is way faster. (see https://codeforces.com/blog/entry/60737, and probably don't worry about anti-hacking because I like to believe nobody on DMOJ is that bored...)

Here is the final solution, which passes every test case comfortably (within 1 second worst case): https://pastebin.com/c2156Ubw

Time Complexity should be around $\mathcal{O}(MN)$ ~\mathcal{O}(MN)~ assuming that hashing is constant.

Additional Notes:

It's important that within a column, there will be no duplicate elements. Otherwise this solution may not work due to undercounting

Checking whether a key exists first instead of creating it every time speeds it up a bit. gp_hash_table does not have a .count() function, so just do .find() != .end()

The reason I used an array of maps is because you can't hash pairs without a custom hash function (afaik)

Edit: Looking through some more solutions, it appears that PBDS are not even necessary if we instead iterate column by column and clear the unordered_map each time. This way, the starting index is guaranteed to be the same, saving us a dimension of memory, and apparently allowing the program to pass.