wocagav's blog

By wocagav, history, 22 months ago, In English
  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
22 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Bump. I would also like to know how to approach this question. Clear image of the problem statement with example:

Spoiler
  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    I couldn't get the time to do it because of the 2nd problem. Solved 2 barely.

    Upon upsolving I made some observations.

    1. We don't need to wait for more than $$$N$$$ seconds where $$$N$$$ is the total number of gems in input to destroy them all.

    2. When picking a gem at index $$$i$$$ we can destroy up to $$$A[i][0]$$$ gems.

    3. Most important observation i.e if we choose to take some gems and leave the others then such a sequence will be valid iff the count of remaining gems is $$$\le \sum_{i = 0}^nA[i][0] $$$ of the gems we chose.

    so I maintain a $$$dp$$$ of non-chosen gems.

    $$$dp[idx][time left]$$$

    where the dp indicates that at idx we are left with timeleft amount of time after we decided to not include non-zero amount of gems.

    Transitions are simple kind of like typical knapsack fashion.

    1. You either choose to not include the gem and reduce its contribution to time_left and also by 1.
    2. You choose to include the gem and thus you move to the next without reducing the time.

    $$$dp[idx][time left] = max(A[idx][1] + dp[idx + 1][timeleft - A[idx][0] - 1], dp[idx + 1][timeleft])$$$

    Base cases are simple and also the timeleft will be min (size of input, sum of net time over all indices).

    If it is wrong, incorrect please let me know.

    • »
      »
      »
      22 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      here is a simple recursive solution https://pastebin.com/9niQeL7M . Approach is explained in comments.Did same as u but in recursive manner.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Hey If you don't mind can you tell me the approach of 2nd problem

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for the detailed explanation! since we are on it, can you also tell what was needed to solve the second problem(longest path in a tree)? thanks!

      • »
        »
        »
        »
        22 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        The brief idea is that what the problem wanted us to find out is called the diameter of a tree.

        The problem stated couple of conditions to allow us to find one out of multiple diameters and that bit is implementation heavy.

        I had 3 dfs functions.

        1. A normal dfs for taking out the node at largest distance from root and also with the largest node value among all valid answers.

        2. A boolean dfs to allow me to find all the nodes on the path of the diameter. You can implement in a backtracking fashion using a visited vector. (You mark the node as you enter it and unmark it as you leave it, therefore from the starting node of the diameter when you find the other end marked you will only have nodes marked that are on the diameter path. Once you find out the endpoint of diameter simply return true to prevent any further dfs)

        3. This dfs deals with the actual problem which is to find the simple paths. Notice the fact that due to the diameter of the tree our tree will be split into various components and within a component, each node can be reached from the other, so we need to find the component sizes and take nc2 where n is the size and add them to the answer.

    • »
      »
      »
      22 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Um, actually the states are a bit wrong. If we do it in this manner we will end up with a TLE since the total time left can be of the order 4e6 so instead take out the minimum possible sum of bad luck due to chosen gems and subtract it from total bad luck.

      In this approach, the 2nd state will initially be at max 2e3 since we can have at most 2e3 non-chosen items.

      Transitions :-

      $$$dp[idx][notchosen]=min(A[idx][1]+dp[idx+1][max(notchosen−A[idx][0]-1, 0)],dp[idx+1][notchosen])$$$

      base case is if notchosen $$$ == 0$$$ at idx == size return $$$0$$$ else return Infinity.

      Hopefully this is the proper solution.

»
22 months ago, # |
  Vote: I like it -23 Vote: I do not like it

Nobody cares! Please, only write relevant stuff.

Marinush