Форум Всеукраїнської інтернет-олімпіади NetOI

Джулгаков Дмитрий · 2007-01-10 14:38:40

Уважаемое жюри!

Во-первых, хочу выразить благодарность за прием аппеляции по задаче Trees.

Ну а во-вторых, мне кажется (и не только мне - см. пост xXx в ветке про задачу Trees), что в этой задаче есть еще одна ошибка.

А именно входные тесты не соответствуют условию. Экспериментальным путем было установлено, что в тестах имеются деревья с ребрами, концы которых имеют номера больше чем P для этого дерева. Т.е. по сути ребра выходят в несуществующие вершины.

Как это проявляется. Я взял правильное решение Reiten-а с форума - в исходном виде оно набирает 60 баллов в онлайн проверке. В решение добавляется строка, которая вызывает деление на ноль при вершинах больше чем p. (См. строку с комментарием "Проблема").

Код:

#include <cstdio>

using namespace std;

const int maxN=20;
const int maxP=50;
const int maxV=maxN*maxP;

struct edge {
     int w;
     edge *next;
     edge(int W=0,edge *NXT=0):w(W),next(NXT) {}
};

edge *adj[maxV];
edge edgs[2*maxV];
int eCnt;
int sg[maxV];

inline void AddEdge(int a,int b) {
     edgs[eCnt]=edge(b,adj[a]);
     adj[a]=&edgs[eCnt++];
}
int CountSG(int v,int prv=-1) {
     bool reachable[maxP+2]={0};
     for(edge *e=adj[v];e;e=e->next)
      if(e->w!=prv) 
           reachable[CountSG(e->w,v)]=true;
     for(sg[v]=0;reachable[sg[v]];sg[v]++);
     return sg[v];
}
int main() {
     int firstv[maxN];
     int v,n,p,i,a,b,j,sumsg,cnt;
     edge *e;
//      freopen("trees.in","r",stdin);
     scanf("%d",&n);
     for(i=0,v=0;i<n;i++) {
      firstv[i]=v;
      scanf("%d",&p);
      for(j=0;j<p-1;j++) {
           scanf("%d%d",&a,&b);

            if ((a<1)||(a>p)||(b<1)||(b>p)) n /= 0;  ////////// ПРОБЛЕМА

           AddEdge(a-1+v,b-1+v);
           AddEdge(b-1+v,a-1+v);
      }
      v+=p;
     }
     for(i=0,sumsg=0;i<n;i++)
      sumsg^=CountSG(firstv[i]);
     if(sumsg) {
      for(i=0,cnt=0;i<n;i++)
           for(e=adj[firstv[i]];e;e=e->next)
            if((sumsg^sg[firstv[i]]^sg[e->w])==0)cnt++;
      printf("1 %d\n",cnt);           
     }
     else {
      for(i=0,cnt=0;i<n;i++)
           if(sumsg^sg[firstv[i]])cnt++;
      printf("2 %d\n",cnt);           
     }
     return 0;
}

Такое решение не проходит тесты 21..27. Т.е. делаем вывод, что эти тесты содержат ребра, выходящие за пределы дерева.

В подтверждение этого свидетельствует и то, что только Reiten набрал 60 баллов по этой задаче, но довольно многие набрали 53-54 балла.

Причина прохождения решения Reiten-а состоит в том, что он использует сквозные номера, а другие участники (например, я или xXx) использовали отдельные массивы для каждого дерева.

Поэтому вердикт такой: тесты 21..27 скорее всего некорректны, а решение жюри также использует сквозную нумерацию и потому работает.

Прошу рассмотреть данную аппеляцию и извинить меня, если она не обоснована.

С наступающим Старым новым годом!

xXx · 2007-01-10 21:33:16

в своем посте в ветке Trees я не совсем это имел ввиду... на мой взгляд тесты соответсвуют условию (тк в условии не оговорено, что вершины эт числа от 1 до P, сказано лишь про корень)...
я вижу проблему в том, что решение, которое плотно размещает деревья (напр через каждые Pi вершин), допускает коллизии(если номера вершин < 1 or > P)... те одни деревья могут нарушать структуру других деревьев(как это сделанно в решении reiten'a и мне кажется в авторском)....
а решение, которое размещает деревья с запасом(напр как сделал Джулгаков Дмитрий) получает wa...(чем больше запас, тем меньше балов )

Відредаговано xXx (2007-01-10 21:37:31)

reiten · 2007-01-11 09:13:43

xXx написав:
в своем посте в ветке Trees я не совсем это имел ввиду... на мой взгляд тесты соответсвуют условию (тк в условии не оговорено, что вершины эт числа от 1 до P, сказано лишь про корень)...
я вижу проблему в том, что решение, которое плотно размещает деревья (напр через каждые Pi вершин), допускает коллизии(если номера вершин < 1 or > P)... те одни деревья могут нарушать структуру других деревьев(как это сделанно в решении reiten'a и мне кажется в авторском)....
а решение, которое размещает деревья с запасом(напр как сделал Джулгаков Дмитрий) получает wa...(чем больше запас, тем меньше балов )

Такая точка зрения конечно возможна, но тогда все решения будут некорректными, так как я уверен, что ни одно решение не делает принудительной перенумерации вершин, а иначе, можно сделать тесты с вершинами и 1000000 и 1000000000 и т. д.

reiten · 2007-01-11 09:14:46

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

necro · 2007-01-11 14:15:52

А жюри на посты только смотрит

Журі NetOI-2006-Пасіхов · 2007-01-11 16:11:21

necro написав:
А жюри на посты только смотрит

Нет, не только смотрит, еще и проверило еще раз тесты. Все ваши рассуждения интересны, но тесты корректны. В любом случае удельный вес вопроса в общем результате/10 ничтожно мал, на состав участников 4 тура и на их баллы в 4-м туре не влияет НИКАК. Истина, она, конечно, дороже балла за тест, мы ее выясним, но попозже.

xXx · 2007-01-11 17:35:07

reiten написав:
...............
Такая точка зрения конечно возможна, но тогда все решения будут некорректными, так как я уверен, что ни одно решение не делает принудительной перенумерации вершин, а иначе, можно сделать тесты с вершинами и 1000000 и 1000000000 и т. д.

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

Відредаговано xXx (2007-01-11 17:35:50)

xXx · 2007-01-11 18:24:32

Передумал...

Номер

М.

1) Порядковое число предмета в ряду других однородных.

2) Что-л., обозначенное определенным числом по порядку.

3) ....
........

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

решение которое перенумеровует вершины получает wa23,24,25...которое максимально плотно размещает вершины деревьев - 60б...

надеюсь когда-нибудь услышать мнение жури по этому поводу....

Ivan · 2007-01-11 18:40:28

Можно вопрос? А этот словарь входит в число официальных документов олимпиады?

Джулгаков Дмитрий · 2007-01-11 18:49:47

Журі NetOI-2006-Пасіхов написав:
В любом случае удельный вес вопроса в общем результате/10 ничтожно мал, на состав участников 4 тура и на их баллы в 4-м туре не влияет НИКАК. Истина, она, конечно, дороже балла за тест, мы ее выясним, но попозже.

Честно говоря, я уже совсем запутался в причинах этого странного эффекта. Действительно вес вопроса всего 6 баллов - т.е. 0,6 балла на очном туре А что касается истины... подождем архива олимпиады и все прояснится.

necro · 2007-01-11 21:59:58

Скажи мужик если бы ты написал межнар был вторым абсолютом и отстал от первого на 1 бал, а после этого к тебе подходит первый абсолют и говорит мужик да ты круче

Відредаговано necro (2007-01-11 22:00:41)

xXx · 2007-01-12 21:19:07

Ivan написав:
Можно вопрос? А этот словарь входит в число официальных документов олимпиады?

имхо, умничать - это не лутший способ убить время....

Форум Всеукраїнської інтернет-олімпіади NetOI

#1 2007-01-10 14:38:40

Еще одна ошибка в задаче Trees

Код:

#2 2007-01-10 21:33:16

Re: Еще одна ошибка в задаче Trees

#3 2007-01-11 09:13:43

Re: Еще одна ошибка в задаче Trees

xXx написав:

#4 2007-01-11 09:14:46

Re: Еще одна ошибка в задаче Trees

#5 2007-01-11 14:15:52

Re: Еще одна ошибка в задаче Trees

#6 2007-01-11 16:11:21

Re: Еще одна ошибка в задаче Trees

necro написав:

#7 2007-01-11 17:35:07

Re: Еще одна ошибка в задаче Trees

reiten написав:

#8 2007-01-11 18:24:32

Re: Еще одна ошибка в задаче Trees

#9 2007-01-11 18:40:28

Re: Еще одна ошибка в задаче Trees

#10 2007-01-11 18:49:47

Re: Еще одна ошибка в задаче Trees

Журі NetOI-2006-Пасіхов написав:

#11 2007-01-11 21:59:58

Re: Еще одна ошибка в задаче Trees

#12 2007-01-12 21:19:07

Re: Еще одна ошибка в задаче Trees

Ivan написав:

Нижній колонтитул