algos-and-data-structs

[solemn moss]

Like we have A+A+A
so 3 A
then C = [(1, 1), (2, 1)]?

That wouldn't be correct

[regal spoke]

Assume you are allowed to chose between 0 and up to 3 copies of A

[solemn moss]

Probably I explained the task bad

I will start from the beggining without something extra

So we have a math expression like (A+A)-B+100
(with only +, - and brackets)

Each variable can take any value in range [1..10]
How many different values can we get as a result

So the stupid solve would be liike

s = set()
for a in range(1,11):
 for b in range(1,11):
  s.add(eval(expr.replace("a",a).replace("b",b)))
print(len(s))

[regal spoke]

The problem becomes a lot nicer if the values are in range [0,..,9]

Then it would become the "classical" version of this problem

[solemn moss]

That doesn't really change something I believe

[regal spoke]

It does

The trick I talked about

Only works if the range starts at 0

[solemn moss]

ah, maybe

[obtuse brook]

Hey, everyone 👋 New to DS & Algorithms. So I was studying the time complexities of list operations. According to https://www.pythonmorsels.com/time-complexities/, the time complexity for a list.insert operation was O(n). So I wanted to visualize that using a graph.

I wrote the following script to do it (using matplotlib for plots).

import time
from typing import List

import matplotlib.pyplot as plt

def construct_list(size: int) -> List[int]:
    return [i for i in range(0, size)]

element = 4
time_taken = []

list_size = 50000

for size in range(1, list_size):
    target_list = construct_list(size)

    start_time = time.process_time()

    target_list.insert(0, element)

    end_time = time.process_time()
    time_taken.append(end_time - start_time)

plt.plot(
    range(1, list_size),
    time_taken,
)
plt.xlabel("Size of list")
plt.ylabel("Time (sec)")
plt.grid()
plt.xlim(0)
plt.title("Complexity of list.insert() operation")
plt.show()

I was expecting a linearly increasing chart, but I got the following chart.

Any idea why this is ?

Thanks for any help on this !

[outer rain]

Because you are measuring an event so fast, there is not enough time resolution to measure it precisely. On windows time.time() only updates each 15ms, so there are multiple inserts between the updates. You should use timeit module for benchmarks like these instead, or at least do multiple inserts, or try measuring something else like cpu cycles, or idk. Time is hard.

[obtuse brook]

Thanks. I am able to see an approximate linear curve if I replace time.time() with timeit.timeit instead.

[haughty mountain]

time.perf_counter if you don't want to use timeit

[pure loom]

I can't add the ta-lib library in python. Can anyone help?

[raw zealot]

@regal spoke (sorry for mention) is there a range update (lazy) segment tree in that pyrival repo

i see add in the lazy one

wait i can just make another exact method but set it to the value

[regal spoke]

Yeah you'll have to modify it if you want some other feature

[raw zealot]

got it 👍

[final night]

does anyone the best resource to practice regex? preferably with solutions and explanations?

I'm using regex101 but it's just telling me that my solution is horribly long

[raven dagger]

help
this might be more math tho

question:

Given a number n (n <= 10^6), and k, find the amount of numbers between 1 -> n that have exactly k factors```

cant think of anythink rn pls give some hints

[narrow mica]

use a sieve

[raven dagger]

hmm

how'd that work

[narrow mica]

sieve for the number of divisors of each number between 1 and n, then just count how many of those equal k

[narrow mica]

@raven dagger

[raven dagger]

ye

[narrow mica]

well... do you get it?

[raven dagger]

uhhhhhhhhhhhm

[raven dagger]

do i just

get an array

and factors[i] = len(factorize(i))

[narrow mica]

no, you use the sieve to find the number of divisors, then after the sieve you can do a simple loop and check how many of them equal k

[raven dagger]

[narrow mica]

do you know what I'm refering to when I say 'sieve'?

[raven dagger]

kinda

filtering?

[narrow mica]

no, it's a specific algorithm (the sieve of eratosthenes) that was originally for finding all prime numbers between 1 and n
you can augment it so it instead finds the number of divisors for all numbers between 1 and n

[raven dagger]

o the prime sieve

hold up

OH I GET IT

[raven dagger]

omfg tysm

[narrow mica]

seems like you got it
gl implementing

[raven dagger]

so like

def sieve(n: int) -> list[int]:
    factors = [2] * n
    factors[0] = 0
    factors[1] = 1

    for i in range(sqrt(n)):
        for j in range(i * i, n, i):
            factors[j] += 1

    return factors``` right?

omfg

[narrow mica]

well, almost

        if factors[i] != 2:
            continue
```you can't do that, e.g. `6` is also a factor of `12`

[raven dagger]

oh yeah

[narrow mica]

you probably also can't stop at sqrt(n), e.g. 12 is a factor of 36
and also remember that range(n) stops at n-1

[raven dagger]

😭

[narrow mica]

complexity's still like n log n even if you went to n instead of sqrt(n) though
so you should be fine in that regard

[raven dagger]

true

[dusky creek]

Henlo

Looking at the pins rn

I've been considering following this though, anyone tried it and has opinions?
https://goalkicker.com/AlgorithmsBook/

[barren void]

I had a bit of a broad question. I am testing A* and Dijkstra on a grid structure and testing their efficiency with different obstacle probabilities. The question is, should the time difference and nodes explored difference not be less significant if the obstacle probability is higher?

[half owl]

why is this O(2^n)?

intuitively it has to be 2n at most operations

comparing n digits from both k and m

full code implemention (came after the explanation)

[regal spoke]

2^(n-1) <= min(k,m) < 2^n

[half owl]

2^n = min(k,m) at worst
that i follow

now what?

itll be an easy O(1) if both are the same size

[regal spoke]

Definition of n is "number of bits in min(k,m)"

[half owl]

oh wait

no it wont

735 and 221 both are 2^3

[half owl]

okay i follow go on

it isnt time complexity

just the amount of bits

also not true

thats the max value possible

there are n bits at most

comparing these bits is at most 2n operations like i said

nothing here is exponential

[regal spoke]

n = floor(log_2(min(k,m))) + 1

n is the log of min(k,m)

[half owl]

and that is?

[regal spoke]

so if something runs linear in min(k,m)

it runs exponential in n

[regal spoke]

number of bits in min(k,m)

[half owl]

it's just n, min(k,m) would also at worst just be n

[half owl]

this

is just values

not lengths

[regal spoke]

735 in base 2 is

1011011111

[half owl]

okay now i see it

[regal spoke]

10 bits

[half owl]

that i dont understand

(base 2 n) amount of iterations is understandable now

[regal spoke]

Think of 2^n as the same thing as min(k,m)

They might be a factor of 2 off from eachother

So they are not identical

but almost the same thing

[half owl]

but thats not true

[regal spoke]

Take this example: 735 in base 2 is 1011011111 (10 bits)

[half owl]

n is just the amount of digits in the min, which we will for this purpose look at in base 2 rather than base 10 for some reason

[regal spoke]

2^10 = 1024 (11 bits)

[half owl]

okay

[regal spoke]

735 and 1024 are roughly the same

They lie within a factor of 2 from eachother

[half owl]

i just dont understand

i dont see the implications here

[regal spoke]

Take this massive number 123456789123456789

In base 2 represeentatiom, it gas 57 bits

2^57 = 144115188075855872

[half owl]

okay that i understand

[half owl]

dont you mean? 2^58 as in an upper bound

for the value of the number

[regal spoke]

Stop thinking about bounds

123456789123456789 is roughly 2^57

[half owl]

yes

so how come

2^57 = 144115188075855872 is bigger than something in base 57 bits represenation?

are some left-most digits 0?

it's a bigger number than the original for no reason as i see it

[regal spoke]

2^56 <= 123456789123456789 < 2^57

[half owl]

okay that i follow (that number is probably 56 bits in size)

[regal spoke]

Both 2^56 and 2^57 are good estimates for 123456789123456789

[half owl]

well i dont see where you're going with this

[regal spoke]

For the purposse of big O analysis, it doesnt matter if you use 123456789123456789 or 2^56 or 2^57

[half owl]

okay lets continue then

[regal spoke]

The slow gcd algorithm runs in:

O(min(k,m)) time

and also

O(2^n) time

and also

O(2^(n-1)) time

[half owl]

okay

well worst case is
both k and m are n bits/digits

and division is done twice in each iteration, division will always be here O(n) right?

so since the iterations are from n to 1 or 0 including

those are n iterations, which each iteration executes 2*O(n) operations

[regal spoke]

They assume division is O(1).

[regal spoke]

there are 2^n iterations

[half owl]

but there are only n options for common dividers

1<=divider<=n

[regal spoke]

Look here

[half owl]

we just need to check n options (n iterations)

[regal spoke]

This is a for loop

[half owl]

true

we assume 1 is the common divisor (worst case)

[regal spoke]

That in worst case runs for min(k,m) iterations

[half owl]

yeah exactly!

[regal spoke]

i.e. 2^n iterations

[half owl]

yes, since 2^n is the upper bound for the value of the min(m, k) right? since it has n digits

[regal spoke]

It is more than just an upper bound

really you should think of 2^n = min(m,k)

[half owl]

it's not possible i think?

[regal spoke]

You are completely missing my point

[half owl]

as in for every n digit number in base 2 represantion:
2^n <= value < 2^n+1

[regal spoke]

I'm not claiming that min(m,k) is a power of two

[half owl]

then what is it?

[regal spoke]

min(m,k) could be any number

[half owl]

although it should be to get a ~approximation of the number of iterations

[regal spoke]

However, 2^n is always going to be close to min(m,k)

[half owl]

so long it has n digits right?

[regal spoke]

n is defined as the number of bits of min(m,k), yes

[half owl]

oh because we dont care if it's 2^n or 2*2^n right?

[regal spoke]

yes exactly

[simple dove]

hmm

[half owl]

the minimum value that satisfies n digits will in any case be the worst case time complexity, others will just be it and a multiplication of of some constant c

which is negligble

[regal spoke]

For big O analysis, 5 * min(k,m), 1000*min(k,m), min(k,m) or 2^n are equivalent

[half owl]

yes i see it now, i just had a very had time understanding why O(2^n) is possible but now i understand it completely i think

thank you very much mate for your help

[raw zealot]

    def add(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] += value
                self.data[start] += value
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] += value
                self.data[stop] += value
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy - 1)

    # make range_update same as the add method if you want to set the value instead of adding
    def range_update(self, start, stop, value):
        """lazily set value to [start, stop)"""
        start += self._size
        stop += self._size
        start_copy = start
        stop_copy = stop
        while start < stop:
            if start & 1:
                self._lazy[start] = value
                self.data[start] = value
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] = value
                self.data[stop] = value
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy - 1)

this probably has some bug lmao

[regal spoke]

Exactly what operations do you want to support?

[raw zealot]

just overwrite a range with the given arg

[regal spoke]

so for modification query you want to set a range with a specific value?

[raw zealot]

yes

[regal spoke]

And for the question query?

Return the sum on a range?

[raw zealot]

actually i only need point query

so the function doesnt matter

[regal spoke]

Well then you shouldnt do lazy to begin with

[raw zealot]

[l-1,l)

oh

so i should probably do this range update in normal segtree

[regal spoke]

Here is the trick for what you are doing:
Everytime you want to modify something, have an list called modification_at_time

In this list, store the value you want to modify to

The trick now is that you can use indices to modification_at_time inside your segment tree

Allowing you to use a max segment tree

[raw zealot]

ah max for time

got it

interesting tq

[regal spoke]

Btw there is a general segment tree that supports this which is useful from time to time.
Suppose you allow modify queries of the form (a,b)
x -> a * x + b

If you set a = 0 then you get your set query.
If you set a = 1 then you get add queries

I've considered adding this to pyrival since it could be used to solve tons of problems

[raw zealot]

strong

i like this

generic

[regal spoke]

Yes, but noticably slower than the less generic versions

[raw zealot]

this is the lambda function we are talking about right

which we will pass

[regal spoke]

Not really

Supporting general lambas would be impossible probably

You need to hard code in which operations you want to support

[raw zealot]

makes sense

[regal spoke]

The operation
lambda x: a * x + b
turns out to be nice

Both for normal segment tree, and for a lazy segment tree

[raw zealot]

actually

pretty handy

[regal spoke]

Sometimes there are even more things people add to this

I've seen

[raw zealot]

but it takes only one arg

[regal spoke]

x -> x + i * a
where i is the index of x

https://cses.fi/problemset/task/1736 here is a problem that uses that kind of modification query

[raw zealot]

yeah true

but how does it handle

children

like where does this lambda get passed

[regal spoke]

There is no passing of lambdas

[raw zealot]

because while combining we will use the func = lambda x,y : x+y right

oh

hardcoded ic

[regal spoke]

Very hardcoded, yes

[raw zealot]

so this goes in the add of lazy st

why not pass custom lambda inplace of value of add 🤔

but only for sum st i.e

a bit rewriting needed then

[regal spoke]

I think you are underestimating how tricky it is to code lazy segment trees

[raw zealot]

haha

( i dont even properly understand it)

recursive form makes very sense xD

[regal spoke]

The idea is that you need to know how a value of a node in the segment tree will be modified by a modificiation query

Without digging down into the segment tree

[raw zealot]

true

we would need the indices too

nvm

[regal spoke]

Suppose that you want to deal with sums both as modification queries, and as range queries

Suppose that you decide to add 123 (some arbitrary number) to the entire range

Then the value of the root node of the segment tree would not increase by 123

it would increase by n * 123

[raw zealot]

yeah

[regal spoke]

That is what makes things to tricky

[raw zealot]

okay i see

[regal spoke]

If you instead have min on modification query and min on range query, then things become simple

x -> min(x, a)

[raw zealot]

yeah

pretty simple

it doesnt even require much change

[regal spoke]

Now the root node just acts like any other node

There is no need for an n when updating it

[raw zealot]

yeah

setting the entire range to n , will overwrite root as n^2 for sum

too strong stuff

[regal spoke]

Another thing making lazy segment trees tricky is that sometimes the order of the modification queries matter, and sometimes they do not.

For the x -> min(x, a) segment tree the order doesnt matter

But for the x -> a * x + b, the order matters

This kind of thing makes coding lazy segment trees very tricky if you want something generic

The more generic you try to make them, the more unesseccarily complicated they need to become

[raw zealot]

yeah

the idea is to hardcode whats necessary then

[regal spoke]

One of the most well known code libraries for c++, kactl, has gone with the approach of only having a very basic and simple lazy segment tree https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LazySegmentTree.h

[raw zealot]

normal set and add are more than enough as of now for me

i dont solve 2000+s yet so yeah :P

[regal spoke]

I think the most important thing is to get used to modifiying the standard segment tree

[raw zealot]

right

[regal spoke]

Coding it from scratch

I always code segment trees from scratch

[raw zealot]

directly implementing the iterative version is too strong for me

[regal spoke]

Its not really bad once you learn how they work

[raw zealot]

but i did understand the code

yeah

[regal spoke]

1. Start with a power of 2 sized segment tree (there are other versions, but dont bother with them)

2. You walk down the tree by i -> 2 * i for left child, and i -> 2 * i + 1 for right child

3. You go up the tree by i -> i // 2

4. You are at a leaf when you are at i >= n

The only really tricky thing is how to convert a range [l, r) into a set of nodes in the segment tree

[raw zealot]

1 << (self._len - 1).bit_length() , this is basically 2^h - 1 right

h is height of tree

[regal spoke]

# Convert interval [l, r) to set of nodes
def find_nodes_from_interval(self, l, r):
    nodes = []
    # Jump to the leaves that correspond to l and r
    l += self.n 
    r += self.n
    while l < r:
        if l & 1: # if l is a right child
            nodes.append(l)
            l += 1
        if r & 1: # if r - 1 is a left child
            nodes.append(r - 1)
        # Walk up the tree
        l //= 2
        r //= 2
    return nodes

This is the tricky code ^

Try scetching down a small segment tree and think about what this code does

[raw zealot]

aight tysm

[celest thicket]

What is the very important topic in the dsa

[wooden gulch]

hello, i was wondering if someone could explain why this solution for longest consecutive sequence is O(N) and if you could try to dumb down the answer because i'm having a hard time understanding. There is a while loop running inside of the for loop, if in the worse case scenario this while loop runs N times (assuming the whole array is consecutive) wouldn't the time complexity be O(N^2)? I know looking up something in a set is O(1) but if we increment the value inside the while loop N times, wouldn't this add up?

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:

        num_set = set(nums)
        longest = 0

        for num in nums:

            if num-1 not in num_set: # if the previous number is not in the set, it means that we have to start looking at a new sequence starting with cur
                cur = num
                cur_len = 1

                while cur+1 in num_set:
                    cur += 1
                    cur_len += 1

                longest = max(longest, cur_len)
        
        return longest

[regal spoke]

define consecutive sequence

[wooden gulch]

here's an example from the problem statement:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

[regal spoke]

Thats not a definition

[wooden gulch]

you can infer it from the problem statement idk what you mean lol

one number after the other

[regal spoke]

ok

[regal spoke]

This definitely looks O(n^2) to me

Is there a reason you think it is O(n)?

[wooden gulch]

i'm watching neetcode which is the person who gave out that solution https://www.youtube.com/watch?v=P6RZZMu_maU&ab_channel=NeetCode

[outer rain]

this while only runs once per each consecutive sequence

[regal spoke]

ah yes

if num-1 not in num_set:

This is the key

to make it run O(n)

Otherwise it would be O(n^2)

[wooden gulch]

if i have [0, 1, 2, 3, 4, 5]

I enter the for loop once where num = 0
-1 isn't in the set so I enter the while loop now, wouldn't this while loop continue until I check if 6 is in the set?

[regal spoke]

yes

Which is O(n)

[wooden gulch]

but the for loop will keep running, now num = 1, but it won't pass the if condition and so on

that for loop will go on until N

[regal spoke]

The for loop goes over the elements in the set in an arbitrary order

If it hits a "left most element" of a consecutive sequence, then it starts a search

[wooden gulch]

yes but the for loop is O(N)

in the particular example I sent, the while loop will run N times too

even if we have visited all the numbers in the sequence, the for loop will continue until it's done (N times no matter what)

[regal spoke]

Think about it like this. The set can be split up into consecutive sequences.
For example {23,5,3,1,4,2,22} can be split into [1,2,3,4,5] and [22,23]

The inner while loop will go over each of these consecutive sequences exactly once

The total number of iterations of the inner while loop is n

[wooden gulch]

i think i get it, it would be O(N^2) if that while loop was iterating N times every single time we increment in the for loop

but in this solution that would never happen

[regal spoke]

yes, which is basically what happens if you were to remove if num-1 not in num_set:

[wooden gulch]

okay thanks!!

[stiff quartz]

Hi,
I'm trying to understand why this codeforces submission (https://codeforces.com/contest/25/submission/270922167) passes but not this one (https://codeforces.com/contest/25/submission/270922138).
The problem is that one: https://codeforces.com/contest/25/problem/D
I'm solving it using Disjoint Union Sets.
My reasoning is the following:

• Get all connected component of the initial graph (I call them "islands")
• Iterate through each of those components, if you find a cycle, remove an edge and use it to connect to another component. To join the connected components in almost O(1), use what's described here https://cp-algorithms.com/data_structures/disjoint_set_union.html
• Do that until there is only one connected component
  The only difference between the two codes is that in the one that doesn't pass I add
  if island not in dealt_with:
  It's a O(1) operation (it's a set and I tried replacing set[int] par set[str] in case there were weird hacks to make this O(n))
  It should even improve the computation because if we arrive there it means we left the previous connected component so there are no more cycles to be found there and since that island is now in that previous connected component we save ourselves one dfs to find a cycle since we know there are none.
  Weirdly enough instead of decreasing the solution from 400 ms to something lower, it TLE at 2s. This is doing my head in. Would love some insight!

[regal spoke]

n is 1000 on that problem

To tle you'd need to basically be stuck in an infinite loop

[stiff quartz]

Um

Ah

I see

Nevermind

That’s a logic issue

Not a tle issue

I guess the one that passed could probably even be hacked

(Thanks btw)

Actually I'm having doubts

[regal spoke]

For this problem I wouldnt even use a dsu to begin with

[stiff quartz]

To be fair I was learning dsu

and clicked on a random problem with a tag dsu so i didn't think too much, i just wanted to make sure i understood the concept

[regal spoke]

If I understand it correctly, then any spanning tree will work

BFS spanning tree is probably easiest to make with Python

[stiff quartz]

well they "started" the spanning tree

and you have to "fix it"

update: it was a logic issue and indeed an infinite loop 😦 fixed it it passes now 🙂

[regal spoke]

I tried making some solutions
BFS: https://codeforces.com/contest/25/submission/270932536
DSU: https://codeforces.com/contest/25/submission/270933096

The DSU solution is really short (excluding the DSU implementation)

[wide thistle]

I'm writing one program for tree data structure and I want to insert one node in that tree.
code:

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value


def new_node(value):
    return Node(value=value)


def insert_node(root, data):
    root = new_node(data)


def main():
    root = None
    insert_node(root, 8)
    print(root.data)


main()

error:

D:\codes\Python\.venv\Scripts\python.exe D:\codes\Python\dsa\practice\program.py 
Traceback (most recent call last):
  File "D:\codes\Python\dsa\practice\program.py", line 22, in <module>
    main()
  File "D:\codes\Python\dsa\practice\program.py", line 19, in main
    print(root.data)
          ^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'data'

Process finished with exit code 1

Can anyone help me how to fix it

[stiff quartz]

Thx I’m gonna look at it!

[half owl]

why is this the algo?

in between

[torn tiger]

i Dont now

[narrow mica]

it's not a specific algorithm per se, but an application of binary search

[haughty mountain]

if I can check if a guess is too high/too low, then I can use binary search

[raw zealot]

https://cses.fi/problemset/task/1163/

i suppose it cant be done with treapmultiset and treapset of pyrival without TLE'ing ?

seems like cses is so biased to cpp

the former is literally converted code of the latter using chatgpt

lol

def solve(case=None):
    x, n = map(int, input().split())
    arr = list(map(int, input().split()))

    lis = TreapSet([0, x])
    tset = TreapMultiSet()
    tset.add(x)
    for i in range(n):
        l = lis.floor(arr[i])
        r = lis.higher(arr[i])
        tset.remove(r - l)
        tset.add(r - arr[i])
        tset.add(arr[i] - l)
        print(tset.max(), end=" ")
        lis.add(arr[i])

its probably because of the constant factor

because like

yeah

i have too many logn operations

[regal spoke]

I would use the sorted list datastructure in pyrival (it is faster even though it has worse time complexity).
But for performance reasons, it is likely better to go with a completely different approach based on segment trees

[raw zealot]

but removing from sortedlist is O(n) right

i am not sure

damn

[regal spoke]

No, it is n^(1/3)

Same as insert

[raw zealot]

strong

n^1/3 on 2e5 is nice

[regal spoke]

Don't think too much about the exact time complexity

[raw zealot]

yeah i just need an approx wrt logn

[regal spoke]

Sorted list is simply faster for any feasible n (n<1e7)

[raw zealot]

cool

how can we do this with segtree btw?

i can probably set light val to 0 and anything else 1

then maybe add if both are 1

idk

[regal spoke]

Go through the elements in time order and put a 1 in its position.

Have a standard sum segment tree

Now binary search inside the segment tree to find which light is closest to the left and which is closest to the right

Additionally, you can for each light store which light is to the left or right of it, removing half of the binary searches

[raw zealot]

understood, ty

[raw zealot]

and what for Multiset ?, like to fetch the max at any point in the gaps

if only heapq maintained a sorted list too it would have been too nice lol

[regal spoke]

For the gaps you can just compute the max of suffixes

gaps = [...]
for i in range(len(gaps)-1)[::-1]:
    gaps[i] = max(gaps[i], gaps[i + 1])

[raw zealot]

oh

isnt this equivalent to max(gaps)

i was worried for the time cost lets try this

    lis = SortedList([0, x])
    tset = CustomHashMap() # some xor hashmap
    tset[x] = tset.get(x, 0) + 1
    for i in range(n):
        l = lis.lower_bound(arr[i])
        r = lis.upper_bound(arr[i])
        tset[r - l] -= 1
        if not tset[r - l]:
            del tset[r - l]
        tset[r - arr[i]] = tset.get(r - arr[i], 0) + 1
        tset[arr[i] - l] = tset.get(arr[i] - l, 0) + 1
        print(max(tset.keys()), end=" ")
        lis.insert(arr[i])

[narrow mica]

import heapq
import bisect
import sys

def fn(input):
    x, n = map(int, input().split())
    arr = map(int, input().split())
    cut_off = int(x**0.5) + 1

    pq = [-x, 0]
    queued_removes = dict()
    blocks = [list() for _ in range(cut_off)]
    blocks[0].append(0)
    blocks[-1].append(x)
    ans = []
    for add_light in arr:
        block_i = add_light // cut_off
        block = blocks[block_i]
        ins_point_in_block = bisect.bisect(block, add_light)

        prev_block_i = block_i - 1
        next_block_i = block_i + 1

        if ins_point_in_block:
            lower = block[ins_point_in_block - 1]
        else:
            while not blocks[prev_block_i]:
                prev_block_i -= 1
            lower = blocks[prev_block_i][-1]

        if ins_point_in_block != len(block):
            higher = block[ins_point_in_block]
        else:
            while not blocks[next_block_i]:
                next_block_i += 1
            higher = blocks[next_block_i][0]

        queued_removes[lower - higher] = queued_removes.get(lower - higher, 0) + 1

        while pq[0] in queued_removes and queued_removes[pq[0]] > 0:
            queued_removes[pq[0]] -= 1
            heapq.heappop(pq)
        heapq.heappush(pq, add_light - higher)
        heapq.heappush(pq, lower - add_light)

        block.insert(ins_point_in_block, add_light)
        ans.append(-pq[0])

    sys.stdout.write(" ".join(map(str, ans)))

fn(sys.stdin.readline)
```passes everything in 0.7s except test6 and test7 because the ascending/descending input makes it keep doing the `while not blocks[next_block_i]: next_block_i += 1` thing
probably optimizable but annoying to do so

[raw zealot]

damn

[stiff quartz]

This is depressing, your DSU solution is like 10x more elegant than mine

[haughty mountain]

study and learn :P

[lilac cradle]

https://www.youtube.com/watch?v=GSxgb7tD-YY
anyone know a way to recreate this effect?

or like those 'holograms' you sometimes see where it's like it changes when you tilt it

[stiff quartz]

haha yeah doing it as much as i can 😄

good thing the community is nice to beginners like me, really helps

[opal oriole]

A high resolution texture with a bunch of details in it has problems being rendered at a distance. Your screen only has so many pixels and when picking the pixel color it needs to pick some color from the texture, but at a long distance even a tiny change in position / angle can cause a large change in which texel is being picked to be shown as the final color on the screen (may be interpolated). For example, imagine you only have 1 pixel on your screen, and you are viewing a detailed texture. You can imagine drawing an arrow going from that pixel into the scene and hitting the texture (projecting outward from the camera). As you slightly turn a bit that ray is touching an entirely different texel of the texture (small change is amplified over distance). The fix that video games use for this (usually) is to have mipmaps, which are basically down scaled versions of the texture that it switches to when the object is far away enough. Texture and its mipmaps:

[lilac cradle]

im aware of the concept, but idk how to really figure that out without just straight up rendering a bunch

[opal oriole]

So to create this effect, you have a highly detailed texture at a distance, where different slices become the sampled final result color at different positions / angles.

This depends on how the texture is being rendered, especially which texture filtering is set.

The FOV matters too.

You can then calculate the projection of camera frustum.

[lilac cradle]

ok so it's not trivial at all, i'd need to recreate the camera basically then?

[opal oriole]

Yeah, it's not super complicated, but not trivial either.

You need to basically figure out how the image is projected onto the screen, which depends on the specific camera setup, the screen resolution / ratio, the texture filtering method, and any other methods that might be applied to the rendering (for the specific game).

[lilac cradle]

mmk

[opal oriole]

If they are using mipmaps (like they should be), then you are out of luck (probably).

[zinc sky]

has anyone tried neetcode pro here, is it worth it if I am sitting for interviews in like 6 months?

[regal spoke]

Here is a relatively simple solution using SortedList (https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SortedList.py) that gets AC

x,n = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
 
Psorted = sorted(P + [0,x])
SL = SortedList(Psorted)
 
largest_gap = max(Psorted[i + 1] - Psorted[i] for i in range(n + 1))
largest_gaps = [largest_gap]
for p in P[1:][::-1]:
    i = SL.lower_bound(p) # Index of p in the sorted list
    L = SL[i - 1]
    R = SL[i + 1]
    SL.pop(i)
    largest_gaps.append(max(largest_gaps[-1], R - L)) 
print(*largest_gaps[::-1])

The idea is to simulate the process backwards in time, and keeping track of largest gap at each time step

[regal spoke]

Here is a similar solution, but without any use of sorted list

x,n = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
 
Psorted = sorted(P + [0,x])
 
to_left = {}
to_right = {}
 
largest_gap = 0 
for i in range(n + 1):
    a = Psorted[i]
    b = Psorted[i + 1]
    to_left[b] = a
    to_right[a] = b
    largest_gap = max(largest_gap, b - a)
 
largest_gaps = [largest_gap]
for p in P[1:][::-1]:
    L = to_left[p]
    R = to_right[p]
    largest_gaps.append(max(largest_gaps[-1], R - L))
    to_left[R] = L
    to_right[L] = R
print(*largest_gaps[::-1])

Here is basically the same algorithm as above, but avoiding using hashmaps. This is the fastest version

import bisect

x,n = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
 
Psorted = sorted(P + [0,x])

to_left  = list(range(-1, n+1))
to_right = list(range( 1, n+3))

largest_gap = max(Psorted[i + 1] - Psorted[i] for i in range(n + 1))
largest_gaps = [largest_gap]

for p in P[1:][::-1]:
    i2 = bisect.bisect_left(Psorted, p)
    i1 = to_left[i2]
    i3 = to_right[i2]
    L = Psorted[i1]
    R = Psorted[i3]
    largest_gaps.append(max(largest_gaps[-1], R - L))
    to_left[i3] = i1
    to_right[i1] = i3
print(*largest_gaps[::-1])

[regal spoke]

Had some fun codegolfing this (according to cses rules which is that whitespace counts as 0 bytes). 214 bytes:

f = lambda:map(int,input().split())
x,n = f()
P = [0,x,*f()]
 
L = [0,*range(n+2)]
R = L[2:]
 
Q = sorted(P)
M = {Q[i]:i for i in R}
 
G = [max(Q[i]-Q[i-1] for i in L)]
 
for p in P[:2:-1]:
    i = L[M[p]]
    R[i] = k = R[R[i]]
    L[k] = i
    G += max(G[-1], Q[k] - Q[i]),
print(*G[::-1])

I think this is the shortest non-brute solution (there are however some shorter C++ sol that look like O(n^2))

[raw zealot]

orz

okay we didn't even need the insert of SL due to going reverse , so strong

[wide thistle]

I'm deleting whole binary tree but still root still remain in the memory. how to delete root as well?

How to fix it?

code:

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value


def new_node(value):
    return Node(value=value)


def create_binary_tree():
    root = new_node(1)
    root.left = new_node(2)
    root.right = new_node(3)
    root.left.left = new_node(4)
    root.left.right = new_node(5)
    root.right.left = new_node(6)
    root.right.right = new_node(7)
    return root


def delete_tree_recursion(root):
    if root is None:
        return

    # before deleting root, first delete both subtrees
    delete_tree_recursion(root.left)
    delete_tree_recursion(root.right)

    # delete current node only after deleting subtrees
    print(root.value, ' ', end=' ')
    root.left = None
    root.right = None
    del root


def main():
    root = create_binary_tree()
    print('deleted nodes: ', end=' ')
    delete_tree_recursion(root)
    # still I can access root value
    print('\nroot value:', end=' ')
    print(root.value)


main()

[outer rain]

You don't have to delete objects in python manually. In fact, you can't do that completely, and your deletion function does nothing. If don't want to access root anymore for some reason, you can simply write del root in main, and it will delete the whole tree behind the scenes in your example. But you don't have to, the tree will be deleted anyway right after exiting main, so why bother?

[haughty mountain]

drop your reference to the root

but really, you're probably better off just setting stuff to None and letting gc clean it up

[fiery cosmos]

I am wondering why False is returned for my code. So this is problem that I am trying to solve:

You are given two strings s1 and s2.

Return true if s2 contains a permutation of s1, or false otherwise. That means if a permutation of s1 exists as a substring of s2, then return true.

Both strings only contain lowercase letters.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        char_freq = {}
        for c in s1:
            char_freq[c] = char_freq.get(c, 0) + 1
        start_char_freq = char_freq
        matched = 0
        s1_len = len(s1)
        for i, right_char in enumerate(s2):
            if right_char in char_freq:
                char_freq[c] -= 1
                if char_freq[c] >= 0:
                    matched += 1
                    if matched == s1_len:
                        return True
                else:
                    char_freq = start_char_freq
                    char_freq[right_char] -= 1
                    matched = 1
            else:
                char_freq = start_char_freq
                matched = 0
        return False

I have another solution for which I passed test cases but I would like to understand why for input s1="ab"
s2="lecabee" False is returned for this code that I pasted

[boreal relic]

Is the issue that you're using char_freq[c] instead of char_freq[right_char]?

[fiery cosmos]

yes, you are right

[boreal relic]

BTW, I think it would be enough to calculate char frequencies for both strings, then check that for every char in s1 the same frequency or higher is present in s2. Something like (untested):

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        char_freq_s1 = {}
        for c in s1:
            char_freq_s1[c] = char_freq_s1.get(c, 0) + 1
        char_freq_s2 = {}
        for c in s2:
            char_freq_s2[c] = char_freq_s2.get(c, 0) + 1
        return all(char_freq_s1[k] <= char_freq_s2.get(k, 0) for k in char_freq_s1)

Not sure that the return all(... line is correct, can you see if this passes the test cases?

[fiery cosmos]

For s1="abc"
s2="lecaabee" it returns False...if I understood your code correctly, you are not using just slice of string, but whole string which lead to wrong result

anyway my logic for that problem above is flawed, you can see how from this example

s1="adc"
s2="dcda"

I solved it in different way

but this is better solution than mine

class Solution:
    def findPermutation(self, str1, pattern):
        window_start, matched = 0, 0
        char_frequency = {}

        for chr in pattern:
            if chr not in char_frequency:
                char_frequency[chr] = 0
            char_frequency[chr] += 1

        # our goal is to match all the characters from the 'char_frequency' with the current
        # window try to extend the range [window_start, window_end]
        for window_end in range(len(str1)):
            right_char = str1[window_end]
            if right_char in char_frequency:
                # decrement the frequency of matched character
                char_frequency[right_char] -= 1
                if char_frequency[right_char] == 0:
                    matched += 1

            if matched == len(char_frequency):
                return True

            # shrink the window by one character
            if window_end >= len(pattern) - 1:
                left_char = str1[window_start]
                window_start += 1
                if left_char in char_frequency:
                    if char_frequency[left_char] == 0:
                        matched -= 1
                    char_frequency[left_char] += 1

        return False


def main():
    sol = Solution()
    print('Permutation exist: ' + str(sol.findPermutation("oidbcaf", "abc")))
    print('Permutation exist: ' + str(sol.findPermutation("odicf", "dc")))
    print('Permutation exist: ' + str(sol.findPermutation("bcdxabcdy", "bcdyabcdx")))
    print('Permutation exist: ' + str(sol.findPermutation("aaacb", "abc")))


main()

wondering whether this solution is better

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        
        s1_count = Counter(s1)
        window_count = Counter()

        for i, char in enumerate(s2):
            window_count[char] += 1

            if i >= len(s1):
                left_char = s2[i - len(s1)]
                window_count[left_char] -= 1
                if window_count[left_char] == 0:
                    del window_count[left_char]

            if window_count == s1_count:
                return True

        return False

[regal spoke]

You should consider making simpler solutions

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        char_freq1 = {}
        for c in s1:
            char_freq1[c] = char_freq1.get(c, 0) + 1
        char_freq2 = {}
        for c in s2:
            char_freq2[c] = char_freq2.get(c, 0) + 1 
        return char_freq1 == char_freq2

[fiery cosmos]

That returns false for

s1="ab"
s2="lecabee"

[regal spoke]

Oh I missread the problem

Still there are simpler solutions

[fiery cosmos]

Probably

I guess this is better

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        
        s1_count = Counter(s1)
        window_count = Counter()

        for i, char in enumerate(s2):
            window_count[char] += 1

            if i >= len(s1):
                left_char = s2[i - len(s1)]
                window_count[left_char] -= 1
                if window_count[left_char] == 0:
                    del window_count[left_char]

            if window_count == s1_count:
                return True

        return False

[regal spoke]

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        char_freq1 = {}
        for c in s1:
            char_freq1[c] = char_freq1.get(c, 0) + 1
        char_freq2 = {}
        for c in s2:
            char_freq2[c] = char_freq2.get(c, 0) + 1 
        return all(char_freq1[c] <= char_freq2.get(c, 0) for c in char_freq1)

[fiery cosmos]

That fails for

s1="abc"
s2="lecaabee"

[regal spoke]

fixed it

[fiery cosmos]

again it fails becaus it outputs True instead of False (for s1="abc"
s2="lecaabee"), I think that you missread problem

https://leetcode.com/problems/permutation-in-string/description/

[regal spoke]

ah ok that complicates things a bit

[regal spoke]

Something that is good to know about is that from Python 3.10 you dont need to delete 0 elements from a counter

[haughty mountain]

Counter(s1) <= Counter(s2)

oh wait, substring not subsequence

[agile moth]

Is there anything better than haarcascade_frontalface_default?

[dreamy nacelle]

I'm not saying they're pretty. And I'm probably packing too much deferred execution behind my GUI. But I wrote my own observable property classes and I'm proud of them https://paste.pythondiscord.com/MOBQ

[ripe swan]

have a difficulty understanding Linked lists

i get the concept but the idk how to actually use it

do i need to know oop to be able to work with linked lists

[old rover]

yes.

[old rover]

https://youtu.be/WwfhLC16bis?si=Pa-7A_TimSdanCC5

[ripe swan]

thanks

[tight cedar]

linked list sucks anyway

[old rover]

ye.

[left mulch]

This guy seems to have a whole series on data structures, is it any good? I'm a total beginner when it comes to this stuff

[old rover]

He’s good

[left mulch]

Thanks!

[final night]

hey

I have a question about a basic exercise

removing duplicates, on leetcode

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        dist = [nums[0]]
        i = 1
        k =0
        while i<len(nums):
            if dist[k] < nums[i]:
                print(nums[i])
                dist.append(nums[i])
                k+=1
            i+=1
        nums = dist
        return k

What exactly is wrong with this?

it's failing all test cases

the question https://leetcode.com/problems/remove-duplicates-from-sorted-array/
for reference

[vocal gorge]

It says "remove the duplicates in-place", but you never modify nums, merely reassign the name

nums[:] = dist would work.

(it's possible to do this task in O(n) time and O(1) memory, though, whereas this solution is O(n) memory)

[final night]

I tried, the dist is the correct output, but the last element is not getting added
So if dist is [1,2,3,4] , nums ends up being [1,2,3]

this problem only happens in leetcode

the only solution other solution I could think of is O(n^2) so I didn't even try

[vocal gorge]

That shouldn't be possible, nums[:] = dist makes it so that nums == dist.

[final night]

this solution works fine in my vscode environment

I wish I could see what the tests look like

oh wait this is the test

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

[vocal gorge]

Well, you're doing nums[0:len(nums)] =, not nums[:] =

[final night]

both don't work

same output

[vocal gorge]

ah, true, actually

it may be because you're off by 1 in k

[final night]

oh

you were right

it's accepted

but how do I implement the O(1) memory solution?

[vocal gorge]

You'd need to not have a second list at all. You also can't delete elements because that's O(n) each time. So the solution is to use the nums list itself - simultaneously read and write to it.

[agile moth]

What pixel number is best for training? to make a facial recognition system

[rigid trench]

13

[austere sparrow]

Any recommendations for a book/other resource on graph algorithms?

[raven dagger]

help

Given l and r, find the number of numbers `i` from l to r that have a prime number of factors.

Constraints:
l < r <= 10^12```

[solemn moss]

Interesting.. All primes have a prime number of factors.. (That's not all needed numbers but they are the part of answer). And I am not sure that we can calculate count of primes from 1 to n

Maybe prime factors are meant?

[raven dagger]

nop

prime number of factors

[stiff quartz]

How do you guys deal with this sort of things when online judges don't tell you how any lines there will be

if i do while True: a = input()

It's going to time out waiting for a new line even though there wasn't a new line right?

ah turns out there is an empty line necessarily at the end on codeforces

my bad

[outer rain]

hint: ||most numbers have even number of factors||
hint 2: ||eratosthenes sieve can be used to count the number of divisors of all squares 1^2..n^2 too||

[solemn moss]

But what about primes ? That have 2 divisors

[haughty mountain]

wdym by factors?

[raven dagger]

like

facctor

s

[outer rain]

all primes are either 2 or odd (re: @solemn moss)

[haughty mountain]

divisors or prime factors

[raven dagger]

divisors

[haughty mountain]

divisors or proper divisors?

[raven dagger]

fym proper divisor

divisor as in x % d = 0

[solemn moss]

Yes
I am talking about that all primes have 2 divisors, which is a prime number. So we need to count all primes

[narrow mica]

perfect squares?

[haughty mountain]

e.g. does a prime p have divisors [1] or [1, p]?

[raven dagger]

what about numbers with 3 factors

[raven dagger]

[1, p]

[outer rain]

hm, you are right

[solemn moss]

Everything else (that have >= 3 factors) is very easy to count

[outer rain]

my bad

[haughty mountain]

if so at minimum you need to find all primes, which isn't very feasible for 10^12

[raven dagger]

yeah

[solemn moss]

Is there a link to that problem?

[outer rain]

r - l < 1e6 would be nice

[raven dagger]

no

[solemn moss]

Well, we can precalculate primes count for 10^6, 2 * 10^6 and so on

[haughty mountain]

(or rather, you need to at least count the number of primes)

[solemn moss]

But this kinda sucks lol

[raven dagger]

the example is

Input:
2 5

Output:
1```

[outer rain]

wait, isn't it exactly the number of primes?

[raven dagger]

hold up this isnt making senes

oh

[raven dagger]

i also isnt a prime

im assuming they'd have to be squares

[solemn moss]

Yes

They can be only squares

And you can just check them all

[outer rain]

I think you just need to count primes

[raven dagger]

huh really?

[outer rain]

because if n = p1^i1 * p2^i2 * ... pm^im then it has (i1 + 1)(i2 + 1)...(im + 1) divisors

[raven dagger]

yeah

.wa s number of squares from 1 to 10^12

[haughty mountain]

squares fit it too

[solemn moss]

10^6 * 10^6 = 10 ^ 12

[narrow mica]

factors of 9 include 1, 3, and 9

[outer rain]

why?

oh

right

[haughty mountain]

p^2 has 3 divisors

[outer rain]

so p^n too

p^(q - 1)

[raven dagger]

true

but then i'd also have to count the divisors

[solemn moss]

To proof that it's only squares you can just look on the finding divisors algo

for d in range(1, int(x ** .5) + 1):
    if x % d == 0:
        ans += 2 # except the case d * d == x

[raven dagger]

that'd go over time limit

10^6 * 10^3

actually mayben ot

[solemn moss]

For python probably
So you can do that with eratosthenes sieve i believe

[raven dagger]

also p^4

[narrow mica]

I mean no matter what sieving 10^12 numbers doesn't seem great
any limit on r - l?

[haughty mountain]

p**(q-1) where p and q prime

[solemn moss]

p^4 = (p^2)^2

[raven dagger]

no

[solemn moss]

Ah yeah, big numbers

[raven dagger]

hmm

idk imma take a shower and think about it later

[outer rain]

is it possible to speed up linear eratosthenes maybe?..

well, not speedup..

[raven dagger]

ok shower's taken so more thinking

[outer rain]

forget it

[haughty mountain]

is this an existing problem or just something you made up?

[raven dagger]

existing problem

[haughty mountain]

where?

[raven dagger]

idk i found a google doc with a ton of questions

i translated it to english lol

[narrow mica]

tbh I'd assume there's more likely a memory problem rather than a time limit problem
so try segmented sieve

[outer rain]

that's 10^12 anyway

[raven dagger]

also any speedup wouldn't deccrease the biggo whicch is the issue

[outer rain]

I mean, you don't need the primes themselves

only counts

[raven dagger]

yeah

[solemn moss]

We can calculate count of each prime divisor for numbers <= 10^6 and do something with that because we have just squares of that probably?

[solemn moss]

Like with this formula

[raven dagger]

yeah, so it has to be p^n

factors(p^n) = {p^0, p^1, ... p^n} i think

[narrow mica]

I mean that memory's still a bigger problem than time

[outer rain]

sure ig

[stiff quartz]

Is there a better way than a sorted list to support find median / pop median / insert element?

[haughty mountain]

you can probably do some segmented sieve, but it still won't be fast

[raven dagger]

insert element is O(1) /j

[agile sundial]

can't you do that with 2 heaps?

[outer rain]

any ordered set

[stiff quartz]

If i'm not forgotten with a sorted list it's O(1) / O(n^1/3) / O(n^1/3)

[haughty mountain]

2 heaps is a common approach, yeah

[narrow mica]

honestly I'd just hope that r - l is limited (despite them not telling you)

[stiff quartz]

what? what is j?

[raven dagger]

how fast can a computer calculate a log?

[stiff quartz]

i don't see any apart from sorted list in python?

[raven dagger]

a joke

[stiff quartz]

didn't know about it, i'm gonna check

[outer rain]

yeah, there isn't one in standard library

[haughty mountain]

if r-l is limited you can just find primes ≤1e6 and use those, yeah

[outer rain]

precalc works too

(assuming you don't have to send the solution)

(it's gonna be big)

[stiff quartz]

just found a tutorial talking about it, nice, I'll try and see if my O(n*n^1/3) is actually worse than O(nlogn) with two heaps on the codeforces problem i was on or if that optimization was too small for me to notice 💀 thanks!

[haughty mountain]

for reference, the two heap solution involves keeping a min heap and a max heap and balancing the sizes to be equal

[stiff quartz]

yeah that's what they say too

i guess from a dsa point of view might be a good thing to know

[haughty mountain]

I think you can even modify it to work with a sliding window

[raven dagger]

honestly i think the best one i can think of is (in pseudocode)

out = 0
for p in primes:
    out += (floor(log_p(r)) - ceil(log_p(l)))

does this work?

oops wrong order

[solemn moss]

It seems previous problem is still not fully solved

If we have cnt[p] then for square of it we will have cnt[p] = cnt[p] * 2
And count of divisors is (cnt[p1] + 1) * (cnt[p2] + 1) * ... for all primes

(We do that for all x such as l <= x ** 2 <= r and check if the result count is prime)

[haughty mountain]

anything that's not a prime power for sure has a composite number of divisors

if we were allowed to ignore primes themselves (so ignore stuff with two divisors) we could solve things faster

something like O(sqrt(n) log(log(n)))

I think

[solemn moss]

#algos-and-data-structs message
we skip primes

[haughty mountain]

roughly the thing I imagine is

sieve primes up to sqrt(r)
for every prime p
  find largest k such that p**k <= r
  count += π(k) - 1

(I'm currently assuming l is irrelevant, things can be adjusted to work with a range)

[grand sphinx]

I want to start learning DSA coz I've finished the basics of python

Can anyone tell what things I have to cover to learn DSA

and suggest me some content to learn from

thanks in advance

[topaz condor]

Like is it good idea to start with dsa quickly

[half owl]

def quicksort(lst, rand=True):
    """ quick sort of lst """
    if len(lst) <= 1:
        return lst
    else:
        pivot = random.choice(lst) if rand else lst[0]
        smaller = [elem for elem in lst if elem < pivot]
        equal = [elem for elem in lst if elem == pivot]
        greater = [elem for elem in lst if elem > pivot]

        return quicksort(smaller, rand) + equal + quicksort(greater, rand)

can anyone explain why deterministic quicksort is faster than randomized quicksort? in the case of a randomized list

test code:

a = random.sample(range(1,10**5 + 1), 10**5)
t0 = time.perf_counter()
res = quicksort(lst=a, rand=True)
t1 = time.perf_counter()
print(t1 - t0)

b = random.sample(range(1,10**5 + 1), 10**5)
t0 = time.perf_counter()
res = quicksort(lst=a, rand=False)
t1 = time.perf_counter()
print(t1 - t0)

i mean it makes 0 sense, only explanation is "well the list is already random and not sorted so the random function to generate pivot needlessly takes more time" but this shouldnt be the case

i've ran more rigirous tests as well and this is the case, but i dont wanna send 2 functions since you get the point

[outer rain]

that's exactly the explanation, what do you dislike about it?

[half owl]

the whole point of quicksort is that the time complexity is O(nlogn) on average for a random list with a randomized pivot right?

and making a determinstic quicksort is supposed to be O(n^2) on average

so i dont see how O(nlogn) > O(n^2)

[outer rain]

do you understand where the O(n log n) comes from?

[half owl]

i guess not entirely, i do understand the O(n^2) for determinstic though

[outer rain]

this statement is wrong

it's O(n log n) on average on randomly shuffled list

[half owl]

for index=0 it is true, for median it's nlogn

[outer rain]

regardless of the choise of pivot

[outer rain]

nope

[half owl]

doesnt make sense

[outer rain]

it's worst case O(n^2)

not on average

[half owl]

when is worst case then?

[outer rain]

when chosen pivot is always the smallest or largest element

i.e. sorted list

[half owl]

alright i get that

[half owl]

so youre saying for the implementation above the only thing make quicksort randomized pivot slower is the random generation of a pivot?

that seems like itd hardly be the case

[outer rain]

Here's a rough idea why quick sort is O(n log n) with random pivot: there is 1/2 probably of choosing a pivot above 25th percentile and below 75th percentile. Imagine for a second that all other iterations do nothing (it makes time worse, obviously). Then all iterations split list in half, very roughly, so does on average O(log n) recursion calls in depth, and each "layer" of recursion is O(n)

Notice that you only need the pivot to be roughly close to the median

In case of random list it doesn't matter which element you choose. They all have same probability of being close to median

[half owl]

i guess i just dont understand

ill try to see another explanation later i guess

though thanks for the help mate

[half owl]

if i have a recursion tree of height=logn, and each level there n operations being done in that level, how do i write the sum?
0->lognSIGMA n = n * log n = O(nlogn)?

or does the sum start from 1, and not 0?

[haughty mountain]

does it matter?

[half owl]

no, but i want to be rigirous

[haughty mountain]

.latex $$\sum_{i=1}^h n = n h$$

[half owl]

also, generally should i do depth*n, or height*n?

i mean of the tree

since i saw my lecturer do it for depth, but depth = height -1

which might not matter but it seems not good

[haughty mountain]

it's more a matter of convenience

you could sum from 0 to depth

[half owl]

i see, so thats why they used 0, ty mate

[half owl]

so for depth do i write 0->dSIGMA n=nlogn=O(nlogn)? or do i write (logn+1)*n?

which is the same

but i mean in reality

actually it doesnt matter

[lean walrus]

.latex $$\sum_{i=1}^n n = n^2$$

[haughty mountain]

not false

[stiff quartz]

Hey I'm solving this problem

This is the solution that I implemented (it works on loads of test cases and the idea is standard):

Yes it's not optimal there is a O(n^3) solution, but after giving it some thinking, I think that O(n^4) solution doesn't work

On this example BYYYBYYYB 3 there is no way to segment it in three parts such that it works with dp.
Am I missing something and implementing it wrongly? My implementation returns No. Or is the official ICPC solution actually wrong? I highly doubt it but I really can't wrap my head around how they could be right

[agile moth]

yolo ultralytics vs mediapipe vs MTCNN what's good for use webcam to detect face and crop face and go to encode face recognition

[haughty mountain]

BYYYB YYY B

where the concatenation BYYYBB is eliminatable

[stiff quartz]

Oh

I see

but @haughty mountain then there is something I'm missing, how do you check that the concatenation BYYYB B is "eliminatable" in O(1). Currently what I do is:
mono_colour_first: int = get_colour(start, i)
mono_colour_third: int = get_colour(j, start+length)
with memoization on the get_colour calls assuming that I'd only have to check if they have the same colour to determine if the concatenation is "eliminatable"

and that is clearly not the case here, I have to show that BYYYB B is eliminatable in the non "uni-color sequences" case

Any ideas how I should go around that?

I need to "store" somewhere that BYYYB is reducible to BB easily, right? 🤔
EDIT: Ah I think I see how I might be able to do it
EDIT2: got it accepted FINALLY

[fiery cosmos]

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

Is this code

from collections import Counter

def are_anagrams(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

# Example usage:
s = "listen"
t = "silent"
print(are_anagrams(s, t))

actually same as

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        occurences_s = {}
        occurences_t = {}
        for c in s:
            occurences_s[c] = occurences_s.get(c, 0) + 1
        for c in t:
            occurences_t[c] = occurences_t.get(c, 0) + 1
        for c in occurences_s:
            if occurences_s[c] != occurences_t.get(c, 0):
                return False
        for c in occurences_t:
            if c not in occurences_s:
                return False
        return True

[brave hound]

Yes, pretty much. The comparison of the two dicts can be improved tho

[half owl]

does anyone know if instead of drawing the recursion tree i can just draw the chart on the right instead? and then calc the TC

also, what do i do if im analyzing the TC of a function which uses an envelope function with a lot parameters? do i really have to draw them out inside the circles?

• and put the TC of each node on the right after it*

[haughty mountain]

the tree can help you derive such a table

it's just another way to visualize the process

also, what do i do if im analyzing the TC of a function which uses an envelope function with a lot parameters? do i really have to draw them out inside the circles?
you rarely have many parameters that matter

often 1, sometimes 2, rarely more than that

[half owl]

def reverse(L): # <--- envelope function
    def reverse_recursive_func(L, reversed_L, i_end_to_add): # <--- recursive function
        if i_end_to_add == 0:
            reversed_L.append(L[0])
            return reversed_L

        reversed_L.append(L[i_end_to_add])
        return reverse_recursive_func(L, reversed_L, i_end_to_add - 1)

    if len(L) == 0:
        return []
    return reverse_recursive_func(L, [], len(L) - 1)

for example here, how can i explain the TC is O(n)? i mean the last node in the recusive function is a huge list at that point and i cant write L[n-1], L[n-2],...,L[0] since on 1 node this just takes so much space

is there a better way to explain why the TC is O(n)? like i dont think it's okay to plaining just write O(1)*n=O(n), but also i dont wanna explain verbally much beforehand

[haughty mountain]

do the lists L and reversed_L matter for the complexity?

some aspect of them might, but the details less so

[half owl]

but i have to write the details right? they else wouldnt recognize whats the parameters are

[haughty mountain]

let n be the length of L
T(n) = 1 + T(n-1)

this is the relevant recurrence hidden in your recursion

you do constant O(1) amount of processing in the body, and then call recursively with some data that is 1 smaller

[half owl]

yeah true, but you dont just write that

[haughty mountain]

you kinda do

that's the analysis that gives you T(n) = 1 + T(n-1)

[half owl]

i mean sure it's obvious, but it's like omitting details and making assumptions

think about this when there's a hard DSA question this might lead to errors and just generally be vague

[haughty mountain]

what details am I omitting?

[half owl]

here this is a basic recusive function so it's not a big deal but thats not feeling like a method i can use universally

[haughty mountain]

and what assumptions were made

[half owl]

i see what you mean

but i dont think it's correct to just write it down

the recursive tree seems more correct and well grounded

[haughty mountain]

T(n) = 1 + T(n-1) defines a recursive tree

(a very boring tree, but whatever)

[half owl]

but can we literally do:

"write the function, and explain the TC."

• "T(n) = 1 + T(n-1)."

no nothing before?

no "how" or "why"

[haughty mountain]

the point is that you want to get rid of the stuff that doesn't matter

does the body of the loop do constant amount of work, cool we can get rid of the details

[haughty mountain]

is the motivation

[half owl]

but you dont say that

[haughty mountain]

I just did

[half owl]

but you agree when asked to explain why your TC is what it is you cant just write the equation?

[haughty mountain]

I mean fine, I didn't say it in order before.

you do constant O(1) amount of processing in the body, and then call recursively with some data that is 1 smaller

let n be the length of the data being processed, the time T for the recursive call can be expressed as
T(n) = 1 + T(n-1)

and then you analyse that recurrence

to see that it ends up being O(n)

[half owl]

yes thats great,
and whats the final step to calculate T(n)? i dont know how to do it rigirously on paper the step itself

as in sure i can do 1+1+...+1 (sigma 1 to n) = n = O(n)

[haughty mountain]

in the general case techniques like induction ends up being important

but in this can you can just kind of...expand things

[half owl]

oh ill have to google then how to do it for this

but i think this is a better approach than mine

not sure completely on the method

but i get the idea

also, any idea whats the Ohm here is for?

[haughty mountain]

T(n) = 1 + T(n-1)
     = 1 + (1 + T(n-2))
     = 2 + T(n-2)
     = 2 + (1 + T(n-3))
     = 3 + T(n-3)
     = ...
     = n + T(0)

[half owl]

true but here it's easy to see

anyway i think i know what to look for

thank you very much

[haughty mountain]

O is an upper bound, Ω is a lower bound

there are actually 5 symbols relevant to this
o, O, Θ, Ω, ω

which corresponds to basically
<, ≤, =, ≥, >

[half owl]

oh i see, but not a percise one right?

[haughty mountain]

asymptotic bound, yes

[half owl]

cant see the difference between o and O?

oh i do

[haughty mountain]

it all boils down to how 2 functions behave, what happens to f(n)/g(n) as n grows large

[half owl]

okay i get it now

[half owl]

yes, thank you very much for point that out, i also think i've seen people wrongly using o(n) instead of O(n) or teta(n) to explain their TC

[haughty mountain]

if it goes to 0 then "f(n) < g(n)" which we can write as f(n) = o(g(n))

if it goes to 0 or a constant, then ≤, i.e. O

if it goes to a constant, then =, i.e. Θ
if it goes to a constant or ∞, then ≥, i.e. Ω
if it goes to ∞, then >, i.e. ω

[half owl]

we didnt learn
f = O(g) -> f <= c*g (c is a constant)

for for o itll be:
f < c*g?

for all c != 0?

or c > 0?

technically the original was
| f | <= | c*g |
so it doesnt matter right?

just change <= to < here

with the absolute ones

of course, it's from a certain index N>n

[haughty mountain]

I think the typical formal way of writing it that
f(n) = O(n) if there exists some n0, such that for n≥n0 there exists a c such that f(n) ≤ c*g(n)

[half owl]

yes

[haughty mountain]

the more useful way of looking at it in practice is that it's all about what happens to f(n) vs g(n) as n grows

e.g. f(n) ≤ c*g(n) → f(n)/g(n) ≤ c in the case of O

[half owl]

so all O is also o right?

[haughty mountain]

the thing that changes for the different versions is just that inequality

[half owl]

because if i can say:
f(n)= c * n
then i can just do:
g(n)= (c+1) * n

[half owl]

yes

well i think i get it

[haughty mountain]

other way around

everything < is also ≤

[half owl]

yes exactly

alright i got it

thanks again

[astral bough]

hey guys, wanted to know how many of you faced this probelm, like when learnig coding you have to go back and forth from your youtube video to code editor.

[fiery cosmos]

I don't think that's a problem when you're new

[fiery cosmos]

Yoo

[stiff quartz]

I have two monitors 💀

[fiery cosmos]

How?

[brave hound]

instead of looping over both dicts to check if they are subsets of each other, check if length of both of them are the same then check if all elements of first dictionary exist in the second one

[half owl]

T(0) = 1 ```

any idea how to formalize for k=n-2 the end TC?

[scarlet chasm]

with open("cowsignal.in") as read:
    height, width, scale = map(int, read.readline().split())
    signal = [read.readline() for _ in range(height)]

with open("cowsignal.out", "w") as written:
    for i in range(scale * height):
        for j in range(scale * width):
            print(signal[i // scale][j // scale], end="", file=written)

        print(file=written)

https://usaco.org/index.php?page=viewproblem2&cpid=665

the problem link is right here, and the solution code is the code above

my question is, why did they use floor division here print(signal[i//scale] [j // scale]?

[ashen niche]

import NDTM # assume this NDTM is an external computer which runs a NDTM that decides 3SAT, and returns the result

def solve_3SAT(phi):
  return NDTM.query(phi)
def solve_U3SAT(phi):
  solveable = solve_3SAT(phi) # If there exists any assignment, this will be True
  return not solveable

Why is this theoretically not a polynomial time solution to the complement of 3SAT?

[fiery cosmos]

3UNSAT is Co-NP-complete, meaning it is among the hardest problems in Co-NP. A problem being Co-NP-complete implies that it is unlikely to be solvable in polynomial time unless Co-NP is a subset of P (problems solvable in polynomial time). It is not known whether Co-NP problems, including 3UNSAT, can be solved in polynomial time.

[ashen niche]

I know this

I was more curious about the error in this

I think the issue is that once you consider this program non deterministic, flipping the answer of the NDTMs doesn't actually give you the correct answer

[fiery cosmos]

what does querying the NDTM actually do? Does it verify if the solution (given inputs) satisfies the problem?

[ashen niche]

Yeah, I was working by the idea that there is a black box, a NDTM that decides 3SAT.

It's probably more like an oracle at that point, though.

[ashen niche]

for this program to be non deterministic means that any accepting path existing should accept
hence flipping the branches where , for example, half are rejects and half are accepts, wouldn't reject

https://imgur.com/PKVJD4F

basically the situation on the right here

[fiery cosmos]

so if a set of inputs correctly determines a solution to 3SAT, that means you've also found a solution to 3UNSAT by flipping the result. Since it would flip True to False

for an NDTM you only need 1 branch to return True for the entire problem to return True

[fiery cosmos]

You don't need to look at multiple branches. Once you've found at least ONE set of inputs that satisfy a formula, you've already answered 3UNSAT

[ashen niche]

yeah, it solves it if we consider the NDTM a black box

but if we consider it as a NDTM I'm flipping the states

[fiery cosmos]

You only have to flip the result, you don't have to flip each individual branch.

[ashen niche]

well, yes, but then it won't be a NDTM

[fiery cosmos]

How so? an NDTM is a black box by definition because we only care about the final result and not the individual paths. The internal computations are abstracted away.

Think of an NDTM as a map-reduce problem. You map a function to all possible inputs and at the end you're taking an or of the results from every path and reducing it to a single truth value.

[ashen niche]

I guess "it" is confusing, the NDTM will be a NDTM but the entire program won't be

that's what I meant

[ashen niche]

think about it, this isn't proof that the complement of 3SAT is in NP

[fiery cosmos]

Yes. This isn't proof that NP = Co-NP. Because that's essentially what you're trying to prove here.

[ashen niche]

Yeah, I tried proving it but realized the error, I think.

I mean a NDTM running another NDTM requires it being simulated

[ripe prism]

hello guys I have a question so im a complete beginner, i tried going thru neetcode map but couldn't understand anything even after i see the solution how do i approach learning DSA

its been around a month and i still can't get it thru my head

[fiery cosmos]

You need to start with the basics. Try doing only problems that involve array manipulations.

[ripe prism]

if u don't mind can you give me a roadmap so ik what to study

[agile moth]

To make face recognition effective, approximately how many images of the user should be used? Is 30 images too much?

[fiery cosmos]

https://www.manning.com/books/grokking-algorithms

[left mulch]

Woah it says this entire book is available for free? That's amazing, I'm gonna get started on it

[golden ravine]

hey just recently enrolled in a comp sci class

can someone explain this

i'm having trouble fully understanding what it means

what does defining property mean

[agile sundial]

it defines the set based on whether it's true for a given thing

[golden ravine]

so like it takes an element and checks if it passed a certain condition?

for example if x is larger then 1 or smaller then 5

is that correct?

[agile sundial]

sure. in general it is a proposition

[haughty mountain]

set builder notation 🤩

[stiff quartz]

say i have an array f with n elements and an array g with n elements
elements are all positive integers
how can i choose i, j to maximize the following in O(n) or better:
f[i] + f[j] + g[all indices but i and j]

I only have a naive O(n^2) solution in mind

This is not a real official CP problem, maybe there's no answer

ah maybe i can just look at max(f-g)

[vocal gorge]

yeah, it kind of looks to me like you just want the top 2 indices of f-g

[stiff quartz]

yeah yeah it works

thx!

[stiff quartz]

How can I make that function iterative without using the magic decorator of pajenegod

    def dfs(u: int) -> None:
        visited[u] = True
        if len(graph[u]) == 0:
            # leaf node
            f[u] = 0
            g[u] = 1
            return
        for v in graph[u]:
            if not visited[v]:
                dfs(v)
            
        f[u] = sum(max(f[v], g[v]) for v in graph[u])
        g[u] = max(
            max(g[v] for v in graph[u]),
            max(f[v] for v in graph[u]) + 1
        )

since I have to do stuff after running dfs(v) I don't see how I can use a stack

The only thing I see is spending a lot of time first sorting the nodes per "height" in the graph:

and do the deepest nodes first etc so that I can ensure f[u] and g[u] can always get the information of their "children"

I forgot to mention, graph is a tree

and I store the children of a node in graph[node]

but that solution does not seem good

[haughty mountain]

do you need to run it immediately after or does it just need to be run in reverse dfs order?

[stiff quartz]

it just needs to be run in reverse dfs order

Ah i see

you can use an iterative dfs to make that order

is that what you're getting at?

[haughty mountain]

you can store the ordering and do the final part afterwards, yeah

[stiff quartz]

yeah that's smart
EDIT actually when I said "spending a lot of time first sorting the nodes per "height" in the graph" that would have just been a bfs and wouldve worked too - wasn't that expensive

thanks!

what would i do without this discord

um

    visited: list[bool] = [False] * (n+2)
    stack: list[int] = [1]
    order: list[int] = []
    while stack:
        curr: int = stack.pop()
        visited[curr] = True
        order.append(curr)
        for v in graph[curr]:
            if not visited[v]:
                stack.append(v)

I don't think that works actually

I think I misunderstood something

oh no it works, i just have to reverse order my bad
got rid of that horrible runtime error!!!!!!!!!

[golden ravine]

if i have two sets

for example

A= 1,2,3,4,

B= 1,2,3

what does

A and B

A or B mean

in these contexts

i know they have their own notations but idk how to make them in discord

is A and B comparing both sets and finding all the same elements?

[solemn moss]

If you mean just and and or, then they behave like usually

https://docs.python.org/3/reference/expressions.html#boolean-operations

The expression x and y first evaluates x; if x is false, its value is returned; otherwise, y is evaluated and the resulting value is returned.

The expression x or y first evaluates x; if x is true, its value is returned; otherwise, y is evaluated and the resulting value is returned.

A & B finds intersection of sets, A | B finds union of sets

[golden ravine]

this is huge thank you

[opal oriole]

Could you do any of the problems? Like the first one, contains duplicate?

[hard wyvern]

at what point in my programming journey should I start delving into algorithms and data structures? I have read a little bit of grokking algorithms but ive decided for now Im going to focus on doing personal projects to keep me out of my year long tutorial hell

[fiery cosmos]

You should implement data structures and algorithms while you work on your programming projects. Like try and solve 1 - 2 problems a day. Overtime that really adds up.

[young jay]

Hello guys! I have no idea if this issue should be reported here but, eitherways i would love to hear any suggestions on how i can fix this error. Unterminated string starting at: line 1 column 4092 (char 4091) its when im handlling large json responses.

[fiery cosmos]

#python-discussion

[stiff quartz]

Is there an easy proof that the operations in DSU with path compression & union by rank allow us to have an amortized time complexity of alpha(n) (inverse Ackermann Function) which is almost 1?

I only find people saying "we will skip the proof that it is but you can intuitively see that lolilol it's fast clearly"

But maybe I'm searching the wrong way

[haughty mountain]

I don't suspect the proof of that is easy, no

proving O(log^* n) is a slightly weaker result, but the wiki includes a proof for that

where log star is the number of times you need to apply log to get something <= 1

[lean walrus]

log is inverse of exponentiation
log* is inverse of tetration (repeated exponentiation)
right?

[haughty mountain]

it's related

the inverse of iteration tends to be called slog

super logarithm

but yeah, they are very related

log^* is an integer though

[stiff quartz]

that's good enough for me

what wiki are you referring to?

[haughty mountain]

https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Proof_of_O(m_log*_n)_time_complexity_of_Union-Find

[stiff quartz]

thanks!!

[stiff quartz]

did you read through their proof?

I'm struggling to understand the analysis for T3

I get that there are at most log*n buckets and there can't be more than 2n/2^B elements per bucket of size [B, 2^B-1]

[haughty mountain]

nope 🙃

[stiff quartz]

ah nvm no worries

i'll figure it out

[outer rain]

https://codeforces.com/blog/entry/98275 this is also this

did I reat it? no
do I believe it? yes

[lilac cradle]

in re, how do i get everything EXCEPT things that are specifically in square brackets
ive been trying to figure this out for like an hour but i cant get it to work

ok i found one online, no clue how it works but its r'\[[^\]]*\]|\([^\)]*\)|\"[^\"]*\"|\S+'

it actually just gets everything i think, i just ignore the match if it has "[" in it

[haughty mountain]

regex doesn't really do negative matching well

depending on what you actually need, maybe splitting on \[[^\]]*\] can be useful

or just do a linear time pass through the string with a stack if you need to handle nesting

[fiery cosmos]

Anyone help me

Im making image grab mod that lets u get images of ur pc when ur away

This is the errorr

[fiery cosmos]

#python-discussion

[lilac cradle]

is there an algorithm to calculate the sort of 'average result' for something like, say, repeating an action N times

now that i think of it more i guess for like a given percentage it'd just converge to that given a large sample size; i.e flipping a regular coin would have roughly N/2 heads and tails for N attempts, so its kind of a dumb question lol

[haughty mountain]

depends on the action

[lilac cradle]

yeah fair
but i think for my case i was just forgetting how statistics worked for a sec lol

[haughty mountain]

in general, the average result converges to the mean of the distribution

which in the case of a Bernoulli trial (e.g. a coin flip) is just the probability of success, yeah

[fiery cosmos]

Average is generally computed as a sum of probabilities and their weights. The more precise term is Expected Value. So in your coin flip example, the expected value of getting heads or tails is 1 / 2 * N. If for example the coin was weighted so that the probability of getting heads was 1 / 3 then the average or expected value of getting heads would be 1 / 3 * N

[slim galleon]

Hi can anyone suggest a full stack development project, easy to build

[haughty mountain]

topic pls

[fiery cosmos]

ToDo app

Functionalities:

• adding a new toDo
• editing existing toDo
• removing toDo
• UI for those activites and displaying UI

[haughty mountain]

topic pls

[ember igloo]

can someone help me implement this

https://arxiv.org/abs/cs/0206022

[agile moth]

tolerance and confidence How are they different in face recognition

[agile moth]

I have a problem with face detect, after turning on the webcam, there will be face detect, after that it will crop the face about 30 pictures, the picture sequence 1, 2, 3 have a chance to be incomplete. I think it is caused by the webcam not being ready to use, but it has started working, causing an error. I think I have to fix it at the point where when I start turning it on, I want it to be blank for about 3 seconds to prepare, after that start face detect and crop face. I think this method should solve the problem of corrupted images. Can anyone help me?

[fiery remnant]

Hello!
Any documentation based resource for dsa in python just like odin project?

[haughty mountain]

#data-science-and-ml will be a much better fit for these questions

[night haven]

hey i need some help, i made some python problems. can anyone tell me where they would rank on the leetcode scale? like whether they would be considered a leetcode easy/medium/hard. I dont have much exp in leetcode

[dusky creek]

just share the problem, if someone knows they'll reply

[night haven]

You are given a permutation array nums whos length is n and a positive integer X. For each index j=X, X+1, X+2.....n , find the X-th greatest value among the first j elements of nums.

For example:

For example, given an array (1,2,3) and X=2

For j=2, first greatest value among the first 2 terms of (1,2) is 2

For j=3, second greatest value among the first 3 terms of (1,2,3) is 2

can anyone rate?

[modern gulch]

Are you familiar with nested loops?

[modern gulch]

Oh you're just asking for ranking. I'd classify this as an easy.

[haughty mountain]

sounds quadratic

you can for sure do this in ~O(n log n)

O(n) might be possible, but no immediate idea there

[jolly mortar]

i cant relate the example to the statement

what are j, k and X

[haughty mountain]

I think the example is wrong yeah

[modern gulch]

Well yah, it's just a sliding window, so you can do it in single pass

[haughty mountain]

(1, 2, 3), X=2

(1, 2) -> 1
(1, 2, 3) -> 2

answer [1, 2]

this is an example that matches the statement

[modern gulch]

Since its average, you need to track sum of the window, and have memory of the window, so for each step you add new value and subtract the first value

[haughty mountain]

average?

[jolly mortar]

its not average though

[modern gulch]

Oh sorry, greatest value... remembered it wrong

[jolly mortar]

X'th greatest value

[haughty mountain]

you're tracking something similar to a median

a kth statistic

the typical median tracking algo that balances heaps would give you n log n

actually, you can do n log X with that, since you only really need to add/remove from one of the heaps in this case

[outer rain]

When j = X, answer is just min. You can then go for i in range(j + 1, n) and compare the i-th value to the last answer. There are two cases, in one the answer does not change, and in the other it's the next largest value in the prefix after the previous answer. Since the array is a permutation, you can track that in O(n) in total (with bitset and pointer to the current answer). I don't know about O(n) if array is not permutation.

[haughty mountain]

yeah, I'm kinda ignoring the permutation part

that's the less weird feeling problem anyway

[outer rain]

maybe O(X log X + n) is possible somehow

nah, unlikely

[night haven]

I meant j not k sorry. k is a typo

[pine glade]

guys i got a question. i built a minimax algorithm with python. if you dont know what it is its basically an algorithm that beats you at board games like chess or tic tac toe. i built one for tic tac toe and the wya it works is it recursively goes down the game tree looking at every single possible move, and at the end, assigns it a score of -1, 0, or 1, corresponding to whetrher the AI won, lost, or tied, and it then predicts if the player will go here or there (depending on the player it will go for the highest score or lowest to make the AI win or lose) and when it goes all the way back up it chooses the best move.

I made several enhancements to the algorithm. currently on my computer its not an actual tic tac toe game its just a program that simulates the algorithm and gives you data on the time complexity.

With the first version each match of tic tac toe took 2657 milliseconds. After all the enhancements i got it down to 0.89934 milliseconds, which is pretty fast.

It calls the recursive method 45 times in the first move, then 8, then 7, and slowly goes down. (this is on average)

The issue is that i tried upping it to a 4x4 board to get more data points and the program ended up running for like 2 whole minutes and threw a "MemoryError".

How do i fix this? What can i do with my program to lower the memory usage

[hybrid umbra]

can anyone tell me on discord how can i format the code like this

like will it only be shown in python code ?

like this one ?

[narrow mica]

```py
print('python code')
```

print('python code')

[hybrid umbra]

what about cpp ?

hmm got that

thanks

[narrow mica]

replace the py there with cpp

I think discord uses highlight.js, so for a full list of supported langs maybe check that

[outer rain]

I think you cache something, otherwise idk how minimax can take that much memory, and you simply solve the game until completion. That said, 4x4 tic tac toe has A LOT of states, and you probably will have to squeeze a lot of performance out of your algorithm to make it somewhat real-time. Let alone 5x5. If you want to analyze more interesting games, you usually don't run minimax until completion, and instead run it to some depth (not necessarily uniform across all search space) and once you reach the limit, evaluate the position approximately, and use that instead. That's kind of the whole point of minimax: using an evaluation instead of completely solving the game. You can try doing alpha-beta pruning then, it reduces search space drastically.

[ripe prism]

Quick update, I have started to understand a bit, I managed to solve a medium problem using two pointers and currently progressing

[night haven]

Alice's teacher gave her a task. The teacher provided Alice with an array A containing N unique positive integers.

Then teacher told her you can draw an edge between
a[i] and a[j] if gcd(a[i], a[j]) > 1 where gcd denotes the greatest
common divisor.

The task is to identify the largest connected component within the graph.

how would you rate this?

leetcode easy/medium/hard

[modern gulch]

I dunno, leetcode rates it as a hard - https://leetcode.com/problems/largest-component-size-by-common-factor/description/

[pine glade]

I used lots of enhancements already. If you go to #game-development you’ll see the list of stuff I added which includes those things you mentioned. I believe the problem is the transposition tables. Whenever I compute the value for a state, I save it onto a dictionary so that next time I come across it I can directly get it from there instead of using the recursive method. This cut down on the time by a lot but now with so many states I believe the size of it would be approximately 16!

[plucky umbra]

I'm making a bot on a host, I get an error and I think it's something with the token, can I send you the code of my bot and you can check what's wrong? My bot doesn't turn on because of that error and I don't know what's wrong.

[willow hollow]

what is the right book to start dsa in python ? any suggestions

[stiff quartz]

What's the real definition of a Euler Tour?

I see sometimes this

And sometimes this

Both from Geeksforgeeks

Trying to learn how to do segment trees on trees

But struggling to find any consistency between tutorials

Maybe both work?

[stiff quartz]

I managed to do range sum queries on sub trees of a rooted tree

But I don’t understand why the Euler tour is relevant at all

We can just use the dfs order as the flattened array

Im so confused

[haughty mountain]

a dfs order doesn't give enough info to recreate the tree, if that matters

[stiff quartz]

Ah makes sense

[kind oracle]

Can anybody help me work out what steps need to be taken in order to determine if two tiles can be removed in a game of shisen sho? https://en.wikipedia.org/wiki/Shisen-Sho

This picture represents a shisen sho board. Each tile is represented as such:

class Tile:
  x: int
  y: int
  kind: str
  removed: bool = False

These tiles are populated in a 2d array.

Given the input of two tiles after checking if they are the same kind, I need to find if the path is clear between the tiles respecting the rules of the game (check link). I've tried walking the board starting from a position of one of the tiles but it quickly turns into a mess once I start introducing turns. Is there an obvious way to do it?

I've tried looking at other people's implemetation but:
https://github.com/shlomif/PySolFC/blob/master/pysollib/games/mahjongg/shisensho.py this one seems to be using a direction walking method and looks like a mess
https://github.com/knilch0r/freeshisen/blob/master/app/src/main/java/de/cwde/freeshisen/Board.java and this one seems to solve this by drawing lines which I also don't like

[kind oracle]

X - columns, Y - rows, if it's not clear

[haughty mountain]

thinking out loud, for 0/1 turn try expanding from one tile vertically and the other tile horizontally (and vice versa), if the expansions meet you have a 1 (or possibly 0) turn path

for 2 turn you would expand both horizontally, and then check if there is any vertical line that can connect the horizontals (or again, swap horizontal/vertical)

vague sketch, expand blue as much as you can, then check if any red line connecting the blues exist

[kind oracle]

Looks good to me, I'll try that, thank you 🙏

[final night]

I found a post about binary search.
I don't understand
we're looking for the min k such that k^2>n and the answer to that is k-1 ? How?
say n = 24, then for k =5, k^2 = 25>24, but clearly (k-1)^2 = 16 does not satisfy this condition

what?

What exactly is going on here?

https://leetcode.com/discuss/general-discussion/786126/Python-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems

[outer rain]

The intended integer square root of 24 is indeed 4. They should have defined sqrt as the max k such that k^2 <= n (it's the same as int(sqrt(n)), well, assuming the exact floating point arithmetic smh)

oh, wait, it's actually defined as such

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

[final night]

this : max k such that k^2 <= n makes sense
this: min k such that k^2 > n is k-1 does not make sense

the integer square root of 24 is 4, but I'm specifically talking about the condition for the algorithm

in the end they're returning k-1 after finding the min k that satisfies k^2>x. it makes sense when you look at it this way but the sentence itself makes zero sense

nevermind actually

[regal spoke]

Segment tree on trees? Only time I've heard that it has involved splay trees

[regal spoke]

What do you mean by segment tree on trees?

Oh you are talking about subtree queries and not path queries

[stiff quartz]

Yes sorry I was talking about https://cses.fi/problemset/task/1137/

I ended up doing it with just dfs order which I guess is good enough for this exercise

I don't know if it's called Euler tour but it's basically Euler tour without repetitions

@regal spoke Are you aware if it's possible to sum over (or max over, etc) all ancestors (query & update) instead of sum over (or max over, etc) the **subtree **(query & update)?

e.g. for this tree if I ask query(2) I would like to get val(2) + val(4) + val(5) + val(1)

I feel like this should be similar, we need to flatten the array somehow so that all indices after 2 are its ancestors

Although I guess that would not be possible since 4 is 2's ancestor and 3's ancestor too 🤔