TIDRICE - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

We are given the votes of many users in the order they arrived and we are asked to calculate the correct final score. The only thing we need to worry about is, how to handle multiple votes by the same user. The statement says, “If a user votes more than once, the user’s previous vote is first nullified before the latest vote is counted”. Given the votes of a particular user in the order he voted, we need to process them one by one and update the final score, as shown in the explanation of Case 1.

But wait, do we really need to count each vote only to nullify it again ? The answer is No. If we are going to nullify a vote, why to count it at all ? Lets count only the votes that are not going to be nullified. It should be easy to observe that such votes are nothing but the last votes of each user. So, all we need to do is count the last vote of each user. The low constraints allowed codechefs to use any bruteforce method. As its been quite long since I coded in plain C, you can refer my C code below. For C++ / Java coders, a Map ( string ? int ) will do, as it replaces the old value with the new value, when a new (key, value) is put with the same key.

{ Those of you who didn’t observe , TID RICE is an anagram of DIRECTI :slight_smile: }

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes