UVa 12049

From Algorithmist
Jump to navigation Jump to search

UVa 12049 - Just Prune The List[edit]

Summary[edit]

You are given two list of integers. You can remove any number of elements from any of them. You have to ensure that after removing some elements both of the list will contain same elements, but not necessarily in same order.

Explanation[edit]

Calculate the number of elements, i, in the intersection of both lists. Given that the lists are of size N and M, the output value is therefore: N + M - i.

This can be done in (at least) two ways:

std::set_intersection

Read in each input list, sort and then calculate the intersecting elements via std::set_intersection. This is fast to implement and easy to understand but slower to execute, as the complexity is log linear for the sorting plus linear for the intersection.

Hashed Intersection

Process each list and hash each element. This is aided by a favourable size constraint on the two lists (<= 10,000 elements). As there is no sorting pass required, this algorithm is linear and hence has faster execution speed than the above approach. This also avoids computing the actual intersecting elements and only counts the number of hash matches of a given element. This is significantly slower to code and more complex (hash collisions still need to be handled).

Gotchas[edit]

  • I/O concerns are significant in reading the input for very fast solutions.
  • The numbers within the list can be any 32-bit signed integer.

Implementations[edit]

Implementation using std::set_intersection is straighforward.

Optimizations[edit]

  • Calculate the number of intersecting elements using hashing (or another fast intersection algorithm).

Input[edit]

1
25 50
20000010 20000049 20000009 20000034 20000032 20000037 20000037 20000048 20000045 20000019 20000005 20000031 20000020 20000019 20000029 20000022 20000045 20000030 20000040 20000031 20000035 20000008 20000036 20000039 20000014
20000868 20000852 20000853 20000873 20000867 20000859 20000862 20000864 20000872 20000855 20000867 20000873 20000868 20000859 20000874 20000851 20000861 20000853 20000851 20000854 20000855 20000868 20000850 20000867 20000852 20000851 20000874 20000863 20000854 20000852 20000853 20000874 20000856 20000856 20000873 20000873 20000865 20000860 20000861 20000864 20000867 20000854 20000861 20000861 20000863 20000862 20000865 20000850 20000865 20000866

Output[edit]

75

References[edit]

  1. http://stackoverflow.com/questions/4642172/computing-set-intersection-in-linear-time