Λύσεις Β' Φάσης
-
- Δημοσιεύσεις: 48
- Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm
Re: Λύσεις Β' Φάσης
@στάθης είσαι σίγουρος ότι η λύση σου είναι σωστή? Δεν έχω κοιτάξει ακόμα προσεκτικά την λύση σου, απλώς το λέω διότι ως καλύτερη επίλυση στην εκφώνηση είχαν την Ν^3.
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Λύσεις Β' Φάσης
Ναι, είναι.
Δοκίμασέ την.
Και του thelastnicholas N² είναι απ' ότι κοίταξα.
Δοκίμασέ την.
Και του thelastnicholas N² είναι απ' ότι κοίταξα.
-
- Δημοσιεύσεις: 74
- Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm
Re: Λύσεις Β' Φάσης
Το πιο σημαντικό πράγμα είναι να καταλαβαίνετε τι σας λέει ο άλλος.
(Υπάρχουν τρεις τουλάχιστον αλγοριθμικές επιλύσεις του παραπάνω προβλήματος με πολυπλοκότητα Ο(Ν!), Ο(2Ν) και Ο(Ν3))
Re: Λύσεις Β' Φάσης
Κώδικας: Επιλογή όλων
/*
LANG: C++
TASK: evripos
*/
#include <iostream>
#include <fstream>
#include <cmath>
#define BIG 9007199254740991.0
using namespace std;
struct Point
{
int x,y;
};
int N;
Point p[205];
double sol[205][205];
int n;
void quicksort (int l,int r)
{
int i=l,j=r;
Point m=p[(l+r)/2];
while (i<=j)
{
while (i<=j && p[i].x<m.x) ++i;
while (i<=j && p[j].x>m.x) --j;
if (i<=j)
{
Point x=p[i];
p[i]=p[j];
p[j]=x;
++i;
--j;
}
}
if (l<j) quicksort(l,j);
if (i<r) quicksort(i,r);
}
int main ()
{
ifstream fin ("evripos.in");
fin >> N;
p[1].x=p[1].y=0;
fin >> p[N+2].x >> p[N+2].y;
for (int i=2;i<=N+1;++i)
fin >> p[i].x >> p[i].y;
fin.close();
quicksort(1,N+2);
sol[1][1]=0;
sol[2][1]=sqrt((p[1].x-p[2].x)*(p[1].x-p[2].x)+(p[1].y-p[2].y)*(p[1].y-p[2].y));
for (int i=3;i<=N+2;++i)
for (int j=1;j<=i;++j)
{
if (i==j && i!=N+2)
continue;
if (i>j+1)
{
sol[i][j]=sol[i-1][j]+sqrt((p[i].x-p[i-1].x)*(p[i].x-p[i-1].x)+(p[i].y-p[i-1].y)*(p[i].y-p[i-1].y));
++n;
continue;
}
double MIN=BIG;
for (int k=1;k<j;++k)
{
++n;
double cost=sol[j][k]+sqrt((p[k].x-p[i].x)*(p[k].x-p[i].x)+(p[k].y-p[i].y)*(p[k].y-p[i].y));
if (MIN>cost)
MIN=cost;
}
sol[i][j]=MIN;
}
ofstream fout ("evripos.out");
fout << round(sol[N+2][N+2]) << endl;
fout << n << endl;
return 0;
}
Re: Λύσεις Β' Φάσης
Γεια και χαρά σε όλους.
Είμαι ένας "μεγάλος" που θέλει να ξεσκουριάζει το μυαλό του λύνοντας ασκήσεις από τον ΠΔΠ.
Ρίξτε μια ματιά στην λύση μου για το πρόβλημα του Γυμνασίου:
Σας έκανα επικόλληση από το τερματικό του Hardy Heron μου (Ubuntu 8.04 LTS 32bit).
Ο χρόνος είναι για 10000 σημεία σε ένα C2D E6400 με 2Gb μνήμη.
Ευχαριστώ για την φιλοξενία.
ΥΓ. Μην με αντιμετωπίσετε σαν μεγάλο... είμαι πιο μικρός από εσάς
Είμαι ένας "μεγάλος" που θέλει να ξεσκουριάζει το μυαλό του λύνοντας ασκήσεις από τον ΠΔΠ.
Ρίξτε μια ματιά στην λύση μου για το πρόβλημα του Γυμνασίου:
Κώδικας: Επιλογή όλων
chiossif@chiossif-6400:~/Code/PDP_21B/PDP_21_B_GYM$ cat gym.c
#include <stdio.h>
#include <stdlib.h>
int inline int_sqr(int x) {
return x*x;
}
int main(void) {
int *x, *y, *z, d, a, b, s1, s2, s3, s, n, n_1;
register int i, j;
scanf("%d",&n);
n_1=n-1;
x=malloc(n*sizeof(int));
y=malloc(n*sizeof(int));
z=malloc(n*sizeof(int));
for (i=0;i<n;i++)
scanf("%d %d %d", &x[i], &y[i],&z[i]);
d=int_sqr(x[1]-x[0])+int_sqr(y[1]-y[0])+int_sqr(z[1]-z[0]);
a=0;
b=1;
for (i=0;i<n_1;i++)
for (j=i+1;j<n;j++)
if ((s1=int_sqr(x[j]-x[i]))<=d &&
(s2=int_sqr(y[j]-y[i]))<=d &&
(s3=int_sqr(z[j]-z[i]))<=d && (s=s1+s2+s3)<d) {
a=i;
b=j;
d=s;
}
printf("%d %d\n",a+1,b+1);
return 0;
}
chiossif@chiossif-6400:~/Code/PDP_21B/PDP_21_B_GYM$ time ./gym <gym_10000.in
5540 8477
real 0m0.557s
user 0m0.528s
sys 0m0.004s
chiossif@chiossif-6400:~/Code/PDP_21B/PDP_21_B_GYM$
Ο χρόνος είναι για 10000 σημεία σε ένα C2D E6400 με 2Gb μνήμη.
Ευχαριστώ για την φιλοξενία.
ΥΓ. Μην με αντιμετωπίσετε σαν μεγάλο... είμαι πιο μικρός από εσάς
Re: Λύσεις Β' Φάσης
ο Ο(Ν^2) πρεπει να εχει αρκετες μορφες. Η δικη μου ειναι αυτη:
C(j) ειναι η αποσταση της διαδρομης που περνα απ ολα τα λιμανια και ξεκινα απο το λιμανι j-1 και καταληγει στο j περνοντας απ ολα τα λιμανια πριν το j και που κινειται παντα αριστερα μεχρι να φτασει στο πρωτο λιμανι (0,0) και παντα δεξια απο εκει μεχρι το j
Ετσι προσθετοντας ενα ακομα λιμανι l που να ταυτιζεται με το τελευτεο η απατηση θα ειναι C(l)
ισχυει λοιπον για καθε λιμανι jπου ειναι πιο δεξια απο το 2ο λιμανι
(μπορει να φενεται λιγο μπερδεμα η εκφραση ομως με χαρτι και μολυβι ειναι σχετικα ευκολο στην κατανοηση)
C(j) ειναι η αποσταση της διαδρομης που περνα απ ολα τα λιμανια και ξεκινα απο το λιμανι j-1 και καταληγει στο j περνοντας απ ολα τα λιμανια πριν το j και που κινειται παντα αριστερα μεχρι να φτασει στο πρωτο λιμανι (0,0) και παντα δεξια απο εκει μεχρι το j
Ετσι προσθετοντας ενα ακομα λιμανι l που να ταυτιζεται με το τελευτεο η απατηση θα ειναι C(l)
ισχυει λοιπον για καθε λιμανι jπου ειναι πιο δεξια απο το 2ο λιμανι
(μπορει να φενεται λιγο μπερδεμα η εκφραση ομως με χαρτι και μολυβι ειναι σχετικα ευκολο στην κατανοηση)
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Λύσεις Β' Φάσης
darksaga, όντως χρειάζεται χαρτί και μολύβι. Μόνο που βαριέμαι.
Την λύση σου θα την ποστάρεις να τη δούμε;
Την λύση σου θα την ποστάρεις να τη δούμε;
Re: Λύσεις Β' Φάσης
ωπ συγγνομι.
Απλα στον κωδικα εκανα μερικες μικρες αποκλισεις απο το το αρχικο μοντελο του αλγοριθμου για να παει λιγο πιο γρηγορα οποτε καλο ειναι για να καταλαβετε τη λυση να κοιταξετε το απραπανω ποστ
http://pastebin.com/m6eecb65f
Απλα στον κωδικα εκανα μερικες μικρες αποκλισεις απο το το αρχικο μοντελο του αλγοριθμου για να παει λιγο πιο γρηγορα οποτε καλο ειναι για να καταλαβετε τη λυση να κοιταξετε το απραπανω ποστ
http://pastebin.com/m6eecb65f
Re: Λύσεις Β' Φάσης
πάρτε και τη δικιά μου....! (σε Πασκάλ... αν τη θυμάται κανείς σε αυτό το φόρουμ λολ )
Πρέπει να είναι πάντος ένας από τους πιο user-friendly κώδικες
edit: Παρεπιπτοντως O(n^2) όσον αφόρα την χρονική πολυπλοκότητα.
Πρέπει να είναι πάντος ένας από τους πιο user-friendly κώδικες
edit: Παρεπιπτοντως O(n^2) όσον αφόρα την χρονική πολυπλοκότητα.
Κώδικας: Επιλογή όλων
PROGRAM evripos;
{LANG: Pascal
TASK: evripos}
USES
SysUtils;
CONST
MaxPoints = 204;
INF = 100000;
TYPE
coordinates = record
X:integer;
Y:integer;
end;
Coordsys = array[1..MaxPoints] of coordinates;
VAR
N,
I,J,K,
d:integer;
q:real;
input,output:text;
points:Coordsys;
l:array[1..MaxPoints,1..MaxPoints] of real;
FUNCTION dist(a,b:coordinates):real; //euclidean distiance//
BEGIN
dist:=sqrt(sqr(a.X-b.X)+sqr(a.Y-b.Y))
END;
(*---------------- start of quicksort ------------------*)
PROCEDURE swap(VAR a, b: coordinates);
VAR
t: integer;
BEGIN
t := a.X;
a.X := b.X;
b.X := t;
t := a.Y;
a.Y := b.Y;
b.Y := t;
END;
FUNCTION Split(start, stop: integer): integer;
VAR
left, right: integer;
pivot: integer;
BEGIN
pivot := points[start].X;
left := start + 1;
right := stop;
WHILE left <= right DO BEGIN
WHILE (left <= stop) AND (points[left].X < pivot) DO
left := left + 1;
WHILE (right > start) AND (points[right].X >= pivot) DO
right := right - 1;
IF left < right THEN
swap(points[left], points[right]);
END;
swap(points[start], points[right]);
Split := right
END;
PROCEDURE QuicksortRecur(start, stop: integer);
VAR
splitpt: integer;
BEGIN
IF start < stop THEN BEGIN
splitpt := Split(start, stop);
QuicksortRecur(start, splitpt-1);
QuicksortRecur(splitpt+1, stop);
END
END;
PROCEDURE Quicksort(size: Integer; VAR points: Coordsys);
BEGIN
QuicksortRecur(1, size)
END;
(*------------- end of quicksort ------------------*)
BEGIN
(*------------- input data -------------------*)
assign(input,'evripos.in');
reset(input);
readln(input,N);
N:=N+2;
points[1].X:=0;
points[1].Y:=0;
readln(input,points[N].X,points[N].Y);
FOR I := 2 TO N-1 DO
readln(input,points[I].X,points[I].Y);
close(input);
(*--------------- end of input ---------------------*)
(*-------- sorting coordinates by increasing X -----*)
Quicksort(N, points);
(*--------------------------------------------------*)
(*--- computing all minimum normal bitonic paths ---*)
FOR J := 2 TO N DO
FOR I := 1 TO J-1 DO
IF (I=1) AND (J=2) THEN
l[I,J] := dist(points[i],points[j])
ELSE IF J>I+1 THEN
l[I,J]:= l[I,J-1] + dist(points[J-1],points[J])
ELSE BEGIN
l[I,J] := INF;
FOR K := 1 TO I-1 DO BEGIN
q:= l[K,I] + dist(points[K],points[J]);
IF q < l[I,J] THEN
l[I,J]:= q;
END;
END;
(*------------------------------------------------*)
(*----- computing the shortest bitonic tour ------*)
d:= Round( l[n-1,n] + dist(points[n-1],points[n]));
(*------------------------------------------------*)
(*---------------- output data -------------------*)
assign(output,'evripos.out');
rewrite(output);
writeln(output,d);
close(output);
(*--------------- end of output ------------------*)
end.
Τελευταία επεξεργασία από το μέλος Thrasos την Τρί Μαρ 17, 2009 3:43 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Re: Λύσεις Β' Φάσης
Ouchdarksaga έγραψε:συγγνομι
Re: Λύσεις Β' Φάσης
σοβαρα περιμενα ο Νικ να μου την πει γι αυτο
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Λύσεις Β' Φάσης
Thrasos, γιατί να την έχουμε ξεχάσει;
Και εγώ είχα κάνει μια λύση σε Pascal όταν βαριόμουν, ορίστε:
Και εγώ είχα κάνει μια λύση σε Pascal όταν βαριόμουν, ορίστε:
Κώδικας: Επιλογή όλων
program evripos;
type CoordSet = record
x, y: Integer
end;
var Fi: TextFile;
i, j, tmp, N: Integer;
ans, dist: Array [1..203, 1..203] of Real;
Coord: Array [1..203] of CoordSet;
begin
Assign(Fi, 'evripos.in');
Reset(Fi);
ReadLn(Fi, N);
ReadLn(Fi, Coord[N+1].x, Coord[N+1].y);
for i:=1 to N do
ReadLn(Fi, Coord[i].x, Coord[i].y);
Close(Fi);
N := N+2;
Coord[N].x := 0;
Coord[N].y := 0;
for i:=1 to N do
for j:=1 to N do
if Coord[i].x > Coord[j].x then begin
tmp := Coord[i].x;
Coord[i].x := Coord[j].x;
Coord[j].x := tmp;
tmp := Coord[i].y;
Coord[i].y := Coord[j].y;
Coord[j].y := tmp;
end;
for i:=1 to N do
for j:=1 to N do begin
dist[i, j] := sqrt( (Coord[i].x-Coord[j].x)*(Coord[i].x-Coord[j].x) + (Coord[i].y-Coord[j].y)*(Coord[i].y-Coord[j].y) );
ans[i, j] := 99999999;
end;
ans[1, 1] := 0;
for i:=1 to N do
for j:=1 to N do begin
if ans[i+1, i] > ans[i, j]+dist[j, i+1] then
ans[i+1, i] := ans[i, j]+dist[j, i+1];
if ans[i+1, j] > ans[i, j]+dist[i, i+1] then
ans[i+1, j] := ans[i, j]+dist[i, i+1];
if ans[i+1, i+1] > ans[i, j]+dist[i, i+1]+dist[j, i+1] then
ans[i+1, i+1] := ans[i, j]+dist[i, i+1]+dist[j, i+1];
end;
Assign(Fi, 'evripos.out');
Rewrite(Fi);
WriteLn(Fi, Round(ans[N, N]));
Close(Fi);
Halt(0);
end.
Re: Λύσεις Β' Φάσης
Ωραίος ο Στάθης
Η αλήθεια είναι πως σε διαγωνισμούς η C είναι "καλύτερη" από άλλες, λόγω του ότι είναι middle level και έτσι δεν κάνεις περιττά πράγματα που σου τρώνε χρόνο (τα οποία στη Πασκαλ πχ δν μπορείς να τα αποφύγεις...)
Βέβαια εγώ την προτιμὼ για να κάνω εύκολη εκσφαλμάτωσή (και για να παω κόντρα στο πλήθος χαχα )
Η αλήθεια είναι πως σε διαγωνισμούς η C είναι "καλύτερη" από άλλες, λόγω του ότι είναι middle level και έτσι δεν κάνεις περιττά πράγματα που σου τρώνε χρόνο (τα οποία στη Πασκαλ πχ δν μπορείς να τα αποφύγεις...)
Βέβαια εγώ την προτιμὼ για να κάνω εύκολη εκσφαλμάτωσή (και για να παω κόντρα στο πλήθος χαχα )
-
- Δημοσιεύσεις: 7
- Εγγραφή: Πέμ Δεκ 18, 2008 12:23 am
Re: Λύσεις Β' Φάσης
αν καταλαβα βρισκει δυο διαδρομες παραλληλα μια για να παει και μια για να γυρισειstathis έγραψε: Βλέπω το πρόβλημα ως ένα επίπεδο που έχει δύο διαδρομές οι οποίες μόνο πηγαίνουν.
Το ans έχει ως indexes το που βρίσκεται η κάθε διαδρομή-σχοινί. Δηλαδή με ans[1][2] σημαίνει πως το ένα σχοινί είναι στο σημείο 1, και το δεύτερο στο σημείο δύο. Η τιμή που αποδίδεται σε αυτή την "κατάσταση" (DP state) είναι η συνολική διανυόμενη διαδρομή ως εκείνα τα σημεία. Επομένως, όταν φτάσει στο τελικό σημείο, η λύση μας βρίσκεται στο ans[N][N], εφόσον εκεί τερματίζει.
πως ομως βρισκει αυτη την συνολικη διανυομενη διαδρομη εως εκει
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Λύσεις Β' Φάσης
Όχι, δεν βρίσκει μια για να πάει και μια για να γυρίσει. Βρίσκει δυο για να πάει.
Ο καλύτερος τρόπος για να καταλάβεις είναι να δοκιμάσεις να χρησιμοποιήσεις τη λύση μου σε χαρτί.
Ο καλύτερος τρόπος για να καταλάβεις είναι να δοκιμάσεις να χρησιμοποιήσεις τη λύση μου σε χαρτί.
Re: Λύσεις Β' Φάσης
lol
το ιδιο κανει
το ιδιο κανει
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Λύσεις Β' Φάσης
Είναι αρκετοί που δε το καταλαβαίνουν.darksaga έγραψε:lol
το ιδιο κανει
-
- Δημοσιεύσεις: 7
- Εγγραφή: Πέμ Δεκ 18, 2008 12:23 am
Re: Λύσεις Β' Φάσης
για την O(N^3) λυση μπορουσε κανεις να στηριχτει στον Floyd–Warshall ;
για την O(N^2) εχει ο αλγοριθμος καποιο όνομα;
για την O(N^2) εχει ο αλγοριθμος καποιο όνομα;
Re: Λύσεις Β' Φάσης
ο floyd-warshall ειναι για weighted γραφους μονο, γιατι σε unweighted δεν εχει νοημα... δες λιγο πως λειτουργει ακι θα καταλαβεις γιατι ειναι εντελως ασχετος με το θεμα.
ο n^2 δεν νομιζω πως εχει ονομα η οτι υπαρχει γενικα σαν καθιερωμενος στη βιβλιογραφια αλγοριθμος... Εγω τουλαχιστον δε βρηκα καποια υλοποιηση εκει εξω...
Ν^3 νομιζω πως ειναι απλως μια κακογραμμενη version καποιου Ν^2 δεδομενου οτι δεν υπαρχει ακποιος εδω μεσα που να τον βρηκε...
ο n^2 δεν νομιζω πως εχει ονομα η οτι υπαρχει γενικα σαν καθιερωμενος στη βιβλιογραφια αλγοριθμος... Εγω τουλαχιστον δε βρηκα καποια υλοποιηση εκει εξω...
Ν^3 νομιζω πως ειναι απλως μια κακογραμμενη version καποιου Ν^2 δεδομενου οτι δεν υπαρχει ακποιος εδω μεσα που να τον βρηκε...
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Λύσεις Β' Φάσης
Ο Ν² δεν υπάρχει σαν στάνταρ αλγόριθμος κάπου, ωστόσο είναι εφαρμογή της μεθόδου του dynamic programming.
Και, απ' όσο βλέπω στο Poll υπάρχουν άτομα με N³, αλλά απλά μου φαίνεται πως δεν έδειξαν τη λύση τους-ή απλά δε τη προσέξαμε...
Edit: δείτε μια σελίδα πίσω, του ioannidis007.
Και, απ' όσο βλέπω στο Poll υπάρχουν άτομα με N³, αλλά απλά μου φαίνεται πως δεν έδειξαν τη λύση τους-ή απλά δε τη προσέξαμε...
Edit: δείτε μια σελίδα πίσω, του ioannidis007.