Блог пользователя wocagav

Help in codenation problem
Автор wocagav, история, 23 месяца назад, По-английски

Question's Pic

testcases

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
23 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

Spoiler
→ Ответить
  • »
    »
    23 месяца назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      23 месяца назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      23 месяца назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      23 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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!

      → Ответить
      • »
        »
        »
        »
        23 месяца назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
    • »
      »
      »
      23 месяца назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
23 месяца назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

Nobody cares! Please, only write relevant stuff.

Marinush

→ Ответить