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

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)

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

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

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

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

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)

1)

LVV написав:

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

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


2)

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


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

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)

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, которые оптимально разбивали подотрезки - наглядность, ах

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

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


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

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

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)

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

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

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

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

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

Ilya Porublyov написав:

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

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

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

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

Да никто!!!

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

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)

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

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

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

Конкретно щодо тесту... Якщо Байтазар пробурить 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, або бінарним пошуком серед одиничок.