Give Me My Vector

upobir National Girls' Programmi...
Limits 5s, 512 MB

I am in a hurry. I have nn 2D vectors. And I have created all possible subsets of these nn vectors. For each of these subsets, I have determined the sum of the vectors in that set. Now, I have 2n2^n vectors in front of me. I am not really interested in all of them. I just want to lexicographically sort all these vectors and then pick the kkth smallest one. As I am in a rush, you will have to do this task for me.

Please note that we consider the sum of vectors for an empty set to be the vector (0,0)(0, 0). To lexicographically compare (a,b)(a, b) and (c,d)(c, d) we first compare aa and cc, if a<ca < c then (a,b)(a, b) is lexicographically smaller, if a>ca > c then (c,d)(c, d) is lexicographically smaller, if a=ca=c then we compare b,db, d and the smaller number among bb and dd belongs to the lexicographically smaller vector.


The first line of the input will contain a positive integer TT, the number of testcases.

The first line of each testcase will contain two positive integers nn and kk. Next nnlines will contain the vectors. The iith line will contain two integers xix_i, yiy_i, the coordinates of the iith vector.

1T51 \leq T \leq 5

1n401 \leq n \leq 40

1k2n1 \leq k \leq 2^n

xi109,yi109|x_i| \leq 10^9, |y_i| \leq 10^9


For each test case output in a line two integers xx and yy, coordinates of the lexicographically kkth sum.


3 4
1 2
5 -1
2 0
3 5
1 -1
-2 3
-2 5
3 2
-1 2

In the first test case suppose a=(1,2)a = (1 , 2), b=(5,1)b = (5, -1), c=(2,0)c = (2, 0). then the 88 created vectors are

  1. empty set \to (0,0)(0, 0)

  2. aa \to (1,2)(1, 2)

  3. bb \to (5,1)(5, -1)

  4. cc \to (2,0)(2, 0)

  5. a,ba, b \to (6,1)(6, 1)

  6. b,cb, c \to (7,1)(7, -1)

  7. a,ca, c \to (3,2)(3, 2)

  8. a,b,ca, b, c \to (8,1)(8, 1)


Login to submit.


33% Solution Ratio
ArcturusEarliest, Dec '21
ArcturusFastest, 2.7s
ArcturusLightest, 51 MB
ArcturusShortest, 4065B
Toph uses cookies. By continuing you agree to our Cookie Policy.