starkkk's blog

Problem K (2017 ACM-ICPC, Universidad Nacional de Colombia Programming Contest)
By starkkk, history, 7 years ago, In English

101466K - Random Numbers Can any one give me a hint? Thank you!

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

How to find Kth smallest number in an array which formed by product of each element of 3 array A,B,C? (Time limit :2s)
By starkkk, history, 7 years ago, In English

Here is the full description of the problem

The length of each array A,B and C <= 1000 and K <= min(10^6, na * nb * nc) (na,nb,nc is the length of each array A,B and C)

I have thought that we can run through array A and B to find all the products of A and B in O(n^2) and generate Kth number by multiply that products with element in array C. But I don't know how to exactly generate Kth number in step 2th.

In this problem, the number can be NEGATIVE

Does anyone help me about this or give me your idea how to solve this problem? Thank you!

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it