Тестовое задание от питерского представительства крупной западной конторы.
Разместил в этюдах

Автор: Skorodum
Дата: 25.11.10

, т.к. мне задача понравилась: чисто алгоритмическая и не было её решения в гугле. На решение 24 часа.
Но работодателю чем-то не понравилось мое решение. Общался через кадровое агенство и никаких комментариев от работодателя им добиться не удалось, поэтому моя совесть не грызет меня за раскрытие тестового задания.
Может кто подскажет, что совсем отталкивает?

Здравствуйте, Skorodum, Вы писали:

S>Может кто подскажет, что совсем отталкивает?

дрочуны они в том представительстве. Вы уверены что хотите у них работать? =)
Ну незачем давать такие задания апп девелоперу. В реальной жизни такое никогда ему не встретится.

Здравствуйте, Alf, Вы писали:

Alf>Здравствуйте, Skorodum, Вы писали:

Alf>дрочуны они в том представительстве. Вы уверены что хотите у них работать? =)
Alf>Ну незачем давать такие задания апп девелоперу. В реальной жизни такое никогда ему не встретится.

Я уже устроился. Мне задание понравилось: мозги немного напрягает и никакой практической полезности, интересно что неправильно.
Внутри компанию не видел и не с кем не общался, так что не знаю, насколько я захотел бы там работать.

Здравствуйте, Skorodum, Вы писали:

S>Тестовое задание от питерского представительства крупной западной конторы.
S>Разместил в этюдах

Автор: Skorodum
Дата: 25.11.10

, т.к. мне задача понравилась: чисто алгоритмическая и не было её решения в гугле. На решение 24 часа.
S>Но работодателю чем-то не понравилось мое решение. Общался через кадровое агенство и никаких комментариев от работодателя им добиться не удалось, поэтому моя совесть не грызет меня за раскрытие тестового задания.
S>Может кто подскажет, что совсем отталкивает?

для точного ответа я бы не стал использовать sqrt

Здравствуйте, Skorodum, Вы писали:

S>Тестовое задание от питерского представительства крупной западной конторы.
S>Разместил в этюдах

Автор: Skorodum
Дата: 25.11.10

, т.к. мне задача понравилась: чисто алгоритмическая и не было её решения в гугле. На решение 24 часа.
S>Но работодателю чем-то не понравилось мое решение. Общался через кадровое агенство и никаких комментариев от работодателя им добиться не удалось, поэтому моя совесть не грызет меня за раскрытие тестового задания.
S>Может кто подскажет, что совсем отталкивает?

Я не силен срр, но при y — x = 1 оно нормально себя поведет?

Предлагаю такое решение.
Для начала определим пороговые случаи абсолютно симметричных прогрессий, составляющих некоторые четные числа (до середины вверх и с средины вниз). Особенность такого представления состоит в том, что бОльшая разница между x и y уже потребует бОльшего количества значений. Вот примеры:
(y-x) мин кол-во элементов
2 2
6 4
12 6
20 8
30 10
42 12

Из этого набора видно, что количество элементов одной из прогрессий (т.е. половины элементов) можно определить как:
n = Floor(sqrt(y-x))

осталось только вернуть искомое количество
if ((y-x) == (n*n)) -- нижний порог
return n * 2 — 1;
else if ((y-x) <= (n*n + n) ) -- верхний порог
return n * 2;
else
return n * 2 + 1;

Здравствуйте, Skorodum, Вы писали:

S>Тестовое задание от питерского представительства крупной западной конторы.
S>Разместил в этюдах

Автор: Skorodum
Дата: 25.11.10

, т.к. мне задача понравилась: чисто алгоритмическая и не было её решения в гугле. На решение 24 часа.
S>Но работодателю чем-то не понравилось мое решение. Общался через кадровое агенство и никаких комментариев от работодателя им добиться не удалось, поэтому моя совесть не грызет меня за раскрытие тестового задания.
S>Может кто подскажет, что совсем отталкивает?

Если я правильно понял задачу, в чем я сомневаюсь, то задача абсолютно идиотическая.
Первый шаг 1, последний 1, промежуточные — без ограничений. Получается что минимальное количество шагов три
шаг 1 = 1
шаг 2 = y-x-2
шаг 3 = 1

Муть полнейшая. Я, кстати, совсем не понял необходимость в векторе, когда задача решается за один проход.

Здравствуйте, Skorodum, Вы писали:

S>Может кто подскажет, что совсем отталкивает?

Ну вообще поскольку задача относительно простая, то явно собирались смотреть на стиль кода — комментарии, именование переменных, обработка ошибок. Я не смотрел правильность математики (да, вечер, лень), но оформление явно никуда не годится. Или к работодателю ушел другой вариант, с нормальными комментами и именами переменных? Просто по хорошему по комментариям должно понятно назначение и работа программы. Сейчас глядя на код вообще непонятно что и как программа делает — чего-то где-то ввела (без вывода приглашения, без подсказок), чего-то поколбасила, чего-то вывела. В таком коде даже на саму математику смотреть не хочется.

Здравствуйте, Skorodum, Вы писали:

S>Тестовое задание от питерского представительства крупной западной конторы.
S>Разместил в этюдах

Автор: Skorodum
Дата: 25.11.10

, т.к. мне задача понравилась: чисто алгоритмическая и не было её решения в гугле. На решение 24 часа.
S>Но работодателю чем-то не понравилось мое решение. Общался через кадровое агенство и никаких комментариев от работодателя им добиться не удалось, поэтому моя совесть не грызет меня за раскрытие тестового задания.
S>Может кто подскажет, что совсем отталкивает?

содержимое функции, цикл while не более 31 (?30?) раз

int len = y-x;
if (len == 0) return 0;
if (len == 1) return 1;
int stepsize = 1, steps = 0;
while(len >= 2*stepsize)
{
    len -= 2*stepsize;
    stepsize++;
    steps += 2;
}
if (len > stepsize) return steps+2;
if (len > 0) return steps+1;
return steps;

Здравствуйте, Skorodum, Вы писали:

Задачу можно преобразовать в задачу, где по сумме натуральных чисел надо вычислить их количество.
Т.е. прогрессия в общем случае выглядит так:

0 -> +1 -> +2 -> +3 -> +4 -> ... -> +4 -> +3 -> +2 -> +1 -> =X

Где X — это разность y-x исходного диапазона.

Отсюда, чтобы получить минимальное количество шагов, прогрессия слева должна постоянно расти. Регрессия справа должна постоянно убывать начиная с определённой позиции.
Получается уравнение общего вида:

P + R = X

где:
P — сумма чисел прогрессии до некоторой позиции N.
R — сумма чисел регрессии от некоторой позиции N.

Очевидно, что R зависит от P, иначе можно "не успеть" зарегресситься до +1 по условию задачи. Но также очевидно, что прогрессия и регрессия симметричны для чётных X, т.к. разность соседних шагов тоже симметрична. А т.к. по условиям задачи ближайшие шаги могут совпадать по значению, то для нечётного X можно вставить недостающий шаг в нужное место один раз.

Отсюда X надо привести к чётному в меньшую сторону и поделить на 2, чтобы получить сумму и прогресси (и регресии, т.к. в этом случае P = R).
А дальше надо по сумме прогрессии от +1 до +N (где N — чётное) получить N (надеюсь сами догадаетесь как ).

Если X чётное, то шагов 2xN;
Если X нечётное, то шагов 2xN+1;

Вообщем, как-то так.

Здравствуйте, ilnar, Вы писали:

I>Здравствуйте, Skorodum, Вы писали:

S>>Тестовое задание от питерского представительства крупной западной конторы.
S>>Разместил в этюдах

Автор: Skorodum
Дата: 25.11.10

, т.к. мне задача понравилась: чисто алгоритмическая и не было её решения в гугле. На решение 24 часа.
S>>Но работодателю чем-то не понравилось мое решение. Общался через кадровое агенство и никаких комментариев от работодателя им добиться не удалось, поэтому моя совесть не грызет меня за раскрытие тестового задания.
S>>Может кто подскажет, что совсем отталкивает?

I>содержимое функции, цикл while не более 31 (?30?) раз
I>

I>int len = y-x;
I>if (len == 0) return 0;
I>if (len == 1) return 1;
I>int stepsize = 1, steps = 0;
I>while(len >= 2*stepsize)
I>{
I>    len -= 2*stepsize;
I>    stepsize++;
I>    steps += 2;
I>}
I>if (len > stepsize) return steps+2;
I>if (len > 0) return steps+1;
I>return steps;
I>

с оценкой while лажа, сорри

Здравствуйте, Vain, Вы писали:

V>Вообщем, как-то так.
Также наблюдается некоторая рекурсия с остатком. Пример:

X=18
Ряд: +1, +2, +3, ..., +3, +2, +1
Остаток: +6

Ещё раз натравливаем алгоритм:

X=6
Ряд: +1, +2, ..., +2, +1
Остаток: 0

Результирующий ряд:

+1, +2, +3, +3, +3, +3, +2, +1

Ряд +1, +2, ..., +2, +1 Можно свести к +3, ..., +3 через аккумуляцию.

Здравствуйте, JointIntelligence, Вы писали:

JI>Предлагаю такое решение.

Собственно, я так и решил. Вроде никаких подводных камней, что не понравилось

Здравствуйте, Handie, Вы писали:

H>Здравствуйте, Skorodum, Вы писали:

H>Муть полнейшая. Я, кстати, совсем не понял необходимость в векторе, когда задача решается за один проход.

Ну вот если бы я так ответил, было бы не удивительно что мне не предложили даже собеседования.

Здравствуйте, Jesmus, Вы писали:

J>Здравствуйте, Skorodum, Вы писали:

S>>Может кто подскажет, что совсем отталкивает?

J>Ну вообще поскольку задача относительно простая, то явно собирались смотреть на стиль кода — комментарии, именование переменных, обработка ошибок. Я не смотрел правильность математики (да, вечер, лень), но оформление явно никуда не годится. Или к работодателю ушел другой вариант, с нормальными комментами и именами переменных? Просто по хорошему по комментариям должно понятно назначение и работа программы. Сейчас глядя на код вообще непонятно что и как программа делает — чего-то где-то ввела (без вывода приглашения, без подсказок), чего-то поколбасила, чего-то вывела. В таком коде даже на саму математику смотреть не хочется.

Какие комментарии к полуолимпиадным задачам? Наверняка они уже видели не одно решение и комментарии по способу решения им ничего нового не скажут. Задание чисто математическое, на 7 строчек. Если бы это было что-то типа "чат в локальной сети", "копирование двусвязного списка с одним рандомным указателем", "умный указатель на массив", тогда да: комментарии, обработка ошибок и т.д. и т.п.

Здравствуйте, Skorodum, Вы писали:


S>Собственно, я так и решил. Вроде никаких подводных камней, что не понравилось

Вероятно требовалось не математическое решение, а алгоритмическое, что предложил выше ilnar

Здравствуйте, ilnar, Вы писали:

Решение верное, я до него тоже дошел, но отправить не успел. Для больших чисел более медленное, чем например такое

Автор: JointIntelligence
Дата: 25.11.10

.

Здравствуйте, Vain, Вы писали:

Ну вот я примерно так же и рассуждал, только как-то чуть попроще

Так откуда такой снобизм что не отвечают почему выполнение не понравилось? Сложно 2 слова сказать/написать девушки из кадрового агенства?
Находящиеся за границей компании ведут себя куда вежливее.

Вот так и складывается репутация компании.

З.Ы. Про плохие слухи о Parallels знают даже в кадровом агентстве, хоть лично я против них пока ничего не имею.

Здравствуйте, JointIntelligence, Вы писали:

JI>Вероятно требовалось не математическое решение, а алгоритмическое, что предложил выше ilnar

х-м-м... "математическое" != "алгоритмическое" ????
"математическое" как минимум быстрее...

Здравствуйте, ilnar, Вы писали:

I>Здравствуйте, Skorodum, Вы писали:

S>>Тестовое задание от питерского представительства крупной западной конторы.
S>>Разместил в этюдах

Автор: Skorodum
Дата: 25.11.10

, т.к. мне задача понравилась: чисто алгоритмическая и не было её решения в гугле. На решение 24 часа.
S>>Но работодателю чем-то не понравилось мое решение. Общался через кадровое агенство и никаких комментариев от работодателя им добиться не удалось, поэтому моя совесть не грызет меня за раскрытие тестового задания.
S>>Может кто подскажет, что совсем отталкивает?

I>содержимое функции, цикл while не более 31 (?30?) раз
I>

I>int len = y-x;
I>if (len == 0) return 0;
I>if (len == 1) return 1;
I>int stepsize = 1, steps = 0;
I>while(len >= 2*stepsize)
I>{
I>    len -= 2*stepsize;
I>    stepsize++;
I>    steps += 2;
I>}
I>if (len > stepsize+1) return steps+2;
I>if (len > 0) return steps+1;
I>return steps;
I>

исправил
if (len > stepsize+1) return steps+2;
т.к. можно еще на один пойти выше, и пойти на спуск
иначе если выше, придется где-то в 2-х местах шагнуть не меняя размер шага
если меньше, то только один