K
Двумерное дерево отрезков
Size: a a a
2020 October 06
ИС
А, расстояние манхеттенское.
ИС
Да, тогда само собой.
ИС
Я пропустил, думал, евклидово.
K
Если у Вас есть его код, пишите в личку
AD
а повернуть на 45 не работает?
ИС
Повернуть на 45 работает в R^2, в больших размерностях можно обобщать, но чуть сложнее (и за 2^d, да).
2020 October 07
q
q
Подскажите плиз, как можно оптимизировать? Не проходит последний тест(TL)
S
БОЛЬШЕ СКРИНШОТОВ КОДА!
IS
Подскажите плиз, как можно оптимизировать? Не проходит последний тест(TL)
посмотри решение
IS
так быстрее всего 🙃
A
твоё решение работает за O(MAX_H * N), перепиши так чтобы работало за O(N)
DK
Да можно и O(N log N): для каждого столбца находить бинпоиском максимальную высоту, которая не выльется, используя максимум на префиксе и максимум на суффиксе
IS
А разве можно без доп памяти? 🤔
q
i've task
You are going to be given an array of integers. Your job is to take that array and find an index N where the sum of the integers to the left of N is equal to the sum of the integers to the right of N. If there is no index that would make this happen, return -1.
For example:
Let's say you are given the array {1,2,3,4,3,2,1}: Your function will return the index 3, because at the 3rd position of the array, the sum of left side of the index ({1,2,3}) and the sum of the right side of the index ({3,2,1}) both equal 6.
Let's look at another one.
You are given the array {1,100,50,-51,1,1}: Your function will return the index 1, because at the 1st position of the array, the sum of left side of the index ({1}) and the sum of the right side of the index ({50,-51,1,1}) both equal 1.
Last one:
You are given the array {20,10,-80,10,10,15,35}
At index 0 the left side is {}
The right side is {10,-80,10,10,15,35}
They both are equal to 0 when added. (Empty arrays are equal to 0 in this problem)
Index 0 is the place where the left side and right side are equal.
Note: Please remember that in most programming/scripting languages the index of an array starts at 0.
Input:
An integer array of length 0 < arr < 1000. The numbers in the array can be any integer positive or negative.
Output:
The lowest index N where the side to the left of N is equal to the side to the right of N. If you do not find an index that fits these rules, then you will return -1.
Note:
If you are given an array with multiple answers, return the lowest correct index.
there is my solution:
https://pastebin.com/z48Y09Hx
but in check tacking array [1,2,3,4,5,6] and answer must be -1 but i got 6, coz we have 3 value from left its 6 and 1 value from right 6
what i do wrong , i need help
You are going to be given an array of integers. Your job is to take that array and find an index N where the sum of the integers to the left of N is equal to the sum of the integers to the right of N. If there is no index that would make this happen, return -1.
For example:
Let's say you are given the array {1,2,3,4,3,2,1}: Your function will return the index 3, because at the 3rd position of the array, the sum of left side of the index ({1,2,3}) and the sum of the right side of the index ({3,2,1}) both equal 6.
Let's look at another one.
You are given the array {1,100,50,-51,1,1}: Your function will return the index 1, because at the 1st position of the array, the sum of left side of the index ({1}) and the sum of the right side of the index ({50,-51,1,1}) both equal 1.
Last one:
You are given the array {20,10,-80,10,10,15,35}
At index 0 the left side is {}
The right side is {10,-80,10,10,15,35}
They both are equal to 0 when added. (Empty arrays are equal to 0 in this problem)
Index 0 is the place where the left side and right side are equal.
Note: Please remember that in most programming/scripting languages the index of an array starts at 0.
Input:
An integer array of length 0 < arr < 1000. The numbers in the array can be any integer positive or negative.
Output:
The lowest index N where the side to the left of N is equal to the side to the right of N. If you do not find an index that fits these rules, then you will return -1.
Note:
If you are given an array with multiple answers, return the lowest correct index.
there is my solution:
https://pastebin.com/z48Y09Hx
but in check tacking array [1,2,3,4,5,6] and answer must be -1 but i got 6, coz we have 3 value from left its 6 and 1 value from right 6
what i do wrong , i need help
T
Как такое решать на фулл?
A
ухты, фотка экрана
T
Могу файлом кинуть
A
я бы предпочел копи-паст текста или ссылку на текст