For doing CP in general? Or doing CP with Python?
#algos-and-data-structs
regal spoke
regal spoke
Tbh the most important thing is just to keep practicing
If you look at people rating graphs, then you'll notice that the one secret to going up in rating is time
cobalt mirage
If you look at people rating graphs, then you'll notice that the one secret to g...
Nah like I just can't seem to be improving because of the observational skill
or like a math sht i dont know
but I haven't done many cf questions
I am talking about in general
summer fossil
I am talking about in general
which language do u use for cp?python?
summer fossil
Great Can u share ur profile?
cobalt mirage
Whats your rating
summer fossil
0
cobalt mirage
😹
summer fossil
Didn't start yet
cobalt mirage
i created a new acount
summer fossil
I want to start but busy nowdays!
regal spoke
Btw one of the good things about codeforces is that all problems have a written editorial.
regal spoke
i hate the editorials
"the editorials", the editorials are written by completely different people. You cant possibly hate all editorials
summer fossil
i hate the editorials
how many problem do u solved daily
cobalt mirage
how many problem do u solved daily
havent done any recently because of uni and job applications and stufetc
summer fossil
okay
regal spoke
Another thing you guys might not know about is that all problems on codeforces have a rating
cobalt mirage
ofc 💀
regal spoke
That rating is pretty good estimate for how difficult a problem is
cobalt mirage
i can't do <= 1200 rated problems which are mostly adhoc or observation questions 😭
regal spoke
The easy problems are around 800 to 1200.
I'm personally dont think training on problems like those are all that useful
summer fossil
i will start cp after completing graphs and dp!
regal spoke
The "good" problems start at like 1700 to 1900
cobalt mirage
I'm personally dont think training on problems like those are all that useful
I cant' even solve them 🤷♀️
I've done good amount of problems on leetcode aswell, but I can see why observation skills are bad
summer fossil
I've done good amount of problems on leetcode aswell, but I can see why observat...
I also solved on leetcode!
I like leetcode ui codeforce ui is horrible!
cobalt mirage
I am fine with the UI
i just suck at codeforces
whcih is what I wanna improve on anyways
summer fossil
u will improve one day!
regal spoke
Here is a fun problem if you want to challenge yourself https://codeforces.com/contest/221/problem/D
A lot of people I've showed it to said they liked it
It doesn't require knowing any advanced data structures or anything like that
But its rating is 1800, so it is still relatively difficult
summer fossil
Here is a fun problem if you want to challenge yourself https://codeforces.com/c...
Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers alj, alj + 1, ..., arj.
What this line want to say?
I need to count the occurence of number
like
input
7 2
3 1 2 2 3 3 7
1 7```
So
l = 1
r = 7
so start from l <=n:
and count the occurence
so start from r <=n:
and count the occurence
then return which has similar count occurenceor in range of l<r:
?
regal spoke
You'll be given m intervals
For each interval (l,r) you are tasked to count how many values x that occur exactly x times in A[l-1:r]
regal spoke
I need to count the occurence of number
like
```py
input
7 2
3 1 2 2 3 3 7
1 7`...
l=1 and r=7 here means that the interval covers the entire array.
1 occurs one time in the array
2 occurs two times in the array
3 occurs three times in the array
7 occurs one time in the array
So the number of values x that occur exactly x times in the array is 3 values
It is 1,2 and 3
summer fossil
Now I understand
nums = a[l:r]
Counter(nums)
print(len(Counter(nums)))
we can do this?
regal spoke
No, that would also count the 7
summer fossil
we need to exclude r?
summer fossil
we need to use minus 1 then
regal spoke
In python I read the l and r, and then subtract 1 from l
That gives me Python closed leftside open rightside style for describing intervals
l <= I < r
summer fossil
what is the right answer?
regal spoke
The solution is a little bit tricky, but not super difficult
summer fossil
rating of this problem?
regal spoke
It says in the bottom right
1800
Don't be deterred by the rating. If anything see it as a challenge
summer fossil
Good Advice!
cobalt mirage
@regal spokeis getting better at observation just purely come from practice?
the question I sent earlier took me a whole day to understand
😹
regal spoke
<@475657117509091329>is getting better at observation just purely come from prac...
That problem was just a basic math problem
The problem asked you to sum some things, so I summed them
fallow mortar
I am looking for leetcode prep buddy, Is anyone interested?
summer fossil
I am looking for leetcode prep buddy, Is anyone interested?
U can consider me
regal spoke
the question I sent earlier took me a whole day to understand
Btw that problem description for that problem is horrible. I honestly need to look at the example for it to make any kind of sense.
From the examples it looks like the score of an array is
def score(A):
n = len(A)
for i in range(n):
A[i] += max(A)
return sum(A)
So that is what I made a solution for
!e
def score(A):
n = len(A)
for i in range(n):
A[i] += max(A)
return sum(A)
# O(n^3)
def brute_solve(A):
n = len(A)
return [score(A[:i+1]) for i in range(n)]
# O(n)
def solve(A):
n = len(A)
out = []
prefix_max = A[0] # Could default to -float('inf'), but A[0] works too
prefix_sum = 0
prefix_isum = 0
for i in range(n):
a = A[i]
prefix_max = max(a, prefix_max)
prefix_sum += a
prefix_isum += i * a
out.append(prefix_sum * (i + 1) - prefix_isum + (i + 1) * prefix_max)
return out
A = [2,4,5,6,1,7]
print(solve(A))
print(brute_solve(A))
halcyon plankBOT
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
001 | [4, 16, 34, 60, 84, 121]
002 | [4, 16, 34, 60, 84, 121]
Something else I dont really understand is the point of modding by 10^9 + 7. Normally that is only done if the numbers grow really big. But that doesn't really happen here
The values in the output can be upper bounded by n * (sum(A) + max(A)), which is kinda small
gleaming pivot
Linear correct?
haughty mountain
wolfram alpha says that it is nlogn
which shouldn't be surprising
it's basically the same scenario you have with merge sort
just a bit lopsided
I think you can do the same analysis as you do for merge sort, just with some upper bounding
every layer still sums to n
you still have a logarithmic number of layers
lean walrus
it's basically the same scenario you have with merge sort
oh, i see
regal spoke
its quadratic
If it is O(n log n) then quadratic is a really bad name for it
regal spoke
Linear correct?
I would say linear since it is almost linear
But that is still a really bad description of it
However, it is a better description than quadratic
haughty mountain
I would say linear since it is almost linear
linearithmic
vernal girder
Alr, I had a problem previously, but I found a new angle of attack
This was the original problem, where I wanted to find a cheap algorithm to essentially create these diagrams to test whether a set of pairs would pass a certain test.
However, I found a new way to test the same thing.
Each pair of numbers connects to the other pairs that have a difference of 1 in either of their elements. (2, 11) and (3, 6), for example, would be connected because of the 2 and 3 (and would be so even if the 3 were the second element of the pair).
As it turns out, in a set that passes the test, there are as many “shapes” that can be made as the amount of pairs + 1, where no shape is a subset of another shape (not counting 2 pointed shapes, aka twins, which I will clarify)
A shape would be, for example, ((5, 12), (4,11), (3, 6)), because each point is connected to the next, AND, the fist and last points are connected as well. A twin is when, for example in ((9, 14), (10, 13)), both elements in each pair correspond with each other, in this case 9 to 10 and 13 to 14. These count as shapes, but do NOT break the subshape rule.
I’m trying to find the quickest way to count the amount of valid shapes who have no subshapes. After I do this, I can simply test it against len(sets) + 1
lean walrus
If it is O(n log n) then quadratic is a really bad name for it
Its in the margin of error
cobalt mirage
That problem was just a basic math problem
It was very hard for me imo
regal spoke
It was very hard for me imo
Btw where did you get the problem from?
cobalt mirage
Can you explain the process you went through to get to the right solution, I know the solution now, but I wanna know what your intuition was
regal spoke
So to begin with I'm not even sure that I've understood the problem correctly
The problem description is really bad
It is like the text says one thing, and then the example says something else
cobalt mirage
Yeah
But after you understood what the problem is asking
What was your intuition
regal spoke
Do you agree with me that the task is to compute ```py
def score(A):
n = len(A)
for i in range(n):
A[i] += max(A)
return sum(A)
I don’t think so
?
regal spoke
It agrees with the example
!e
def score(A):
n = len(A)
for i in range(n):
A[i] += max(A)
return sum(A)
print(score([1]))
print(score([1,2]))
print(score([1,2,3]))
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
001 | 2
002 | 8
003 | 19
Wait
def solve(n, A):
ans = [0] * n
mx, M, sum_, ssum = 0, 10**9 + 7, 0, 0
for i in range(n):
sum_ = (sum_ + A[i]) % M
ssum = (ssum + sum_) % M
print(sum_, ssum)
mx = max(mx, A[i])
ans[i] = (ssum + mx * (i + 1)) % M
return ans```This was similar to your optimal solution right
I thought this is what you did
regal spoke
!e
def solve(A):
n = len(A)
ans = [0] * n
mx, M, sum_, ssum = 0, 10**9 + 7, 0, 0
for i in range(n):
sum_ = (sum_ + A[i]) % M
ssum = (ssum + sum_) % M
print(sum_, ssum)
mx = max(mx, A[i])
ans[i] = (ssum + mx * (i + 1)) % M
return ans
print(solve([1,2,3]))
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
001 | 1 1
002 | 3 4
003 | 6 10
004 | [2, 8, 19]
Lmao
cobalt mirage
But this is not a brute force solution
The one I sent
Yeah
But I don’t agree with your brute force
I don’t get it
regal spoke
!e
def score(A):
n = len(A)
for i in range(n):
A[i] += max(A)
return sum(A)
# O(n^3)
def brute_solve(A):
n = len(A)
return [score(A[:i+1]) for i in range(n)]
# O(n)
def solve(A):
n = len(A)
out = []
prefix_max = A[0] # Could default to -float('inf'), but A[0] works too
prefix_sum = 0
prefix_isum = 0
for i in range(n):
a = A[i]
prefix_max = max(a, prefix_max)
prefix_sum += a
prefix_isum += i * a
out.append(prefix_sum * (i + 1) - prefix_isum + (i + 1) * prefix_max)
return out
def solve2(A):
n = len(A)
ans = [0] * n
mx, M, sum_, ssum = 0, 10**9 + 7, 0, 0
for i in range(n):
sum_ = (sum_ + A[i]) % M
ssum = (ssum + sum_) % M
#print(sum_, ssum)
mx = max(mx, A[i])
ans[i] = (ssum + mx * (i + 1)) % M
return ans
A = [2,4,5,6,1,7]
print(solve(A))
print(brute_solve(A))
print(solve2(A))
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
001 | [4, 16, 34, 60, 84, 121]
002 | [4, 16, 34, 60, 84, 121]
003 | [4, 16, 34, 60, 84, 121]
They all match
cobalt mirage
Nah I’m saying
Your brute force doesn’t make sense to me 😹
It’s probably right
Like why do max?
For every element
regal spoke
regal spoke
The text is really bad
cobalt mirage
Lol
regal spoke
From the example I'm guessing they actually mean max of the entire array
regal spoke
!e
def score(A):
n = len(A)
for i in range(n):
A[i] += max(A)
return A
print(score([1,2,3]))
But you got the right solution
halcyon plankBOT
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
[4, 6, 9]
How do you get to 4,6,9 starting with 1,2,3
regal spoke
Using prefix max gives the wrong result according to the example
!e
def score(A):
n = len(A)
for i in range(n):
A[i] += max(A[:i+1])
return A
print(score([1,2,3]))
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
[2, 4, 7]
Hmmm
cobalt mirage
!e
```py
def score(A):
n = len(A)
for i in range(n):
A[i] += max...
Because
Nvm
I mean
I’m shocked gimme a secon
In the example, they use prefix of the current subarray 🤔
@regal spoke
like
[1+2, 2+3]
regal spoke
[1+2, 2+3]
Why add 2 to 1 here?
cobalt mirage
because the prefix array is [1,2] and I add 2 which is the max of the subarray
regal spoke
But in that case, then the definition of score would be
def score(A):
n = len(A)
for i in range(n):
A[i] += max(A)
return sum(A)
Remember that we are supposed to score each prefix of the inputted array
So A here will be a prefix of the inputted array
cobalt mirage
!e def score(A): n = len(A) for i in range(n): A[i] += max(A) return A print(score([1,2,3]))
halcyon plankBOT
@cobalt mirage :white_check_mark: Your 3.11 eval job has completed with return code 0.
[4, 6, 9]
isnt the first eleemnt suppose to be 2?
regal spoke
The example says 4 6 9
cobalt mirage
thats the final array aint it tho
We're looking for all 3 subarrays
Oh this is just for the last one?
haughty mountain
ok yeah, the description doesn't match the examples
gleaming pivot
linearithmic
yeah that makes sense
well
it doesnt make sense that its wuadratic
but linear or linearthimic seems like the asnwwer
haughty mountain
but linear or linearthimic seems like the asnwwer
linear is not the answer
because it's not linear
gleaming pivot
lets say that the last term was something like 3n/5
regal spoke
Oh now we are multiple people talking in the same channel about different things
gleaming pivot
would it be lienar then?
cobalt mirage
what does this mean
haughty mountain
Oh now we are multiple people talking in the same channel about different things
so we use replies 😛
regal spoke
what does this mean
where is this from?
cobalt mirage
where is this from?
errichtos
regal spoke
what is "convert between the 2"
cobalt mirage
anyways, ignoire that
regal spoke
cobalt mirage
i wanna know your thought process from going from that "score calculation" to the optimal output
😹
gleaming pivot
or lets just say we remove the +n would it be lienar then?
regal spoke
or lets just say we remove the +n would it be lienar then?
then the algorithm would run in 0 time
haughty mountain
would it be lienar then?
no?
haughty mountain
or lets just say we remove the +n would it be lienar then?
something like
f(n) = f(n/2) + n
```would be linearif its like 100 = constant
if its 3n^3 its polynomial
if its 2n its linear
if its k^n its exponential
is how i undertand
haughty mountain
yeah?
gleaming pivot
so in this example it's n/5 n/5 +n
i would drop the constants like the 5
n + n + n
why does this fail to work?
haughty mountain
so in this example it's n/5 n/5 +n
how is it that?
haughty mountain
so in this example it's n/5 n/5 +n
this doesn't follow from the recurrence in the image
haughty mountain
you have some currently unknown function T
your goal is to try to figure out what that function is like
gleaming pivot
well we can plug in1. to n right?
haughty mountain
wdym?
regal spoke
what does this mean
I looked up the conversation. It has to do with the an implementation I made that got added into CPython (and PyPy) https://github.com/python/cpython/issues/90716 for converting strings (base 10) into Python's built in int (base 2). It is getting added into CPython 3.12
cobalt mirage
I looked up the conversation. It has to do with the an implementation I made tha...
didn't realize you were the first python gm 😹
haughty mountain
didn't realize you were the first python gm 😹
not in the current cf timeline :^)
cobalt mirage
yeh
regal spoke
Back to
def score(A):
n = len(A)
for i in range(n):
A[i] += max(A)
return sum(A)
The goal is to make some kind of formula for the answer
gleaming pivot
your goal is to try to figure out what that function is like
so should my goal be to figure out the runtime like in terms of big O(n), O(logn), etc?
cobalt mirage
The goal is to make some kind of formula for the answer
ok
Well, I could think of a bruteforce one, but not this way 🤔
but this bruteforce is just for one subarray
haughty mountain
so should my goal be to figure out the runtime like in terms of big O(n), O(logn...
T(n) is O(something) yes. you want to find that something
regal spoke
but this bruteforce is just for one subarray
ye but the idea is that we come up with a formula, and then we try to implement an O(n) algorithm using the formula
cobalt mirage
Okay
haughty mountain
T(n) is O(something) yes. you want to find that something
(or really Θ(something) if we want to be pedantic)
cobalt mirage
What was the next thought process or step you got to after this
haughty mountain
yeah
gleaming pivot
so if its o(logn) this function the answer would be linearithmic
agile sundial
that's just logarithmic
regal spoke
What was the next thought process or step you got to after this
Okey, so now notice that after A[0] += max(A) in the first iteration, on every succedent iteration max(A) will be A[i - 1]
gleaming pivot
yes n log n my bad
cobalt mirage
Okey, so now notice that after A[0] += max(A) in the first iteration, on every s...
True, I didn't realize this when I first attempted, what made you think that 🤔
Or it just came naturally lol
regal spoke
Adding max to something makes it bigger than the rest of the array
regal spoke
So lets now think about what happens.
This is what we have now
def score2(A):
n = len(A)
A[0] += max(A)
for i in range(1, n):
A[i] += A[i - 1]
return sum(A)
Yeah, it just adds the max from the left
haughty mountain
T(n) is O(something) yes. you want to find that something
some examples of what small changes to the recurrence can mean
T(n) = 2T(n/2) + n -> T is Θ(n log n)
T(n) = T(n/2) + n -> T is Θ(n)
T(n) = 4T(n/2) + n -> T is Θ(n²)
regal spoke
Yeah, it just adds the max from the left
Ye so lets see if we can find a formula for it.
Note that the intial max(A) will be "copied" n times
So we can do this
def score3(A):
n = len(A)
maxA = max(A)
for i in range(1, n):
A[i] += A[i - 1]
for i in range(n):
A[i] += maxA
return sum(A)
Do you agree that score2 and score3 are equivalent?
cobalt mirage
Is this just for one score right
regal spoke
Is this just for one score right
yes
That is what we are trying to make a formula for. Only after we have a formula do we try to solve the actual problem
cobalt mirage
So what I forgot is that why do we need max to be added to all the A[i]?
for one score 🤔
regal spoke
Look at score2
max(A) gets added to A[0] in the beginning
Then A[0] gets added to A[1], A[1] gets added to A[2], and so on...
regal spoke
This means that max(A) will effectively be added to A[0], A[1], A[2], ....
cobalt mirage
if we added it once, why do we need to do it again 🤔
regal spoke
Lets score A=[0,0,0,0,0,10,0] as an example (according to score2 function)
First step is to add max(A) to A[0], resulting in A = [10,0,0,0,0,10,0]
Then in the next iteration we add A[0] to A[1], resulting in A = [10,10,0,0,0,10,0]
This will continue until we get to
A = [10,10,10,10,10,20,20]
cobalt mirage
Yeah I agree with that
regal spoke
Do you see now how you effectively have added max(A) (the 10 in my example) to all indices of A?
cobalt mirage
wait a min
haughty mountain
||no it's a max||
cobalt mirage
aight bro
cobalt mirage
A = [10,10,10,10,10,20,20]
Yeah I understand this, this is score2 right
regal spoke
Yes
cobalt mirage
So why do we need to add max(a) * n again?
regal spoke
My example shows that we can wait until the end with adding maxA, but if we do that we need to add it to all indices
def score3(A):
n = len(A)
maxA = max(A)
for i in range(1, n):
A[i] += A[i - 1]
for i in range(n):
A[i] += maxA
return sum(A)
A[i] += maxA``` I am still confused why this needs to be here lolNote how there are a lot of 10s here A = [10,10,10,10,10,20,20]
cobalt mirage
If we are looking at just one iteration, this is essentially just adding the last index,
regal spoke
I see that as
[1 + maxA, 2 + (1 + maxA), 3 + (2 + (1 + maxA))]
So each index gets one copy of maxA
cobalt mirage
Yea
cobalt mirage
I see that as
[1 + maxA, 2 + (1 + maxA), 3 + (2 + (1 + maxA))]
I also agree with this
OH WAIT
iM DUMB
if we are in a new subarray
are we adding the new max n times thats why?
since the max hasn't been added previously?
regal spoke
It is equivalent to either add maxA to A[0] at the start, or wait until after the for loop and then add maxA to all indices
cobalt mirage
def score3(A):
n = len(A)
maxA = max(A)
for i in range(1, n):
A[i] += A[i - 1]
for i in range(n):
A[i] += maxA
return sum(A)```Oh yeah, thats what you were trying to show me here
I agree
regal spoke
Okey now we are almost done
First trivial step is to remove the 2nd for loop and just add n * maxA at the end
def score4(A):
n = len(A)
maxA = max(A)
for i in range(1, n):
A[i] += A[i - 1]
return sum(A) + n * maxA
Do you agree?
cobalt mirage
First trivial step is to remove the 2nd for loop and just add n * maxA at the en...
Yeah we agree
I think I pretty much understood it, and we do the sum of prefixsum because we can use the duplicates to recalculate the value
regal spoke
I think I pretty much understood it, and we do the sum of prefixsum because we c...
yes that is one way
Another is to use that this is a formula for score4
Which can be simplified to this
solid galleon
f(n) = ∑ n to 2n for i
can some one give a exact closed-form solution for this?
do i find for 0 to 2n and then 0 to n and then substract?
regal spoke
f(n) = ∑ n to 2n for i
can some one give a exact closed-form solution for this?
Do you mean sum of i for i = n to i = 2n ?
regal spoke
do i find for 0 to 2n and then 0 to n and then substract?
You can do that
solid galleon
is it 0 to 2n or 1 to 2n tho
regal spoke
Write it down on paper. It is easier that way
gleaming pivot
HAHAHA
this stuff is starting to make sense
i am horrible at math but im starting to be able to understand it
gleaming pivot
why did you do i - n + n
regal spoke
Because I wanted to do a change of variables
solid galleon
its doable but i dont find the purpose too
gleaming pivot
is your goal to get the 2n out of the top of the sum?
is that what you had in mind?
regal spoke
You can think of it like in the sum for i=n to 2n all terms have an extra n
solid galleon
the third step makes no sense to me please
regal spoke
If you subtract that you get a sum from i=0 up to n
regal spoke
the third step makes no sense to me please
Maybe I should have changed the name of the variable for the third step
woven mirage
sorry for the intrusion, but where could i learn to read these math symbols? I see this all the time on pages about algorithms and never could understand then
gleaming pivot
this one is called a summation
khan academy is good
also google images
is good
regal spoke
the third step makes no sense to me please
Maybe this will make more sense to you
woven mirage
do you recommend anywhere to learn algorithms and data structures? i use stuff like codewars and kattis but i'd like to hear more
regal spoke
It is a change of variable
from variable i
to j = i - n
i goes from n to 2n
j goes from 0 to n
regal spoke
do i find for 0 to 2n and then 0 to n and then substract?
Here is that calculation
solid galleon
if j = i - n
i = j+n
regal spoke
regal spoke
if j = i - n
i = j+n
ye
solid galleon
wait why is it n-1 instead of n for second summation
regal spoke
wait why is it n-1 instead of n for second summation
You need to subtract what is missing in the sum from n to 2n
If you think about it, you'll see that you need to subtract the sum from i = 0 to n-1
regal spoke
isnt it summation of i=0 to 2n minus i= 0 to n
No it is not.
Let us take n = 2 as an example
Then the sum from n to 2n is the sum of the numbers i = 2,3,4
The sum from 0 to 2n is the sum of the numbers i = 0,1,2,3,4
The sum from 0 to n-1 is the sum of the numbers i = 0,1
solid galleon
still trying to understand. i respect your help.
one sec
i think i'm too stupid?
regal spoke
i think i'm too stupid?
It just takes a while to get used to working with sums
solid galleon
No it is not.
Let us take n = 2 as an example
Then the sum from n to 2n is the ...
The sum from 0 to n is the sum of the numbers i = 0,1,2
regal spoke
The sum from 0 to n is the sum of the numbers i = 0,1,2
yes
problem is that 0+1+2+3+4 - (0+1+2) = 3 + 4
solid galleon
so whats the purpose of substrascting o to 2n minus 0 to n-1
maths class, i thought i learne it 0 to bigger minus 0 to smaller
regal spoke
so whats the purpose of substrascting o to 2n minus 0 to n-1
There is a nice and standard formula for sum of all intergers <= n
It is sum i from i = 0 to n = n * (n + 1)/2
solid galleon
It is sum i from i = 0 to n = n * (n + 1)/2
yes that uve used in the solution
i get it just the differnce part is confusing me
regal spoke
In the case of sum i = 0 to 2n, you can use the same formula, but you need to switch out n with 2n
So you get
sum i from i = 0 to 2n = 2n * (2n + 1)/2
The reason why I'm rewriting the initial sum as a difference of two sums
Is that we can use the standard formula for those two sums
regal spoke
do you recommend anywhere to learn algorithms and data structures? i use stuff l...
The two largest sites nowdays for competitive programming are codeforces and atcoder.
They are both really good sites if you want to challenge yourself and/or compete in competitions
If you just want to solve rather straight forward problems, then https://cses.fi/problemset/ is a really good website
Cses has a huge problem bank of "standard" problems.
For example they have a problem called Tree diameter where the task is just to calculate the diameter of a tree https://cses.fi/problemset/task/1131
solid galleon
The reason why I'm rewriting the initial sum as a difference of two sums
0:36
this is what i meant
cobalt mirage
@regal spoke Yo
could you check a solution for a question?
I wrote it up but not sure if its right
regal spoke
this is what i meant
Are you asking why splitting up sums into two sums is helpful in general?
cobalt mirage
do you recommend anywhere to learn algorithms and data structures? i use stuff l...
is codewars good?
regal spoke
could you check a solution for a question?
sure
cobalt mirage
You can perform any task from a list of n types in each second.
There must be at least x seconds between two consecutive tasks of the same type.
You can only perform one task at a time.
Given the number of task types (n), an array of task priorities, and values for x and y, you need to find the maximum possible sum of priorities achievable in y seconds.
For example, with n = 3, priorities = [3, 1, 2], x = 5, and y = 7:
In the first second, you perform a task of the 1st type, adding 3 to the sum.
In the second second, you perform a task of the 3rd type, adding 2 to the sum (total: 3+2=5).
In the third second, you perform a task of the 2nd type, adding 1 to the sum (total: 3+2+1=6).
In the fourth and fifth seconds, no tasks are performed, so the sum remains at 6.
In the sixth second, you perform a task of the 1st type again, adding 3 to the sum (total: 3+2+1+3=9).
In the seventh second, you perform a task of the 3rd type, adding 2 to the sum (total: 3+2+1+3+2=11).
So, the maximum possible sum of priorities achievable in 7 seconds is 11.
Another example, if you have tasks with priorities [2, 1, 3], and you have 'x' set to 2 and 'y' set to 3:
In the first second, you can choose to perform task 3, so the sum of priorities is 3.
In the second second, you choose to perform a task of type 1, adding 2 to the sum, making it 5.
In the third second, you can again choose to perform task 3, adding 3 to the sum, resulting in a final sum of 8.``` //first Soltuion
# output = 0;
# heap = [];
# time = 1;
# counter = 1;
# priority.sort();
# priority = reversed(priority);
# #3, 2, 1
# for n in priority:
# if counter > x:
# break;
# heap.append([1, -n]);
# counter+=1;
# heapq.heapify(heap);
# while time <= y:
# if time >= heap[0][0]:
# _, n = heapq.heappop(heap);
# output+=(-n);
# heap.append([time+x, n]);
# print(n, time, heap);
# time+=1;
# return output;
//second solution
# priority.sort()
# priority = priority[::-1]
# print(priority)
# total = 0
# amt = 0
# if len(priority) > x:
# total += sum(priority[:x])
# else:
# total = sum(priority)
# amt = (total) * (y // x)
# amt += sum(priority[:y % x])
# return amt```What are the limits on x and y?
cobalt mirage
What are the limits on x and y?
I am not sure about y limitation thats why I wrote the second solution
regal spoke
If the limit on x is small, then there are some really nice and short solutions to the problem
cobalt mirage
x <= 10^9
regal spoke
ew
cobalt mirage
let me know if my solutiosn look right
my second solution shouldn't be able to TLE but it might be wrong not sure
regal spoke
Your first solution is definitely pretty slow
cobalt mirage
Yeah, I think it would TLE, but I wasn't sure what Y would be
regal spoke
also
cobalt mirage
You are missing a - in the first solution
wym
regal spoke
it should be heapq.push
cobalt mirage
Oh sht
regal spoke
It should have -n
regal spoke
and heapq.heappush
regal spoke
Why?
oh
ah
nvm then
Btw you don't need ; at the end of lines in Python, thats a C++ thing
The only people I ever see using ; in Python are codegolfers
cobalt mirage
brb
woven mirage
is codewars good?
pretty good imo
cobalt mirage
The only people I ever see using ; in Python are codegolfers
What does that mean
cobalt mirage
Btw you don't need ; at the end of lines in Python, thats a C++ thing
I am used to it
regal spoke
!e
a = 1; b = 2
print(a,b)
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
1 2
You can use ; like this in Python
solid galleon
https://www.youtube.com/watch?v=3eC2V31-jcs
@regal spoke its a formula. i get it now thank u
regal spoke
But like no one uses it
Other than for that specific usecase, you shouldn't use ; in Python
solid galleon
I know that an algorithm with worst case time behavior of 3n doesnt takes
at least 30 operations for every input of size n=10.
but im having trouble understanding why
going through notes in class and just getting help from you all.
cobalt mirage
Does my second solution look good tho @regal spoke
regal spoke
Does my second solution look good tho <@475657117509091329>
No
cobalt mirage
Id it wrong
solid galleon
lets say input size = 10, if it takes 30 operation, it obv makes sense that the worst time behavior would be 3n 3*10 = 30
regal spoke
priority.sort()
priority = priority[::-1]
print(priority)
total = 0
amt = 0
if len(priority) > x:
total += sum(priority[:x])
else:
total = sum(priority)
amt = (total) * (y // x)
amt += sum(priority[:y % x]) # <-- This line is wrong
return amt
Oh
regal spoke
Suppose x is 10^9 and y = 10^8
Hmm maybe it still works because of how slicing works
Btw I think a much nicer way to code that 2nd solution is
priority.sort()
priority = priority[::-1]
print(priority)
if len(priority) > x:
priority = priority[:x]
amt = sum(priority) * (y // x)
amt += sum(priority[:y % x])
return amt
Thinking about it more, I think this actually is correct
regal spoke
You are doing things like priority[:10**9]
cobalt mirage
How
regal spoke
y = 10^9 - 1, x = 10^9
regal spoke
Then y%x = 10^9-1
cobalt mirage
But why would that cause an issue
regal spoke
Ye I don't think it is causing an issue thinking about it
cobalt mirage
But the idea of the solution would work for the question?
regal spoke
I think your solution is correct
cobalt mirage
Thanks 
regal spoke
priority.sort(reverse=True)
amt = sum(priority[:x]) * (y // x)
amt += sum(priority[:y % x])
return amt
Here is a codegolfed version / more compact version
😄
cobalt mirage
I still don’t know what codegolf is
cobalt mirage
```py
priority.sort(reverse=True)
amt = sum(priority[:x]) * (y // x)
amt += sum...
Thanks
regal spoke
Oh
regal spoke
I still don’t know what codegolf is
Check out #esoteric-python
It is trying to find solutions to problems using as few characters as possible
solid galleon
ig its like where more inbuilt functions are used?
for example reverse, sort, etcc
regal spoke
Using 1 character vaiable names is a good start
And abusing things in Python like or or 1<n!=f(n)
solid galleon
An algorithm with worst case time behavior of 3n takes
at least 30 operations for every input of size n=10. Justify your answer.
Please tell if if this is tru or false
regal spoke
1<n!=f(n) only calls f if 1<n
solid galleon
`1<n!=f(n)` only calls f if 1<n
in other wordds call fn if 1<n
regal spoke
in other wordds call fn if 1<n
yes
and that can be signifcantly shorter than trying to use an if statement
regal spoke
An algorithm with worst case time behavior of 3n takes
at least 30 operations fo...
I'm not sure what the exact definition is of worst case time behavior of 3n. However the answer is no since at least is going the wrong way
solid galleon
I'm not sure what the exact definition is of `worst case time behavior of 3n`. H...
yes but why do u think its no
i thought it true
regal spoke
Had it said at most instead of at least, then maybe the answer would be yes
solid galleon
yes but its at least
regal spoke
Ye and that is wrong
solid galleon
means if n=11, 3*11 = 33 which is larger than 30
regal spoke
Worst case is an upper bound on how many operations are needed
Meaning it should say at most and not at least
If n <= 234, then n is at most 234. <--- This is a correct statement
If n <= 234, then n is at least 234. <--- This is an incorrect statement
solid galleon
If n <= 234, then n is at least 234. <--- This is an incorrect statement
true
so this is justa logical question
if asked in a test, u would just logically answer it?
i dont understand how the professor wants us to answer these questions in a test. rn it justa an assignment
but if it was a test, answering it would be confusinh
lean walrus
i dont understand how the professor wants us to answer these questions in a test...
Thats just common sense
at least != at most
You cant swap words randomly
regal spoke
On a test I would circle at least and make a comment pointing to it saying, "Wrong! It should say at most and not at least."
cobalt mirage
@regal spokeThat question took me a lil longer than expected to solve
its mainly because of not reaidng the problems properly, do you have any advice reading the problem statement
regal spoke
its mainly because of not reaidng the problems properly, do you have any advice ...
Looking at the input constraints is usually really helpful
It helps you get a feel for the kind of solution you need to make
If both x and y could be 10^9, then you know that you will probably have to use something like y%x and y//x
cobalt mirage
Looking at the input constraints is usually really helpful
It wasn't the getting to the solution
it was more so about understanding the problem
When I read it orignially, I understood a different question lmao
quaint harbor
does this look like a sufficient sudocode to represent a tree data structure ? Since trees (unlike binary trees) can have more than one child, i have used a list to store the childrenclass Node: def __init__(self, data): self.data = data self.children = list()
regal spoke
does this look like a sufficient sudocode to represent a tree data structure ? S...
That would work.
The way I'm used to people storing a tree is as a list of lists
graph = [[] for _ in range(n)]
for u,v in edges:
graph[u].append(v)
graph[v].append(u)
Which representation you should use depends on what you are trying to do
If it is for implementing algorithms / competitive programming then I would advice using a list of lists
quaint harbor
That would work.
The way I'm used to people storing a tree is as a list of lis...
this is slightly confusing for me
regal spoke
cpers dont like pointerss do they
They definitely dont like object oriented programming
regal spoke
this is slightly confusing for me
The code I gave is for a tree without a root
cobalt mirage
this is slightly confusing for me
it looks like they're representing tree with an adjcency list
regal spoke
yes
cobalt mirage
this is slightly confusing for me
like dis
but as a list isntead.. etc
this might make it more confusing lmao
cobalt mirage
@quaint harbor if you're doing it for class or interviews, you might have to get used to the way you're trying to do it now
quaint harbor
but this is a graph and isnt a gragh fundamentally different form a tree as a tree is directed
cobalt mirage
all trees are a graph 🤔
regal spoke
A tree is just a graph that is connected and has no loops
quaint harbor
<@429902017587314689> if you're doing it for class or interviews, you might have...
i am preparing for interviews
cobalt mirage
i am preparing for interviews
Yeah, I suggest getting used to what you're doing imo, not sure if pajenegod would object to it lol
@regal spoke how would you do tries?
regal spoke
<@475657117509091329> how would you do tries?
Easiest way is as a list of dictionaries. The dictionary takes in a letter and outputs the index of the next node
cobalt mirage
I was thinking that for this instance
🤔
@quaint harbor ```py
class TrieNode:
"""A node in the trie structure"""
def __init__(self, char):
# the character stored in this node
self.char = char
# whether this can be the end of a word
self.is_end = False
# a counter indicating how many times a word is inserted
# (if this node's is_end is True)
self.counter = 0
# a dictionary of child nodes
# keys are characters, values are nodes
self.children = {}``` I was thinkin similar to this
i dont know if it would be any good in your instance
But like if they give you list of lists of x connected to y, I suggest doing it pajenegod's way
quaint harbor
i have not reached tries yet. i am yet to start binary trees (which i plant to do next). i will come back to this when i do tries
thanks
cobalt mirage
🙏
regal spoke
It really is just a matter of taste
quaint harbor
But like if they give you list of lists of x connected to y, I suggest doing it ...
yes list of lists makes a lot of sense
you can sort the lists easily and then insertions and deletions are quicker
cobalt mirage
It really is just a matter of taste
I think in my opinion, it depends on how the input is given, and its easier to convert one way to one representation over other ways 🤔
regal spoke
does this look like a sufficient sudocode to represent a tree data structure ? S...
One situation when this kinda fails is if you are given a list of edges and the index of the root of a tree.
quaint harbor
cpers dont like pointerss do they
are you refering to c++ coders ?
cobalt mirage
are you refering to c++ coders ?
i was also refering to how python uses class and objects to represent node pointers 🤔
idk
quaint harbor
One situation when this kinda fails is if you are given a list of edges and the ...
can you elaborate ?
cobalt mirage
im stupoid 🤷♀️
quaint harbor
i was also refering to how python uses class and objects to represent node point...
i think its cleaner
regal spoke
can you elaborate ?
Suppose the tree is made up of the edges
(1, 3)
(1, 2)
(4,1)
and the root is 2. Suppose you are given the tree on this format,
Then there is no easy way to store this tree as your node class
Really what I'm trying to say is that having an adjecency list can be preferable over a children list
cobalt mirage
@regal spoke do you participate in leetcode contests?
regal spoke
<@475657117509091329> do you participate in leetcode contests?
Never touched leetcode or g4g
cobalt mirage
🤔
quaint harbor
Really what I'm trying to say is that having an adjecency list can be preferable...
yes i get it now.
i am working on leetcode problems too but i have to check solutions very often
cobalt mirage
i am working on leetcode problems too but i have to check solutions very often
send link
regal spoke
send link
Btw have you thought anything about https://codeforces.com/contest/221/problem/D ?
The problem I sent yesterday
cobalt mirage
Btw have you thought anything about https://codeforces.com/contest/221/problem/D...
I haven't looked at it, I am currently doing math homework lol
quaint harbor
no. i am preparing notes. so what i do is, i go to leetcode and pick up a problem and then if i cant solve it i learn the data structure required. i need to learn binary trees for https://leetcode.com/problems/symmetric-tree/
cobalt mirage
and I gotta prepare for an OA 😭
quaint harbor
OA ?
quaint harbor
oh
cobalt mirage
You apply
OA -> interview or phone etc
perosnally, I feel like OAs are harder than interviews
Snowflake 🛌 all DP hards
@regal spoke i accidently saw rating and problem tag
🛌
regal spoke
<@475657117509091329> i accidently saw rating and problem tag
It is a really nice problem
It is very easy to make an O(n^2) solution. But actually solving the problem requires some thinking
cobalt mirage
Would this still be a 1800 now?
regal spoke
I think the rating on codeforces is pretty consistent in general, it doesn't matter if it is a new problem or an old problem.
cobalt mirage
no. i am preparing notes. so what i do is, i go to leetcode and pick up a proble...
For questions like these, you just need to know how to do dfs properly 😹
quaint harbor
For questions like these, you just need to know how to do dfs properly 😹
yes. getting to it.
cobalt mirage
stack solution probably tough 😭
regal spoke
I'm a big fan of bfs solutions in Python
cobalt mirage
deque is op
cobalt mirage
I'm a big fan of bfs solutions in Python
I have a question, i was struggling really hard on it
its a tree query quesrtion
Ignore the input for root, you might not like it 😹
regal spoke
Here is a bfs solution
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
leftbfs = [root.left]
for node in leftbfs:
if not node: continue
leftbfs.append(node.left)
leftbfs.append(node.right)
rightbfs = [root.right]
for node in rightbfs:
if not node: continue
rightbfs.append(node.left)
rightbfs.append(node.right)
return [node.val if node else None for node in leftbfs] == [node.val if node else None for node in rightbfs]
wait wtf
that doesn't even look like a conventional bfs
Stack BFS 💀
you're insane
regal spoke
Bfs is very easy to do for a binary tree like this
cobalt mirage
🛌
regal spoke
Just for loop and append
agile sundial
i usually go for the while Q: Q.popleft() etc
regal spoke
I'm not a big fan of doing that. There is so many nice things about not using a double ended queue
One of them is that the bfs is stored, so you can reuse it like I did above
cobalt mirage
Any thoughts on this pajene
regal spoke
Any thoughts on this pajene
I know how to easily do this with something called small to large merging running in O(n log n)
soft apex
@regal spoke do you practice BFS on pen and paper
What are some good tips@to improve at Bfs And drawing trees
I feel like it’s just pencil?
cobalt mirage
I know how to easily do this with something called small to large merging runnin...
no idea what that is lol
soft apex
It helps
cobalt mirage
https://usaco.guide/plat/merging?lang=cpp
I thought that question was bottom up dp ngl
usaco plat 😭
pajene how would you do it normally?
like without the knowledge of small to large merging
cobalt mirage
Thats what I tried to do, but implementation is hard to try to use it 😭
regal spoke
Then it is possible (but a bit tricky) to make a dfs solution starting from the root that when it arrives at some node queries[i], then it has enough information to solve query i in O(1) time
cobalt mirage
def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
m = {};
d = defaultdict(list)
for i, n in enumerate(queries):
m[n] = i;
output = [0]*len(queries);
def comp(node):
if not node:
return -1;
left = comp(node.left) + 1;
right = comp(node.right) + 1;
d[node.val] = [left, right];
return max(left, right);
comp(root);
def calc(node, val):
if not node:
return;
calc(root);
return output;``` i think i was tryna do what you're sayingbut couldn't finish
regal spoke
yes
cobalt mirage
thats why I said ignore the input earlier for root 😹 , but it's just a tree node (gives a object of class?)
regal spoke
def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
bfs = [root]
for node in bfs:
if node.left: bfs.append(node.left)
if node.right: bfs.append(node.right)
n = max(node.val + 1 for node in bfs)
depth = [0] * n
for node in bfs:
if node.left: depth[node.left.val] = deppth[node.val] + 1
if node.right: depth[node.right.val] = deppth[node.val] + 1
deepest_in_subtree = [0] * n
for node in bfs[::-1]:
d = depth[node.val]
if node.left: d = max(d, deepest_in_subtree[node.left.val])
if node.right: d = max(d, deepest_in_subtree[node.right.val])
deepest_in_subtree[node.val] = d
ans = [0] * n
for node in bfs:
if node.left:
d = deepest_in_subtree[node.right.val] if node.right else 0
ans[node.left.val] = max(d, ans[node.val] + 1)
if node.right:
d = deepest_in_subtree[node.left.val] if node.left else 0
ans[node.right.val] = max(d, ans[node.val] + 1)
return [ans[q] for q in queries]
I don't know, I just coded this right here in discord
cobalt mirage
lemme try
cobalt mirage
root =
[5,8,9,2,1,3,7,4,6]
queries =
[3,2,4,8]
Output
[4,3,4,2]
Expected
[3,2,3,2]```Ehm
cobalt mirage
The idea looks right tho lol
regal spoke
```Input
root =
[5,8,9,2,1,3,7,4,6]
queries =
[3,2,4,8]
Output
[4,3,4,2]
Expecte...
I dont know how to read this
cobalt mirage
wym
regal spoke
Is it a balanced subtree?
regal spoke
oh is it that tree
cobalt mirage
yea
regal spoke
oh I see now the error
def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
bfs = [root]
for node in bfs:
if node.left: bfs.append(node.left)
if node.right: bfs.append(node.right)
n = max(node.val + 1 for node in bfs)
depth = [0] * n
for node in bfs:
if node.left: depth[node.left.val] = deppth[node.val] + 1
if node.right: depth[node.right.val] = deppth[node.val] + 1
deepest_in_subtree = [0] * n
for node in bfs[::-1]:
d = depth[node.val]
if node.left: d = max(d, deepest_in_subtree[node.left.val])
if node.right: d = max(d, deepest_in_subtree[node.right.val])
deepest_in_subtree[node.val] = d
ans = [0] * n
for node in bfs:
if node.left:
d = deepest_in_subtree[node.right.val] if node.right else depth[node.val]
ans[node.left.val] = max(d, ans[node.val])
if node.right:
d = deepest_in_subtree[node.left.val] if node.left else depth[node.val]
ans[node.right.val] = max(d, ans[node.val])
return [ans[q] for q in queries]
Try this
regal spoke
My bug was that I didn't remove the root of the subtree when I was supposed to remove the entire subtree
regal spoke
was this trivial 4 u?
Kinda. Half of this was figuring out the weird input format
So many if left.node
cobalt mirage
i need to practice a problem
regal spoke
Btw this problem kinda shows how nice it is to use my bfs style of coding
You see how I only did one bfs, and then resued it 3 times
cobalt mirage
I legit dont know what you're doing with your bfs lmao
how is that even bfs shocks me
regal spoke
bfs = [root]
for node in bfs:
if node.left: bfs.append(node.left)
if node.right: bfs.append(node.right)
``` this is my bfs codeOnce I've computed bfs, I just reuse it over and over
cobalt mirage
😹
Ima ignore your bfs code 😭
I am sorry
can't think rn
@regal spoke Any advice on greedy problems?
like in general
lol
regal spoke
<@475657117509091329> Any advice on greedy problems?
use my bfs code
Greedy problems are mostly hard when you don't know that the solution is greedy.
Once you've realized that the intended solution is greedy, it is usually pretty easy to solve them
cobalt mirage
🤔
Actually, the question i am trying to do is greedy, but I can't think of a way to implement it
regal spoke
https://codeforces.com/gym/101623/attachments Btw this is a really good problem on greediness
Problem I, Installing Apps
polar lodge
anyone here ever had an interview that didnt have a DS / algo question?
agile sundial
yes, behavioral interviews are quite common
cobalt mirage
pajene, can you try this problem
There are n GPUs available, where the cost of the ith GPU is represented by array element cost[i]. Also, there are two arrays compatible1 and compatible2 each containing n integers, where each integer is either 0 or 1, representing the following:
If compatible1[i]= 1, then the ith GPU is compatible with cluster 1, else it is not compatible with cluster 1.
If compatible2[i]= 1, then the ith GPU is compatible with cluster 2, else it is not compatible with cluster 2.
The company wants to buy the GPUs such that there are at least a min_compatible number of GPUs compatible with each of cluster 1 and cluster 2.
Given n GPUs, an integer min_compatible, and three arrays cost, compatible1 and compatible2, find the minimum possible cost of GPUs such that there are at least a min_compatible number of GPUs compatible with each of cluster 1 and cluster 2.
Return -1 if it is not possible to buy the GPUs satisfying the above condition.
Example
Given, cost = [2, 4, 6, 5], compatible1 = [1, 1, 1, 0], compatible2 = [0, 0, 1, 1], and min_compatible = 2. Some of the ways of buying the GPUs are explained below:
Hence the minimum possible cost is 13.
I suck at implementing this lol
modern gulch
I suck at implementing this lol
My first take is: this is likely an np complete or hard problem, so coming up with a clever polynomial solution ain’t going to happen
cobalt mirage
My first take is: this is likely an np complete or hard problem, so coming up wi...
wym
watch @regal spoke solve it in 5 mins of trying lol
modern gulch
It’s easy to solve in exponential time
cobalt mirage
nah he finna get it in less than o(N^2)
modern gulch
Bet
modern gulch
There’s certainly a DP optimization here, might yield nlogn
cobalt mirage
nah
you can solve with greedy
i can think of a nlogn solution but I suck at implementation
and if you do dp, it will TLE
cobalt mirage
There’s certainly a DP optimization here, might yield nlogn
wait
modern gulch
Can you describe your nlogn?
cobalt mirage
nlogn dp solution?
modern gulch
Yah, I would expect
cobalt mirage
How would you get nlogn dp 🤔
modern gulch
Ok, so brute force is to try every combination, right? You’d find every combination from list 1 and every combination from list 2, and then every combination from 1 and 2 and calculate cost.
cobalt mirage
Yea
cobalt mirage
it would tle if you did knapsack dp
🤔
the constraint is n <= 2*10^5
What are you thinking for the states?
modern gulch
If n is small enough, why not greedy it? Start with CPUs in both?
cobalt mirage
In my opinion, not sure, it would TLE if your state is i and number of clusters for both
modern gulch
Or sort combinations from l1 and l2 by cost
cobalt mirage
How are you correlating small n to greedy 🤔 I am not sure
modern gulch
I wonder if there’s an optimization to prefer a ‘in both’ gpu if it’s ‘worth it’: if the next cheapest gpus cost less?
cobalt mirage
Yeah
modern gulch
Like, in that example: 6 made sense because it was cheaper than buying the two cheapest
cobalt mirage
I think you would take the cheapest non matching unless the matching is less than both of them added
🤔
modern gulch
Yes, this might actually end up polynomial, hmm
cobalt mirage
How would it not be polynomial? 🤔
modern gulch
Well, now I think so, but it felt like an np problem
cobalt mirage
modern gulch
Hah, yah, make a sorted list of prices of ‘in both’. Sort the remaining prices (in one) into l1 and l2. Pick the cheaper in both or the next item from l1 and l2. Continue until picked n.
Oh, altho I guess it’s still nlogn: since you have to sort.
cobalt mirage
Oh, altho I guess it’s still nlogn: since you have to sort.
Yep
I don’t know how you would do it dp and still achieve nlogn
modern gulch
Fun problem. I always like these ones with elegant solutions
cobalt mirage
Fun problem. I always like these ones with elegant solutions
def solve(cost, compatible1, compatible2, min_compatible):
if sum(compatible1) < min_compatible or sum(compatible2) < min_compatible:
return -1;
arr1 = [];
arr2 = [];
arr3 = [];
for i in range(len(compatible1)):
if compatible1[i] and compatible2[i]:
arr3.append(cost[i]);
elif compatible1[i]:
arr1.append(cost[i]);
elif compatible2[i]:
arr2.append(cost[i]);
arr1.sort();
arr2.sort();
arr3.sort();
i=0;
j = 0;
k = 0;
print(arr1);
print(arr2);
print(arr3);
total = 0;
while min_compatible:
if k < len(arr3) and i < len(arr1) and j < len(arr2) and arr3[k] <= arr1[i] + arr2[j]:
total+=arr3[k];
k+=1;
else:
total+=arr1[i]+arr2[j]
i+=1;
j+=1;
min_compatible-=1;
print(total, min_compatible)
print(total)```I was thinkin this
💀
modern gulch
The while loop won’t stop if there’s no solution?
Could vectorize some of this, like: adding arr1 + arr2 and just take from the head of the list
cobalt mirage
The while loop won’t stop if there’s no solution?
Well
modern gulch
Actually, could add arr1 plus arr2 into arr4 and sort arr4 + arr3, then just start at head of the combined list.
cobalt mirage
I already checked originally
modern gulch
I’m sure the best solution doesn’t create multiple lists anyway. Probably sorts cost but keeps position, and iterates over the two lists, and only needs to look ahead to cost = sum of the elements at current position
tacit charm
Honestly not sure where to put this. I was trying to take a hash of a unique function call (name, arguments) and was using hash((args, frozenset(kwargs.items()))) inside a decorator wrapper where args is the function. However that function lives in a class that regularly gets created and destroyed. I noticed each new instance creates a new hash. Is there anyway for the hash to check on uniqueness of the function name and parameters and ignore the parent class?
tacit charm
solved. Removed first entry from args to prevent instance level
haughty mountain
Problem I, Installing Apps
this is from our year?
regal spoke
this is from our year?
Yes
haughty mountain
My first take is: this is likely an np complete or hard problem, so coming up wi...
it's not at all
it's super greedy
-
split into three groups based on compatibility
both,first,second -
sort all of them by cost
-
greedily pick cheapest from
both, or the cheapest fromfirstandsecond(whichever is cheaper)
repeat 3 until you have enough
ah, you got to this solution later on
modern gulch
ah, you got to this solution later on
Took me a while, felt like knapsack at first glance!
haughty mountain
it's...some unweighted knapsack without any real constraints I guess?
regal spoke
1. split into three groups based on compatibility `both`, `first`, `second`
2. ...
Something that is helpful is to first remove unnecessary cards from first and second. That way you won't accidentally overbuy.
haughty mountain
how would you overbuy?
regal spoke
Depends on how you implement step 3
haughty mountain
for _ in range(n_needed):
# pick cheapest option...
You don't want to buy more than min_compatible cards from either first or second
haughty mountain
the point is you can pair up first and second
so any move (pick one from both, or one from each of first and second) gets you one closer to the target
regal spoke
Suppose there is a crazy amount of super cheap graphics cards only compatible with cluster 1
Then you need to avoid overbuying them
haughty mountain
you still need to bundle it with a cluster 2 only card
modern gulch
Then you need to avoid overbuying them
Doesn’t matter? Since… that (what fff said)
regal spoke
you still need to bundle it with a cluster 2 only card
Oh did I misunderstand the problem
haughty mountain
probably
modern gulch
You have two choices at each step: buy a card that’s compatible with only 1 and another card compatible with only 2, or buy a card compatible with both.
regal spoke
Oh ok
haughty mountain
tl;dr: you want to end up with a pool of gpus such that you could put min_compatible ones into either of the clusters
(not a pool that can satisfy both at once)
modern gulch
What rating is this problem anyway?
regal spoke
On cf I would guess like 1600
haughty mountain
1600 would be what? early to mid div2?
regal spoke
Yes
haughty mountain
sounds about right
regal spoke
Btw there is also a non greedy solution to this problem
For all k in [0, min_compatible] you could check the cost of buying k first and second cards and min_compatible - k double compatible cards
Then you return the minimal possible cost over all k
summer fossil
It comes from practice!
I am also suffering from this i solved so many problems and i can say i am improving!
regal spoke
I dont know what you want us to tell you. Practice makes perfect
The one advice I can give is to not be too fixated on solving a problem when practicing.
If it takes too long time, then it is fine to "cheat" and look up the answer.
Looking up other people's solutions can also be helpful, even if you've solved the problem
You can learn a lot from reading other peoples code
This is one of the reasons that I prefer using sites like codeforces, atcoder or cses.fi
On for example kattis you cannot look up other peoples solutions
polar lodge
what is the best ds/algo site yall use ?
polar lodge
I dont know what you want us to tell you. Practice makes perfect
this is so true , after like 20 easy problems you begin to get the hang of it, all interviews i failed was cuz i didnt do good on technical questions smh
vague maple
Hmm how do I display a DAG with multiple root nodes, with the following style: Each node is an oval, which fits text inside of it, stored in the 'name' property of the node map. Each child node has lines drawn to it's parents. The nodes are arranged spherically around the center nodes. The size of the node/text also decreases as the 'level' variable stored within the node's map increases.
regal spoke
Hmm how do I display a DAG with multiple root nodes, with the following style: E...
DAG with multiple roots? What is a root in a DAG?
About plotting graphs, I would advice using something like graphviz
vague maple
In all fairness my DAGs don't discriminate roots from other nodes. But it's a node on the 0th level, with no parents
vague maple
About plotting graphs, I would advice using something like graphviz
GraphViz can do DAGs?
vague maple
Oh nice
Issue is I'm not allowed to use external libraries for this project according to the bossman
vague maple
Basically we have to write it from core code, no imports
regal spoke
Basically we have to write it from core code, no imports
Then you cant even make an image
vague maple
Eh. I've done that much, albeit it was a pain
regal spoke
It makes no sense to do it absolutely from scratch
regal spoke
Dude, that cannot possibly be what the "bossman" wants
agile sundial
is this for a real job ?
regal spoke
Hmm how do I display a DAG with multiple root nodes, with the following style: E...
To me this sounds like instructions for making a graph in graphviz
vague maple
It is, but this is also in a non-python language based off python which doesn't have the graphviz library
Its very much like python code-wise, and since python is one of my core languages I figured I could just port the code over
Issue is we don't got those libraries
vague maple
I guess what I'm asking for is the code of the unix dot algorithm
oh wait no I'm needing twopi
modern gulch
Graphviz is the goat
And graph layout algorithms are -hard-: there’s a reason why nobody has replaced graphviz with something better, and it’s not lack of trying
vague maple
Yeah, I'm seriously considering porting this over to python and just doing it from there
prime oar
Please support a friend, who’s writing a Cartesian Tree on assembler
cobalt mirage
On cf I would guess like 1600
this greedy problem 1600?
cobalt mirage
1. split into three groups based on compatibility `both`, `first`, `second`
2. ...
Can you explain the intutition behind how you approached it?
shadow glen
is there a python librar where i can work with lists with more efficience
do anyone knows one?
lean walrus
is there a python librar where i can work with lists with more efficience
numpy?
regal spoke
is there a python librar where i can work with lists with more efficience
Numpy or you could also try using PyPy.
PyPy is fast Python intepreter. One feature in it is that lists that only contain small integers (fits in a signed long long), will be stored compectly in memory (like using vector<long long> in C++).
shadow glen
and for a list that contains a list of dictionaries?
regal spoke
and for a list that contains a list of dictionaries?
Well that changes things a bit.
When you said efficient, did you meam more memory efficient?
Or faster running?
regal spoke
You could try out PyPy.
regal spoke
https://www.pypy.org/ PyPy is its own program
shadow glen
thought in replit i can only install stuffs through shell/cmd
regal spoke
I've got no experience with replit so I cant help you with that
vague maple
I'm getting this error with graphViz:
> proc = subprocess.run(cmd, **kwargs)
> File "", line 403, in run
> with Popen(*popenargs, **kwargs) as process:
> File "", line 707, in __init__
> restore_signals, start_new_session)
> File "", line 992, in _execute_child
> startupinfo)
> FileNotFoundError: [WinError 2] The system cannot find the file specified
>
> The above exception was the direct cause of the following exception:
>
> Traceback (most recent call last):
> File "C:\Users\mthom\PycharmProjects\pythonProject\main.py", line 36, in <module>
> GlobalGraph.view()
> File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\_tools.py", line 172, in wrapper
> return func(*args, **kwargs)
> File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\rendering.py", line 183, in view
> cleanup=cleanup, quiet=quiet, quiet_view=quiet_view)
> File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\_tools.py", line 172, in wrapper
> return func(*args, **kwargs)
> File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\rendering.py", line 119, in render
> rendered = self._render(*args, **kwargs)
> File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\_tools.py", line 172, in wrapper
> return func(*args, **kwargs)
> File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\backend\rendering.py", line 320, in render
> capture_output=True)
> File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\backend\execute.py", line 88, in run_check
> raise ExecutableNotFound(cmd) from e
> graphviz.backend.execute.ExecutableNotFound: failed to execute 'dot', make sure the Graphviz executables are on your systems' PATH```graphbiz executables?
import graphviz
FeatIndex = {}
GlobalGraph = graphviz.Graph('GlobalGraph', filename='process.gv', engine='sfdp')
#Adds a node to the DAG
def AddFeat(name, parents, descr, prereqs):
level = 1000
if len(parents) > 0:
for i in parents:
parent = FeatIndex.get(i)
level = min(level, parent.get('level'))
else:
level = 0
level = level+1
newFeat = {}
newFeat['name'] = name
newFeat['parents'] = parents
newFeat['description'] = descr
newFeat['prerequisites'] = prereqs
newFeat['level'] = level
newFeat['children'] = []
if len(parents) > 0:
for i in parents:
parent = FeatIndex.get(i)
GlobalGraph.edge(name, i);
parent.get('children').append(name)
FeatIndex[name] = newFeat
# Press the green button in the gutter to run the script.
if __name__ == '__main__':
print('PyCharm')
while True:
GlobalGraph.view()```idk if I have anything other than "this greedy thing is obviously optimal"
cobalt mirage
idk if I have anything other than "this greedy thing is obviously optimal"
Wym
haughty mountain
to me it's just obvious given the problem
you can't buy something just for one cluster
you need to eventually pair it up with a card for the other cluster
so you have two choices, get a card that works for both, or one of each other kind
cobalt mirage
Yeah
cobalt mirage
I understand that but
But how did you think about the implementation part
Like you said 3 array right
haughty mountain
I need some way of repeatedly looking at the minimum of all three types
the simplest way I can think of is splitting into three lists and sorting them
cobalt mirage
Yeah
I was thinking of implementing it with a single array but I couldn’t impermanent it well enough
modern gulch
Graphviz is a executable that you install, separate from the Python wrapper
vague maple
Yup I realized that
modern gulch
```py
import graphviz
FeatIndex = {}
GlobalGraph = graphviz.Graph('GlobalGraph',...
You have to download and install it separately
vague maple
is there a way to view the graph in a live manner from python
modern gulch
No, it generates static images
I mean, you can do whatever you want with the images tho
vague maple
True that. Is there a graph style that has central 'nodes' and then scales things as smaller the farther they are from those central 'nodes'?
modern gulch
I dunno, you’d have to set the node sizes yourself I think
lilac cradle
is there an algorithm to fill a plane?
like say i have a few points that represent the vertices, is there an algo that will give points of that plane (ideally like grid-aligned points)
like bresenham's line function but for a 2d space
like if you wanted to, say, figure out all the points you'd place a block if you made a 3d shape in mc or something
vague maple
like standard distance field functions?
https://www.shadertoy.com/view/cldSzf
Like this, except you can convert the math out
quasi tree
Hi Does python support dynamic and static programming
modern gulch
What do you mean by static programming? @quasi tree
fiery cosmos
Hi Does python support dynamic and static programming
Python is dynamic program!!!
vague maple
How do I track the size and location in an image of the ovular nodes created by graphViz, as well as the text inside said ovals?
this probably gets into some light image recognition at easiest, doesn't it
vague maple
is there a quick function to return the index of a value in a list, if it exists, and -1 or something telling if it does not have said value?
modern gulch
is there a quick function to return the index of a value in a list, if it exists...
See index here: https://docs.python.org/3/tutorial/datastructures.html
open mirage
Is there anyone here which are working on image processing
vague maple
Warning: Overlap value "prism" unsupported - ignored
dot: graph is too large for cairo-renderer bitmaps. Scaling by 0.0017855 to fit
Traceback (most recent call last):
File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\backend\execute.py", line 95, in run_check
proc.check_returncode()
File "C:\Users\mthom\AppData\Local\Programs\Python\Python36-32\lib\subprocess.py", line 369, in check_returncode
self.stderr)
subprocess.CalledProcessError: Command '['dot', '-Kfdp', '-Tpng', '-O', 'unix.gv']' returned non-zero exit status 3221225477.
During handling of the above exception, another exception occurred:
Traceback (most recent call last):
File "C:\Users\mthom\PycharmProjects\pythonProject\main.py", line 86, in <module>
GlobalGraph.view()
File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\_tools.py", line 172, in wrapper
return func(*args, **kwargs)
File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\rendering.py", line 183, in view
cleanup=cleanup, quiet=quiet, quiet_view=quiet_view)
File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\_tools.py", line 172, in wrapper
return func(*args, **kwargs)
File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\rendering.py", line 119, in render
rendered = self._render(*args, **kwargs)
File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\_tools.py", line 172, in wrapper
return func(*args, **kwargs)
File ```"C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\backend\rendering.py", line 320, in render
capture_output=True)
File "C:\Users\mthom\PycharmProjects\pythonProject\venv\lib\site-packages\graphviz\backend\execute.py", line 97, in run_check
raise CalledProcessError(*e.args)
graphviz.backend.execute.CalledProcessError: Command '['dot', '-Kfdp', '-Tpng', '-O', 'unix.gv']' returned non-zero exit status 3221225477. [stderr: b'Warning: Overlap value "prism" unsupported - ignored\r\ndot: graph is too large for cairo-renderer bitmaps. Scaling by 0.0017855 to fit\r\n']
How do I fix this?
The graph contains roughly 3,800 nodes but that's non-negotiable
languid heron
```py
import graphviz
FeatIndex = {}
GlobalGraph = graphviz.Graph('GlobalGraph',...
Typically you should have the Graphviz executable in your PATH, idk for sure but i dont beliece pip installing will install the executable. if you have cmdline access try typing "dot" and seeing if there is output.
example: "echo 'digraph { a -> b }' | dot -Tsvg > output.svg"
pearl bane
guys
recently i installed anaconda so that i could work with .ipynb archives
but when i try to run python codes on a new file it doesnt run
i tried to install a environment manager but even tho i try to set a different one it doesnt run sucessfully
vague maple
Typically you should have the Graphviz executable in your PATH, idk for sure but...
graphviz is in PATH
graphviz works for smaller graphs, this is entirely a size issue since it breaks only if I try to make it render all 3,800 nodes
outer rain
graphviz works for smaller graphs, this is entirely a size issue since it breaks...
considering that it returns 0xC000005 it might be out-of-memory
in which case, you can't do anything other than get more ram
vague maple
oof yeah
which means I'd need another mobo and cpu since this old thing is running ddr3
outer rain
can you use another layouting algorithm?
outer rain
try sfdp
vague maple
for i in FeatIndex:
feat = FeatIndex[i]
parents = feat.get('parents')
newParents = parents;
if len(newParents) > 0:
for j in parents:
_feat = FeatIndex[j]
_par = _feat.get('parents')
if len(_par) > 0:
for p in _par:
found = False;
for l in newParents:
if l == p:
found = True;
if found:
newParents.remove(p)
for k in newParents:
GlobalGraph.edge(k, i)
How do I reduce the time this takes?
Essentially:
It is removing the parent, _feat's parents from the parents list of the current feat, feat, and then adding just the new parents to the graph
thorn mesa
do i need to learn html and css before streamlit ?
shadow glen
ERROR discord.app_commands.tree Ignoring exception in command 'create'
Traceback (most recent call last):
File "/home/runner/RP-Utilities-Beta/.pythonlibs/lib/python3.10/site-packages/discord/app_commands/commands.py", line 827, in _do_call
return await self._callback(self.binding, interaction, **params) # type: ignore
File "/home/runner/RP-Utilities-Beta/RP-Utilities-Beta/cogs/CharactersCog.py", line 132, in _character_default_create_slash
response = "Error, the character with this prompt already exist." if await self.client.database.register_default_character(user_id=user, name=name, prompt_prefix=prompt, image=url) else "Character created."
File "/home/runner/RP-Utilities-Beta/RP-Utilities-Beta/rpu_database.py", line 394, in register_default_character
db['characters'] = pivot | database
TypeError: unsupported operand type(s) for |: 'ObservedDict' and 'dict'
ObservedDict and dict incompatible
what is observed dict?
solemn moss
type of data stored in pivot variable
!e
class ObservedDict: ...
pivot = ObservedDict()
database = {}
pivot | database
@solemn moss :x: Your 3.11 eval job has completed with return code 1.
001 | Traceback (most recent call last):
002 | File "/home/main.py", line 6, in <module>
003 | pivot | database
004 | ~~~~~~^~~~~~~~~~
005 | TypeError: unsupported operand type(s) for |: 'ObservedDict' and 'dict'
maybe it's from this library but it can be from anywhere
https://pypi.org/project/observedstruct/
languid heron
site says it requires py <= 3.10
solemn moss
then it's not from here
languid heron
is there anyway to get the discord bot to run on a lower python version?
solemn moss
you can run it on any version
i guess you mean some special api wrapper
then you'd need to find another one
or write bot without wrappers, just with requests
languid heron
you can run it on any version
i guess you mean some special api wrapper
oh just that you ran the previous class, but the bot returned "your 3.11 eval job" and a type error. after looking at the pypi link you posted it showed it wouldnt run on 3.11. nothing more, sorry.
mild cosmos
#1151541891708485722 message I think my problem should fall in this channel as well
vernal girder
I’m interested in finding a program to test the opaque set problem. https://en.m.wikipedia.org/wiki/Opaque_set
Right now I don’t want a program that finds short opaque sets, just one that can tell whether a given set of lines is in fact an opaque set for a given area
vernal girder
I think to start off, I would need to find all “m” and “b” where the line “y = mx + b” crosses through a square who’s length is 1 and who’s center is at the origin
(Assuming that is the area I want to test)
modern gulch
I think to start off, I would need to find all “m” and “b” where the line “y = m...
Or, the lazy approach: render the top layer in a different color, and see if the underlying color is visible.
Maybe 20 minutes with cairo or canvas 🙂
vernal girder
Not quite
modern gulch
(or maybe i dont understand the q)
vernal girder
The Wikipedia article explains it better, but a set is an opaque set of an area if there is no line that can be drawn that passes through the area without also passing thru one of the lines in the set
The set is just a group of line segments
modern gulch
hmm, not anything i know anything about, I've been wondering if there's some sort of graphical/visual approach to this.
(besides just testing all lines of sight)
vernal girder
To start with, the set of all lines that pass through the target area is given here:
y = mx + b
Where -1 >= m >= 1, and
-(abs(m)*0.5 + 0.5) >= b >= (abs(m)*0.5 + 0.5)
There’s a reason we don’t need any value m above 1 or below -1, but I can explain in more detail if anyone wants to pick this up to give it a shot
summer fossil
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
n = len(arr)
s=i=0
j = 0
q=[]
while i<n:
q.append(arr[i])
if len(q)%2!=0:
s+=sum(q)
if i==n-1:
i=j
j+=1
q = []
i+=1
return s
```
Time complexity o(n!)?What’s this?
main bison
```py
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int...
what makes you think its n! ?
summer fossil
what makes you think its n! ?
value of firstly iterate i=n -1then iterate again from i+1,....i=n-1
main bison
time complexity is about how things change when you scale the input up
user input is the size of the list
when you increase the sice of the list n , your while loop will get n longer
what more inside your while loop scales up?
summer fossil
time complexity big(o(n))
n+n-1+n-2,....1
?
main bison
not sure why you are just throwing things out. what more scales up?
the while loop scales up by n
if you double the length of the list, you double the length of the while loop
is that part clear?
summer fossil
yeah!
main bison
so what more scales up by the sice of the array?
summer fossil
O(n**2)?