online advertising

Thursday, October 16, 2014

UVa Problem 957 - Popes

Problem:

Please find the problem here.

Solution:

Competitive programming hinted on it as complete search + binary search. It doesn't take me long to understand that as for all possible beginning year (i.e. complete search), binary search for the ending year, and just count the size.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=898

#include "UVa957.h"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int UVa957()
{
    while (true)
    {
        int period_length;
        int number_of_popes;
        cin >> period_length;
        if (cin.eof())
        {
            break;
        }
        cin >> number_of_popes;
        vector<int> years;
        for (int i = 0; i < number_of_popes; i++)
        {
            int year;
            cin >> year;
            years.push_back(year);
        }

        int maxFrom = -1;
        int maxTo = -1;
        int maxSize = -1;

        for (unsigned int i = 0; i < years.size(); i++)
        {
            int lower_year = years[i];
            int upper_year = lower_year + period_length - 1; // Inclusive index
            vector<int>::iterator upper_bound_pointer = upper_bound(years.begin(), years.end(), upper_year);
            int exclusive_upper_index = upper_bound_pointer - years.begin();

            int size = exclusive_upper_index - i;
            if (size > maxSize)
            {
                maxFrom = lower_year;
                maxTo = *(upper_bound_pointer - 1);
                maxSize = size;
            }
        }
        cout << maxSize << " " << maxFrom << " " << maxTo << endl;

    }

    return 0;
}

No comments :

Post a Comment