# | User | Rating |
---|---|---|

1 | Benq | 3813 |

2 | tourist | 3768 |

3 | maroonrk | 3570 |

4 | Radewoosh | 3535 |

5 | fantasy | 3526 |

6 | jiangly | 3523 |

7 | Um_nik | 3522 |

8 | orzdevinwang | 3441 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 178 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

6 | adamant | 163 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | antontrygubO_o | 155 |

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/29/2023 17:55:42 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

SpoilerAre you able to solve 2nd question?

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

Upon upsolving I made some observations.

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.

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

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.

$$$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.

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

Nope once a round is over on Interviewbit it's no longer accessible as far as I know.

ok :(

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

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!

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.

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

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)

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.

I too had same idea but how you handled the farthest node and largest one, can you please share code?

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.

Nobody cares! Please, only write relevant stuff.

Marinushis there anyone who got 3rd one ?

who got third problem in a contest you mean.If that what you mean than what contest?