Discussion @ 1741. Communication Fiend @ Timus Online Judge

For WA#3 and Some hints how to solve the problem with O(n * log(n))

Posted by Leonid (SLenik) Andrievskiy 23 Jul 2011 01:44

If you have WA#3 check whether you have a correct understanding of updating:

(Thanks for Vit Demidenko (http://acm.timus.ru/author.aspx?id=74435)

Format:

UpdateType
Source -> Destination
---
Pirated
Licensed -> Pirated
Pirated -> Pirated

Licensed
Licensed -> Licensed

Cracked ->
Pirated -> Pirated
Licensed -> Licensed

I have WA#3 when I write a wrong interpretation of "Cracked" update.

P.S. About O(m*log(m)) solution:
1. Sort the updates by "yi" parameter ascending.
2. Then use dynamic programming.

Re: For WA#3 and Some hints how to solve the problem with O(n * log(n))

Posted by S.77 4 Aug 2011 17:43

You can even avoid sorting, simply create an array of linked lists and group the update read to the list with index 'y'. Then go through all of them from least 'y''s up to the greatest ones and use DP. This solution is O(m), if i've not mistaken :)

Re: For WA#3 and Some hints how to solve the problem with O(n * log(n))

Posted by Leonid (SLenik) Andrievskiy 14 Aug 2011 16:01

Yes, it is true. And the method you suggested, is counting sort (http://en.wikipedia.org/wiki/Counting_sort)
And if you use radix sort, you 'll need to make only one additional array of n elements (http://en.wikipedia.org/wiki/Radix_sort), and the complexity of your solution will remain O(m).

Edited by author 14.08.2011 16:08

Re: For WA#3 and Some hints how to solve the problem with O(n * log(n))

Posted by S.77 16 Aug 2011 00:59

Thanks, Leonid.
All linear-time sortings are almost the same and use the same idea. "Radix sort" uses less memory than "Counting sort", but it works some time longer. But since "n,m<=10^4", should we care about the memory we use?

Discussion of Problem 1741. Communication Fiend