Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Give Me My Vector

By upobir · 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)



50% Solution Ratio

ArcturusEarliest, 1M ago

ArcturusFastest, 2.7s

ArcturusLightest, 51 MB

ArcturusShortest, 4065B


Login to submit


Since number of subsets can be 2402^{40}240 we cannot generate all of the subsets. But if we divide ...

Toph uses cookies. By continuing you agree to our Cookie Policy.