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

23:59 ???? за минуту до окончания тура???

Відредаговано xXx (2007-01-04 20:41:36)

Ідея рішення базується на функції Гранді.

ось похожа задача http://www.ttb.by/trainingzone/tasks/Fr … ement.htm, а ось її рішення (там написано про функцію Гранді ) http://www.ttb.by/trainingzone/tasks/Fr … lution.htm

Уважаемое Жури! Я обнаружил странную ситуацию. По условию задачи:

условие написав:

а потім  N  послідовностей, кожна з яких - кількість вершин  P (1<=P<=50)  чергового "дерева" і  P-1  пар цілих чисел – номери вершин, що з’єднані відповідним ребром ( "коренева" вершина, з якої починається гра, завжди має номер 1).

Отсюда НЕ СЛЕДУЕТ, что пара направленная. Поэтому мое решение считало пару ненаправленной и учитывало ненаправленность.

#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);
           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;
}

Решение получило 36 балов. Остальное - ВА. Но если закомментировать строку помеченную комментарием "проблема", то решение перестает учитывать ненаправленность пары и получает 60. Проблема в том, что если все деревья действительно являются деревьями, то решение не должно зависеть от направленности пары. Просьба проверить тесты на возможную ошибку.

Да в мене та сама проблема. Тести потрібно виправити.

partisan написав:

reiten написав:

......Решение получило 36 балов. Остальное - ВА. Но если закомментировать строку помеченную комментарием "проблема", то решение перестает учитывать ненаправленность пары и получает 60. Проблема в том, что если все деревья действительно являются деревьями, то решение не должно зависеть от направленности пары. Просьба проверить тесты на возможную ошибку.

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

В умові сказано:"P-1  пар цілих чисел – номери вершин, що з’єднані відповідним ребром", звідки слідує, що в твому прикладі з 1 досягається вершина 3. В умові не сказано що в парі цілих чесил (а,b) з (а) можна потрапити в (b), а з (b) в а цього зробити не можна.

Відредаговано Yevgeniy (2007-01-07 12:25:56)

partisan написав:

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

Наличие вершин, не достижимых из корня, противоречит самому определению дерева.

RuslanSM написав:

partisan написав:

reiten написав:

......Решение получило 36 балов. Остальное - ВА. Но если закомментировать строку помеченную комментарием "проблема", то решение перестает учитывать ненаправленность пары и получает 60. Проблема в том, что если все деревья действительно являются деревьями, то решение не должно зависеть от направленности пары. Просьба проверить тесты на возможную ошибку.

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

Шановний partisan наскільки я пам'ятаю, то дерево - це звязний граф без циклів. Зверніть увагу на слово зв'язний. У іншому випадку цей граф називають лісом, але в умові чітко сказано слово "дерево". Тому ваше зауваження мені здається невірним... У мене та сама проблема, що і у інших і я теж прошу жюрі переглянути умову і тести...

Понятие "дерево"(тем более как связний граф без циклов) определено только для неориентированых графов. Я из "дерева" и "движения вверх" понял неориентированность ребер (просто представилась полная картина задачи - вся суть, и никаких противоречий). В условии действительно движение строго не описано (а имелось ввиду, что если граф дезориентировать, то получится дерево (в классическом понимании этого понятия для неориентированного графа)). Однако этот вопрос можно было поднять на форуме, чего, как я вижу не сделали. И такая, наверняка, будет позиция жюри. Хотя действительно он мог не встать. Надо было уточнить понятие "движения вверх".

Відредаговано partisan (2007-01-07 13:10:01)

partisan написав:

RuslanSM написав:

partisan написав:

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

Шановний partisan наскільки я пам'ятаю, то дерево - це звязний граф без циклів. Зверніть увагу на слово зв'язний. У іншому випадку цей граф називають лісом, але в умові чітко сказано слово "дерево". Тому ваше зауваження мені здається невірним... У мене та сама проблема, що і у інших і я теж прошу жюрі переглянути умову і тести...

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

Цікаво як ти догадався, виходячи з умови, що дерево направлене? І якщо зчитуємо пару чисел (А,С), то орієнтація з А в С, а не з С в А?

Yevgeniy написав:

partisan написав:

RuslanSM написав:

Шановний partisan наскільки я пам'ятаю, то дерево - це звязний граф без циклів. Зверніть увагу на слово зв'язний. У іншому випадку цей граф називають лісом, але в умові чітко сказано слово "дерево". Тому ваше зауваження мені здається невірним... У мене та сама проблема, що і у інших і я теж прошу жюрі переглянути умову і тести...

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

Цікаво як ти догадався, виходячи з умови, що дерево направлене? І якщо зчитуємо пару чисел (А,С), то орієнтація з А в С, а не з С в А?

Напевно деревом для орієнтованого графа вважав граф, при дезорієнтації ребер воно стає неорієнтованим деревом в класичному розумінні цього поняття. Рух вверх посприяв асоціації, що рух в одну сторону. Задача видалася абсолютно зрозумілою і природньою. Хоча не виключено, що схожим інтуїтивним шляхом інші люди можуть прийти до інших, абсолютно природних, сприйняттів. У випадках неточних визначень єдиний шлях вирішення проблеми - попросити дати більш чіткі і формальні означення, можливо навіть перевіряти всі ті місця (як "рух вверх"), що здаються природніми, але не зовсім чітко визначені.

Відредаговано partisan (2007-01-07 13:29:04)

Yevgeniy написав:

Рух фішки по дереву орієнтований, а не саме дерево. А це зовсім різні речі.

+100
Чтобы исключить кривотолки, поднимем более старые сообщения форума. Ветка: задача "Trees"

AlexeyS написав:

В условии написано:

"...P-1 пар целых чисел - номера вершин, соединенных соответствующим ребром..."

Вопрос: номера вершин в паре указываются в правильном порядке, т. е. снечала нижняя потом верхняя, или нет?

Как видим, вопрос был задан. Как видно из цепочки сообщений, ответа Жури не последовало.

reiten написав:

Yevgeniy написав:

Рух фішки по дереву орієнтований, а не саме дерево. А це зовсім різні речі.

+100
Чтобы исключить кривотолки, поднимем более старые сообщения форума. Ветка: задача "Trees"

AlexeyS написав:

В условии написано:

"...P-1 пар целых чисел - номера вершин, соединенных соответствующим ребром..."

Вопрос: номера вершин в паре указываются в правильном порядке, т. е. снечала нижняя потом верхняя, или нет?

Как видим, вопрос был задан. Как видно из цепочки сообщений, ответа Жури не последовало.

По-видимому, был задан не так. Единственный способ точно узнать, почему вопрос остался без ответа, - спросить у жюри. У меня предположение: при условии направленности тот вопрос не имеет смысла - тавтология условия, и жюри могло так к этому отнестись. Я согласен, что условие было дано нечетко, допускало не одно понимание. При чем и то, и другое, имели смысл, поэтому вопросы по поводу неточностей могли не возникать, да и жюри могло не подозревать о двузначности. Можно задавать так: "условие допускает двузначное понимание. Непонятно, что значит то-то. Объясните, пожалуйста". Думаю, жюри обратит на такое внимание и перепроверит, действительно ли есть двузначность, и исправит. Или просто выложить свое понимание вещи и спросить, верно ли оно. Но все равно - один понял по-одному, другой по-другому. У каждого получилась вполне осмысленная картина, и не возникает вопросов.

По  формальным критериям виновато жюри, которое не дало четкого условия. Однако тут наверно уже ничего не поделаешь - нету четкого основания, от которого отталкиваться.