## 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 time, checking if the singers form a parallel- between that beat and the next.

Time complexity:

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 with at most one other note on that beat. Additionally, if notes and form an interval of , any note higher than can only form an interval of with a note higher than .

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 . We can then check if the notes' singers still form an interval of on the next beat; if so, we have found a parallel-.

Time complexity:

• commented on Feb. 1, 2021, 10:50 p.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?

• commented on Feb. 1, 2021, 5:09 p.m. edit 2

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.

So when we have 1 horizontally adjacent pair (x,y), we can determine whether it forms a parallel-K by asking, "is there another pair that starts in the same column as 'x' whose numbers are (x+k,y+k)?". (to avoid double counting, we only add, since if there exists a pair (x-k,y-k) then we will find that parallel-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 to umap[startingIndex][x+k]. When we try to find whether a pair (x+k,y+k) exists, simply check if umap[startingIndex][x+k] == y+k. If so, then we have found a parallel-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 O(MN) assuming that hashing is constant.