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


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

Ви не зайшли.

#26 2010-12-29 22:53:04

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

Ilya Porublyov написав:

рішення задачі Wie

Код:

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i,n) for (int i=0; i<(n); ++i)
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define FORE(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); ++it)
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define CLR(x) memset(x,0,sizeof x)
#define xx first
#define yy second
typedef long long int lli;
typedef pair<int, int> P;
typedef vector<int> vi;


using namespace std;
#define MAXN 2007
#define INF 100000000
int n,t[MAXN],dp[MAXN][MAXN]={0},prawog[MAXN]={0},lewog[MAXN]={0};
deque<P> prawo[MAXN],lewo[MAXN];

void dodaj(deque<P>& q,P p){
        while(!q.empty() && q.back().yy >= p.yy) q.pop_back();
        q.PB(p);
}

int nast(deque<P>& q){
        P x=q.front();
        q.pop_front();
        if(q.empty()) return INF;
        P res=q.front();
        q.push_front(x);
        return res.yy;
}

void go(int l,int r){
//        cout << "op " << prawo[l].front().xx << "/" << prawo[l].front().yy << endl;
//        cout << "op " << lewo[r].front().xx << "/" << lewo[r].front().yy << endl;
        while(prawo[l].front().xx + lewo[r].front().xx < r-l){
                if(nast(prawo[l]) < nast(lewo[r])) prawo[l].pop_front();
                else lewo[r].pop_front();
        }
        dp[l][r]=max(prawo[l].front().yy, lewo[r].front().yy);
//        cout << "go " << l << " " << r << " " << dp[l][r] << endl;
        dodaj(prawo[l], P(r-l+1, dp[l][r]+t[r+1]));
        dodaj( lewo[r], P(r-l+1, dp[l][r]+t[l-1]));
}

int main(){
        //in
        scanf("%d",&n);
        FOR(i,1,n) scanf("%d",&t[i]);
        //rozw
        FOR(i,1,n) {
                prawo[i].PB(P(0,t[i]));
                lewo[i].PB(P(0,t[i]));
        }
        REP(d,n) FOR(i,1,n-d) go(i,i+d);
        //out
        printf("%d\n",dp[1][n]);
        return 0;
}

Думаю, что эта задача должна решаться методом двоичного поиска(дихотомия) (делением массива пополам). И никаких ограничений 200 здесь не нужно. Самым худшим вариантом (не в нефтяном а в математическом смысле) следует считать тот вариант, когда нефть достигает конца отрезка. Ведь при этом поиск конца залежей самый трудный. В условии задачи именно этот вариант должен подразумеваться под худшим. А иначе какой?

Это что-то вроде задачи по поиску перегоревшей лампочки в елочной гирлянде. Сначала делим гирлянду пополам. Проверяем тестером одну из половин и определяем в какой части сгоревшая лампочка. Затем делим пополам участок со сгоревшей лампочкой... и т.д.

В худшем варианте Wie для участка длиной 200 нужно пробурить самое меньшее восемь скважин (координаты 100, 100+100/2=150, 150+50/2=175, 175+25/2=188, 188+12/2=194, 194+6/2=197, 197+3/2=199, и 200) При делении округляем вверх чтобы получить середину отрезка, а если делится без остатка, берём левую точку.

Но тогда для случая
6    8 24 12 6 7 1
ответ должен быть 12+7+1=20

Возможно я и не прав. Но поясните мне пожалуйста (логически, алгоритмически, статистически... как угодно) почему предложенное вами решение
на данные 4 8 24 12 6 Выдаёт:42
и на данные 5 8 24 12 6 7 Выдаёт 42
и на данные 6 8 24 12 6 7 1 Выдаёт 42
и на данные 7 8 24 12 6 7 1 20 Выдаёт 42
и на данные 8 8 24 12 6 7 1 20 10 Выдаёт 42
и на данные 9 8 24 12 6 7 1 20 10 12 Выдаёт 42
и на данные 10 8 24 12 6 7 1 20 10 12 13 Выдаёт 42
и на данные 11 8 24 12 6 7 1 20 10 12 13 12 Выдаёт 42
и так далее...

Откуда 42 ??? Почему всё время 42 ???

Відредаговано LVV (2010-12-30 06:57:50)


Вік живи - вік навчайся.

Поза форумом

 

#27 2010-12-29 23:30:49

Иванов
Новий користувач
Зареєстрований: 2010-12-09
Повідомлень: 21

Re: Лучшие решения задач второго тура

LVV написав:

Но тогда для случая
6    8 24 12 6 7 1
ответ должен быть 12+7+1=20

Если я не прав, то поясните мне пожалуйста (логически, алгоритмически, статистически... как угодно) почему предложенное вами решение
на данные 4 8 24 12 6 Выдаёт:42
и на данные 5 8 24 12 6 7 Выдаёт 42
и на данные 6 8 24 12 6 7 1 Выдаёт 42
и на данные 7 8 24 12 6 7 1 20 Выдаёт 42
и на данные 8 8 24 12 6 7 1 20 10 Выдаёт 42
и на данные 9 8 24 12 6 7 1 20 10 12 Выдаёт 42
и на данные 10 8 24 12 6 7 1 20 10 12 13 Выдаёт 42
и на данные 11 8 24 12 6 7 1 20 10 12 13 12 Выдаёт 42
и так далее...

Откуда 42 ??? Почему всё время 42 ???

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

мое решение тоже выдает 42 для этих примеров

чтобы не морочить голову со сложными примерами, попробуйте единичные:
2 1 1
3 1 1 1

и т.д. посмотрите на ответ. каждое новое уникальное число в ответах будет повторяться больше раз, чем предыдущее. ну вроде как при поиске в отсортированном массиве: число операций пропорционально log2 N и, например, при длинах массива от 1024 до 2047 log2 N e [10,11). вам ведь не кажется странной такая "бешеная" скорость. вот и в случае с wie происходит нечто подобное

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

Поза форумом

 

#28 2010-12-30 00:21:46

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

Уважаемый Иванов, и Ilya Porublyov. Вполне возможно, что я не прав. Очень даже может быть что результат 42 должен повторяться для приведенных мною примеров.
Но ведь в любом решении должна быть какая-то логика, алгоритм. Не мог ли бы кто-то пояснить саму идею решения.

Предложенное MItornaDOS обьяснение:
"У цій задачі рекурсія = утопія, це зрозуміло, тому я використовував повний перебір варіантів динамікою.
Спочатку ділимо всі відрізки на групи по 2 відрізки, знаходимо мінімальний час для них (це вийде сума)
Потім ділимо всі відрізки на групи по 3 відрізки, знаходимо мінімальний час для них (це вийде середній елемент + більший з двох крайніх)
Потім ділимо всі відрізки на групи по 4 відрізки, знаходимо мінімальний час для них ... etc"
как-то не очень помогает из указанных выше тестов в ручном режиме получить результат 42.

А предложение Иванова использовать простые примеры, типа 3 1 1 1, ничего не проясняет. Так как здесь полная аналогия с моим решением методом двоичного поиска(ну, типа, найти лампочку в гирлянде).

Відредаговано LVV (2010-12-30 00:28:35)


Вік живи - вік навчайся.

Поза форумом

 

#29 2010-12-30 01:36:32

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Лучшие решения задач второго тура

LVV, найгірший сценарій - це коли треба витратити найбільше часу, а не пробурити найбільше скважин. Тобто для тесту 5 100 1 1 1 1 відповідь - 101. Починаємо в першій одиниці і при найгіршому сценарії нафти там не буде і доведеться бурити ще і 100. (Якщо вона буде, то треба перевірити ще 2 одиниці, а 3 це значно кращий сценарій, ніж 101).
Для тесту 6 8 24 12 6 7 1 - аналогічно. Буримо 24, при найгіршому сценарії границя десь справа. Там починаємо з 6. Якщо нафта є, то треба бурити ще 7 і 1. Тоді відповідь - 7+1+6+24=38. Якщо нафти там немає, то буримо 12. Відповідь - 12+6+24=42. Це гірше, ніж 38, отже остаточна відповідь - 42

Відредаговано Dim_ov (2010-12-30 01:38:49)

Поза форумом

 

#30 2010-12-30 09:25:12

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

Dim_ov написав:

LVV, найгірший сценарій - це коли треба витратити найбільше часу, а не пробурити найбільше скважин. Тобто для тесту 5 100 1 1 1 1 відповідь - 101. Починаємо в першій одиниці і при найгіршому сценарії нафти там не буде і доведеться бурити ще і 100. (Якщо вона буде, то треба перевірити ще 2 одиниці, а 3 це значно кращий сценарій, ніж 101).
Для тесту 6 8 24 12 6 7 1 - аналогічно. Буримо 24, при найгіршому сценарії границя десь справа. Там починаємо з 6. Якщо нафта є, то треба бурити ще 7 і 1. Тоді відповідь - 7+1+6+24=38. Якщо нафти там немає, то буримо 12. Відповідь - 12+6+24=42. Це гірше, ніж 38, отже остаточна відповідь - 42

Если заменить в условии задачи слова "найгірший сценарій" на Ваше определение, то получаем:
"Ви повинні створити такий план буріння, що час, необхідний  для визначення дальньої від точки A границі нафтового родовища, мінімальний (за умови що треба витратити найбільше часу).
Что-то не вяжется со здравым смыслом...

Просмотрим согласно Вашей логике тест 7 8 24 12 6 7 1 20 (7- число точек)

Бурим 24, если нефти нет, то бурим 8 . (Бурение закончено, сумма 32)
если нефть в 24 есть, то бурим в 6. Если в 6 нефти нет, то бурим в 12. (Бурение закончено, сумма 42)
Если нефть в 6 есть, то бурим в 1. Если нефти в 1 нет, то бурим в 7. (Бурение закончено, сумма 38)
Если нефть в 1 есть, то бурим в последней точке 20. (Бурение закончено, сумма 51)

Вопрос: Почему из всех этих сумм, правильным ответом считается 42 ???

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

Если использовать метод половинного деления массива, то всё ясно и логично (читайте пример с гирляндами). Но смущает то, что время везде разное и пример с гирляндами здесь немного не "катит". Хотя и здесь можно определить так: если участок имеет среднюю точку - бурим в ней, а если не  имеет - бурим в соседней точке с наименьшим временем бурения. Тогда тоже всё ясно и логично. но в тесте 6 8 24 12 6 7 1 (6-число точек) всё равно имеем: 12+7+1, но никак не 24+7+1 !!!

P.S. Я уже подправил своё высказывание #29 на счет "...наибольшее количество скважин... "  Признаю - ошибочное утверждение было.

Відредаговано LVV (2010-12-30 09:32:14)


Вік живи - вік навчайся.

Поза форумом

 

#31 2010-12-30 09:36:17

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Лучшие решения задач второго тура

LVV написав:

7 8 24 12 6 7 1 20 (7- число точек)

Вы взяли точку со временем бурения 24 и обнаружили, что самое большое время = 51.
Значит нужно взять другую точку и проверить все возможные случаи для нее. И в какой точке максимум времени будет минимальным это и будет ответом.
Вот кстати рекурсивное решение, попробуйте разобраться:

Код:

var bur:array[0..300]of longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
function minsum(a,b:integer):longint;
var i,minimum,mins:longint;
   begin
      minimum:=2000000000;
      if a=b then minsum:=bur[a] else
         if a-b=1 then minsum:=bur[a]+bur[b] else begin
      for i:=a to b do begin
      mins:=max(minsum(a,i-1),minsum(i+1,b))+bur[i];
      if mins<minimum then minimum:=mins;
      end;
      minsum:=minimum;
      end;
   end;
var n,i:integer;
begin
read(n);
for i:=1 to n do read(bur[i]);
writeln(minsum(1,n));
end.

Поза форумом

 

#32 2010-12-30 11:11:36

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

Re: Лучшие решения задач второго тура

1)

LVV написав:

Если заменить в условии задачи слова "найгірший сценарій" на Ваше определение, то получаем:
"Ви повинні створити такий план буріння, що час, необхідний  для визначення дальньої від точки A границі нафтового родовища, мінімальний (за умови що треба витратити найбільше часу).
Что-то не вяжется со здравым смыслом...

Ви уявляєте собі гру двох гравців, коли один докладає усіх зусиль для того щоб зменшити певну величину, а інший -- щоб збільшити? Ну і тут приблизно та сама ситуація: припускаємо, ніби природа не діє тупо за принципом найменших зусиль, а докладає певних зусиль, щоб протидіяти Байтазару. Оце і означає "песимістичне припущення". Але Байтазар теж діє не за принципом найменших зусиль, а робить усе від нього залежне, щоб мінімізувати сумарний час. Оце і означає "мінімальний".


2)

Пояснити код Андриховича я не можу.


На решту повідомлень спробую відповісти пізніше -- пробачте, зараз зайнятий.

Поза форумом

 

#33 2010-12-30 12:38:37

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

LeonID, спасибо за решение. Но любому решению предшествует логический разбор задачи, продумывание соответствующего алгоритма (если, конечно, решение не взято готовым из каких-то источников)

Так вот я пока не прочитал здесь никакого мало-мальски толкового законченного алгоритма или удовлетворяющего все мои претензии и возражения обьяснения. Решения есть. И не одно. И, судя по результатам тура, решений много. Но как можно решить задачу, заработать 40 баллов, и не уметь обьяснить основные моменты или наброски алгоритма по которым решалась задача.
Я не исключаю, что просто я не понимаю чего-то. Но помогите, пожалуйста, обьясните, если все такие умные.

А с решением Вашим, LeonID, обязательно попробую разобраться. Хотя трудно из программного кода вытягивать алгоритм решения.


Вік живи - вік навчайся.

Поза форумом

 

#34 2010-12-30 12:40:14

Loginf
Новий користувач
Зареєстрований: 2009-11-25
Повідомлень: 37

Re: Лучшие решения задач второго тура

LVV.
Тест  7   8 24 12 6 7 1 20
Бурим шестёрку.
Если нету, бурим 24, если нету бурим 8 (получается 38) если есть бурим 12 (получается 42)
Если в шестёрке есть, тогда бурим единицу. Если нету, бурим 7 (итого 14) если есть бурим 20 (итого 27)

42 - самый худший случай, поэтому:
Ответ: 42.

Во всех остальных, как ни странно, ответ 42 тоже верный=)

Відредаговано Loginf (2010-12-30 12:50:54)

Поза форумом

 

#35 2010-12-30 12:52:06

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Лучшие решения задач второго тура

LVV написав:

LeonID, спасибо за решение. Но любому решению предшествует логический разбор задачи, продумывание соответствующего алгоритма (если, конечно, решение не взято готовым из каких-то источников)

Так вот я пока не прочитал здесь никакого мало-мальски толкового законченного алгоритма или удовлетворяющего все мои претензии и возражения обьяснения. Решения есть. И не одно. И, судя по результатам тура, решений много. Но как можно решить задачу, заработать 40 баллов, и не уметь обьяснить основные моменты или наброски алгоритма по которым решалась задача.
Я не исключаю, что просто я не понимаю чего-то. Но помогите, пожалуйста, обьясните, если все такие умные.

А с решением Вашим, LeonID, обязательно попробую разобраться. Хотя трудно из программного кода вытягивать алгоритм решения.

EDIT:
прибрав свій алгоритм, бо Иванов у наступному пості пояснив значно краще

Відредаговано Dim_ov (2010-12-30 14:47:06)

Поза форумом

 

#36 2010-12-30 14:33:15

Иванов
Новий користувач
Зареєстрований: 2010-12-09
Повідомлень: 21

Re: Лучшие решения задач второго тура

LVV написав:

LeonID, спасибо за решение. Но любому решению предшествует логический разбор задачи, продумывание соответствующего алгоритма (если, конечно, решение не взято готовым из каких-то источников)

Так вот я пока не прочитал здесь никакого мало-мальски толкового законченного алгоритма или удовлетворяющего все мои претензии и возражения обьяснения. Решения есть. И не одно. И, судя по результатам тура, решений много. Но как можно решить задачу, заработать 40 баллов, и не уметь обьяснить основные моменты или наброски алгоритма по которым решалась задача.
Я не исключаю, что просто я не понимаю чего-то. Но помогите, пожалуйста, обьясните, если все такие умные.

А с решением Вашим, LeonID, обязательно попробую разобраться. Хотя трудно из программного кода вытягивать алгоритм решения.

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

рассмотрим N точек.
какие действия для нас допустимы ? - мы можем пробурить каждую отдельную точку.
------ допустим, что какая-то (любая) точка выбрана и мы ее пробурили.
------ данные по бурению: нефть либо есть, либо нет.
------------ если есть - значит продолжать поиск, начав его в ЭТОЙ точке, нужно вправо.
------------ если нет - значит продолжать поиск, начав его в ЭТОЙ точке, нужно влево.
------ а теперь возвращаемся к условию и понимаем, что нас должно интересовать не конкретное наличие/отсутствие нефти в точке бурения, а ХУДШИЙ вариант ПРОДОЛЖЕНИЯ поиска, начав его в ЭТОЙ точке.
------ итак, если поиск мы начали бурением в точке i, значит ХУДШЕЕ время поиска составит t[i] + max(F(1..i-1),F(i+1...N))
------ теперь остается вспомнить, что предполагая худшее в каждом отдельном бурении, мы все-таки можем начать бурение с любой из точек. поэтому F(1...N) = min (t[i] + max(F(1..i-1),F(i+1..N))) по i.

как видите, это естественным образом записывается через рекурсию, но слишком уж много будет перевычислений. поэтому рекурсию нужно заменить тупой мемоизацией, начав с очевидных соотношений: F(i...i) = t[i], F(i...i+1)=t[i]+t[i+1]

итак
1) ХУДШЕСТЬ выплывает тогда, когда мы из двух частей, на которые разбивается отрезок при бурении в любой его точке, выбираем худший вариант продолжения поиска
2) НАИМЕНЬШЕСТЬ выплывает, когда мы перебираем все возможные точки, в которых начинаем бурить


/п/с/ если вас все еще преследует 42, напишите программу рекурсией с выводом списка i, которые оптимально разбивали подотрезки - наглядность, ах

Поза форумом

 

#37 2010-12-30 15:37:56

Loginf
Новий користувач
Зареєстрований: 2009-11-25
Повідомлень: 37

Re: Лучшие решения задач второго тура

нет, там тоже 42=)
Сначала сверлим 6, там нету, потом 24, там есть, потом 12. Итого 42- это в наихудшем варианте.
А если в 6 есть, то  мы бурим 10, если есть - 12, если нету - 1. Если в 1 есть - 20, если в 1 нету - 7. В любом случае получится меньше чем 42.

Відредаговано Loginf (2010-12-30 15:39:39)

Поза форумом

 

#38 2010-12-30 16:32:28

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

Спасибо, Иванов.

"... итак
1) ХУДШЕСТЬ выплывает тогда, когда мы из двух частей, на которые разбивается отрезок при бурении в любой его точке, выбираем худший вариант продолжения поиска
2) НАИМЕНЬШЕСТЬ выплывает, когда мы перебираем все возможные точки, в которых начинаем бурить."


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

Вроде бы начинаю понимать.


Вік живи - вік навчайся.

Поза форумом

 

#39 2010-12-30 16:38:03

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

Loginf написав:

нет, там тоже 42=)
Сначала сверлим 6, там нету, потом 24, там есть, потом 12. Итого 42- это в наихудшем варианте.
А если в 6 есть, то  мы бурим 10, если есть - 12, если нету - 1. Если в 1 есть - 20, если в 1 нету - 7. В любом случае получится меньше чем 42.

Тест  7   8 24 12 6 7 1 20
а если нету в 24 и есть в 8 ??? Почему Вы исключаете такой сценарий?


Вік живи - вік навчайся.

Поза форумом

 

#40 2010-12-30 16:45:42

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Лучшие решения задач второго тура

LVV написав:

Loginf написав:

нет, там тоже 42=)
Сначала сверлим 6, там нету, потом 24, там есть, потом 12. Итого 42- это в наихудшем варианте.
А если в 6 есть, то  мы бурим 10, если есть - 12, если нету - 1. Если в 1 есть - 20, если в 1 нету - 7. В любом случае получится меньше чем 42.

Тест  7   8 24 12 6 7 1 20
а если нету в 24 и есть в 8 ??? Почему Вы исключаете такой сценарий?

тому що він не найгірший(6+8+24 < 6+12+24)

Відредаговано Dim_ov (2010-12-30 16:46:37)

Поза форумом

 

#41 2010-12-30 17:28:54

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

Dim_ov написав:

LVV написав:

Loginf написав:

нет, там тоже 42=)
Сначала сверлим 6, там нету, потом 24, там есть, потом 12. Итого 42- это в наихудшем варианте.
А если в 6 есть, то  мы бурим 10, если есть - 12, если нету - 1. Если в 1 есть - 20, если в 1 нету - 7. В любом случае получится меньше чем 42.

Тест  7   8 24 12 6 7 1 20
а если нету в 24 и есть в 8 ??? Почему Вы исключаете такой сценарий?

тому що він не найгірший(6+8+24 < 6+12+24)

Пардон. И правда. smile

Но это уже не существенно. Иванов всё вроде бы толково пояснил.


Вік живи - вік навчайся.

Поза форумом

 

#42 2010-12-30 17:34:19

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

Re: Лучшие решения задач второго тура

На мою думку, той код, яким починається дана тема, -- цілком ясний і зрозумілий розв'язок задачі WIE. І цей код достатньо ефективний при обмеженні на N до 200.

a[i][j] -- час, за який вдасться проаналізувати частину відрізку від i-ої до j-ої точки, якщо припустити, ніби природа буде робити все від неї залежне, щоб Байтазару довелося працювати якнайдовше, а сам Байтазар -- усе від нього залежне, щоб йому довелося працювати якомога менше. Пробачте, але це -- досить примітивний приклад застосування парадигми динамічного програмування, і мені не ясно, що саме кому не ясно (в кубічному розв'язку, наведеному в першому повідомленні даної теми). Якщо є конкретні запитання -- задавайте.

Але тема називається "Лучшие решения...". Тому, на мою думку, було б несправедливо взагалі не згадати, що взагалі-то існує значно ефективніший розв'язок.

А що я не можу його (розв'язок Андриховича) пояснити -- да, я недорозвинений, да, я не можу його пояснити, але стрілятися з цієї причини не буду. Давайте на наступні тури свої цікаві задачі з поясненнями. Те само пропоную тим, хто стібався з надзвичайно великої практичної цінності задачі, бо вона про нафту.

Відредаговано Ilya Porublyov (2010-12-30 17:39:13)

Поза форумом

 

#43 2010-12-30 17:43:30

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

Иванов написав:

.... выбираем худший вариант продолжения поиска....

Вопрос. А по какому принципу осуществлять этот самый поиск?
Где и как бурить справа и слева от выбранной точки?

Может следует бурить подряд? Тогда в худшем сценарии, когда нефть есть, везде придётся пробурить все скважины.
Что может быть хуже этого варианта поиска. Это ли не худший вариант?

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

А может он воспользуется методом двоичного поиска и будет бурить в центре каждого отрезка, и дальше в центре слева или в центре справа в зависимости от наличия нефти?

В каждом из этих методов поиска будут разные варианты.
Так как же бурить и почему.

Извините за надоедливость, но уж очень хочется докопаться до сути... smile


Вік живи - вік навчайся.

Поза форумом

 

#44 2010-12-30 17:53:55

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

Ilya Porublyov написав:

А що я не можу його (розв'язок Андриховича) пояснити -- да, я недорозвинений, да, я не можу його пояснити, але стрілятися з цієї причини не буду. Давайте на наступні тури свої цікаві задачі з поясненнями. Те само пропоную тим, хто стібався з надзвичайно великої практичної цінності задачі, бо вона про нафту.

Наоборот. Я лично считаю Вас на голову выше всех тех авторов заданий, кто отмалчивается на форуме.

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

Кто еще кроме Вас выставил сейчас здесь авторское решение задачи второго тура?

Да никто!!!

Хвост трубой!! С наступающим Вас и всего самого наилучшего !!!


Вік живи - вік навчайся.

Поза форумом

 

#45 2010-12-30 17:59:45

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Лучшие решения задач второго тура

LVV написав:

Иванов написав:

.... выбираем худший вариант продолжения поиска....

Вопрос. А по какому принципу осуществлять этот самый поиск?
Где и как бурить справа и слева от выбранной точки?

Может следует бурить подряд? Тогда в худшем сценарии, когда нефть есть, везде придётся пробурить все скважины.
Что может быть хуже этого варианта поиска. Это ли не худший вариант?

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

А может он воспользуется методом двоичного поиска и будет бурить в центре каждого отрезка, и дальше в центре слева или в центре справа в зависимости от наличия нефти?

В каждом из этих методов поиска будут разные варианты.
Так как же бурить и почему.

Извините за надоедливость, но уж очень хочется докопаться до сути... smile

я думав, що пояснення, повнішого за пояснення Иванова немає... smile
Байтазар бурить за інтуїцією. І треба було написати програму, яка б моделювала цю інтуїцію smile. Це не буріння всих точок підряд, і не бін пошук(не обов'язково буритиметься середина лівого чи правого відрізка)

Поза форумом

 

#46 2010-12-30 18:00:18

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

Re: Лучшие решения задач второго тура

Olesuk написав:

І ще, а які обмеження по пам'яті і часу має ця задача на 2-ох тисячах точок.

Час 1 сек, пам"ять 128 Мб

LVV написав:

Кто еще кроме Вас выставил сейчас здесь авторское решение задачи второго тура?

Мій розв"язок --

Код:

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN=1000;

long est[MAXN+2][MAXN+2];
long t[MAXN+2];

long T(int l, int r) // l..r range including both l and r
{
    if(l>r)
        return 0;
    if(l==r)
        return t[l];
    if(est[l][r]>0)
        return est[l][r];
    long curr,min=0x7FFFFFFF;
    for(int k=l; k<=r; k++)
    {
        curr = t[k] + max(T(l,k-1), T(k+1,r));
        if(curr<min)
        {
            min=curr;
        }
    }
    return (est[l][r]=min);
}

int main(int argc, char* argv[])
{
    int N;
    scanf("%d",&N);
    for(int i=1; i<=N; i++)
        scanf("%d",t+i);

    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            est[i][j]=-1;

    printf("%d\n",T(1,N));

    return 0;
}

Що майже ідентично розв"язку, яким починалася дана тема.

до LVV:
Ви прочитали (наведене ДВІЧІ ДО Вашого останнього на даний момент повідомлення) еквівалентне формулювання, що Байтазар і природа буцімто грають один проти одного?
Що саме Вам у ньому незрозуміло?

Відредаговано Ilya Porublyov (2010-12-30 18:13:49)

Поза форумом

 

#47 2010-12-30 19:30:04

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Лучшие решения задач второго тура

Ilya Porublyov написав:

Ви прочитали (наведене ДВІЧІ ДО Вашого останнього на даний момент повідомлення) еквівалентне формулювання, що Байтазар і природа буцімто грають один проти одного?
Що саме Вам у ньому незрозуміло?

На данный момент непонятно не само условие задачи, а алгоритм хотя бы примитивного её решения.

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

Но Байтазар не тупой и не станет бурить все точки подряд, чтобы получился тот самый "наихудший вариант бурения".
Тем более что с Ваших слов:
"...Байтазар робить усе від нього залежне, щоб мінімізувати сумарний час"

Но ведь вроде бы самый оптимальный писк - это двоичный, бурением в центрах отрезков?. Но Dim_ov подсказывает, что "не обов'язково буритиметься середина лівого чи правого відрізка"

Короче, вот тест 6 8 24 12 6 7 1 . Сначала пробурили первую точку 8. Где Байтазар пробурит следующую точку и чем при этом он будет руководствоваться?


Вік живи - вік навчайся.

Поза форумом

 

#48 2010-12-30 19:57:23

Loginf
Новий користувач
Зареєстрований: 2009-11-25
Повідомлень: 37

Re: Лучшие решения задач второго тура

Если уж Байтазар пробурит точку 8 (чего б я не советовал ему делать, так как надо бы начать с 6smile. То следующей точкой будет 12.
Потом либо 24, либо 7. После 7: либо 6, либо 1.
Почему именно 12 будет следующей точкой? Потому что именно так мы можем получить МИНИМАЛЬНЫЙ НАЙХУДШИЙ СЛУЧАЙ, а это уже из того, что я в уме прикинул как будут происходить дела при остальных случаях. Но это вместо моего ума должна делать программа=) Грубо говоря, она тоже будет перебирать почти все варианты бурения. Как именно, разбирайтесь в коде LeonID'а smile

Відредаговано Loginf (2010-12-30 20:00:32)

Поза форумом

 

#49 2010-12-30 20:11:49

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Лучшие решения задач второго тура

LVV написав:

На данный момент непонятно не само условие задачи, а алгоритм хотя бы примитивного её решения.

Закомментировал рекурсивное решение, надеюсь это что-то прояснит:

Код:

var bur:array[0..300]of longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
function minsum(a,b:integer):longint;{рекурсивная функция поиска минимального времени бурения на отрезке a-b}
var i,minimum,mins:longint;
   begin
      minimum:=2000000000;{вначале минимальное время - максимально}
      if a=b then minsum:=bur[a]{если точка одна время бурения = времени бурения в этой точке.
                                 В этом месте рекурсия имеет первый выход} 
        else
               if a-b=1 then minsum:=bur[a]+bur[b]{если точек две, то время бурения = суме
            времени бурения в этих точках 
            В этом месте рекурсия имеет второй выход} 
             else begin
    {если точек(буровых вышек) больше двух, действуем так}
      for i:=a to b do begin {на отрезке от а до b последовательно выбираем все точки}
    {пусть в даный момент это точка i}
    {рекурсивно вызывая функцию minsum вычисляем значение наихудшего(максимального) времени
        бурения на отрезках (a,i-1) и (i+1,b), к вычисленному времени прибавляем время бурения в 
        точке i(bur[i])}
      mins:=max(minsum(a,i-1),minsum(i+1,b))+bur[i];{что выбрать minsum(a,i-1) или minsum(i+1,b)?
     определяем используя описаную выше функцию max()}
      if mins<minimum then minimum:=mins;{последовательно выбирая все точки на отрезке отрезке a-b
                будем получать разные значения наихудшего времени, теперь из наихудших
                ищем наилучшее(проще говоря ищем минимум и запоминаем его)}
      end;
      minsum:=minimum;(найденный результат присваиваем значению функции)
      end;
   end;
var n,i:integer;
begin
read(n);
for i:=1 to n do read(bur[i]);
writeln(minsum(1,n));{первый вызов функции естественно на максимальном отрезке от 1 до n}
end.

Поза форумом

 

#50 2010-12-30 20:24:28

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

Re: Лучшие решения задач второго тура

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

Конкретно щодо тесту... Якщо Байтазар пробурить 1-шу точку, де 8, може виявиться, що там нафта є (Байтазар походив "точка 1", природа може відповісти ходом "є"). Тоді Байтазару найбільш вигідно відповісти бурінням у точці 3, де 12. Після такого ходу, якщо природа походить ходом "нема", Байтазару залишиться пробурити у точці 2, де 24 (остаточна відповідь 8+12+24=44); якби природа походила не "нема", а "є", то вона б піддалася Байтазару і він зміг би завершити буріння за час аж ніяк не більший 8+12+6+7+1=34 (а насправді, здається, й за ще менший).

Ясний чіткий контрприклад до ідеї "бурити посередині" досить простий:
42 42 42 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
(перше 42 -- кіль-ть точок)
Відповідь буде 84, і для її досягнення треба пробурити спочатку в точці 2, а потім, залежно від відповіді природи, або в точці 1, або бінарним пошуком серед одиничок.

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt