rmr's blog

By rmr, 6 months ago, In English

My issue concerns 1840D - Wooden Toy Festival. Within the contest I used an approach similar to the one given by the authors of the problem in tutorial, and the first step was to sort an input array and don’t consider duplicates. As usual, I used a combination sorted(set(a)), which always worked well and seemed to me quite reliable. The submission 208933459 successfully passed all pretests. However, then I got a hack with TL exceed. After the contest I submitted an almost identical submission 208932147 with the only one exception: I replaced the combination above with the following block:

b = [a[0]]
for i in a:
	if i != b[-1]:

As I understand it, it performs no better. The first step of sorting the array works with $$$O(n \log(n))$$$ complexity, and the second one of removing duplicates with $$$O(n)$$$. However, with the such replacement my solution passed all the tests. Could you explain why this is so? And does it mean that henceforth it’s better to use something like the block above instead of using combination sorted(set(a)))? I would appreciate a lot!

Full text and comments »

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