Codility
Тут была тема, но в связи с прошедшим дедлайном она более не релевантна.
×
Facebook
Twitter
LinkedIn
mobile mobile
Тест прошёл, вопросы оказались очень легкими. Результаты пока не известны.
mobile mobile
я ж тебе говорил — не паникуй, куда тысячу потратишь ?
Grez
Кстати, любопытства ради, гденить на фриланс.сру искать пробовали ?
Alex Kukharchuk
Yurii V
Я думаю Вам потрібно було звернутись на факультету Кібернетика, до викладачів, щоб вони допомогли особисто чи дали студентів. В них рука набита на ТопКодер чи інших.
Обращался в личку к Киевским ребятам с Codeforces, студентам, к семи, или восьми. Во всех случая получил отказ.
Только один написал, что ему к сесии надо готовится, и он занят. Остальные ограничились молчанием в ответ.
Видимо тысяча доларов для украинского студента, за два часа работы — это слишком мало сейчас.
Yurii V
Можливо вони думали, що тут якийсь підвох (дадуть по голові і гроші заберуть, наспокійна часи настали). Звикли студенти до 15 грн/год, а тут такий куш. Або солідарність.
Можливо потрібно зробити трохи інший формат. Провести змагання із спортивного програмування — призовий фонд 1к $.
Andrey
После теста в кодилити частенько идет следующее собеседование с разбором написанного. Так что смотрите чтобы штукарь не пропал зря.
Это меня не пугает, с решением задач у меня все в порядке: легкие решаются примерно за час, на сложную вчера потратил два с половиной. Пугают заанные временные рамки: во время теста на каждую задачу даётся пол часа. Так быстро у меня не получается. В целом мнут
Коля Пещерный
Времени все меньше и меньше, повышаю ставки.
Плачу 1000 долларов за два часа работы. 500 до теста, 500 после.
нефигасе ты валишь ) покажи пример задачки, скажи на каком языке писать код, когда и в какой аудитории сдавать ???
codility.com/...ammers/lessons
можно брать любую задачу из списка, писать можно на любом языке.
а какая у вас заняла 2а часа ? какой уровень ?
«MaxCounters» из раздела Counting Elements, но хотя в этом примере проблема была не в реализации алгоритма, а в том что Codility поддерживает формат С90, и в случае объявления в функции массива через переменную в структуру Result у меня попадал рэндомый мусор из памяти. До сих пор не могу понять почему так.
Помогло объвление массива таким способом: int *C = calloc(N,sizeof(int));
Да, я тесты пробую на С проходить.
а нетом пользоваться можно или нет ?
конечно можно, но, если для демо задач полно решений на всех языках, то для реальных не думаю что можно найти уже готовые решения, поэтому на тренировке я полагался только на свои силы.
скука сложные условия, одно понимание занимает 10 минут. Осталось 20 минут на кодинг — это в принципе мало. думаю за 40 минут реально справится с отладкой. Я могу сказать что я сильный програмист, и если я говорю что 30 минут на такую задачу — это анриал — то это анриал. Поэтому, давай работать с твоими ожиданиями — задачка одна на выбор из тех что на кодилити или компания даст свою задачку ? точно ли дается всего пол часа на решение ?
дается 4 задачи, аналогичных тем, что в примерах на кодилити, но с другими условиями, возможно будут усложненные варианты. По времени на все задачи дается два часа.
Вот такие условия(
а что нада решить все 4 или бест эффорт ?
Надо все четыре. Там по каждой задаче дается определенное количество балов. Для успешного прохождения надо набрать не менее 80% по каждой.
А это начит, не только сделать правильный алгоритм, но учесть крайние варианты, сделать защиту от переполнения значений int и уложиться в требуемую сложность — чаще всего это O(n) по скорости.
Та задача что ты два часа рашал решается так — ты инициализируешь даные — грузиш операции в массив и нулевые счетчики в массив. Потом в цикле запускаешь процедуру в которую передаешь численное значение операции и ссылку на массив со счетчиками. Внутри процедуры проверяешь значение операции, и или увеличиваешь соответствующий счетчик или находишь макс и все счетчики приводишь к макс.После этого возвращаешься в мейн и считываешь следующую операцию из массива. После выхода из цикла у тебя есть массив со счетчиками. если никто на 1000 не подпишется — то напиши мне в личку, я тебе через скайп помогу.
Vasya Pupking
Поздравляю. Вы провалили решение этой задачи.
да шо вы говорите ))) или у вас есть конкретные комменты или вы просто тролите )))
А что там в условии сказано про сложность решения? Подскажу, O(N+M). А у вас какая сложность получилась?
я тему комплексити уже прослушал и мне кажется что у меня О(M).
Еще раз прослушайте :)
Проход по циклу операций — O(n)
находишь максх O(n)
и все счетчики приводишь к максx O(n)
итого О(n^3)
Даже если макс будем хранить отдельно, все равно n квадрат
по циклу операций это О(М), максимум можна передавать в процедуру и возвращать из процедуры если измененное значение вдруг стало больше максимума. перевод всех в макс будет выполняться не каждую итерацию, поэтому им можна принебречь.
Ок. O(MxN) если хранить максимальное значение. Квадратическая сложность как ни крути.
Нельзя пренебречь. Тем более на кодилити тестят и по крайним случаям. Так вот минимум один крайний случай будет 100% состоять из одних максов. Так что не спорте.
Вам показать решение за О(n) или все-же самому охота решить? :)
ну есть еще решение — это хранить текущий макс и абсолютную разницу элементов с макс в массиве счетчиков, при каждой новой найденной операции макс обновлять значение макса и занулять массив со счетчиками путем инициализации нового массива. если больше операции макс не нашлось то к массиву счетчиков поприбавлять макс. Итого О(М+Н). Но это мутный непрозрачный метод который будет тяжело поддерживать и его имеет смысл использовать только если вам нужны миллисекунды выиграша. раскажите метод на О(н)
Ну там есть требование по памяти тоже. Описание метода с O(n) подсказал ниже Коля же. Ну или вот, держите
public int[] solution(int N, int[] A) {
int[] counters = new int[N];
int max = 0;
int add = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] <= N) {
int p = A[i]-1;
if (counters[p] < add) counters[p] = add;
counters[p]++;
if (counters[p] > max) max = counters[p];
}
else {
add = max;
}
}
for (int i = 0; i < counters.length; i++) {
if (counters[i] < add)
counters[i] = add;
}
return counters;
}
метод классный, но сходу я такие алгоритмы не придумываю. только если где то раньше видел — тогда быстро можна набросать.
Пупкин, мое решение с переопределением массива где то на 10% быстрее. что бы ты не мучался, вот листинг
import java.util.*;
public class zadacha {
private static final int n_Actions = 15000000;
private static final int N_len = 20;
private static Random rand = new Random(N_len);
public static void main(String[] args) {
int [] actionsList = new int[n_Actions];
for (int i=0;i<n_Actions;i++){
actionsList[i] = rand.nextInt(N_len) + 1;
//System.out.println(actionsList[i]);
}
System.out.println("Action is ready");
long currentTime = System.currentTimeMillis();
int [] result = solutionPupkin(N_len,actionsList);
long elapsedTimeInMiils = System.currentTimeMillis() - currentTime;
System.out.println("Pupkin done in: " + elapsedTimeInMiils + "ms");
currentTime = System.currentTimeMillis();
int [] result1 = solutionMobile(N_len,actionsList);
elapsedTimeInMiils = System.currentTimeMillis() - currentTime;
System.out.println("Mobile done in: " + elapsedTimeInMiils + "ms");
for (int i=0;i<N_len;i++){ System.out.println(result[i]+" "+result1[i]); }
};
public static int[] solutionPupkin(int N, int[] A) {
int[] counters = new int[N];
int max = 0;
int add = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] <= N) {
int p = A[i]-1;
if (counters[p] < add) counters[p] = add;
counters[p]++;
if (counters[p] > max) max = counters[p];
}
else {
add = max;
}
}
for (int i = 0; i < counters.length; i++) {
if (counters[i] < add)
counters[i] = add;
}
return counters;
}
public static int[] solutionMobile(int N, int[] A) {
int[] counters = new int[N];
int local_max = 0;
int max = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] <= N) {
counters[A[i]-1]++;
if (counters[A[i]-1]> local_max) {local_max = counters[A[i]-1];};
}
else {
max=max+local_max;
local_max = 0;
counters = new int[N];
}
}
for (int i = 0; i < counters.length; i++) {
counters[i]=counters[i]+ max;
}
return counters;
}
}
чувак, а теперь возьми свое решение и загони в тестирование на кодилити. И посмотрим сколько баллов оно наберет. Ну чтоб ты не мучался, вот ответ
88 out of 100 points
extreme_large
all max_counter operations 12.640 s. TIMEOUT ERROR
running time: >12.64 sec., time limit: 5.84 sec.
а мое решение
так что про какие там 10% ты мне говоришь?
extreme_large
all max_counter operations 1.820 s. OK
пришлось сделать дополнительную проверку для супер максимумов. Теперь 100 процентов. Твое и Колино решение полюбому красивее, я с этим не спорю. Ты то согласился ему помочь за 100 баксов
if(local_max>0) {max=max+local_max;
local_max = 0;
counters = new int[N];}я, к сожалению, считаю, что не обладаю достаточным уровнем чтоб помогать в таких вопросах.
зря, ты тут один из крутых, я счас на кодилити челендж зарешаю
Я решил задачу вводом дополнительного «базового» значения, до которого повторным циклом довел значения счетчиков, оказавшиеся меньше его.
Вышло O(n), решение могу показать. Но все-же, повторюсь, пришлось потратить более получаса на это.
в тренингах на кодилити, насколько я помню, 3 разных уровня сложности задач. Какие уровни Вы ожидаете в реальном тесте?
Вот это не известно, но одна сложная точно будет.
кстати, может кого-то пнуть на топкодере?
п.с. что за компания хоть, секрет?
Самое интересное, что я сам не знаю, что за компания. Но судя по условиям, вполне так «компания мечты».
Помню когда-то решал эту задачку. Она далеко не самая сложная в тренингах.
Но, думаю, Вы зря так сильно беспокоитесь. Никто не даст 4 задачи высокого уровня сложности на 2 часа, тем более в случае автоматизатора. Да и чаще всего компании не ждут решения всех задач со 100% результатом.
я тоже пытаюсь автора успокоть, никто не может решать задачки такого типа за 30 минут. Вернее 30 минут — это минимум на кодинг.
не, ну MaxCounters за 30 мин решается вообще без проблем.
открыт секрет откуда у миллиона индусов тысячи сертификатов....
Про индусов это вы верно сказали. У них взаимоподдержка на очень высоком уровне. Один куда-то попадает, сразу всех своих близких пытается перетянуть. Протежируют друг-друга.
А наши же наоборот, кто-то добьется успеха и потом перестает общаться со старыми друзьями. Сплошь и рядом такое.
Pavel Lyubchenko
А наши же наоборот, кто-то добьется успеха и потом перестает общаться со старыми друзьями.Правильно делают, а то старые друзья так и норовят вытащить тебя из успеха и снова окунуть в гавно
А разве это не так? (если статистически прикинуть)
55 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів