A
Answer can be 0 - ~10^100, so it only depends on the answer how mush steps it will take (I think)
Is there a better way of doing this problem(optimised way)?
Size: a a a
2020 April 08
A(
Ajay
Is there a better way of doing this problem(optimised way)?
where did you find this problem?
A
where did you find this problem?
cchef
A(
link?
MB
Ajay
Is there a better way of doing this problem(optimised way)?
dp[cnt][people_set]
Numbers of ways to assign first
Numbers of ways to assign first
cnt shirts to all people from people_set (some shirts can be unused)A
dp[cnt][people_set]
Numbers of ways to assign first
Numbers of ways to assign first
cnt shirts to all people from people_set (some shirts can be unused)Is this the same as I explained above?
MB
Ajay
Is this the same as I explained above?
Your solution does not use dynamic programming.
A
Your solution does not use dynamic programming.
At each recusion, I am ensuring that I don't give a t-shirt to someone who has already got one in the previous steps of recursion. Is there more that I need?
MB
Ajay
At each recusion, I am ensuring that I don't give a t-shirt to someone who has already got one in the previous steps of recursion. Is there more that I need?
My solution has time complexity O(2**N * R). I am not sure if your bruteforce is as fast
MB
But if you add some memoization, you will achieve desired complexity
A
My solution has time complexity O(2**N * R). I am not sure if your bruteforce is as fast
Can you explain how you arrived at your solution? I've started learning dp+bitmasking but couldn't get to the approach of this problem. Why are we dealing with different sets of people and how is it R* 2^N?
EZ
https://twitter.com/sadisticsystems/status/1247780313691901952
Чот туплю, можно ли замутить гибридный интерполяционно-бинарный поиск с средним log log n и худшим log n?🤔
Чот туплю, можно ли замутить гибридный интерполяционно-бинарный поиск с средним log log n и худшим log n?🤔
MB
https://twitter.com/sadisticsystems/status/1247780313691901952
Чот туплю, можно ли замутить гибридный интерполяционно-бинарный поиск с средним log log n и худшим log n?🤔
Чот туплю, можно ли замутить гибридный интерполяционно-бинарный поиск с средним log log n и худшим log n?🤔
In fact, DP is very similar to bruteforce with memoization.
BF can look like this:
void solve(people, current_shirt) {
if people.empty() {
++ans;
return;
}
if current_shirt == R {
return;
}
for p in people {
if current_shirt in allowed[p] {
solve(people - p, current_shirt+1)
}
}
}
It is slow solution, smth like O(answer)
Now, let's introduce memoization:
memo[people][current_shirt] = x;
such that solve(people, current_shirt) will increment
Now solve looks like:
solve(people, current_short) {
if (people, current_shirt) in memo {return memo[people][current_shirt]}
t = _solve_inner(people, current_shirt);
memo[people][current_shirt] = t
return t
}
We can see that each (people, current_shirt) pair will be processed once: after that it will be inserted into cache.
It means that now we have at most O(MAX_CACHE_SIZE) recursive calls, and cache size if R*(2**N)
BF can look like this:
void solve(people, current_shirt) {
if people.empty() {
++ans;
return;
}
if current_shirt == R {
return;
}
for p in people {
if current_shirt in allowed[p] {
solve(people - p, current_shirt+1)
}
}
}
It is slow solution, smth like O(answer)
Now, let's introduce memoization:
memo[people][current_shirt] = x;
such that solve(people, current_shirt) will increment
ans x times.Now solve looks like:
solve(people, current_short) {
if (people, current_shirt) in memo {return memo[people][current_shirt]}
t = _solve_inner(people, current_shirt);
memo[people][current_shirt] = t
return t
}
We can see that each (people, current_shirt) pair will be processed once: after that it will be inserted into cache.
It means that now we have at most O(MAX_CACHE_SIZE) recursive calls, and cache size if R*(2**N)
EZ
In fact, DP is very similar to bruteforce with memoization.
BF can look like this:
void solve(people, current_shirt) {
if people.empty() {
++ans;
return;
}
if current_shirt == R {
return;
}
for p in people {
if current_shirt in allowed[p] {
solve(people - p, current_shirt+1)
}
}
}
It is slow solution, smth like O(answer)
Now, let's introduce memoization:
memo[people][current_shirt] = x;
such that solve(people, current_shirt) will increment
Now solve looks like:
solve(people, current_short) {
if (people, current_shirt) in memo {return memo[people][current_shirt]}
t = _solve_inner(people, current_shirt);
memo[people][current_shirt] = t
return t
}
We can see that each (people, current_shirt) pair will be processed once: after that it will be inserted into cache.
It means that now we have at most O(MAX_CACHE_SIZE) recursive calls, and cache size if R*(2**N)
BF can look like this:
void solve(people, current_shirt) {
if people.empty() {
++ans;
return;
}
if current_shirt == R {
return;
}
for p in people {
if current_shirt in allowed[p] {
solve(people - p, current_shirt+1)
}
}
}
It is slow solution, smth like O(answer)
Now, let's introduce memoization:
memo[people][current_shirt] = x;
such that solve(people, current_shirt) will increment
ans x times.Now solve looks like:
solve(people, current_short) {
if (people, current_shirt) in memo {return memo[people][current_shirt]}
t = _solve_inner(people, current_shirt);
memo[people][current_shirt] = t
return t
}
We can see that each (people, current_shirt) pair will be processed once: after that it will be inserted into cache.
It means that now we have at most O(MAX_CACHE_SIZE) recursive calls, and cache size if R*(2**N)
??
MB
MB
In fact, DP is very similar to bruteforce with memoization.
BF can look like this:
void solve(people, current_shirt) {
if people.empty() {
++ans;
return;
}
if current_shirt == R {
return;
}
for p in people {
if current_shirt in allowed[p] {
solve(people - p, current_shirt+1)
}
}
}
It is slow solution, smth like O(answer)
Now, let's introduce memoization:
memo[people][current_shirt] = x;
such that solve(people, current_shirt) will increment
Now solve looks like:
solve(people, current_short) {
if (people, current_shirt) in memo {return memo[people][current_shirt]}
t = _solve_inner(people, current_shirt);
memo[people][current_shirt] = t
return t
}
We can see that each (people, current_shirt) pair will be processed once: after that it will be inserted into cache.
It means that now we have at most O(MAX_CACHE_SIZE) recursive calls, and cache size if R*(2**N)
BF can look like this:
void solve(people, current_shirt) {
if people.empty() {
++ans;
return;
}
if current_shirt == R {
return;
}
for p in people {
if current_shirt in allowed[p] {
solve(people - p, current_shirt+1)
}
}
}
It is slow solution, smth like O(answer)
Now, let's introduce memoization:
memo[people][current_shirt] = x;
such that solve(people, current_shirt) will increment
ans x times.Now solve looks like:
solve(people, current_short) {
if (people, current_shirt) in memo {return memo[people][current_shirt]}
t = _solve_inner(people, current_shirt);
memo[people][current_shirt] = t
return t
}
We can see that each (people, current_shirt) pair will be processed once: after that it will be inserted into cache.
It means that now we have at most O(MAX_CACHE_SIZE) recursive calls, and cache size if R*(2**N)
This is reply to Ajay
SP
Здравствуйте,можете подсказать пожалуйста,мне надо удалить из бинарного дерева корневой элемент (у него есть левое и правое поддерево)для этого мне нужно найти в правом поддереве крайний левый узел и вставить его на место удаляемого узла,но дело в том что в моем правом поддереве у узлов нету левых дочерних узлов,какой узел мне выбрать?
Д🍋
первый правый
если это дерево поиска
если это дерево поиска
TS
Sergey Polyakov
Здравствуйте,можете подсказать пожалуйста,мне надо удалить из бинарного дерева корневой элемент (у него есть левое и правое поддерево)для этого мне нужно найти в правом поддереве крайний левый узел и вставить его на место удаляемого узла,но дело в том что в моем правом поддереве у узлов нету левых дочерних узлов,какой узел мне выбрать?
В таком случае крайний левый узел правого поддерева — это корень правого поддерева.