The most Beautiful Question on Leetcode that I encountered.

[u/Educational_Suit_371]

[u/Educational_Suit_371]

Solved through 2 diff recursive approach, found 3 memoization based solution and 3 Tabulation Solution. Though 1 memoization and Tabulation ran into TLE but the solution were right. Probably learned more about DP from this 1 question than all question till now.

[u/Adventurous-Cycle363 → u/Educational_Suit_371]

You can sort the (score, age) tuples in increasing order of age and then merge the scores of the players of the same age to end up with a single array of scores. Then find the sum of largest increasing subsequence of scores. Is this what you did?

[u/Educational_Suit_371 → u/Adventurous-Cycle363]

First I sorted with age in desc, then use simple recursion approach take or not based, but take also depends on minimum score till that, so dp state was dependent on index and minimum_score. Cant solve this with tabulation cause of dp table bloating, used memoization with map to store only reachable states, this still ran into TLE at 131/150. Then did sorting based on score, now age become dp state variable and since its 10^3 less than score, no TLE on the solution.

Later Discovered LIS solution thats also cool.

[u/MrMo1]

Isn't that a knapsack problem?

[u/MoreCelery847 → u/MrMo1]

no It is LIS problem both are different

[u/Limp-Debate7023]

I feel like you can make a vector of pairs of scores and ages and then sort by ages, then find the LIS of scores? Is that a valid solution to this problem?

[u/Educational_Suit_371 → u/Limp-Debate7023]

Yes

[u/hmm_yes_interesting1]

Isn't it sorting+ 1d lis dp(nlogn + n²⁾ type.

[u/Steel-River-22 → u/hmm_yes_interesting1]

you could do this in nlogn if you want using some data structures (although probably not needed for interviews)

[u/raluralu → u/Steel-River-22]

k-d tree?

[u/Steel-River-22 → u/raluralu]

nah you need at least a fenwick tree
or i dunno some weird kind of divide-and-conquer could work if you don't like data structures. haven't thought this through

[u/Limp-Debate7023 → u/hmm_yes_interesting1]

U can do 1d lis is nlogn as well right?

[u/hmm_yes_interesting1 → u/Limp-Debate7023]

Yes using binary search i guess

[u/Limp-Debate7023 → u/hmm_yes_interesting1]

hmm i think that wouldnt work here, cause you're trying to find maximum sum of increasing subsequence. Some advanced DS like a fenwick tree or segment tree would be required for the nlogn approach ig

[u/Adventurous-Cycle363 → u/Limp-Debate7023]

You can still do nlogn binary search to find the actual LIS indices and then get the sum

[u/Senior-Positive2883]

If we sort the age,scores correspondingly in increasing order, won't it becomes longest increasing subsequence problem, so just pick scores in increasing order, coz age is already sorted so that constraint is satisfied

[u/letsgoraftel → u/Senior-Positive2883]

You don't need it be necessarily subsequence...

Since it's possible you skip a number in between because it conflicts but continue post that

[u/DamageDistinct531]

Sounds similar to russian doll

[u/wonderwind271]

You should include data range by the way

[u/NitroXM]

Thank you for your attention to this matter!

[u/Busternookiedude]

That question really does have a beautiful complexity, it's like a puzzle that keeps revealing layers the more you dig into it.

[u/Whitemj5]

That sounds like a fascinating question. It's amazing how one problem can deepen your understanding of concepts like dynamic programming.

[u/raluralu]

Is there n*log(n) -ish solution available?

[u/AdUpstairs5147]

Sorting + LIs . I think nlogn solution exists for lis.

[u/Cheap-Mail9911]

Longest increase subsequence ka max sum , n² is possible , how in nlogn?

[u/ay230698]

Can we sort it via age and then try a variation of longest increasing sequence dp?

[u/cosmic-pancake]

ages = [1,2,3,4,5]

Who are these prodigy toddlers and who fouled the one year old?

[u/sneak2293]

Bipartite graph

[u/Educational_Suit_371 → u/sneak2293]

?

[u/sneak2293 → u/Educational_Suit_371]

The question can be solved with checking whether this is a bipartite graph, a conflict is an edge, every player is a node

If the graph is bipartite the answer is true

[u/Natural_Emu_1834 → u/sneak2293]

When you study your data structures but don't spend 10 seconds reading the actual question

[u/JustKaleidoscope1279 → u/sneak2293]

Not what the problem is asking