Λύσεις Β' Φάσης

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
georgeha98
Δημοσιεύσεις: 48
Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από georgeha98 »

@στάθης είσαι σίγουρος ότι η λύση σου είναι σωστή? Δεν έχω κοιτάξει ακόμα προσεκτικά την λύση σου, απλώς το λέω διότι ως καλύτερη επίλυση στην εκφώνηση είχαν την Ν^3.
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Λύσεις Β' Φάσης

Δημοσίευση από stathis »

Ναι, είναι.
Δοκίμασέ την. :P
Και του thelastnicholas N² είναι απ' ότι κοίταξα.
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από thelastnicholas »

Το πιο σημαντικό πράγμα είναι να καταλαβαίνετε τι σας λέει ο άλλος.
(Υπάρχουν τρεις τουλάχιστον αλγοριθμικές επιλύσεις του παραπάνω προβλήματος με πολυπλοκότητα Ο(Ν!), Ο(2Ν) και Ο(Ν3))
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από userresu »

Κώδικας: Επιλογή όλων

/*
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;
}
Είμαι ο μόνος που έκατσε κι έγραψε quicksort; :P
chiossif
Δημοσιεύσεις: 1
Εγγραφή: Παρ Δεκ 19, 2008 1:01 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από chiossif »

Γεια και χαρά σε όλους.

Είμαι ένας "μεγάλος" που θέλει να ξεσκουριάζει το μυαλό του λύνοντας ασκήσεις από τον ΠΔΠ.
Ρίξτε μια ματιά στην λύση μου για το πρόβλημα του Γυμνασίου:

Κώδικας: Επιλογή όλων

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$ 
Σας έκανα επικόλληση από το τερματικό του Hardy Heron μου (Ubuntu 8.04 LTS 32bit).
Ο χρόνος είναι για 10000 σημεία σε ένα C2D E6400 με 2Gb μνήμη.
Ευχαριστώ για την φιλοξενία.

ΥΓ. Μην με αντιμετωπίσετε σαν μεγάλο... είμαι πιο μικρός από εσάς :-)
darksaga
Δημοσιεύσεις: 44
Εγγραφή: Δευ Μαρ 16, 2009 10:57 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από darksaga »

ο Ο(Ν^2) πρεπει να εχει αρκετες μορφες. Η δικη μου ειναι αυτη:

C(j) ειναι η αποσταση της διαδρομης που περνα απ ολα τα λιμανια και ξεκινα απο το λιμανι j-1 και καταληγει στο j περνοντας απ ολα τα λιμανια πριν το j και που κινειται παντα αριστερα μεχρι να φτασει στο πρωτο λιμανι (0,0) και παντα δεξια απο εκει μεχρι το j

Ετσι προσθετοντας ενα ακομα λιμανι l που να ταυτιζεται με το τελευτεο η απατηση θα ειναι C(l)

ισχυει λοιπον για καθε λιμανι jπου ειναι πιο δεξια απο το 2ο λιμανι
Εικόνα

(μπορει να φενεται λιγο μπερδεμα η εκφραση ομως με χαρτι και μολυβι ειναι σχετικα ευκολο στην κατανοηση)
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Λύσεις Β' Φάσης

Δημοσίευση από stathis »

darksaga, όντως χρειάζεται χαρτί και μολύβι. Μόνο που βαριέμαι. :D
Την λύση σου θα την ποστάρεις να τη δούμε; :P
darksaga
Δημοσιεύσεις: 44
Εγγραφή: Δευ Μαρ 16, 2009 10:57 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από darksaga »

ωπ συγγνομι.
Απλα στον κωδικα εκανα μερικες μικρες αποκλισεις απο το το αρχικο μοντελο του αλγοριθμου για να παει λιγο πιο γρηγορα οποτε καλο ειναι για να καταλαβετε τη λυση να κοιταξετε το απραπανω ποστ
http://pastebin.com/m6eecb65f
Thrasos
Δημοσιεύσεις: 29
Εγγραφή: Τετ Δεκ 17, 2008 9:41 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από Thrasos »

πάρτε και τη δικιά μου....! (σε Πασκάλ... αν τη θυμάται κανείς σε αυτό το φόρουμ λολ :P)

Πρέπει να είναι πάντος ένας από τους πιο user-friendly κώδικες :D

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 φορά συνολικά.
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από userresu »

darksaga έγραψε:συγγνομι
Ouch :shock:
darksaga
Δημοσιεύσεις: 44
Εγγραφή: Δευ Μαρ 16, 2009 10:57 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από darksaga »

σοβαρα περιμενα ο Νικ να μου την πει γι αυτο :lol:
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Λύσεις Β' Φάσης

Δημοσίευση από stathis »

Thrasos, γιατί να την έχουμε ξεχάσει; :P
Και εγώ είχα κάνει μια λύση σε 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.
Thrasos
Δημοσιεύσεις: 29
Εγγραφή: Τετ Δεκ 17, 2008 9:41 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από Thrasos »

Ωραίος ο Στάθης :P

Η αλήθεια είναι πως σε διαγωνισμούς η C είναι "καλύτερη" από άλλες, λόγω του ότι είναι middle level και έτσι δεν κάνεις περιττά πράγματα που σου τρώνε χρόνο (τα οποία στη Πασκαλ πχ δν μπορείς να τα αποφύγεις...)
Βέβαια εγώ την προτιμὼ για να κάνω εύκολη εκσφαλμάτωσή (και για να παω κόντρα στο πλήθος χαχα )
TasostheGreat
Δημοσιεύσεις: 7
Εγγραφή: Πέμ Δεκ 18, 2008 12:23 am

Re: Λύσεις Β' Φάσης

Δημοσίευση από TasostheGreat »

stathis έγραψε: Βλέπω το πρόβλημα ως ένα επίπεδο που έχει δύο διαδρομές οι οποίες μόνο πηγαίνουν.

Το ans έχει ως indexes το που βρίσκεται η κάθε διαδρομή-σχοινί. Δηλαδή με ans[1][2] σημαίνει πως το ένα σχοινί είναι στο σημείο 1, και το δεύτερο στο σημείο δύο. Η τιμή που αποδίδεται σε αυτή την "κατάσταση" (DP state) είναι η συνολική διανυόμενη διαδρομή ως εκείνα τα σημεία. Επομένως, όταν φτάσει στο τελικό σημείο, η λύση μας βρίσκεται στο ans[N][N], εφόσον εκεί τερματίζει.
αν καταλαβα βρισκει δυο διαδρομες παραλληλα μια για να παει και μια για να γυρισει

πως ομως βρισκει αυτη την συνολικη διανυομενη διαδρομη εως εκει
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Λύσεις Β' Φάσης

Δημοσίευση από stathis »

Όχι, δεν βρίσκει μια για να πάει και μια για να γυρίσει. Βρίσκει δυο για να πάει.
Ο καλύτερος τρόπος για να καταλάβεις είναι να δοκιμάσεις να χρησιμοποιήσεις τη λύση μου σε χαρτί.
darksaga
Δημοσιεύσεις: 44
Εγγραφή: Δευ Μαρ 16, 2009 10:57 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από darksaga »

lol
το ιδιο κανει
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Λύσεις Β' Φάσης

Δημοσίευση από stathis »

darksaga έγραψε:lol
το ιδιο κανει
Είναι αρκετοί που δε το καταλαβαίνουν. :P
TasostheGreat
Δημοσιεύσεις: 7
Εγγραφή: Πέμ Δεκ 18, 2008 12:23 am

Re: Λύσεις Β' Φάσης

Δημοσίευση από TasostheGreat »

για την O(N^3) λυση μπορουσε κανεις να στηριχτει στον Floyd–Warshall ;

για την O(N^2) εχει ο αλγοριθμος καποιο όνομα;
darksaga
Δημοσιεύσεις: 44
Εγγραφή: Δευ Μαρ 16, 2009 10:57 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από darksaga »

ο floyd-warshall ειναι για weighted γραφους μονο, γιατι σε unweighted δεν εχει νοημα... δες λιγο πως λειτουργει ακι θα καταλαβεις γιατι ειναι εντελως ασχετος με το θεμα.

ο n^2 δεν νομιζω πως εχει ονομα η οτι υπαρχει γενικα σαν καθιερωμενος στη βιβλιογραφια αλγοριθμος... Εγω τουλαχιστον δε βρηκα καποια υλοποιηση εκει εξω...

Ν^3 νομιζω πως ειναι απλως μια κακογραμμενη version καποιου Ν^2 δεδομενου οτι δεν υπαρχει ακποιος εδω μεσα που να τον βρηκε...
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Λύσεις Β' Φάσης

Δημοσίευση από stathis »

Ο Ν² δεν υπάρχει σαν στάνταρ αλγόριθμος κάπου, ωστόσο είναι εφαρμογή της μεθόδου του dynamic programming.

Και, απ' όσο βλέπω στο Poll υπάρχουν άτομα με N³, αλλά απλά μου φαίνεται πως δεν έδειξαν τη λύση τους-ή απλά δε τη προσέξαμε... :mrgreen:

Edit: δείτε μια σελίδα πίσω, του ioannidis007.
Απάντηση