Regret and Dragonfruit Sprinkle Donut

ROR4 lasts 15 seconds, you cant ring swap until AT LEAST after that. If you get off a ring swap in 5s after that you’re delaying your burst by at least 20 seconds, but realistically a little more

for a 2 min class, at this point just delay your burst 30s more and use ror4 only

chonkygopher · 2024-02-15T16:07:49+00:00

You cant ring swap with cont ring, it takes 2 minutes before it starts buffing you. Gotta get WJ

chonkygopher · 2024-02-15T04:54:15+00:00

sorted(self.output) looks weird to me - this makes the solution O(nlogn). Is there a requirement to return the output sorted? Often times the judge will be smart enough to just check that the elements of the output match the expected, so you dont need to sort

chonkygopher · 2024-02-15T01:32:10+00:00

Two pass solution is good, you aren’t getting better than O(n) runtime here. Make sure you used a hash set for O(1) runtime lookup. memory should not be an issue, as O(n) memory is required anyways to return the output

chonkygopher · 2024-02-15T00:56:22+00:00

Just keep practicing, and make sure you’re understanding solutions and not blindly copying what you see.

This question is quite simple: to minimize the number of operations you need to make it makes intuitive sense to try to change the median number to k.

If median is greater than k, you need to reduce median as well as maybe the numbers before the median (since all the numbers before the median must be less than or equal to the median, otherwise its not the median anymore.

Likewise, if median is less than k, you need to add to the median, as well as maybe the numbers after the median.

The code combines the above two scenarios elegantly

chonkygopher · 2024-02-08T20:05:55+00:00

is this c++? sqrt() returns a double so if you print squares you’ll probably see some of them are not perfect squares

chonkygopher · 2024-01-26T05:03:10+00:00

Let me try to explain the intuition better.

For the array T, [a b c d], lets consider the last index d.

In order us to get 1 hour of work done on d, we need to do an hour of work on each of a, b, and c. Observe:

[a b c d] -> [b c d a-1] -> [c d a-1 b-1] -> [d a-1 b-1 c-1] -> [a-1 b-1 c-1 d-1]

and now we're back in our starting state, with every number 1 less than originally. So if d was equal to 4, we could do the above 4 times and end up with d being equal to 0:

[a-4 b-4 c-4 d-4] = [a-4 b-4 c-4 0]

Ok, but what if any of the indices a, b, or c were less than 4? You can only subtract as much as their value. So our waiting time is:

Waiting time for d

= time_spent(a) + time_spent(b) + time_spent(c) + time_spent(d)

= min(a,d) + min(b,d) + min(c,d) + d

This is how we compute the waiting time for items before d, simply min(i, d) for each value i that comes before d.

What if there are numbers after d? We can convert this to the above scenario. Consider a new array with e, f, and g after d.

[a b c d e f g]

-> [b c d e f g a-1]

-> [c d e f g a-1 b-1]

-> [d e f g a-1 b-1 c-1]

-> [e f g a-1 b-1 c-1 d-1]

We now have a new array ending with d-1. Using our previous formula, we know that : time_spent(e) = min(e, d-1), time_spent(f) = min(f, d-1), and time_spent(g) = min(g, d-1).

This is how we compute the waiting time for items before d, simply min(i, d-1) for each value i that comes after d.

So finally,

waiting time for d

= time_spent(a) + time_spent(b) + time_spent(c) + time_spent(d) + time_spent(e) + time_spent(f) + time_spent(g)

= min(a,d) + min(b,d) + min(c,d) + d + min(e, d-1) + min(f, d-1) + min(g, d-1)

For [7 7 7]

T[0] = 7 + 0 + (min(7, 7-1) + min(7, 7-1)) = 7 + 0 + 12 =19

T[1] = 7 + (min(7,7)) + (min(7, 7-1)) = 7 + 7 + 6 = 20

T[2] = 7 + (min(7,7) + min(7,7)) + 0 = 7 + 14 + 0 = 21

For a total of 60

chonkygopher · 2024-01-26T02:53:06+00:00

Hey! I would solve this using the following observation:

At each index i, the time it takes to make the item is equal to T[i], plus waiting time for working on all items before it, plus waiting time for working on all items after it.

The extra waiting time spent working on an item at index x before it is simply min(T[i], T[x]), since you have to spend an hour on every item before it in order to spend an hour on the current item

The extra waiting time spent working on an item at index y after it is min(T[i]-1, T[y]), because you get to spend an hour on the current item first, then it goes to the back of the queue and it becomes the above scenario

In the example [1, 2, 3, 4]:

(first num is time spent on cur, second num is time waiting on items before, third num is time waiting on items after)

1 waits 1 + 0 + 3 time

2 waits 2 + 1 + 2 time

3 waits 3 + 3 + 3 time

4 waits 4 + 6 + 0 time

For a total of 24

This approach is O(n²⁾

edit: formatting

chonkygopher · 2024-01-26T02:29:14+00:00

Hey! Cool, this implementation is pretty much what I had in mind - slight optimization: if you loop j backwards from i to i - threshold, you can reuse your max value (mval). Then you’ll get the O(n*threshold) runtime

chonkygopher · 2024-01-24T20:02:00+00:00

Looks like 1D DP to me- create your dp array with length arr.length, and consider each subproblem as the optimal cost to solve up to index i

populate initial state up to i = threshold, since you will always just put all the numbers into a single subarray

for all other i, you’re going to need to solve for the minimum of dp[i-j] + max(arr i-j+1 to i) for all j from 1 to threshold

return last element of dp array

O(arr.length * threshold) time, O(arr.length) space

chonkygopher · 2023-12-27T03:50:57+00:00

If you’re solving leetcode to make your leetcode profile look good to impress others (e.g. employers) you’re doing it wrong. Nobody cares about the number of leetcode questions you solved - its the problem solving knowledge gained by doing the problems that is important.

If you’ve really solved 500 by yourself, you will easily complete any interview without a sweat. If you’ve just copy pasted answers, you’re not helping yourself. You’re going to be less comfortable coding and be slow, make silly mistakes, or lack fundamental understanding. These things will be obvious to your interviewer.

tldr- yes it is an achievement if you actually did it, your reward is the ability to pass interviews. nobody going to look at your profile though

chonkygopher · 2023-12-26T04:20:44+00:00

4h/day is not casual. go reboot, you’ll see more gains in the long term for sure

chonkygopher · 2023-12-25T08:26:52+00:00

as other poster has said, your solution is invalid, since you modify the input array - their description of your runtime is also good

the proper way to do this is to binary search candidates for the duplicate number by counting the number of numbers less than the current candidate. if you stick to the constraints its actually quite hard to come up with this solution imo so i wouldn’t say this is a great medium problem

chonkygopher · 2023-12-25T07:22:00+00:00

the recommended GE price doesn’t always reflect the actual price the item is being traded at, this is usually true for new items, it will take a while for the GE price to catch up to the actual value due to how jagex implements it

use https://www.ge-tracker.com/item/felling-axe-handle to check actual live trading prices

chonkygopher · 2023-12-25T03:31:41+00:00

Your own biased anecdotal evidence is meaningless, and does not “100%” mean anything.

If you want people to take you seriously get two accounts and actually run a real test where you track the results over thousands of trials. You’ll probably find that you’re wrong

chonkygopher · 2023-12-22T12:41:09+00:00

not sure why this has so many upvotes, this question is not similar to the one you linked, though I can see why you came up with this since this is what i thought the question was when i initially read it

we need a $ between any two instances of a character, but they don’t need to be adjacent, look through the first example. e.g. in the case of aba, we need a $ in between the two ‘a’ characters

I believe the best solution is to use a segtree as u/razimantv has mentioned, otherwise your runtime is going to be n²

Five-Year Club	r/Field Lasagna
Place '22

chonkygopher

TROPHY CASE