Addressing the olimpiad challenge of Interregional Olympics



  • There is a challenge to dynamic programming:

    введите сюда описание изображения

    To accomplish the task, I wrote a code on C++11:

    #include<iostream>
    #include<fstream>
    #include<algorithm>
    #include<vector>
    #include<tuple>
    

    using namespace std;

    struct problem {
    int startTime, solvingTime, endTime, score, index;
    };

    bool sort_problems_by_endtime(problem a, problem b) {
    return a.endTime < b.endTime;
    }

    tuple<int, vector<int>> maxScore(vector<problem> problems) {
    sort(problems.begin(), problems.end(), sort_problems_by_endtime); // сортируем задачи по времени окончания их решения

    vector&lt;int&gt; links(problems.size());
    vector&lt;long&gt; problems_optimal(problems.size()); // создаем динамический массив, хранящий оптимальные решения,
                                                    // где problems_optimal[i] - это максимальное кол-во баллов, которое возможно получить,
                                                    // используюя только первые i задач
    problems_optimal[0] = 0; 
    
    int j = 0;  // j хранит индекс последней задачи, которая заканчивается не позже чем начинается задача i
    problems[j].endTime = 0;
    
    for (size_t i = 1; i &lt; problems_optimal.size(); i ++) {
        if (i == 1) {
            j = 0;
        }
        else {
            for (; j &lt; i; j ++) {
                if (problems[j].endTime &gt; problems[i].startTime) {
                    break;
                }
            }
    
            j --;
        } // вычисляем j методом двойных указателей
                                                // выясняем что лучше: решать или не решать
        problems_optimal[i] = max(problems_optimal[i - 1], problems_optimal[j] + problems[i].score); 
    
        if (problems_optimal[i - 1] &gt; problems_optimal[j] + problems[i].score) { // создаем ссылку
            links[i] = -1;
        }
        else {
            links[i] = j;
        }
    }
    
    vector&lt;int&gt; moves;
    for (int i = problems_optimal.size() - 1; i != 0;) { // восстанавливаем решение (т. е. извлекаем ход решения задач)
        if (links[i] == -1) {
            i --;
        }
        else {
            moves.push_back(problems[i].index);
            i = links[i];
        }
    }
    
    return make_tuple(problems_optimal[problems_optimal.size() - 1], moves); // возвращаем оптимальное кол-во очков и массив с ходом решения
    

    }

    int main() {
    int k;

    cin &gt;&gt; k;
    vector&lt;problem&gt; problems(k + 1); // создаем динамический массив с задачами, причём нумеровать будем с единицы, чтобы не запутаться
    
    for (int i = 1; i &lt;= k; i ++) {
        cin &gt;&gt; problems[i].startTime &gt;&gt; problems[i].solvingTime &gt;&gt; problems[i].score;
    
        problems[i].endTime = problems[i].startTime + problems[i].solvingTime; // высчитываем время конца решения задачи
    
        problems[i].index = i; // так как дальше массив с задачами будет отсортирован, нам необходимо запомнить начальные положения задач
    }
    
    cout &lt;&lt; get&lt;0&gt;(maxScore(problems)) &lt;&lt; endl;
    
    vector&lt;int&gt; moves = get&lt;1&gt;(maxScore(problems));
    
    cout &lt;&lt; moves.size() &lt;&lt; endl;
    
    for (int i = moves.size() - 1; i &gt;= 0; i --) {
        cout &lt;&lt; moves[i] &lt;&lt; " ";
    }
    
    system("pause");
    return 0;
    

    }

    The problem is, the program only runs four out of 50 tests. I don't know what the problem is. Checking out a few simple examples, both of its own and of the conditions, worked correctly. What's the mistake?



  • A common idea. Let us face the challenge. U Over time Tu Then we need to maximise the amount. solve(0,Tu) + Cu + solve(Tu+Su,inf)♪ It's already clear that it's a naive solution to take over the first task we're gonna face.

    I'd say we take over the last task that we're gonna face. 0..NThen we'll figure out the results for her. But it won't be a long time, so the tree will go, but remember the memory.

    Pseudocod (tasks already quashed at start):

    for (last_task = 0; last_task < N; last_task ++){
         Tree.update(T[last_task] + S[last_task], 
                     Tree.max(0,T[last_task]) + C[last_task] );
    }
    cout << Tree.max(0, MAX_INT) << endl;
    

    Restoring the answer is no longer a problem. To this end, a tree needs to be changed to recognize not only the value but also the number + the position of the maximum element. Let the tree return {value,time, position}♪ Then:

    vector<int> ans;
    int MaxTime = MAX_INT;
    while (true){
        auto tmp = Tree.getFullMax(0,MaxTime);
        if (tmp.value == 0) break; 
        ans.push_back(tmp.position);
        MaxTime = tmp.time;
    }  
    cout << ans.size()<<endl;
    for (int i=ans.size()-1;i>=0;i--)
          cout << ans[i]<<" ";
    

    It's like without a tree:

    struct Task{
       int t,s,c,n;
    };
    

    Task task[100000];
    long long bestSum[100010];
    int goSum[100010];

    bool cmp(Task a, Task b){
    return a.t + a.s < b.t + b.s;
    }

    int main() {
    freopen("olympiad.in","r",stdin);
    freopen("olympiad.out","w",stdout);
    int N;
    cin >> N;
    for (int i=0;i<N;i++){
    cin >> task[i].t >> task[i].s >> task[i].c;
    task[i].n = i+1;
    }
    sort(task,task + N, cmp);
    bestSum[0] = 0;
    Task empt;
    empt.s = 0;
    empt.c = 0;
    empt.n = 0;
    for (int i=0;i<N;i++){
    bestSum[i + 1] = bestSum[i];
    goSum[i + 1] = -1;
    empt.t = task[i].t;
    int prev = upper_bound(task,task+N,empt,cmp) - task;
    long long nn = bestSum[prev] + task[i].c;
    if (nn > bestSum[i + 1]){
    goSum[i + 1] = prev;
    bestSum[i + 1] = nn;
    }
    }
    cout << bestSum[N]<<endl;
    vector<int> ans;
    while (N)
    if (goSum[N] == -1)
    N--;
    else {
    ans.push_back(task[N-1].n);
    N = goSum[N];
    }
    cout << ans.size() << endl;
    for (int i=ans.size() -1; i>=0; i--)
    cout << ans[i]<< " ";
    cout << endl;
    }

    Thus, the author &apos; s idea is generally being pursued. ♪ ♪




Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2