idkhandle's blog

By idkhandle, history, 3 years ago, In English

Hello community. I came across an interesting problem where we are trying to find a longest (max nodes covered) with min edge wts cost ( sum of edge wts along the path is minimum). You can find a detailed explanation of the problem here: https://stackoverflow.com/questions/18861817/find-path-with-minimum-cost-and-maximum-length-given-a-maximum-cost

In addition to the graphical representation given there, we can have a node 0 from which we can start (node 0 is connected to every other node with a given weight). We can start from node 0, traverse as many nodes as possible and come back to node 0. In addition, we can traverse node 0 as many times as possible ( but node 0 is not counted in the final length). Any idea how to do this? We need max nodes covered with min path cost and under the given max cost constraint. ( Graph is fully connected)

Constraints:

If N is the number of nodes in the graph, then

1 <= N <= 2000

Also, If C is the max allowable wts cost along the path, the constraints are:

C <= 1e9

Any help would be appreciated :)

Full text and comments »

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

By idkhandle, history, 3 years ago, In English

Recently I came across a question in which we need to solve the problem mentioned here: https://leetcode.com/problems/exam-room/

Such that we are given N and K ( N is total number of seats in exam hall and Kth person enters). There is no leave operation, but only a seat operation is there.

Is there any way I could know where the Kth person would sit? ( assuming no one leaves )

Constraints

1<=N<=1e18

K<=N

Full text and comments »

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