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


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

Ви не зайшли.

#1 2013-02-17 17:58:05

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Задача REMAKE

Коротко: BFS & meet in the middle

На перший погляд: досить тупе, хоча й громіздкувате застосування пошуку в ширину; і взагалі -- передерта і слабко змінена задача 2001 з інформатікса (http://informatics.mccme.ru/moodle/mod/ … terid=2001)

...тільки от правильна реалізація звичайного пошуку в ширину цілком заслужено набирає як правило 60--70%% балів, якщо дуже добре вилизати технічні деталі реалізації, то 75%, І НІЯК НЕ БІЛЬШЕ. Надто великий виходить граф.

Для розв’язання задачі на повний бал, слід модифікувати пошук у ширину ідеєю MEET IN THE MIDDLE. Тобто, робити пошук одночасно і від старта, і від фініша, і зупиняти, коли пошук від старта і пошук від фініша вперше зустрінуться (вперше буде оброблена одна й та сама вершина -- повідомлення змінено лише в межах цих дужок, лише з міркувань благозвучності). Звичайно, мова йде не про справжню одночасність на двох процесорах, а про її емуляцію на одному. Наприклад, так: тримати масив з двох черг, і масив відстаней теж повинен бути вигляду d[2][10000000] (він же d[0..1][0..9999999]) : по одному виміру -- одне з двох значень "від старта"/"від фініша", по іншому -- звичайний номер вершини графа, який у даному випадку є просто значенням числа. І, наприклад, на кожному непарному кроці основного цикла пошуку в ширину працювати з 1-ю чергою та d[1][n], а на кожному парному -- з 0-вою чергою та d[0][n].

Відредаговано Ilya Porublyov (2013-02-17 18:42:08)

Поза форумом

 

#2 2013-02-17 18:17:27

Rubanenko
Новий користувач
Зареєстрований: 2013-02-17
Повідомлень: 7

Re: Задача REMAKE

Це все, звичайно, дуже добре, але як Ви прокоментуєте той факт, що в таблиці у мене за першу задачу 50 балів, а на онлайн тестуванні кілька хвилин тому я отримав 90? Така ж сама ситуація виникла ще у багатаьох учасників з мого закладу і не лише по цій задачі.

Поза форумом

 

#3 2013-02-17 18:29:28

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 425

Re: Задача REMAKE

Ось результат он-лайн (!) перевірки, того, що прийняла у вас, п. Рубаненко, система в 13-53
   
Тест    Результат    Время работы
001    PASSED (+0)    0.02 сек.
002    PASSED (+0)    0.05 сек.
01    PASSED (+2)    0.02 сек.
02    PASSED (+3)    0.02 сек.
03    PASSED (+3)    0.02 сек.
04    PASSED (+3)    0.02 сек.
05    PASSED (+3)    0.02 сек.
06    PASSED (+3)    0.02 сек.
07    PASSED (+3)    0.02 сек.
08    PASSED (+5)    0.02 сек.
09    PASSED (+5)    0.02 сек.
10    PASSED (+5)    0.02 сек.
11    PASSED (+5)    0.02 сек.
12    PASSED (+5)    0.03 сек.
13    FAILED (Wrong Answer)    0.04 сек.
14    FAILED (Wrong Answer)    0.03 сек.
15    PASSED (+5)    0.10 сек.
16    FAILED (Time Out)    0.76 сек.
17    FAILED (Time Out)    0.77 сек.
18    FAILED (Time Out)    0.77 сек.
19    FAILED (Time Out)    0.76 сек.
20    FAILED (Time Out)    0.76 сек.
21    FAILED (Time Out)    0.76 сек.
22    FAILED (Time Out)    0.77 сек.
23    FAILED (Time Out)    0.77 сек.
Прошло тестов: 15 из 25.

Набрано баллов: 50 из 100.
Вм щось зопалу...плутаєте.

Поза форумом

 

#4 2013-02-17 18:31:48

Rubanenko
Новий користувач
Зареєстрований: 2013-02-17
Повідомлень: 7

Re: Задача REMAKE

Тест    Результат    Время работы
00    PASSED (+0)    0.01 сек.
01    PASSED (+4)    0.01 сек.
02    PASSED (+4)    0.01 сек.
03    PASSED (+4)    0.01 сек.
04    PASSED (+4)    0.02 сек.
05    PASSED (+4)    0.01 сек.
06    PASSED (+4)    0.01 сек.
07    PASSED (+4)    0.01 сек.
08    PASSED (+4)    0.01 сек.
09    PASSED (+4)    0.72 сек.
10    FAILED (Time Out)    1.17 сек.
11    FAILED (Time Out)    1.18 сек.
12    PASSED (+4)    0.81 сек.
13    PASSED (+4)    1.15 сек.
14    PASSED (+4)    0.72 сек.
15    PASSED (+4)    1.28 сек.
16    PASSED (+4)    1.13 сек.
17    FAILED (Time Out)    1.51 сек.
18    PASSED (+4)    1.09 сек.
19    PASSED (+4)    1.44 сек.
20    PASSED (+4)    1.08 сек.
21    PASSED (+5)    1.10 сек.
22    PASSED (+5)    1.40 сек.
23    PASSED (+5)    1.45 сек.
24    PASSED (+5)    1.06 сек.
Прошло тестов: 22 из 25.

Набрано баллов: 88 из 100.

А ось результат, що я отримав на онлайн-перевірці по третій задачі...
Можливо це пов"язано з підвищеним навантаженням на сервер під час тестування?

Відредаговано Rubanenko (2013-02-17 18:36:22)

Поза форумом

 

#5 2013-02-17 18:34:57

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Задача REMAKE

Наявність тесту 0000 та відсутність тестів 21, 22, 23 наводить на думку, що явно щось не так...

Поза форумом

 

#6 2013-02-17 18:35:28

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 425

Re: Задача REMAKE

Ні.
13    FAILED (Wrong Answer)    0.04 сек.
14    FAILED (Wrong Answer)    0.03 сек.
Ось такого при навантаженні не може бути В ПРИНЦИПІ. Я первіряв код, ЯКИЙ СИСТЕМА ПРИЙНЯЛА У ВАС.
Ви, ймовірно, де-що інший

Поза форумом

 

#7 2013-02-17 18:38:05

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Задача REMAKE

Будь ласка, припиніть СУТТЄВО редагувати коментарі ПІСЛЯ того, як на них дана відповідь, бо так абсолютно нічого не можна зрозуміти...

Поза форумом

 

#8 2013-02-17 18:39:58

Rubanenko
Новий користувач
Зареєстрований: 2013-02-17
Повідомлень: 7

Re: Задача REMAKE

Так, я помилково зкопіював лог з іншої задачі. Але 88 і 80 балів - це теж різні речі.

Поза форумом

 

#9 2013-02-17 18:48:36

Rubanenko
Новий користувач
Зареєстрований: 2013-02-17
Повідомлень: 7

Re: Задача REMAKE

І це при тому, що рішення лінійне...

Поза форумом

 

#10 2013-02-17 18:56:29

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 425

Re: Задача REMAKE

Ось розв'язок, який ви надіслали, п. Рубаненко. Я не можу зрозуміти,що ви перевіряєте...

Код:

type st=string[10];
Var o:array[0..10]of st;
    s,s1,s2:st;
    used:array[0..10000333]of boolean;
    p,c:array[0..10000333]of longint;
    ot:array[0..100333]of longint;
    n1,k,n2,x,y,u,v,i,j:longint;
    pp:integer;
    q:char;
 procedure add(u:longint);
   begin
     inc(x);
     c[x]:=u;
     p[u]:=c[y];
     used[u]:=true;
   end;
  begin
//    fillchar(c,sizeof(c),0);
//    fillchar(p,sizeof(p),0);
    s1:='';
    s2:='';
    for i:=1 to 7 do
      begin
        read(q);
        s1:=s1+q;
      end;
    read(q);
    for i:=1 to 7 do
      begin
        read(q);
        s2:=s2+q;
      end;
    o[0]:='';
    for i:=1 to 7 do
      o[i]:=o[i-1]+'0';
    fillchar(used,sizeof(used),false);
    val(s1,n1,pp);
    val(s2,n2,pp);
    c[1]:=n1;
    used[n1]:=true;
    x:=1;
    y:=0;
    while x>y do
      begin
        if used[n2] then break;
        inc(y);
        v:=c[y];
        if (v<9999999)and(not used[v+1]) then add(v+1);
        if (v>0)and(not used[v-1]) then add(v-1);
        u:=v;
        for i:=2 to 9 do
          begin
            u:=u+v;
            if u>9999999 then break;
            if (not used[u]) then add(u);
          end;
        for i:=2 to 9 do
           begin
             if v mod i<>0 then continue
             else u:=v div i;
             if not used[u] then add(u);
           end;
        str(v,s);
        s:=o[7-length(s)]+s;
        for i:=1 to 6 do
          begin
            s:=s+s[1];
            delete(s,1,1);
            val(s,u,pp);
            if not used[u] then add(u);
          end;
      end;
    k:=0;
    while n2<>n1 do
      begin
        inc(k);
        ot[k]:=n2;
        n2:=p[n2];
      end;
    Write(k,' ',s1);
    for i:=k downto 1 do
     begin
      str(ot[i],s);
      s:=o[7-length(s)]+s;
      Write(' ',s);
     end;
    Writeln;
  end.

Поза форумом

 

#11 2013-02-17 18:59:54

Rubanenko
Новий користувач
Зареєстрований: 2013-02-17
Повідомлень: 7

Re: Задача REMAKE

Я Вам зараз про третю задачу кажу. З першою розібрався, але ще є питання про авторське рішення, хоча це вже інша розмова. Зараз моє питання полягає в тому, що результати по третій задачі не збігаються.

Поза форумом

 

#12 2013-02-17 19:07:28

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 425

Re: Задача REMAKE

Код:

type st=string[10];
Var o:array[0..10]of st;
    s,s1,s2:st;
    used:array[0..10000333]of boolean;
    p,c:array[0..10000333]of longint;
    ot:array[0..100333]of longint;
    n1,k,n2,x,y,u,v,i,j:longint;
    pp:integer;
    q:char;
 procedure add(u:longint);
   begin
     inc(x);
     c[x]:=u;
     p[u]:=c[y];
     used[u]:=true;
   end;
  begin
//    fillchar(c,sizeof(c),0);
//    fillchar(p,sizeof(p),0);
    s1:='';
    s2:='';
    for i:=1 to 7 do
      begin
        read(q);
        s1:=s1+q;
      end;
    read(q);
    for i:=1 to 7 do
      begin
        read(q);
        s2:=s2+q;
      end;
    o[0]:='';
    for i:=1 to 7 do
      o[i]:=o[i-1]+'0';
    fillchar(used,sizeof(used),false);
    val(s1,n1,pp);
    val(s2,n2,pp);
    c[1]:=n1;
    used[n1]:=true;
    x:=1;
    y:=0;
    while x>y do
      begin
        if used[n2] then break;
        inc(y);
        v:=c[y];
        if (v<9999999)and(not used[v+1]) then add(v+1);
        if (v>0)and(not used[v-1]) then add(v-1);
        u:=v;
        for i:=2 to 9 do
          begin
            u:=u+v;
            if u>9999999 then break;
            if (not used[u]) then add(u);
          end;
        for i:=2 to 9 do
           begin
             if v mod i<>0 then continue
             else u:=v div i;
             if not used[u] then add(u);
           end;
        str(v,s);
        s:=o[7-length(s)]+s;
        for i:=1 to 6 do
          begin
            s:=s+s[1];
            delete(s,1,1);
            val(s,u,pp);
            if not used[u] then add(u);
          end;
      end;
    k:=0;
    while n2<>n1 do
      begin
        inc(k);
        ot[k]:=n2;
        n2:=p[n2];
      end;
    Write(k,' ',s1);
    for i:=k downto 1 do
     begin
      str(ot[i],s);
      s:=o[7-length(s)]+s;
      Write(' ',s);
     end;
    Writeln;
  end.

Ось це ви перевіряєте.
А ось це - резулльтат;
001    PASSED (+0)    0.02 сек.
002    PASSED (+0)    0.05 сек.
01    PASSED (+2)    0.02 сек.
02    PASSED (+3)    0.02 сек.
03    PASSED (+3)    0.02 сек.
04    PASSED (+3)    0.02 сек.
05    PASSED (+3)    0.02 сек.
06    PASSED (+3)    0.02 сек.
07    PASSED (+3)    0.02 сек.
08    PASSED (+5)    0.02 сек.
09    PASSED (+5)    0.02 сек.
10    PASSED (+5)    0.02 сек.
11    PASSED (+5)    0.02 сек.
12    PASSED (+5)    0.03 сек.
13    FAILED (Wrong Answer)    0.04 сек.
14    FAILED (Wrong Answer)    0.03 сек.
15    PASSED (+5)    0.10 сек.
16    FAILED (Time Out)    0.77 сек.
17    FAILED (Time Out)    0.77 сек.
18    FAILED (Time Out)    0.77 сек.
19    FAILED (Time Out)    0.77 сек.
20    FAILED (Time Out)    0.77 сек.
21    FAILED (Time Out)    0.77 сек.
22    FAILED (Time Out)    0.76 сек.
23    FAILED (Time Out)    0.76 сек.
Прошло тестов: 15 из 25.

Набрано баллов: 50 из 100.

Поза форумом

 

#13 2013-02-17 19:10:31

Rubanenko
Новий користувач
Зареєстрований: 2013-02-17
Повідомлень: 7

Re: Задача REMAKE

Я розумію, що через мою помилку на початку виникло певне недорозуміння, але зараз я питаю про ТРЕТЮ задачу.

Поза форумом

 

#14 2013-02-17 19:11:48

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 425

Re: Задача REMAKE

Rubanenko написав:

Я Вам зараз про третю задачу кажу. З першою розібрався, але ще є питання про авторське рішення, хоча це вже інша розмова. Зараз моє питання полягає в тому, що результати по третій задачі не збігаються.

Відкрийте тему по задачі, що вас цікавить, якщо її немає,  чітко сформуюйте проблему.

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt