Use of Linked List and Priority Queue in CF Round 452, Problem E

The difficulty of the round is a lot easier than the previous round. I am really happy about that. :)

Just a little regretted about spending too much time on D. Could have solve E in contest time :<

Anyway, let's look at the question!

Problem Description: Problem - 899E - Codeforces

The problem is pretty straight-forward: we need to keep track of the longest (and then leftmost) consecutive identical numbers and continuing deleting them. Then the only problem remaining is how we implement it.

The method to find the longest sequence we might think is priority queue and, (some might use) set, and those two things work perfectly, since we are continuously getting and removing the longest sequence.

But how can I update the sequences? For example, in sequence [1,1,2,2,2,1,1], the longest sequence is [2,2,2]. After we delete that, it becomes [1,1, ,1,1]. The two parts merge together because their numbers are the same. This reminds me of one problem that I've once solved (the link is provided below), where I used linked list to solve the question.

Using linked list in this problem? Why not? It is perfect match! When I delete one sequence from the array, I can just link the sequence's previous item to the sequence's next item, and push the newly updated length into the priority queue. And that works!

When I found that linked list can be so useful under those circumstances, I was so impressed and admired the power that those data structures gave us to solve problems.

Additional problem you might find insteresting: 
The one that use linked list: Problem - 670E - Codeforces

Note: there is a lot of algorithms or methods of thinking uses the priority queue like dijkstra's algorithm in graph theory. When seeing a problem like keeping the max or min value, try to see whether it is appropriate to use this method!


Popular Posts