Application of sets Solution

This problem is a simple application of the set data structure. The rst part is from the ICPC world nals 2019. The actual description of the problem can be found at https://icpc.kattis.com/problems/azulejos. A more formal description is given below.

Let S1 and S2 be two sequences of length n, the elements of which are ordered pairs of integers, not necessarily distinct. Let S1 = (a1; b1); : : : ; (an; bn) and S2 = (c1; d1); : : : ; (cn; dn). The problem is to nd permutations p and q of f1; : : : ; ng, if they exist, satisfying the following properties.

    1. ap(i)ap(i+1) and cq(i)    cq(i+1) for 1   i < n.

    2. dq(i)    bp(i) for 1   i  n.

In other words, the elements in S1 and S2 must be ordered in non-decreasing order of their rst coordinate, such that the ith element in the ordering of S2 has second coordinate less than or equal to the second coordinate of the ith element in the ordering of S1. Such orderings may not always be possible.

The basic algorithm is as follows. Let a be the minimum value of the ai and c the minimum of the ci. Let A be the subset of pairs in S1 whose rst coordinate is equal to a, and C the subset of pairs in S2 with rst coordinate c. The elements in A must come rst in the ordering of S1 and the elements in C must come rst in the ordering of S2. Suppose jAj jC j. Then for every element of A the corresponding element in the ordering of S2 must be an element in C. Choose an element in C such that its second coordinate is the largest possible but does not exceed the second coordinate of the element in A. Delete these elements from A and C. If for some element in A, no such element in C is found, then an ordering is not possible. If A becomes empty, some elements may be left in C. Now consider the second smallest value of the rst coordinate in S1, let A be the set of those elements and repeat. If jCj jAj, do the same for elements in C, except that the element of A chosen is the one with smallest second coordinate that is greater than or equal to the second coordinate of the element in C. The lower bound and/or upper bound methods of the set class can be used to nd these elements.


The second part of the problem, which was not in the ICPC, is to determine whether the solution is unique, that is, there exists exactly one pair of permutations p; q that satis es the given property.

Input/Output: The rst line of input speci es n, which will be at most 5 105. The next 4 lines contain n numbers each separated by a space, with each number at most 109. The rst line gives the values of ai, the next bi, ci, di in that order. If there exist permutations p; q satisfying the required properties, print p on the rst line and q on the second. If there are many solutions, any one is okay. Note that indices are considered from 1 to n. If there are no such permutations, print \impossible", without quotes. For the second part, if there exist such permutations, print \unique" if the answer is unique, otherwise print \not unique". Nothing needs to be done if it is impossible. Time limit in the contest was 10sec but it should probably take less. The test cases from the contest,

1





for the rst part, are put up on teams. I may use di erent ones, especially for the second part.

Submission: Submit a single  le named RollNo 9.cpp


Note: It may be necessary to compare ordered pairs of numbers based on the rst coordinate, or the second coordinate at di erent times. (It may in fact be easier to consider triples, where the third coordinate is the index). By default, sets and functions like sort use the < operator for comparison. If a di erent comparison function is required, it can be speci ed when de ning the set or calling the sort function. This is done using function objects, for which the function call operator () is de ned. A sample declaration would be

struct compare{

bool operator()(T const &t1, T const &t2) const

{

// comparison for elements of type T

}

};

sort(v.begin(), v.end(), compare());

    • v is a vector of type T, a dummy object of type compare is passed

    • to the sort function. If f is an object of type compare, f(t1,t2)

    • returns a boolean value, comparing t1 with t2.

set<T,compare> S;

    • defines a set with elements of type T using compare

    • as the comparison operation.

Sample Input 1 Sample Output 1

4


3
2 4
1
3
2 1
2
4
2 1
3
2
3 4
3
not unique
2
1 2
1



2
2 1
3



Sample Input 2 Sample Output 2
2


impossible

    • 2

2 3

2 8

2 1


2