Задачки

katrin2201

Скажите, а если я буду постить какие-нибудь не сильно сложные алгоритмические задачки раз в неделю-две, у кого-то будет интерес в них ковыряться помимо меня?
Вот примерно такого уровня задачки:
A non-empty zero-indexed array A consisting of N integers is given.
A monotonic_pair is a pair of integers (P, Q such that 0 ≤ P ≤ Q < N and A[P] ≤ A[Q].
The goal is to find the monotonic_pair whose indices are the furthest apart. More precisely, we should maximize the value Q − P. It is sufficient to find only the distance.
For example, consider array A such that:
A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2
There are eleven monotonic_pairs: (0,0 (0, 2 (1, 1 (1, 2 (1, 3 (1, 4 (2, 2 (3, 3 (3, 4 (4, 4 (5, 5). The biggest distance is 3, in the pair (1, 4).
Write a function:
int solution(int A[], int N);
that, given a non-empty zero-indexed array A of N integers, returns the biggest distance within any of the monotonic_pairs.
For example, given:
A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2
the function should return 3, as explained above.
Assume that:
N is an integer within the range [1..300,000];
each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

katrin2201

Вроде интерес какой-то есть, давайте пробовать. Предлагаю размяться на задачке в пред посте
Пока все относительно просто, поэтому сразу решение постить неинтересно. Если кому-то надо, могу выдать наталкивающую на мысль задачку.

Serab

ты сайт пиаришь что ли o_O

регаться не охота, а задачки давай, это круто, надо чаще мозги разминать

Serab

хотя не, наврал, ща напишу правильное

katrin2201

Не, какой пиар, сайт не мой. Просто одиноко одному мучать задачки Хочется с кем-то поделиться
Регаться там не надо, кстати, просто вводишь в начальной форме имя-почту и поехал.

Serab

жесть какая. Одну попытку что ли дают?
Блин, сайт не очевидный.

Serab

лол
http://codility.com/cert/view/certT3PEPX-DTE4MZK6SXJXYEBV
дали какую-то хуйню. Я не понимаю этот сайт
как дать такую же ссылку, как и тебя, хз.

Serab

вообще мое мнение: такие задачи они не только на алгоритм, но и на красивый понятный код.
дальше немного о задаче

Serab

давай еще интересные задачки. Только не слишком много, еще работать надо

katrin2201

Посередине странички по твоей ссылки есть линк - review detailed assesment.

katrin2201

Да, у меня все так же

katrin2201

Ога

Serab

кстати, а питончик-то сделал джаву
http://codility.com/cert/view/certT3PEPX-DTE4MZK6SXJXYEBV/d...

katrin2201

Да, грустно, но они там хрень какую-то меряют в случае джавы (700мс на экзампл тест из 10 чисел - лол)

zorin29

Отмечаюсь в данном треде. Мне тоже интересны задачки, твою решил практически так же, как и _Ss_ .

Julia79

Задачки это тема! Есть очень неплохой проект Эйлер для алгоритмических задач - 465 задач, после решения каждой доступен форум с решениями:
http://projecteuler.net/problems

VitMix

Скажите, а если я буду постить какие-нибудь не сильно сложные алгоритмические задачки раз в неделю-две, у кого-то будет интерес в них ковыряться помимо меня?

Только на русском языке пости, пожалуйста. Тебе всё равно, а людям приятно. С удовольствием поковыряемся.