Codility, minimalna wartość bezwzględna sumy pary liczb

0

Zadanie z Codility:

Let A be a non-empty zero-indexed array consisting of N integers.

The abs sum of two for a pair of indices (P, Q) is the absolute value |A[P] + A[Q]|, for 0 ≤ P ≤ Q < N.

For example, the following array A:

A[0] = 1
A[1] = 4
A[2] = -3

has pairs of indices (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2).
The abs sum of two for the pair (0, 0) is A[0] + A[0] = |1 + 1| = 2.
The abs sum of two for the pair (0, 1) is A[0] + A[1] = |1 + 4| = 5.
The abs sum of two for the pair (0, 2) is A[0] + A[2] = |1 + (−3)| = 2.
The abs sum of two for the pair (1, 1) is A[1] + A[1] = |4 + 4| = 8.
The abs sum of two for the pair (1, 2) is A[1] + A[2] = |4 + (−3)| = 1.
The abs sum of two for the pair (2, 2) is A[2] + A[2] = |(−3) + (−3)| = 6.

Write a function:

int solution(vector<int> &A);

that, given a non-empty zero-indexed array A consisting of N integers, returns the minimal abs sum of two for any pair of indices in this array.

For example, given the following array A:

A[0] = 1
A[1] = 4
A[2] = -3

the function should return 1, as explained above.

Given array A:

A[0] = -8
A[1] = 4
A[2] = 5
A[3] =-10
A[4] = 3

the function should return |(−8) + 5| = 3.

Assume that:

    N is an integer within the range [1..100,000];
    each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

Complexity:

    expected worst-case time complexity is O(N*log(N));
    expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.
Copyright 2009–2015 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Moje rozwiazanie:

using namespace std;
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
int solution(vector<int> &A) 
{
    // write your code in C++11
    if (A.size() == 0)
    {
        return 0;
    }
    else if (A.size() == 1)
    {
        return A[0];
    }
    else
    {
        int minimum{ numeric_limits<int>::max() };
        int current_sum{ 0 };
        for (auto beg{ cbegin(A) }, end{ cend(A) }; beg != end; ++beg)
        {

            auto tmp_beg{ beg };
            auto tmp_end{ next(tmp_beg) };
            while (tmp_end != end)
            {
                current_sum = abs(*tmp_beg + *tmp_end);
                if (current_sum < minimum)
                {
                    minimum = current_sum;
                }
                ++tmp_end;
            }

        }
        return minimum;
    }

}

Dostaje blad, mowiacy:
The following issues have been detected: wrong answers, timeout errors.

For example, for the input [1000000000] the solution returned a wrong answer (got 1000000000 expected 2000000000).

Ja sie kura pytam, jak moze z jednego wejscia 1'000'000'000 spodziewac sie 2'000'000'000? Jak to kuwa mozliwe?

Jesli ktos chce ten kod wrzucic na Codility to trzeba zmienic ten powyzszy kod na ten (to jest ten sam kod tylko inicjalizacja jest przed C++11 lub C++14):

using namespace std;
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
int solution(vector<int> &A) 
{
    // write your code in C++11
    if (A.size() == 0)
    {
        return 0;
    }
    else if (A.size() == 1)
    {
        return A[0];
    }
    else
    {
        int minimum{ numeric_limits<int>::max() };
        int current_sum{ 0 };
        for (auto beg = A.cbegin(), end = A.cend(); beg != end; ++beg)
        {

            auto tmp_beg = beg ;
            auto tmp_end = next(tmp_beg) ;
            while (tmp_end != end)
            {
                current_sum = abs(*tmp_beg + *tmp_end);
                if (current_sum < minimum)
                {
                    minimum = current_sum;
                }
                ++tmp_end;
            }

        }
        return minimum;
    }

}
1

Bo geniuszu nie czytasz treści. Gdzie niby ci napisali że jak jest tylko jedna liczba to wynikiem jest ta liczba? WTF? Masz wyraźnie napisanie że indeksy NIE MUSZĄ być unikalne i że masz zawsze brać 2 liczby, tzn para (0,0) czyli tab[0]+tab[0] jest poprawnym rozwiązaniem. A jak ty niby chcesz dla jednego wejscia [X] uzyskać wynik [X] skoro masz brać 2 liczby i jedyne możliwe rozwiązanie to X+X?

edit: No i jeszcze ciśniesz O(n2) kiedy w zadaniu wyraźnie napisali O(nlogn). Ty w ogóle przeczytałeś treść? o_O

0

Miałem wolne pół godzinki to naskrobałem, bo zadanie ciekawe. Napisane w Javie, ale chodzi raczej o sposób. Klasy dodane dla trochę większej czytelności. Można poprawić parę rzeczy i upchnąć bardziej, ale reszta jest ok.

Ilość iteracji pętli to (n*(n+1))/2. Reszta, czyli wyliczanie następnej pary i obliczenia to O(1).

// Ciach bo zle rozwiazanie

0

http://ideone.com/WgeB5n

A coś takiego ?

0

"Podpowiedź":

  • liczby trzeba zamienić na pary (liczba, oryginalny indeks).
  • później posortować,
  • później skanować od lewej i prawej jednocześnie,

Można wybrać sortowanie przez złączanie, czyli mergesort. Sortowanie to ma stałą złożoność liniowologarytmiczną (czyli wymaganą w zadaniu). W C++ typowo stable_sort jest sortowaniem przez złączanie.

1

Posortowałbym po wartości bezwzględnej i potem wystarczy patrzeć na pary elementów sąsiednich (+ przypadek 2x ten sam element).

@Artur77: Gdyby nie było elementów ujemnych, to wystarczy brać parę najmniejszych elementów. Co w tym przypadku oznacza 2x najmniejszy element. Natomiast w momencie gdy mamy liczby ujemne, to może być tak, że para (dodatnia + ujemna) mają mniejszą sumę.

-2 + 4 < 4 + 4

Ale zauważ, że cechą charakterystyczną takiej pary jest to, że ich wartości bezwzględne są blisko siebie.

Mając jakąś tablicę z elementami

15 -1 -12 4 56 22

posortuj po wartości bezwględnej

-1 4 -12 15 22 56

Teraz wystarczy patrzeć na sumę (a właściwie wartość bezwględną sumy) elementów sąsiednich:

(-1, -1), (-1, 4), (4, -12), (-12, 15), (15, 22), (22, 56)

Najmniejsza suma będzie wśród nich.

Jako że posortowałeś liczby, to zgubiłeś ich pierwotne indeksy. Dlatego przed sortowaniem trzeba zrobić parę <pierwotny_indeks, wartosc>, potem sortować po wartości, a po odnalezieniu pary wypisać pierwotne indeksy.

0

Wielkie podziekowania dla @twonek, dzieki za wziecie Twojego czasu i wyjasnienie mi tego problemu. Ponizej jest poprawny kod. Jeszcze raz, wielkie dzieki @twonek !

#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

template<class T>
struct less_abs
{
    bool operator()(T left, T right)
    {
        return abs(left) < abs(right);
    }
};

template<class Result,class Cont>
Result make_pairs(const Cont& container)
{
    Result res;
    res.push_back(make_pair(*container.cbegin(), *container.cbegin()));//first pair always from index [0]
    for (auto beg{ cbegin(container) }, real_end{ prev(cend(container)) }; beg != real_end; ++beg)
    {

        res.push_back(make_pair(*beg, *next(beg)));
    }
    return res;
}
int solution(vector<int> &A) 
{
    // write your code in C++11

        sort(begin(A), end(A), less_abs<int>());
        int minimum{ numeric_limits<int>::max() };
        int current_sum{ 0 };
        auto container_with_pairs = make_pairs<vector<pair<int,int>> >(A);
        for (auto beg{ cbegin(container_with_pairs) }, end{ cend(container_with_pairs) };
                                                                                        beg != end;
                                                                                                    ++beg)
        {
            current_sum = abs((*beg).first + (*beg).second);
            if (current_sum < minimum)
            {
                minimum = current_sum;
            }

        }
        return minimum;
} 
3

Wydaje mi się, że można dużo prościej i krócej (pisane na kolanie, nie kompilowane):

int solution(vector<int>& A)
{
    sort(begin(A), end(A), [](int a, int b) { return abs(a) < abs(b); });
    int minimum = abs(A[0] + A[0]);
    for (size_t i = 0; i < A.size()-1; ++i)
        minimum = min(minimum, abs(A[i] + A[i+1]);

    return minimum;
}
0

Uczę się STL, czy ktoś kto się zna może mi ocenić rozwiązanie?

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include "math.h"
#include <map>

int solution(std::vector<int>& A)
{
    int size = A.size();

    if (size == 0)
        return -1;

    else if (size == 1)
        return 2 * A[0];

    else
    {
        std::map <int, int> m;

        for (auto i = A.begin(); i != A.end(); ++i)     
            m[abs(*i)] = *i;

        int candidate = INT_MIN;
        int result = INT_MAX;

        for (auto i = m.begin(); i != m.end(); ++i)
        {
            if (std::next(i) != m.end())
                candidate = abs(i->second + std::next(i)->second);

            result = result > candidate ? candidate : result;
        }

        return result;
    }

}

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0