[TESTCASE] - 502. IPO

[kerryghan-relot]

LeetCode Username

K_Le_Viking

Problem Number, Title, and Link

502. IPO https://leetcode.com/problems/ipo/description/

Bug Category

Missing test case (Incorrect/Inefficient Code getting accepted because of missing test cases)

Bug Description

My Pyhton Solution got accepted by the system and even did great : 596ms runtime, beats 96.84% and categorised as O(NLogN) by the system. A previous submission of mine (same code, just poorer variable naming) got a very similar result : 638ms runtime, beats 96.06%. But I managed to design a testcase which gives me TLE, for the following code.

I first had an idea of my solution without being sure of whether it would work or not. So I tried it and it was accepted ! (Hurray, I still got my daily streak :-) ). However, I wasn't fully satisfied with it and tried to design an extrem testcase just to see if I could get a TLE on the testcase with this accepted solution. So I chose the greatest array size possible with highest value span.

I submitted the issue on the Leetcode website as well as I wasn't sure which one would be best. Do you prefer that we submit issues directly on Leetcode or here in Github?

Language Used for Code

Python/Python3

Code used for Submit/Run operation

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        project_list = sorted(zip(profits, capital), key=lambda x: x[1])
        k = min(k, len(project_list))
        max_capital = max(capital)

        def get_most_profitable_affordable_project(project_list: List[tuple], w: int) -> tuple:
            max_profit = 0
            best_project_index = -1
            for index in range(len(project_list)):
                if project_list[index][1] > w: 
                    break
                if project_list[index][0] > max_profit:
                    max_profit = project_list[index][0]
                    best_project_index = index

            return max_profit, best_project_index

        for iteration in range(k):
            if w < max_capital:
                profit, index = get_most_profitable_affordable_project(project_list, w)
                if index == -1: 
                    return w
                w += profit
                del project_list[index]
            else:
                w += sum(sorted((e[0] for e in project_list), reverse=True)[:k - iteration])
                break

        return w

Expected behavior

When the proposed test case is run with my code, It gets TLE. Hence, I think the testcase (or a similar one) should be added.

Screenshots

My accepted solution:

My solution when run with the proposed test case:

Additional context

Here is the link of my testcase as it overflows the character limit of this input box :

https://justpaste.it/emjph

both arrays are of size 10^5

[exalate-issue-sync[bot]]

Epiphania_Ekenimoh commented: Hello there,

Thank you for reaching out regarding the test case issue.

To help us diagnose and resolve the problem more effectively, could you please place each value of the test case in a separate txt file? This will allow us to analyze the input data more precisely.

Thank you for your cooperation and understanding. We look forward to resolving this issue for you as soon as possible.

Best regards, LeetCode Support Team

[kerryghan-relot]

Thanks for your response: Just for your information, in my previous txt file I printed out the testcase the same way we put them in Leetcode's testcase tab.

Anyway, here are each individual values of the testcase. The first values of the testcase are simple numbers, so I just put them bellow:

k = 98765

w = 10000

profits = https://justpaste.it/c0271

capital = https://justpaste.it/cgo3q

[exalate-issue-sync[bot]]

Epiphania_Ekenimoh commented: Hello,

Your reported issue has been relayed to our team for thorough investigation. We appreciate your patience as we work to address and resolve this matter. We will reach out to you when we have updates regarding the issue.

If you have any further questions or concerns in the meantime, please feel free to let us know.

Best regards, LeetCode Support Team

[kerryghan-relot]

Hello,

Thank you for that. I was just wondering how the credit system ("leetcoins" awarded for submitting a testcase) work?

Do you need my leetcode username or something? In case you need it, here is my leetcode profile: K_Le_Viking

Best regards

[exalate-issue-sync[bot]]

Epiphania_Ekenimoh commented: Hello there,

Thank you for providing your username. If the test case is accepted, you will be rewarded with LeetCoins. Please be patient while we work on it.

Best regards, LeetCode Support Team

[exalate-issue-sync[bot]]

Epiphania_Ekenimoh commented: Thank you for your time.

Your feedback has been used to enhance the problem. As a token of our appreciation, your LeetCode account has been credited with 100 LeetCoins.

If you have any more questions or additional feedback, please don't hesitate to let us know. Your continued support is invaluable to us!

Best regards, The LeetCode Team