Shantanu Dwivedi Ответов: 2

Неправильный ответ на вопрос о hackerrank


Given a set of arrays of size and an integer , you have to find the maximum integer for each and
every contiguous subarray of size for each of the given arrays.
Input Format
First line of input will contain the number of test cases T. For each test case, you will be given the size of
array N and the size of subarray to be used K. This will be followed by the elements of the array A .
Constraints
, where is the element in the array .
Output Format
For each of the contiguous subarrays of size of each array, you have to print the maximum integer.
Sample Input
i
2
5 2
3 4 6 3 4
7 4
3 4 5 8 1 4 10
Sample Output
4 6 6 4
8 8 8 10
Explanation
For the first case, the contiguous subarrays of size 2 are {3,4},{4,6},{6,3} and {3,4}. The 4 maximum
elements of subarray of size 2 are: 4 6 6 4.
For the second case,the contiguous subarrays of size 4 are {3,4,5,8},{4,5,8,1},{5,8,1,4} and {8,1,4,10}.
The 4 maximum element of subarray of size 4 are: 8 8 8 10.


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

Что я уже пробовал:

using namespace std;
#include<iostream>
#include<algorithm>
int m,idx,ct=0;
void maxinwindow(int arr[], int start, int end)
{
    /*If the index of the maximum element in the previous window
    is between the indexes of next windows then no need to compare elements
    that were in previous window */
    if(idx>=start)
    {
        if(arr[idx]>=arr[end])
        {
        	if(arr[idx]==arr[end])
			{
        		idx=end;	
			}
            //ct++;
            m=arr[idx];
        }
        else
        {
            //ct++;
            m=arr[end];
            idx=end;
        }
    }
    else
    {
        if(arr[start]>=arr[start+1])
        {
            //ct++;
            m=arr[start];
        }
        else
        {
            //ct++;
            m=arr[start+1];
        }
        for(int k=start+2;k<=end;k++)
        {
            //ct++;
            if(arr[k]>=m)
            {
                m=arr[k];
                idx=k;
            }
        }
    }
}
int main()
{
    int arr[100000];
    int q;
    cin>>q;
    for(int i=1,size,ws;i<=q;i++)
    {
        m=0;ct=0;
        cin>>size;  //Array size
        cin>>ws;   //Window Size
        //Entering The Elements In The Array
        for(int j=1;j<=size;j++)
        {
            cin>>arr[j];
        }
        //Boundary Condition i.e. Windows size is equal to 1
        if(ws==1)
        {
            for(int j=1;j<=size;j++)
            {
                cout<<arr[j]<<" ";
            }
        }
        else
        {
            for(int k=1;k<=ws;k++)
            {
                //ct++;
                if(arr[k]>=m)
                {
                    m=arr[k];
                    idx=k;
                }
            }
            //ct--;
            cout<<m<<" ";           
            for(int k=2,j;k<=(size-(ws-1));k++)
            {
                j=(k+(ws-1));
                maxinwindow(arr,k,j);
                cout<<m<<" ";
            }
            cout<<endl;
        }
    }
}

CPallini

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

Shantanu Dwivedi

да, конечно.

Patrice T

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

CPallini

Я вижу (спасибо Патрис) он предназначен как упражнение на std::deque. Тогда почему (свежий ад) вы не используете std::deque?

Shantanu Dwivedi

я могу, но я хочу знать, что не так с этим алгоритмом.

Patrice T

Я просто нажимаю на крестик в правом верхнем углу, чтобы закрыть экран подписи.

CPallini

:-О

2 Ответов

Рейтинг:
1

CPallini

Легко обнаруживаемая ошибка в вашем коде выходит за рамки допустимого. arr массив:

Цитата:
int arr[10000];
инт вопрос;
cin>>q;
for(int i=1,size,ws;i<=q;i++)
{
m=0;ct=0;
cin>>size; //размер массива
cin>>ws; //размер окна
//Ввод Элементов В Массив
for(int j=1;j<=size;j++)
{
cin>>arr[j]; //<-- здесь код может неправильно получить доступ к arr[10000]
}

когда size = 10000 вы находитесь вне удачи.


Shantanu Dwivedi

этот предел упоминается в вопросе.

Maciej Los

Взгляните на размытый текст ;)

CPallini

Когда вы объявляете arr[10000], доступные элементы являются
arr[0], arr[1], ..., arr[9999]
Это C++, а не Visual Basic.

Shantanu Dwivedi

проблема все еще сохраняется.

CPallini

Затем появляется еще одна ошибка (или есть другие ошибки).
Самый разумный подход, который я могу видеть, это:
(1) реализовать (возможно, смертельно медленный) пуленепробиваемый алгоритм, либо используя std::deque, либо нет.
(2) генерировать большие наборы случайных входных данных и сравнивать результаты двух реализаций на таких наборах.
(3) освещенный несоответствиями, проверьте код, чтобы обнаружить ошибку(ы).

Maciej Los

Ястребиный глаз!

CPallini

Спасибо,
Кстати, запоздалого с Новым годом, Мацей!

Maciej Los

С Новым Годом, Пауло!

CPallini

Пауло? :-D
Спасибо.

Maciej Los

Ооопс....
Прости, Карло.
Вы должны признать, что это была очень интересная ошибка. Я перепутал твое имя с фамилией ;)
Еще раз прошу прощения...
Овации
Мацей

CPallini

Все в порядке. :большой палец вверх:

Рейтинг:
0

Patrice T

Цитата:
Я пробовал много тестовых случаев, но все еще не могу понять ошибку в коде.

Ваш код ведет себя не так, как вы ожидаете, или вы не понимаете, почему !

Существует почти универсальное решение: запускайте свой код на отладчике шаг за шагом, проверяйте переменные.
Отладчик здесь, чтобы показать вам, что делает ваш код, и ваша задача-сравнить с тем, что он должен делать.
В отладчике нет никакой магии, он не знает, что должен делать ваш код, он не находит ошибок, он просто помогает вам, показывая, что происходит. Когда код не делает того, что ожидается, вы близки к ошибке.
Чтобы увидеть, что делает ваш код: просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.

Отладчик - Википедия, свободная энциклопедия[^]

Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010 - YouTube[^]

1.11 — отладка программы (пошаговое выполнение и останова) | выучить C++[^]

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


Shantanu Dwivedi

я пытался отладить его с помощью IDE для многих тестовых случаев, и все они работают.