MOAE's blog

By MOAE, history, 5 weeks ago, In English

Problem : C. Yet Another Card Deck solution : Link solution by : icecuber

thanks in advance :D

  • Vote: I like it
  • +3
  • Vote: I do not like it

5 weeks ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Ok so first of all, lets talk about set and ordered_set, set saves values in some order (usually increasing order), but you cant take the "index" of some value, for example, if we declare set<int> = {2,3,9,7}, we know that the "index" of 9 is 3, and "index" of 7 is 2, but there is no methods that you can call to get that "index".

So if you want to know the index of some ordered values, you can use the ordered_set(in this code is used as os_set) that as the set, save the values in some order, and has a method called order_of_key() that does exactly what we need, give the index of some value.

Now, lets talk about the ideia of the question: Lets supose that in one query the value asked is A, and A appear K times in the array, you will look to the first appearance of A, show his index, and than move A to the start. So if you query for the same A again and again, you will always look to the same first appearance of A, never looking for the others K-1 A's in the array, so doesnt matter if A appear K times, you will only need the first appearance of A.

So, the idea in this solution is to save the first appearance for all A, as in if (!id.count(a)) id[a] = i;, then save all the indexes of the array in an ordered_set, as in ost.insert(i);. Then, for all queries, we look for the index of A, lets call it B, and then search the index of B in the os_set, after this, we remove B of the os_set, and add the new index as the lowest index at the moment.

At the start, the indexes look as 0 to n-1, after the first query, the lowest index will be -1, then -2, and so on.

For the sample, we have the array as 2 1 1 4 3 3 1, index of all distinct values are: (2,0), (1,1), (4,3), (3,4), and the ordered_set has all the indexes {0,1,2,3,4,5,6}. Then, we query for 3, its index is 4, the index of 4 is 4 in the os_set. So the answer is 4 + 1 = 5 (as the question is 1-indexed). Then we remove the index 4 to the os_set and update the index of 3 as -1.

(2,0), (1,1), (4,3), (3,4) changes to (2,0), (1,1), (4,3), (3,-1) and {0,1,2,3,4,5,6} changes to {-1,0,1,2,3,5,6} (erase 4, add -1).

We query for 2, its index is 0, so we ask for index of 0 in the os_set, and the answer is 1+1 = 2. We again remove 0 of the os_set and add -2, as the new index of 2.

(2,0), (1,1), (4,3), (3,-1) changes to (2,-2), (1,1), (4,3), (3,-1) and {-1,0,1,2,3,5,6} changes to {-2,-1,1,2,3,5,6}. (erase 0, add -2).

And so on.

I hope this helps you, sorry for my poor english.