OI Pionek [Rozwiazanie]

0

Probuje rozwiazac zadanie z zeszłorocznej olimpiady
https://oi.edu.pl/static/attachment/20171016/piozad.pdf
Jednak nie mogę wpaść na rozwiązanie , czy trzeba zastosować tu programowanie dynamiczne ?
Prosilbym o wyjasnienie

0

Zaryzykuj "Greedy Algorithm" - czyli w każdym ruchu szukanie maksymalnej odległości. W przykładzie da ciągi:
3,1 - > 2, -2, lub (zależy od kolejności - bez znaczenia)
-3, 1 -> -2, -2
Łącznie z 0,2 -> 3, 1 -> 2, -2
Odległości te są najdalsze(ewentualnie jeszcze: 0, 2 -> -3, 1 -> -2, -2).
Złożoność czasowa jest O(n^2), także szału nie ma, ale punkt zaczepienia jest.

0
  1. Zauważ, że nie jest istotna kolejność wektorów jaką weźmiemy, bo zawsze po przejściu nimi otrzymamy taki sam dystans.
  2. By dojść "najdalej" wystarczy, że weźmiemy wszystkie wektory, które "nie zawracają".

Więc ja bym podzielił sobie na 4 koszyczki:

  • północ
  • południe
  • wschód
  • zachód

Oczywiście jeden wektor może wylądować w więcej niż jednym koszyczku. Maksymalnie będzie lądował w 3 (jak jest poziomy/pionowy). Następnie liczymy trasę w każdym z koszyczków z osobna i wybieramy największy.

W ten sposób jesteśmy w stanie zrobić to w czasie O(n).

0
hauleth napisał(a):
  1. By dojść "najdalej" wystarczy, że weźmiemy wszystkie wektory, które "nie zawracają".

Mógłbyś to trochę rozwinąć, "wektory, które nie zawracają"? W momencie wyjścia od zera, żaden wektor nie zawraca.

0

@lion137: przykład w Ruscie:

use std::ops::AddAssign;
use std::str::FromStr;
use std::io::{self, BufRead};

#[derive(Copy, Clone, Debug, PartialEq, Eq, Default)]
struct Point(i64, i64);

impl Point {
    fn new() -> Self { Default::default() }

    fn len(self) -> i64 { self.0 * self.0 + self.1 * self.1 }

    fn is_north(&self) -> bool { self.0 >= 0 }
    fn is_east(&self) -> bool { self.1 >= 0 }
}

impl AddAssign for Point {
    fn add_assign(&mut self, rhs: Self) {
        self.0 += rhs.0;
        self.1 += rhs.1;
    }
}

impl FromStr for Point {
    type Err = ();

    fn from_str(s: &str) -> Result<Point, ()> {
        let mut iter = s.split_whitespace();
        let x = iter.next().unwrap().parse().unwrap();
        let y = iter.next().unwrap().parse().unwrap();

        Ok(Point(x, y))
    }
}

fn main() {
    let stdin = io::stdin();
    let input = stdin.lock();

    let mut north = Point::new();
    let mut west = Point::new();
    let mut east = Point::new();
    let mut south = Point::new();

    for point in input.lines().map(Result::unwrap).skip(1).map(|s| s.parse::<Point>().unwrap()) {
        if point.is_north() { north += point } else { south += point }
        if point.is_east() { east += point } else { west += point }
    }

    let lengths = [
        north.len(),
        west.len(),
        east.len(),
        south.len()
    ];
    let max = lengths.into_iter().max().unwrap();

    println!("{}", max);
}

Jak widać, ścieżki można sumować już w trakcie ich wczytywania, więc listę przeglądasz tylko raz, co daje Ci złożoność O(n).

EDIT:

Zauważyłem problem jak mamy trasy pionowe/poziome a nie na skos. Jednak da się to rozwiązać poprzez "skoszyczkowanie" tras pion/poziom osobno i "skośnych" osobno, a następnie poszukania największej z sum. Pracy z poprawieniem kodu wyżej dużo nie będzie, więc zostawię to w gestii czytelników.

1

@hauleth: Koszyczkowanie po kierunkach świata nie zadziała:
3
-4 4
2 1
-1 -2
Na oko powinno dać 32, Twój kod daje 29.

0

Hej,
ja mam trochę inne rozważania:

  1. można rozważać dwa koszyczki, jeden z punktami (x, y), drugi z punktami (-x, -y), zakłądamy, że x, y są nieujemne.
  2. jeżeli punkt (x, y) występuje dwa razy, to można wziąć zamiast niego (2x, 2y)
  3. jeżeli mamy punkt z pierwszego koszyczka o współrzędnych nieujemnych, to zamiast rozpatrywać punkty (x, y), (z, w) można rozpatrzyć punkty (x+z, y+w)
  4. dla punktów o przeciwnych znakach współprzędnych robimy iterację po kolei (dla obu koszyczków osobno), jeżeli zwiększa odległość zostawiamy, jeżeli zmniejsza odrzucamy.

Dla tych trzech podanych testów to zadziała, ale jeżeli ktoś poda jakiś fajny przykład, którego ten opis algorytmu nie optymalizuje, to byłoby fajnie (szczególnie mam wątpliwości, jeżeli chodzi o punkt 4).

1
hurgadion napisał(a):

Hej,
ja mam trochę inne rozważania:

  1. można rozważać dwa koszyczki, jeden z punktami (x, y), drugi z punktami (-x, -y), zakłądamy, że x, y są nieujemne.
  2. jeżeli punkt (x, y) występuje dwa razy, to można wziąć zamiast niego (2x, 2y)
  3. jeżeli mamy punkt z pierwszego koszyczka o współrzędnych nieujemnych, to zamiast rozpatrywać punkty (x, y), (z, w) można rozpatrzyć punkty (x+z, y+w)
  4. dla punktów o przeciwnych znakach współprzędnych robimy iterację po kolei (dla obu koszyczków osobno), jeżeli zwiększa odległość zostawiamy, jeżeli zmniejsza odrzucamy.

Dla tych trzech podanych testów to zadziała, ale jeżeli ktoś poda jakiś fajny przykład, którego ten opis algorytmu nie optymalizuje, to byłoby fajnie (szczególnie mam wątpliwości, jeżeli chodzi o punkt 4).

Punkt 2 jak najbardziej ok, bo wydłuży nam się wektor N-krotnie.
Punkt 4 - wydaje mi się, ze trzeba patrzeć na wartość cosinusa kąta między parą wektorów (ux,uy) i (vx,vy), czyli w zasadzie na znak iloczynu skalarnego u i v. To dlatego, że jak graficznie dodamy wektory u i v, to długość wynikowego będzie sqrt( (u^2 + v^2 + 2uvcos(u,v) ) ) , więc jeśli iloczyn skalarny jest >=0 to zwiększy nam długość wynikowego wektora.

0

To chyba nie jest takie proste. Przykład:

a = [1, 4], b = [1, -1], c = [2, 1] 

Kolejność dodawania wektorów nie ma znaczenia. Ale jeżeli weźmiemy a, b, c, to kąt między a, b jest ostry, a jeżeli weźmiemy c, b, a, to kąt między c, b jest rozwarty, więc cos tego kąta jest mniejszy od zera. Suma kwadratów współrzędnych wektora a+b+c jest równa 32. Natomiast suma kwadratów współrzędnych wektora a+c jest równa 34, więc to takie proste nie jest. Przydałyby się jeszcze ze trzy bardziej skomplikowane Case Testy :)

0
hurgadion napisał(a):

To chyba nie jest takie proste. Przykład:

a = [1, 4], b = [1, -1], c = [2, 1] 

Kolejność dodawania wektorów nie ma znaczenia. Ale jeżeli weźmiemy a, b, c, to kąt między a, b jest ostry, a jeżeli weźmiemy c, b, a, to kąt między c, b jest rozwarty, więc cos tego kąta jest mniejszy od zera. Suma kwadratów współrzędnych wektora a+b+c jest równa 32. Natomiast suma kwadratów współrzędnych wektora a+c jest równa 34, więc to takie proste nie jest. Przydałyby się jeszcze ze trzy bardziej skomplikowane Case Testy :)

Hmm, między a i b wydaje się być 120 stopni.
https://www.wolframalpha.com/input/?i=angle+between+vectors+%7B1,4%7D+and+%7B1,-1%7D

A między c i b 71 z hakiem:
https://www.wolframalpha.com/input/?i=angle+between+vectors+%7B2,1%7D+and+%7B1,-1%7D

Jak się ogarnę z pracą to będzie czas podumać nad tym :-)

0

Implementacja w pythonie tego podejścia z iloczynem skalarnym (bez normalizacji wejścia, tj. zamiany wektorów (1,1), (1,1), (1,1) na (3,3) ) i bez analizy czy jest poprawne ;)

#!/usr/bin/env python
def scalar_product(v, u):
    return u[0] * v[0] + u[1] * v[1]


def add_vectors(u, v):
    return u[0] + v[0], u[1] + v[1]


def solve_pio(input_data):
    candidate1 = input_data[0]
    candidate2 = (0, 0)

    for v in input_data[1:]:
        candidate1 = add_vectors(candidate1, v) if scalar_product(candidate1, v) >= 0 else candidate1
        candidate2 = add_vectors(candidate2, v) if scalar_product(candidate2, v) >= 0 else candidate2

    return max(scalar_product(candidate1, candidate1), scalar_product(candidate2, candidate2))


# test data
pio_input_data = [(2, -2), (-2, -2), (0, 2), (3, 1), (-3, 1)]
afish_input_data = [(-4, 4), (2, 1), (-1, -2)]
hurgadion_input_data = [(1, 4), (1, -1), (2, 1)]

print("Solution: {}".format(solve_pio(afish_input_data)))
print("Solution: {}".format(solve_pio(pio_input_data)))
print("Solution: {}".format(solve_pio(hurgadion_input_data)))

edited: Powyższe nie jest poprawne. Wystarczy (2,1), (-1,-2), (-4,4) (czyli permutację jednego z przypadków) i się wywali. Sortowanie wejścia względem długości wektora (od największego do najmniejszego) poprawia sytuację, ale wtedy robi się O(nlogn) i pewnie jakiś kolejny przypadek można znaleźć.

1

Ja bym podszedł do tego tak:

  1. Posortować według kierunków - wyjdzie cykliczny kontener - sortowanie kubełkowe da tu w patynce złożoność liniową.
  2. wybrać 8 kierunków początkowych i dla każdego
  • wybrać wszystko co jest zgodne z wybranym kierunkiem, czyli wektory z określonego zakresu kontenera cyklicznego
  • poszerzyć granice o wektory w prawo i/lub w lewo i na odwrót - kolejność ma znaczenie, więc to wygeneruje dwa rozwiązania
  1. z tych 16 rozwiązań wybrać to co najdłuższe.

Pytanie jak wykazać, że to da prawidłowe rozwiązanie :/, zadanie zdecydowanie nie jest łatwe.

0

Jak dla mnie trzeba analizować cztery ćwiartki, dla każdej z nich przesortować wektory po kącie względem półprostej zawierającej wersor wchodzący do danej ćwiartki zaczepiony w środku układu współrzędnych, a potem brać zachłannie. Dowodu nie mam, ale intuicyjnie wydaje się poprawne. Można też pokazać, że branie wszystkich wektorów z danej ćwiartki, z danej półpłaszczyzny lub z danej trójki ćwiartek nie jest poprawne.

0

@yarel: no, generalnie nieźle to działa, ale znalazłem zestaw danych, w których kolejność ma znaczenie więc coś nie tak...

a1 = [(1, 1), (-1, -4), (1, 0), (1, -1)]
a2 = [(1, 1), (1, 0), (1, -1), (-1, -4)]
0

Takie demo pokzujące czemu to jest trudne zadanie:
Zrobione na https://www.math10.com/en/geometry/geogebra/geogebra.html
geogebra-export.png

AB to to, co już wybraliśmy do najdłuższego wektora.
BC i BD to kandydaci, którzy nie powiększają odległości od środka.
BE to suma BC i BD, która już zwiększa odległość od środka.

Wygląda na to, że w ten sposób sam sobie udowodniłem, że moja koncepcja na rozwiązanie jest błędna :).

1

Pierwsza obserwacja - sortować po kierunku trzeba. Dlaczego? Bo 1) po czymś sortować trzeba (bo liczba wektorów, n <= 200000, więc oczekiwana złożoność to O(n log n), tak to bywa na OI) 2) jeśli po czymkolwiek sortować, to tylko po kącie.

Taki kod jest poprawny (sprawdzony na wszystkich testach olimpiady), ale większe testy wykonują się koło minuty (z 120 razy za długo):

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdint>
 
template <typename T>
T sqlen(T x, T y) {
    return x*x+y*y;
}
 
template <typename T>
T difflen(std::pair<T, T> a, std::pair<T, T> b)
{
    T x = a.first - b.first;
    T y = a.second - b.second;
    return sqlen(x, y);
}
 
template <typename T>
T maximize(std::vector<std::pair<T, T>> const& tab)
{
    int n = tab.size();
    std::vector<std::pair<T, T>> prefix(n+1, std::make_pair(0,0));

    for (int i = 1; i <= n; ++i) {
        prefix[i].first  = prefix[i-1].first  + tab[i-1].first;
        prefix[i].second = prefix[i-1].second + tab[i-1].second;
    } 

    T max = -1;
    for (int i = 0; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            auto x = prefix[i].first  - prefix[j].first;
            auto y = prefix[i].second - prefix[j].second;
            auto len = sqlen(x, y);
            if (len > max) {
                max = len;
//                if (abs(atanv(tab[i])-atanv(tab[j])) > 1e-6)
//                std::cerr << i << " " << j << " " << atanv(tab[i]) << " " << atanv(tab[j]) << "\n"; 
            }
        }
    }
    return max;
}


int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);
    int n;

    std::cin >> n;
    std::vector<std::pair<int64_t, int64_t>> tab(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> tab[i].first >> tab[i].second;
    }

    std::sort(std::begin(tab), std::end(tab),
            [](auto one, auto two) {
                return atan2(one.first, one.second) < atan2(two.first, two.second);
                }
            );

    int64_t max = maximize(tab);

    std::sort(std::begin(tab), std::end(tab),
            [](auto one, auto two) {
                return atan2(-one.first, -one.second) < atan2(-two.first, -two.second);
                }
            );
    max = std::max(maximize(tab), max);
    std::cout << max << "\n";
}

Wnosek z tego jest taki:

po posortowaniu, trzeba sprytniej wybierać zakresy, które chcemy zsumować.

0

Mam jeszcze taki kod:

def max_sol(data):
    ap = [x for x in data if x[0] >= 0]
    am = [x for x in data if x[0] <= 0]
    bp = [x for x in data if x[1] >= 0]
    bm = [x for x in data if x[1] <= 0]
    a1 = sum([x[0] for x in ap])**2 + sum([x[1] for x in ap])**2
    a2 = sum([x[0] for x in am])**2 + sum([x[1] for x in am])**2
    a3 = sum([x[0] for x in bp])**2 + sum([x[1] for x in bp])**2
    a4 = sum([x[0] for x in bm])**2 + sum([x[1] for x in bm])**2
    return max(a1, a2, a3, a4)

Trzy testy przechodzi, wykłada się na teście @Afish

0

Na moje oko zamiatanie pyknie. Sortuję wektory po kątach, następnie techniką dwóch wskaźników: zaczynam lewym wskaźnikiem od dowolnego i dodaję po kolei prawym wskaźnikiem wszystkie wektory z półpłaszczyzny w prawo, aktualizując najlepszy wynik. Potem przesuwam usuwam skrajny lewy wektor, przesuwam wskaźnik lewy wskaźnik i znowu próbuję dodać. Jak lewy wskaźnik zrobi kółko, to potem usuwam prawym wskaźnikiem wszystkie wektory (ciągle aktualizując wynik). Puściłem to na jakiejś paczce testów z OI i przeszło, czasowo wygląda na nlogn, więc na oko jest dobrze.

0

Ma ktoś linka do sprawdzarki? Jakoś nie mogę namierzyć.

3

Paczka z testami

1

Ok, zacznijmy od tego, że po posortowaniu podzbiór wektorów, który daje optymalny wynik, będą tworzyły wektory tworzące jakiś pojedynczy podciąg w liście, niepodzielony żadnymi innymi. Czyli tak naprawdę szukamy podciągu, który da optymalny wynik :) A taki podciąg można by na dobrą sprawę wyznaczyć iterując najwyżej 2 razy 2 indeksami po liście wektorów, więc w tej części dostaniemy O(n). Czyli całość zamknie się w O(nlogn), przy czym część liniowa będzie miała chyba większą stałą.

Ja bym spróbował w ten sposób:

1. posortuj listę wektorów V rozmiaru n po kącie względem osi np. OX
2. niech W = V[0], max = len(W), p = 0, k = 0, p_mod = 0, k_mod = 0
3. dopóki k < n:
  3.1. niech p_next = p + 1, p_mod_next = (p + 1) mod n
  3.2. jeżeli len(W + V[p_mod_next]) > len(W) oraz p < k + n to:
    3.2.1. W = W + V[p_mod_next]
    3.2.2. p = p_next, p_mod = p_mod_next 
  3.2. WPP:
    3.2.1. W = W - V[k_mod]
    3.2.2. k = k + 1, k_mod = k mod n
  3.3 jeżeli len(W) > max to:
    3.3.1. max = len(W)
4. zwróć max

Wydaje mi się, że w ten sposób na pewno sprawdzisz w pewnym momencie optymalny podciąg wektorów nie za dużym kosztem :)

0

To daje AC, jeżeli komuś chce się rozkminiać kod, to służę pomocą, ale jest to dokładnie ten sposób, który opisałem w poprzednim poście (dwa wskaźniki i sortowanie kątowe). Działa w najnowszym VS i w GCC używanym przez testerkę, standard pewnie C++11.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <cmath>
#include <numeric>
using namespace std;

namespace stanczyk {
	typedef int INT;
	typedef long long LL;
	typedef long double DOUBLE;

	const INT INF = 1000000001;
	constexpr const INT EPS_PRECISION = -9;
	const DOUBLE EPS = pow((DOUBLE)10.0, (DOUBLE)EPS_PRECISION);

	typedef vector<INT> VI;
}
using namespace stanczyk;



#define FOR(x, b, e) for (int x = b; x <= (e); ++x)
#define FORD(x, b, e) for (int x = b; x >= (e); --x)
#define REP(x, n) for (int x = 0; x<(n); ++x)
#ifdef _MSC_VER 
#define VAR(v, n) decltype(n) v = (n)
#else
#define VAR(v, n) __typeof(n) v = (n)
#endif
#define ALL(c) c.begin(), c.end()
#define SIZE(x) (int)x.size()
#define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i)
#define PB push_back
#define ST first
#define ND second
#define PF push_front
#define MP make_pair


namespace stanczyk {

	template<typename T = DOUBLE, typename U = DOUBLE>
	inline bool IsZero(T x, U epsilon) {
		return x >= -epsilon && x <= epsilon;
	}

	template<typename T = DOUBLE>
	inline bool IsZero(T x) {
		return x == 0 || IsZero(x, (T)EPS);
	}

	
	template<typename T = INT, typename U = char>
	struct POINT {
		T x, y;
		U data;
		typedef T coordinate_type;
		typedef U data_type;
		
		
		
		POINT(T x = 0, T y = 0, U data = U()) : x(x), y(y), data(data) { }
		POINT(const POINT<T, U>& other) : x(other.x), y(other.y), data(other.data) {}

		
		template<typename W, typename X>
		operator POINT<W, X>() const {
			POINT<W, X> p;
			p.x = x;
			p.y = y;
			p.data = data;
			return p;
		}

		
		bool operator ==(const POINT<T, U> & a) const {
			return IsZero<T>(a.x - x) && IsZero<T>(a.y - y);
		}

		bool operator != (const POINT<T, U> &a) const {
			return !(*this == a);
		}

		bool operator <(const POINT<T, U>&a) const {
			return IsZero(this->x - a.x) ? this->y < a.y : this->x < a.x;
		}

		bool operator <=(const POINT<T, U>&a) const {
			return OrdXY(this, &a);
		}
	};

	
	template<typename T = POINT<DOUBLE>, typename U = DOUBLE>
	inline U Det(const T& a, const T& b, const T& c) {
		return U(b.x - a.x)*U(c.y - a.y) - U(b.y - a.y)*U(c.x - a.x);
	}

	
	template<typename T = POINT<DOUBLE>, typename U = DOUBLE>
	inline U Det(const T& a, const T& b, const T& c, const T& d) {
		return U(b.x - a.x)*U(c.y - d.y) - U(b.y - a.y)*U(c.x - d.x);
	}

	
	template<typename T>
	bool OrdXY(T * a, T * b) {
		return IsZero(a->x - b->x) ? (a->y < b->y || IsZero(a->y - b->y)) : a->x < b->x;
	}

	
	template<typename T>
	bool OrdYX(T * a, T * b) {
		return IsZero(a->y - b->y) ? (a->x < b->x || IsZero(a->x - b->x)) : a->y < b->y;
	}

	
	
	template<typename T>
	bool OrdX(T & a, T & b) {
		return a.x < b.x;
	}

	
	
	template<typename T>
	bool OrdY(T & a, T & b) {
		return a.y < b.y;
	}
}


namespace stanczyk {
	template<typename T = POINT<INT>, typename U = LL>
	struct AngleSort {
		
		T* _centralPoint;

		
		bool operator ()(const T *a, const T *b) const {
			INT w = Det((*_centralPoint), (*a), (*b));
			if (w == 0) return abs(_centralPoint->x - a->x) + abs(_centralPoint->y - a->y) <
				abs(_centralPoint->x - b->x) + abs(_centralPoint->y - b->y);
			return w > 0;
		}

vector<T*> Sort(vector<T>& points, T& start, T& end) {
	_centralPoint = &start;
	vector<T*> left, right;
	FOREACH(it, points) {
		U determinant = Det(start, end, (*it));
		(determinant > 0 || (determinant == 0 &&
			(start.x == it->x ? start.y < it->y : start.x < it->x))) ? left.PB(&*it) :
			right.PB(&*it);
	}
	sort(ALL(left), *this);
	sort(ALL(right), *this);
	FOREACH(it, right) left.PB(*it);
	return left;
}
	};
}


using namespace stanczyk;

typedef POINT<LL> P;

LL getResult(LL x, LL y) {
	return x * x + y * y;
}

LL calculateSweep(vector<P>& points, P& w) {
	AngleSort<P, LL> sort;
	P zero = P(0, 0);
	vector<P*> sorted = sort.Sort(points, zero, w);

	if (points.size() == 0) {
		return 0;
	}

	LL x, y;
	x = sorted[0]->x;
	y = sorted[0]->y;
	LL best = 0;

	int left = 0;
	int right = 1 % points.size();

	while (left < points.size()) {
		best = max(best, getResult(x, y));

		while (right != left){
			double det = Det(zero, *sorted[left], *sorted[right]);
			if (det < 0)break;
			if (det == 0) {
				if (sorted[left]->x < 0 && sorted[right]->x > 0)break;
				if (sorted[left]->y < 0 && sorted[right]->y > 0)break;
				if (sorted[left]->x > 0 && sorted[right]->x < 0)break;
				if (sorted[left]->x > 0 && sorted[right]->x < 0)break;
			}
			
			x += sorted[right]->x;
			y += sorted[right]->y;
			best = max(best, getResult(x, y));

			right++;
			right %= points.size();
		}

		x -= sorted[left]->x;
		y -= sorted[left]->y;
		left++;
	}

	left = 0;

	while (left < right && left < points.size()) {

		best = max(best, getResult(x, y));
		x -= sorted[left]->x;
		y -= sorted[left]->y;
		left++;
	}
	best = max(best, getResult(x, y));

	return best;
}

int main() {
	int n;
	scanf("%d", &n);

	vector<P> points;
	for (int i = 0;i < n;++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		P p(x, y);
		if (x != 0 || y != 0) {
			points.push_back(p);
		}
	}

	P w = P(-1, 1);
	LL best = calculateSweep(points, w);
	w = P(1, -1);
	best = max(best, calculateSweep(points, w));

	printf("%lld", best);

	return 0;
}


0

Ja zrobiłem dość prosto, cztery ćwiartki dają cztery wektory, które są kandydatami, potem do każdego wektora kandydata dodajemy wektory z sąsiednich ćwiartek, które zwiększają jego długość. Na końcu wybieramy najdłuższego kandydata. W rezultacie algorytm ma złożoność O(n).

const test = [[2, -2], [-2, -2], [0, 2], [3, 1], [-3, 1]];

const x = 0;

const y = 1;

console.log(Pionek(test));

function Pionek(A) {
  var cw = [[0,0], [0,0], [0,0], [0,0]];
 
  A.forEach(function (vector) {
    //pierwsza ćwiartka
    cw[0] = vectorSum(function () {
      return vector[x] >= 0 && vector[y] >= 0;
    }, vector, cw[0]);
    //druga ćwiartka
    cw[1] = vectorSum(function () {
      return vector[x] <= 0 && vector[y] >= 0;
    }, vector, cw[1]);
    //trzecia
    cw[2] = vectorSum(function () {
      return vector[x] <= 0 && vector[y] <= 0;
    }, vector, cw[2]);
    //czwarta
    cw[3] = vectorSum(function () {
      return vector[x] >= 0 && vector[y] <= 0;
    }, vector, cw[3]);
  });

  A.forEach(function (vector) {
    //sąsiedzi pierwszej
    cw[0] = vectorAdd(
      function () {
        return (vector[x] < 0 && vector[y] > 0) || (vector[x] > 0 && vector[y] < 0);
      }, vector, cw[0]);
    //sąsiedzi drugiej
    cw[1] = vectorAdd(
      function () {
        return (vector[x] > 0 && vector[y] > 0) || (vector[x] < 0 && vector[y] < 0);
      }, vector, cw[1]);
    //sąsiedzi trzeciej
    cw[2] = vectorAdd(
      function () {
        return (vector[x] < 0 && vector[y] > 0) || (vector[x] > 0 && vector[y] < 0);
      }, vector, cw[2]);
    //sąsiedzi czwartej
    cw[3] = vectorAdd(
      function () {
        return (vector[x] < 0 && vector[y] < 0) || (vector[x] > 0 && vector[y] > 0);
      }, vector, cw[3]);
  });
  var max = 0;

  cw.forEach(function (v) {
    if (vectorAbs(v) > max) {
      max = vectorAbs(v);
    }
  });
  return max;
}

function vectorSum(selector, vector, sumVector) {
  var result = [0, 0];
  if (selector()) {
    result[x] = vector[x] + sumVector[x];
    result[y] = vector[y] + sumVector[y];
    return result;
  }
  return sumVector;
}

function vectorAdd(selector, vector, sumVector) {
  var result = [0, 0];
  if (selector()) {
    if (isLonger(vector, sumVector)) {
      result[x] = vector[x] + sumVector[x];
      result[y] = vector[y] + sumVector[y];
      return result;
    }
  }
  return sumVector;
}

function vectorAbs(v) {
  return (v[x] * v[x] + v[y] *v [y]);
}

function isLonger(v, s) {
  return vectorAbs(s) < vectorAbs([v[x] + s[x], v[y] + s[y]]);
}
0
cs napisał(a):

Ja zrobiłem dość prosto, cztery ćwiartki dają cztery wektory, które są kandydatami, potem do każdego wektora kandydata dodajemy wektory z sąsiednich ćwiartek, które zwiększają jego długość. Na końcu wybieramy najdłuższego kandydata. W rezultacie algorytm ma złożoność O(n).

Trochę średnio - weźmy taki przypadek:
[100,1] , [1, 100], [-1, 100], [-100, 1]
Na pierwszy rzut oka widać, że najkorzystniej będzie, jeśli dodasz jedynie wektory 1,2,3 lub 2,3,4, bo 1 i 4 niemal się zerują a 2 i 3 mają niemal identyczny kierunek, niemal wzdłuż osi OY. A Twoje rozwiązanie bierze ćwiartki w całości, więc albo weźmie wszystko, albo 1,2, albo 3,4

0
superdurszlak napisał(a):

Ok, zacznijmy od tego, że po posortowaniu podzbiór wektorów, który daje optymalny wynik, będą tworzyły wektory tworzące jakiś pojedynczy podciąg w liście, niepodzielony żadnymi innymi. Czyli tak naprawdę szukamy podciągu, który da optymalny wynik :) A taki podciąg można by na dobrą sprawę wyznaczyć iterując najwyżej 2 razy 2 indeksami po liście wektorów, więc w tej części dostaniemy O(n). Czyli całość zamknie się w O(nlogn), przy czym część liniowa będzie miała chyba większą stałą.

Ja bym spróbował w ten sposób:

1. posortuj listę wektorów V rozmiaru n po kącie względem osi np. OX
2. niech W = V[0], max = len(W), p = 0, k = 0, p_mod = 0, k_mod = 0
3. dopóki k < n:
  3.1. niech p_next = p + 1, p_mod_next = (p + 1) mod n
  3.2. jeżeli len(W + V[p_mod_next]) > len(W) oraz p < k + n to:
    3.2.1. W = W + V[p_mod_next]
    3.2.2. p = p_next, p_mod = p_mod_next 
  3.2. WPP:
    3.2.1. W = W - V[k_mod]
    3.2.2. k = k + 1, k_mod = k mod n
  3.3 jeżeli len(W) > max to:
    3.3.1. max = len(W)
4. zwróć max

Wydaje mi się, że w ten sposób na pewno sprawdzisz w pewnym momencie optymalny podciąg wektorów nie za dużym kosztem :)

from math import atan2
import glob, os


def norm(v: list):
    return sum([x ** 2 for x in v])


def find_opt(V: list):
    V = sorted(V, key=lambda x: atan2(*x))
    n = len(V)
    W = V[0]
    p = k = k_mod = 0
    # Kandydatem na max jest najpierw najdłuższy wektor - przez jakiś bug szukajka nie sprawdza pojedynczych wektorów
    m = max([norm(x) for x in V])
    # szukajka
    while k < n:
        p_next = p + 1
        p_mod = p_next % n
        W_next = vec_add(W, V[p_mod])
        if norm(W_next) >= norm(W) and p_next < (k + n):
            W = W_next
            p = p_next
        else:
            W = vec_sub(W, V[k_mod])
            k = k + 1
            k_mod = k % n
        m_next = norm(W)
        if m_next > m:
            m = m_next
    return m


def vec_add(x: list, y: list):
    return [z[0] + z[1] for z in zip(x, y)]


def vec_sub(x: list, y: list):
    return [z[0] - z[1] for z in zip(x, y)]


# Test
files = [f.rsplit(".", 1)[0] for f in glob.glob("*.in")]

total = 0
score = 0

dir_name = os.getcwd()
for f in files:
    total += 1
    in_file = dir_name + "\\" + f + ".in"
    out_file = dir_name + "\\" + f + ".out"
    with open(out_file, "r") as result:
        expected = int(result.readline().split()[0])
    with open(in_file, "r") as data:
        size = int(data.readline())
        vector = [[int(x) for x in y.split()] for y in data.readlines()]
    my_opt = find_opt(vector)
    if my_opt != expected:
        print("In file {}: expected {}, got {}".format(in_file, expected, my_opt))
    else:
        score += 1

print("Score is: {}%".format(round(100.0 * score / total, 1)))

Teraz przechodzi test na 100%, choć musiałem wprowadzić mały workaround na problem z nieuwzględnianiem pojedynczych wektorów, a trochę nie chce mi się już z tym bawić ;)

0

Krótkie uzasadnienie mojego rozwiązania,

  • najdłuższy wektor musi zawierać sumę wektorów z tej samej ćwiartki, bo wektory należące do tej samem ćwiartki mają te same znaki składowych, i tym samym każde dodanie takiego wektora do sumy zwiększa nam funkcję celu x^2+y^2
  • w najdłuższym wektorze nie mogą występować wektory należące do przeciwćwiartki, bo składowe takich wektorów mają przeciwne znaki do znaków składowych w bieżącej ćwiartce, więc dodanie takiego wektora zawsze zmniejsza poszukiwaną sumę wektorów.
  • w najdłuższym wektorze mogą znaleźć się wektory z ćwiartek sąsiednich, gdyż te mają jedną ze składowych o takim samym znaku jak składowe wektorów w bieżącej ćwiartce, druga zaś przeciwny, dobieramy tylko te wektory które zwiększają funkcję celu. W rezultacie dobierane są z obu ćwiartek tylko wektory należące właśnie do półpłaszczyzny ograniczonej prostą prostopadłą do wektora sumy danej ćwiartki, oczywiście jeśli spełniają warunek poprawy funkcji celu.

Jeśli ktoś widzi jakieś dziury w tym rozumowaniu to .. pewnie się odezwie;-)
W rozwiązaniu @superdurszlaka suma wektorów to podciąg z posortowanej listy wektorów względem kąta, czy kolejno są wektory z I, II, III i IV więc w każdym podciągu będącym rozwiązaniem będą występować wektory należące do tej samej ćwiartki bo każda półpłaszczyzna zawierająca wektor rozwiązania musi zawierać choć jedną ćwiartkę.

0

@cs : odpal taki przykład:

test = [[-3, -8], [-5, -5], [-4, 2], [4, -4], [-5, -4], [-8, 9], [-4, 1], [-2, -3], [2, 0], [-2, -10], [-7, 7], [4, 3], [-7, 2], [-5, -3], [-9, -9], [1, 6], [7, -9], [-8, 8], [7, -9], [10, -2]]

Za pomocą Twojego kodu otrzymujemy wynik 4357, optymalny wynik wynosi 4930.

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