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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

Сторінок: 1 2

 

#26 2007-01-07 22:02:34

reiten
журі
Звідки: Киев
Зареєстрований: 2005-10-16
Повідомлень: 196

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Андрей!
Давай не будем ставить все с ног на голову. Был задан четкий формальный вопрос строго по сути проблемы. Ответа на него не поступило. Как Жури могло не подозревать о двузначности, если был задан четкий вопрос? Но ситуация еще лучше. Если даже допустить, что ребра были ориентированные, то выходит, что тесты некорректны, т. к. имеются вершины не достижимые из корня. Позволю себе привести англоязычное определение дерева с корнем из википедии:

wikipedia.org написав:

A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root.

Про существование же в дереве корня в условии было четко сказано. Так что так понимает не только большинство участников, но и математики. Посему не зависимо, ориентированно дерево, или нет, все его вершины должны быть достижимы из корня. Давай не будем строить аргументов вида "я интуитивно понял". Все формулировки говорят об обратном.

"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар

Поза форумом

 

#27 2007-01-07 22:05:03

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

partisan написав:

...По-видимому, был задан не так. Единственный способ точно узнать, почему вопрос остался без ответа, - спросить у жюри. ......

Единственное к чему можно придраться, так это к слову "снечала"... smile
"сначала нижняя потом верхняя"? - именно этот вопрос и интересует нас сейчас => вопрос задан абсолютно верно... исходя из решений набирающих полный бал можно уверенно сказать, что ответ на этот вопрос должен быть положительный, чего не было ни со стороны жури, ни со стороны учасников(учасники не виноваты, учасники могут знать только то, что написанно в условии(а ещё то что говорит жури))
+ нечеткость условия это следствие вины автора задачи, а не жури (если автор != жури smile )

Відредаговано xXx (2007-01-07 22:08:06)

icq - 402174

Поза форумом

 

#28 2007-01-07 22:29:53

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

reiten написав:

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

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

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

Відредаговано xXx (2007-01-07 22:31:39)

icq - 402174

Поза форумом

 

#29 2007-01-08 12:05:45

Журі NetOI-2006-Пасіхов
Адміністратор
Зареєстрований: 2006-09-09
Повідомлень: 126

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

reiten написав:

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

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

а потім  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. Проблема в том, что если все деревья действительно являются деревьями, то решение не должно зависеть от направленности пары. Просьба проверить тесты на возможную ошибку.

К сожалению (для нас, конечно :-( ), ваша аппеляция обоснована.

1. Тесты корректны.

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

3. Исправлено. Перепроверено. Глобалных изменений не произошло, но истина восторжествовала.

ПРИНОСИМ СВОИ ИЗВИНЕНИЯ.
Отделное спасибо тем, кто указал на ошибку и участвовал в дискусси. Особо отмечаю то, что сделано это было очень КОРРЕКТНО.
( retien, xXx, partisan - особо)

Поза форумом

 

#30 2007-01-08 12:18:36

Женя
Новий користувач
Зареєстрований: 2006-08-23
Повідомлень: 41
Вебсайт

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

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

К сожалению (для нас, конечно :-( ), ваша аппеляция обоснована.

1. Тесты корректны.

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

3. Исправлено. Перепроверено. Глобалных изменений не произошло, но истина восторжествовала.

ПРИНОСИМ СВОИ ИЗВИНЕНИЯ.
Отделное спасибо тем, кто указал на ошибку и участвовал в дискусси. Особо отмечаю то, что сделано это было очень КОРРЕКТНО.
( retien, xXx, partisan - особо)

Ну так нечесно теперь у меня на 8 баллов меньше, чем было :-(((

Поза форумом

 

#31 2007-01-08 13:40:47

Yevgeniy
Новий користувач
Зареєстрований: 2006-10-14
Повідомлень: 67

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Шановні журі можна опублікувати тести 23,24,25. Моя програма проходить всі тести, крім цих, тому мені дуже цікаво дізнатися де я помилився.

"Математика -- цариця наук, арифметика -- цариця математики."
      Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.

Поза форумом

 

#32 2007-01-08 15:39:47

AlexeyS
Новий користувач
Зареєстрований: 2006-11-30
Повідомлень: 18

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

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

3. Исправлено. Перепроверено.

Спасибо за коррекность и справедливость.

Поза форумом

 

#33 2007-01-08 18:37:55

reiten
журі
Звідки: Киев
Зареєстрований: 2005-10-16
Повідомлень: 196

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

AlexeyS написав:

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

3. Исправлено. Перепроверено.

Спасибо за коррекность и справедливость.

+1
Присоединяюсь к благодарности.

"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар

Поза форумом

 

#34 2007-01-09 07:36:27

JurasSic
Новий користувач
Зареєстрований: 2006-10-25
Повідомлень: 21

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Аналогично. С 38 б. за Триз  54б.

Поза форумом

 

#35 2007-01-09 20:27:48

Yevgeniy
Новий користувач
Зареєстрований: 2006-10-14
Повідомлень: 67

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Шановні Журі прошу переглянути коректність тестів 23, 24, 25, оскільки я написав генератор випадкових тестів     і було проведено порівняння результатів програми reiten'а(60 балів) і моєї (54 балів). Зі всіх 116000 випадкових тестів не було знайдено ні одного теста, на якому б відповіді рішень не співпадали. Ось текст програми:

 

Код:

#define MY_DEBUG 10
//-------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>

#ifdef MY_DEBUG
  #include <conio>
  #include <fstream>
  #pragma hdrstop
  #include <system.hpp>
  #pragma argsused
#endif
using namespace std;
#pragma comment(linker, "/STACK:33554432")

//global variable;
#define PI 3.1415926535897932384626433832795
#ifdef MY_DEBUG
  ifstream in("1.txt",ios::in | ios::binary);
  ofstream out("out.txt",ios::out | ios::binary);
#endif

//class
class Task
{
  //global variable
  int N;
  int res;
  int s;
  int lis[32][64][64];
  int nlis[32][64];
  int Grandi[32][64];
  int d[64];
 public:
  Task(){}
  ~Task(){}
  void ReadData();
  void OutData();
  void Solve();
  int mex(int *p,int n)
  {
    bool m[64];
    memset(m,0,sizeof(bool)*64);
    for(int i = 0;i < n;++i)
      m[p[i]] = 1;
    for(int i = 0;i < 64;++i)
      if(!m[i])
        return i;
    return 0;
  }
  int Recurs(int i,int v,int prev)
  {
    int end = nlis[i][v];
    int f[64];
    int nf = 0;
    for(int j = 0;j < end;++j)
    {
      if(lis[i][v][j] != prev)
        f[nf++] = Recurs(i,lis[i][v][j],v);
    }
    Grandi[i][v] = mex(f,nf);
    return Grandi[i][v];
  }

  void Checker(int an1,int an2)
  {
  #ifdef MY_DEBUG
  //here check my solution
 // int an1,an2;
 // in >> an1 >> an2;
  if(an1 != s || an2 != res)
  {
    cout << "\nWrongAnswer: answer1: " << an1 <<" got "<<s << " answer2: "<<an2<<" got "<<res;
  }
  else
    cout << "\nCorrentAnswer";
  #endif
  }
};
//this is realization
void Task::ReadData()
{
  #ifdef MY_DEBUG
    //here reading in file
    in >> N;
    memset(nlis,0,sizeof(int)*32*64);
    int p;
    int a,b;
    int *p1,*p2;
    for(int i = 1;i <= N;++i)
    {
      in >> p;
      for(int j = 1;j < p;++j)
      {
        in >> a >> b;
        lis[i][a][nlis[i][a]++] = b;
        lis[i][b][nlis[i][b]++] = a;
      }
    }
  #endif
  #ifndef MY_DEBUG
    //here standart reading
    cin >> N;
    memset(nlis,0,sizeof(int)*32*64);
    int p;
    int a,b;
    int *p1,*p2;
    for(int i = 1;i <= N;++i)
    {
      cin >> p;
      for(int j = 1;j < p;++j)
      {
        cin >> a >> b;
        if(a > 50 || b > 50)
          continue;
        else
        {
          lis[i][a][nlis[i][a]++] = b;
          lis[i][b][nlis[i][b]++] = a;
        }
      }
    }
  #endif
}
void Task::OutData()
{
  #ifdef MY_DEBUG
    //here writing in file
    //out << s <<" " <<  res;
  #endif
  #ifndef MY_DEBUG
    //here writing in consol
    cout << s << " " << res;
  #endif
}
void Task::Solve()
{
  //here solving problem
  res = 0;
  for(int i = 1;i <= N;++i)
  {
    Recurs(i,1,1);
    res ^= Grandi[i][1];
  }
  if(res != 0)
  {
    res = 0;
    int b;
    for(int i = 1;i <= N;++i)
    {
      int end = nlis[i][1];
      b = 0;
      for(int l = 1;l <= N;++l)
        if(l != i)
          b ^= Grandi[l][1];
      for(int j = 0;j < end;++j)
      {
        if((b ^ Grandi[i][lis[i][1][j]]) == 0)
        {
          ++res;
        }
      }
    }
    s = 1;
  }
  else
  {
    res = 0;
    int b = 0;
    for(int i = 1;i <= N;++i)
    {
      b = 0;
      for(int l = 1;l <= N;++l)
      {
        if(l != i)
          b ^= Grandi[l][1];
      }
      if(b != 0)
        ++res;
    }
    s = 2;
  }
}
#ifdef MY_DEBUG
class GenerateTree
{
  int tree[64][64];
  int ntree[64];
  int N;
  int M;
  public:
  void RecGen(int *v,int n,int &p,int &N)
  {
   start:
    int v1[64],nv = 0;
    for(int i = 0;i < n;++i)
    {
      int l = random(N + 1);
      for(int j = 0;j < l;++j)
      {
        ++p;
        tree[v[i]][ntree[v[i]]++] = p;
        v1[nv++] = p;
        --N;
      }
    }
    if(N != 0 && nv == 0)
      goto start;
    if(nv != 0)
      RecGen(v1,nv,p,N);
  }
  void OutFile(int v)
  {
    int end = ntree[v];
    bool s;
    for(int i = 0;i < end;++i)
    {
      OutFile(tree[v][i]);
      s = random(2);
      if(s)
        out << v << " " << tree[v][i] << endl;
      else
        out << tree[v][i] <<" "<< v << endl;
    }
  }
  void Solve()
  {
    M = random(20) + 1;
    //M = 2;
    out << M << endl;
    for(int i = 0;i < M;++i)
    {
      memset(ntree,0,sizeof(int)*64);
      N = random(50) + 1;
     // N = 50;
      out << N << endl;
      --N;
      int v[12];
      v[0] = 1;
      RecGen(v,1,1,N);
      OutFile(1);
    }
  }
};

const int maxN=20;
const int maxP=50;
const int maxV=maxN*maxP;
class reiten
{
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];
public:
int r1,r2;
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 Solve() {
     for(int i = 0;i < 2*maxV;++i)
     {
       edgs[i].w = 0;
       edgs[i].next = NULL;
     }
     for(int i = 0;i < maxV;++i)
       adj[i] = NULL;
     int firstv[maxN];
     int v,n,p,i,a,b,j,sumsg,cnt;
     edge *e;
//      freopen("trees.in","r",stdin);
     in >> n;
     eCnt = 0;
     for(i=0,v=0;i<n;i++) {
      firstv[i]=v;
      in >> p;
      for(j=0;j<p-1;j++) {
           in >> 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);
      r1 = 1;
      r2 = cnt;
     }
     else {
      for(i=0,cnt=0;i<n;i++)
           if(sumsg^sg[firstv[i]])cnt++;
      //printf("2 %d\n",cnt);
      r1 = 2;
      r2 = cnt;
     }
     return 0;
}
};
#endif
//testing code
int main(int argc, char* argv[])
{
  Task a;
  #ifndef MY_DEBUG
    a.ReadData();
    a.Solve();
    a.OutData();
  #endif
  #ifdef MY_DEBUG
    in.close();
    randomize();
    char filename[64] = "in.txt";
    TDateTime time,time2;
    GenerateTree gen;
    reiten r;
    out.close();
    for(int i = 1;i <= 100000;++i)
    {
   //   time = time.CurrentDateTime();
      out.clear();
      out.open(filename,ios::out | ios::binary);
      gen.Solve();
      out.close();
      in.clear();
      in.open(filename,ios::in | ios::binary);

    //  cout << "TEST " << i << endl;
      a.ReadData();
      a.Solve();
      a.OutData();
      in.close();
      in.clear();
      in.open(filename,ios::in | ios::binary);
      r.Solve();
      //here read corrent answer

      a.Checker(r.r1,r.r2);

      /*  time2 = time2.CurrentDateTime() - time;
        unsigned  short msec,sec,h,m;
        time2.DecodeTime(&h,&m,&sec,&msec);
        cout<<endl<<"Solve Time: "<< m <<":"<<sec<<":"<<msec<<endl;
      */in.close();
    }
    getch();
  #endif
  return 0;
}
//---------------------------------------------------------------------------

Відредаговано Yevgeniy (2007-01-10 10:45:12)

"Математика -- цариця наук, арифметика -- цариця математики."
      Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.

Поза форумом

 

#36 2007-01-09 21:05:48

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Компилятор вернул сообщение об ошибке:
task.cc:10:19: conio: No such file or directory
task.cc:13:24: system.hpp: No such file or directory
/usr/include/stdlib.h: In member function `void GenerateTree::RecGen(int*, int,
   int&, int&)':
/usr/include/stdlib.h:423: error: too many arguments to function `long int
   random()'
task.cc:195: error: at this point in file
/usr/include/stdlib.h: In member function `void GenerateTree::OutFile(int)':
/usr/include/stdlib.h:423: error: too many arguments to function `long int
   random()'
task.cc:216: error: at this point in file
/usr/include/stdlib.h: In member function `void GenerateTree::Solve()':
/usr/include/stdlib.h:423: error: too many arguments to function `long int
   random()'
task.cc:225: error: at this point in file
/usr/include/stdlib.h:423: error: too many arguments to function `long int
   random()'
task.cc:231: error: at this point in file
task.cc:237: error: no matching function for call to `GenerateTree::RecGen(
   int[12], int, int, int&)'
task.cc:190: error: candidates are: void GenerateTree::RecGen(int*, int, int&,
   int&)
task.cc: In function `int main(int, char**)':
task.cc:327: error: `randomize' undeclared (first use this function)
task.cc:327: error: (Each undeclared identifier is reported only once for each
   function it appears in.)
task.cc:329: error: syntax error before `,' token
task.cc:361: error: `getch' undeclared (first use this function)
task.cc:364:2: warning: no newline at end of file

Исправьте ошибку и попробуйте еще раз.

icq - 402174

Поза форумом

 

#37 2007-01-09 22:28:53

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Yevgeniy написав:

Шановні журі можна опублікувати тести 23,24,25. Моя програма проходить всі тести, крім цих, тому мені дуже цікаво дізнатися де я помилився.

Мужик ты еще не разобрался в чем лаги? У меня ровно тоже самое sad Хотя мне эти 4 балла хоть в ... всунь, пофиг на 4 тур попадаю.

Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#38 2007-01-09 22:36:41

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Просьба не воспринимать мой предыдуший пост как апеляцию. Я ненавижу апелянтов которых на этом форуме итак навалом. Мне балы выпрошеные таким путем ненужны. Респект 2 partisan который на этом потерял баллы. Правда не понятно чего он хотел если сначала имел 60 баллов, а так потерял второй абс.

Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#39 2007-01-09 22:48:48

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Уважаемое жури! Похоже это становиться правилом(к сожалению для вас и для нас) но авторское решение снова неверно! sad... (очень огромное СОРРИ если я не прав... smile )
Сначала я думал что решение Yevgeniy'a не верно(слишком громоздкое на первый взгляд), но после я убедился в его правильности(при максимальном номере вершины во входных данных - 63 smile ), и не правильности решений набирающих 60 баллов а также авторского решения....  В условии не сказанно что номера вершин это числа от 1 до P, так и есть... тесты от 21 до 27ого содержат номера вершин превышающие P... так вот... решение которое это учитывает не проходит тесты 23,24,25.... а решение которое это не учитывает - проходит. Чтоб в этом убедиться можно взять решение товарища reiten'a, увеличить размеры массивов в 10раз (на всякий случай) и изменить строку

Код:

v+=p;

на

Код:

v+=2*p;

такая модификация должна давать не менее правильный ответ (просто такая модификация должна принимать вершины от 1 до 2*P), но! такое решений не проходит тесты 23,24,25! Скорее всего это означает, что авторское решение не верно...(так как оно думает, что номера вершин от 1 до P) smile

Відредаговано xXx (2007-01-09 23:23:03)

icq - 402174

Поза форумом

 

#40 2007-01-09 23:20:24

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

necro написав:

...... Респект 2 partisan который на этом потерял баллы. Правда не понятно чего он хотел если сначала имел 60 баллов, а так потерял второй абс.

Если более внимательно читать посты partisan'a, то можно заметить, что он не аппелировал, а наоборот пытался защитить условие или авторское решение(или что-то ещё smile )...

Відредаговано xXx (2007-01-09 23:21:50)

icq - 402174

Поза форумом

 

#41 2007-01-10 09:05:52

Yevgeniy
Новий користувач
Зареєстрований: 2006-10-14
Повідомлень: 67

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Рішення писалось на С++ Builder 6.0. Якщо у вас не компілиться, то закоментуйте  строки   
#pragma hdrstop
  #include <system.hpp>
#pragma argsused
Коду дуже багато, оскільки там моє рішення (клас Task), генератор тестів (клас GenerateTree) і рішення reiten'a (клас reiten) і ще провіряющий код.

"Математика -- цариця наук, арифметика -- цариця математики."
      Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.

Поза форумом

 

#42 2007-01-10 10:34:29

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

Yevgeniy написав:

Рішення писалось на С++ Builder 6.0. Якщо у вас не компілиться, то закоментуйте  строки   
#pragma hdrstop
  #include <system.hpp>
#pragma argsused
Коду дуже багато, оскільки там моє рішення (клас Task), генератор тестів (клас GenerateTree) і рішення reiten'a (клас reiten) і ще провіряющий код.

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

icq - 402174

Поза форумом

 

#43 2007-01-10 10:49:46

Yevgeniy
Новий користувач
Зареєстрований: 2006-10-14
Повідомлень: 67

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

xXx написав:

Yevgeniy написав:

Рішення писалось на С++ Builder 6.0. Якщо у вас не компілиться, то закоментуйте  строки   
#pragma hdrstop
  #include <system.hpp>
#pragma argsused
Коду дуже багато, оскільки там моє рішення (клас Task), генератор тестів (клас GenerateTree) і рішення reiten'a (клас reiten) і ще провіряющий код.

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

Тепер має компілитися. Текст програми відредаговано так, що закометувавши першу стрічку (#define MY_DEBUG) вона буде компілитися на gcc.

"Математика -- цариця наук, арифметика -- цариця математики."
      Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.

Поза форумом

 

#44 2007-01-15 18:52:21

partisan
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-04
Повідомлень: 180

Re: Обсуждение решения задачи Trees (только после 23:59 04.01.07)

reiten написав:

Андрей!
Давай не будем ставить все с ног на голову. Был задан четкий формальный вопрос строго по сути проблемы. Ответа на него не поступило. Как Жури могло не подозревать о двузначности, если был задан четкий вопрос? Но ситуация еще лучше. Если даже допустить, что ребра были ориентированные, то выходит, что тесты некорректны, т. к. имеются вершины не достижимые из корня. Позволю себе привести англоязычное определение дерева с корнем из википедии:

wikipedia.org написав:

A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root.

Про существование же в дереве корня в условии было четко сказано. Так что так понимает не только большинство участников, но и математики. Посему не зависимо, ориентированно дерево, или нет, все его вершины должны быть достижимы из корня. Давай не будем строить аргументов вида "я интуитивно понял". Все формулировки говорят об обратном.

xXx написав:

necro написав:

...... Респект 2 partisan который на этом потерял баллы. Правда не понятно чего он хотел если сначала имел 60 баллов, а так потерял второй абс.

Если более внимательно читать посты partisan'a, то можно заметить, что он не аппелировал, а наоборот пытался защитить условие или авторское решение(или что-то ещё smile )...

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

Поза форумом

 

 

Сторінок: 1 2

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

Powered by Likt
© Copyright 2002–2009 Likt