Олимпиада "Московский учитель 2016"

[bormant]

размер используемой памяти (массивы D1 и D2) зависит от входных данных

Нет два раза.
1) Размеры D1 и D2 составляют 1000 элементов в каждом, в лучшем случае (N=1000) равно N, в остальных -- больше N.
2) Фактически используемые размеры ND1 и ND2 зависят не от N (как выше в примере "на 2"), а от количества подходящих треугольников (Abs(x)=Abs(y)), которое меньше или равно N.

[Дож]

Нет два раза.

Т.е. вы оспариваете утверждение «размер используемой памяти (массивы D1 и D2) зависит от входных данных», написанное организаторами в предлагаемом правильном ответе? :) Таким образом, вы тоже согласны, что организаторы ошиблись?

[tema]

bormant,

Тем не менее, если "array [1..1000] of Integer" является безусловным нарушением критерия "размер используемой памяти зависит от количества точек", то увы, только 2 балла.

А вы сами посмотрите что они пишут про то, как нужно оценивать задание (kreiterii.pdf):

Решение правильное, однако размер используемой памяти (массивы D1 и D2) зависит от входных данных. Согласно критериям, работа ученика должна быть оценена в ... балла.

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

Только хотел процитировать "правильный" ответ комиссии
Тут же всё написано их собственными руками:

Решение правильное, однако размер используемой памяти (массивы D1 и D2) зависит от входных данных.

И, если предположить, что это безусловный критерий на 3 балла, то надо ставить 4, т.к. размер используемой памяти от количества точек совершенно не зависит. И ни одного критерия на 2 балла не присутствует

Добавлено спустя 10 минут 5 секунд:

1) Размеры D1 и D2 составляют 1000 элементов в каждом, в лучшем случае (N=1000) равно N, в остальных -- больше N.

В смысле больше? Количество полезных элементов в двух массивах вместе вообще никак не может превышать N. Только так: ND1+ND2<=N

2) Фактически используемые размеры ND1 и ND2 зависят не от N (как выше в примере "на 2"), а от количества подходящих треугольников (Abs(x)=Abs(y)), которое меньше или равно N.

Как в этом сообщении вообще 2) вяжется с 1)?

[bormant]

Nmax=1000, но любое конкретное N меньше или равно Nmax.
То есть для N<Nmax расход памяти больше чем для N пар точек, то есть эффективность по памяти тем хуже, чем меньше N.
Так понятнее?

Dx -- это массивы, именно их элементы занимают память.
NDx -- это счетчики необходимой для хранения подходящих значений памяти.

Если б мы вспомнили про Turbo Pascal в DOS, то там программа вне зависимости от размера сегмента данных (количества и размера глобальных переменных) получала всю свободную память. Повлиять на это можно было директивой $M. Тут с натяжкой можно было бы говорить, что размер используемой реально памяти зависит от счетчиков.
Но с FPC картина другая. Вероятно, проверяющие считают, что аналогии с TP недопустимы.

[tema]

Понял Вашу мысль.
Вот вариант под 3 критерий. Причём, учитывая, что ученик может допустить 3 ошибки можно считать это его программой.

Код: Выделить всё

    var
    N, ND1, ND2: integer;
    D1, D2: array of integer; //Ошибка неверного описания переменной (сейчас исправлено)
    Max1, Max2: integer; S: integer;
    i, x, y: integer;
    begin
    readln(N);
SetLength(D1,N);
SetLength(D2,N);
    ND1:=0; ND2:=0;
    for i:=1 to N do begin
    readln(x,y);
    if (x=y) then begin
    ND1:=ND1+1;
    D1[ND1]:=abs(x);//Ошибка недопустимой операции
    end;
    if (x=-y) then begin
    ND2:=ND2+1;
    D2[ND2]:=abs(y);//Ошибка недопустимой операции (повтор)
    end;
    end;
    Max1:=0; Max2:=0;
    for i:=1 to ND1 do begin
    if (D1[i] > Max1) then Max1:= D1[i];//Ошибка недопустимой операции (повтор)
    end;
    for i:=1 to ND2 do begin
    if (D2[i] > Max2) then Max2:= D2[i];//Ошибка недопустимой операции (повтор)
    end;
    S:=Max1*Max2;
    if (S=0) then writeln('Треугольник не существует')
    else writeln(S)
    end.

Добавлено спустя 1 минуту 19 секунд:
Ошибки, который можно допустить (3 шт.):

....не описана или неверно описана переменная....
...применяется операция, недопустимая для соответвующего типа данных...
(если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку)

[tema]

Получил ответ от эксперта. Я в шоке. Цитирую как есть.

Комментарии эксперта:

В решенииэкзаменуемого допущена ошибка, размер используемой памяти для массивов D1 и D2 зависит от входных данных,

Во-первых, если размер массива гораздо больше, чем количество точек, то нельзя сказать «размер используемой памяти зависит от количества точек», соответственно критерий на 3 балла не выполняется

Во-вторых, нельзя сказать, что «время работы линейно зависит от N»

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

Добавлено спустя 1 минуту 49 секунд:

Во-вторых, нельзя сказать, что «время работы линейно зависит от N»

КАК????? ПОЧЕМУ???? Почему этого сказать нельзя? Время работы линейно зависит N. Именно так можно и нужно сказать. Нелинейная зависимость - это вложенные циклы, которых в программе нет. Время работы зависит от N так:
t=kt*N+kt*(N-M)=2*kt*N-kt*M где kt - коэффициент перевода в величину времени, а М - количество точек не удовлетворяющих условию x=y или x=-y.
t=2*kt*N-kt*M это классическое линейное уравнение

Добавлено спустя 2 минуты 8 секунд:

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

ДА БЛИН!!!! КАК???????
В массив сохраняются не все исходные данные! В массив сохраняются только те исходные данные, которые соответствуют условию x=y или x=-y, а это, в общем случае, далеко не все исходные данные!
Треугольники все возможные у ученика так же не рассматриваются. Он, полностью соответствуя своему описанию алгоритма, а так же совпадая с правильным ответом из самого задания ищет два максимальных значения катетов. Он не рассматривает треугольники вообще. Рассмотрение всех возможных треугольников - это либо поиск нужного треугольника по площади либо перебор для каждого катета с одной стороны всех катетов с другой. Что никак не сделать с линейной зависимостью от N, а у него зависимость именно линейная.

Добавлено спустя 1 час 59 минут 36 секунд:

2) Фактически используемые размеры ND1 и ND2 зависят не от N (как выше в примере "на 2"), а от количества подходящих треугольников (Abs(x)=Abs(y)), которое меньше или равно N.

Пришло в воспалённую голову.
Чтобы зависело от N, по Вашему, нужно, чтобы все точки были записаны в массив? Тогда ведь будет не меньше или равно, а чётко равно. Т.е., как, собственно, Вы и писали:

Код: Выделить всё

    var
      N: integer;
      D1, D2: array [1..1000] of integer;
      Max1, Max2: integer; S: integer; i, x, y: integer;
    begin
      readln(N);
      for i:=1 to N do readln(D1[i],D2[i]);
      Max1:=0; Max2:=0;
      for i:=1 to N do if (D1[i]=D2[i])  and (Abs(D1[i]) > Max1) then Max1:= Abs(D1[i]);
      for i:=1 to N do if (D1[i]=-D2[i]) and (Abs(D2[i]) > Max2) then Max2:= Abs(D2[i]);
      S:=Max1*Max2;
      if (S=0) then writeln'Треугольник не существует')
      else writeln(S)
    end.


Но "сохранение всех исходных данных в массив" это дословно критерий на 2 балла. Получается, чтобы выполнить критерий на 3 балла нужно, чтобы он был на 2 балла?

Добавлено спустя 1 час 2 минуты 8 секунд:
Последний гвоздь в крышку:

Код: Выделить всё

program project1;
var
  a: array[1..$fffffff] of longint;
  x, i: integer;
begin
  readln(x);
  for i := 1 to x do
    a[i] := i;
  writeln(a[x div 2]);
  readln;
end.

Скриншот "снимок16" - занимаемая память при запуске приложения.
Таки зависит и плевать на объявление статического массива.

[Дож]

Получил ответ от эксперта. Я в шоке. Цитирую как есть.

Комментарии эксперта:

В решенииэкзаменуемого допущена ошибка, размер используемой памяти для массивов D1 и D2 зависит от входных данных,

Во-первых, если размер массива гораздо больше, чем количество точек, то нельзя сказать «размер используемой памяти зависит от количества точек», соответственно критерий на 3 балла не выполняется

Во-вторых, нельзя сказать, что «время работы линейно зависит от N»

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

И эти «эксперты» учат других не ковыряться в носу.

[bormant]

Про нелинейную зависимость, естественно, бред.
Да, оценка по времени хуже, чем у однопроходного решения, но по-прежнему линейна по N. Она останется линейной даже при сохранении всех точек в массив, поскольку 3N это не N^2.

К сожалению, один только "массив с запасом" при строгом подходе к эффективности по памяти способен отбросить на "2 балла", потому как "зависит от Nmax" хуже, чем "зависит от N".

[tema]

К сожалению, один только "массив с запасом" при строгом подходе к эффективности по памяти способен отбросить на "2 балла", потому как "зависит от Nmax" хуже, чем "зависит от N".

обратите внимание на скриншоты. Там убедительно доказано, что используемая память зависит от N. Мой ответ полностью верный.

[Лекс Айрин]

tema, это лишь особенность реализации текущего компилятора, не более.

[Дож]

обратите внимание на скриншоты. Там убедительно доказано, что используемая память зависит от N. Мой ответ полностью верный.

Ничего убедительно не доказано. У меня есть подозрение, что на скриншотах мы наблюдаем размер резидентной памяти. Там всё довольно сложно и запутанно, если вкратце, то память выделяется процессам постранично по мере использования, и вот этот вот статический массив языка паскаль чисто гипотетически может вообще не быть представлен в ОЗУ, если не был использован, может оказаться расчленён на куски и размазан по всей физической ОЗУ, но при этом изнутри процесса всегда существует и будет казаться непрерывно адресуемым, потому что процессор использует таблицы для отображения адреса процесса в физические адреса. Эти страницы могут перемещаться в памяти, отгружаться в своп-файл, вообще это действительно довольно запутанная вещь на стыке аппаратных возможностей и недр операционных систем, и я об этом практически ничего не знаю.

Разумеется, всё это не может являться аргументом при обсуждении сложности программы. Считать ли в паскале статический массив на 1000 элементов, в котором алгоритм использует только первые N элементов, как O(N) памяти или как бесконечное количество памяти — вопрос договорённости по большому счёту. Организаторы олимпиады не могут об этом договориться сами с собой.

[tema]

tema, это лишь особенность реализации текущего компилятора, не более.

Как это отменяет факт зависимости используемой памяти от N?
Вот на скриншоте та же программа в windows 10 и в другой версии лазаруса

Добавлено спустя 3 минуты 1 секунду:

обратите внимание на скриншоты. Там убедительно доказано, что используемая память зависит от N. Мой ответ полностью верный.

Ничего убедительно не доказано. У меня есть подозрение, что на скриншотах мы наблюдаем размер резидентной памяти. Там всё довольно сложно и запутанно, если вкратце, то память выделяется процессам постранично по мере использования, и вот этот вот статический массив языка паскаль чисто гипотетически может вообще не быть представлен в ОЗУ, если не был использован, может оказаться расчленён на куски и размазан по всей физической ОЗУ, но при этом изнутри процесса всегда существует и будет казаться непрерывно адресуемым, потому что процессор использует таблицы для отображения адреса процесса в физические адреса. Эти страницы могут перемещаться в памяти, отгружаться в своп-файл, вообще это действительно довольно запутанная вещь на стыке аппаратных возможностей и недр операционных систем, и я об этом практически ничего не знаю.

Очень много слов, но суть вся на скриншотах. Используемая память зависит от используемых элементов массива и это факт. Аргумент неопровержимый. Есть скриншоты и из винды и из линукса и с разными версиями лазаруса. Можете так же проверить самостоятельно на своём компьютере.

[Дож]

Используемая память зависит от используемых элементов массива и это факт.

Этот факт самоочевиден и не требует никаких подтверждающих измерений :) Да, используемая память зависит от использования памяти.

Можете так же проверить самостоятельно на своём компьютере.

Никто и не подвергает сомнению достоверность скриншотов и воспроизводимость эксперимента.

[Лекс Айрин]

Как это отменяет факт зависимости используемой памяти от N?

Вообще-то в правильной (близкой к канону) реализации место под массив выделяется сразу. Если речь не идет об открытых массивах.

[tema]

Как это отменяет факт зависимости используемой памяти от N?

Вообще-то в правильной (близкой к канону) реализации место под массив выделяется сразу. Если речь не идет об открытых массивах.

Это просто рассуждение.
Вопрос остаётся в силе. Как это отменяет продемонстрированный факт зависимости выделяемой памяти от N?