Δύσκολο πρόβλημα από το cmad

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
Άβαταρ μέλους
ioannidis007
Δημοσιεύσεις: 29
Εγγραφή: Τετ Δεκ 17, 2008 1:08 am
Επικοινωνία:

Δύσκολο πρόβλημα από το cmad

Δημοσίευση από ioannidis007 » Τρί Δεκ 23, 2008 9:50 pm

Εύκολο μέρος:

Για Ν σημεία στο χώρο, με συντεταγμένες (xi,yi,zi) για 2<=i<=N<=10000, να βρείτε τη μέγιστη απόσταση manhattan μεταξύ δύo σημείων, καθώς και τα σημεία που απέχουν περισσότερο.

Δύσκολο μέρος:

Ο αλγόριθμός σας να τρέχει σε Ο(n). :shock:

Αρχείο Εισόδου:
input.in
N
x1 y1 z1
x2 y2 z2
.
.
.
xN yN zN
Αρχείο εξόδου(Έστω τα σημεία i,j απέχουν περισσότερο)
output.out
i
j
d(i,j)

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Δύσκολο πρόβλημα από το cmad

Δημοσίευση από feedWARd » Τρί Δεκ 23, 2008 11:18 pm

http://pastebin.com/m2b4d5ea

Μάλλον από τον κώδικα δεν θα καταλάβετε και πολλά. Δεν εξηγώ ακόμα την λύση μου ;)

Μερικά hints:
1. Σκεφτείτε πρώτα το πρόβλημα σε 2 διαστάσεις... πώς θα μπορούσατε να βρείτε τα δύο σημεία που απέχουν περισσότερο;
2. Για d διαστάσεις, έχουμε 2^d περιπτώσεις...

userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Δύσκολο πρόβλημα από το cmad

Δημοσίευση από userresu » Τετ Δεκ 24, 2008 1:35 am

Χμμ η μεγαλύτερη δυνατή απόσταση σε 2 διαστάσεις λογικά θα είναι max(dist(a,b),dist(c,d)), όπου a το σημείο με ελάχιστο άθροισμα συντεταγμένων, b το σημείο με μέγιστο άθροισμα συντεταγμένων, c το σημείο με ελάχιστη διαφορά συντεταγμένων και d το σημείο με μέγιστη διαφορά συντεταγμένων.

Αλλά μπορεί και όλο αυτό να είναι μία απέραντη κοτσάνα :P

EDIT: Επειδή μάλλον σωστό είναι, ας εξηγήσω τη σκέψη μου. Η απόσταση 2 σημείων a,b είναι ουσιαστικά |a.x-b.x|+|a.y-b.y|. Έχουμε 4 περιπτώσεις:
1) a.x>=b.x και a.y>=b.y => a.x-b.x+a.y-b.y
2) a.x>=b.x και a.y<b.y => a.x-b.x-a.y+b.y
3) a.x<b.x και a.y>=b.y => -a.x+b.x+a.y-b.y
4) a.x<b.x και a.y<b.y => -a.x+b.x-a.y+b.y

Κάπως έτσι βγαίνει.

EDIT 2: Για ν διαστάσεις, η απόσταση 2 σημείων είναι |a.d1-b.d1|+|a.d2-b.d2|+...+|a.dv-b.dv|, όπου d1,d2,...,dν είναι διαστάσεις. Άρα, αφού για κάθε όρο έχουμε 2 περιπτώσεις, θα έχουμε σύνολο 2^ν περιπτώσεις.

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Δύσκολο πρόβλημα από το cmad

Δημοσίευση από feedWARd » Τετ Δεκ 24, 2008 2:22 am

Ακριβώς!

Congrats ;)

Άβαταρ μέλους
ioannidis007
Δημοσιεύσεις: 29
Εγγραφή: Τετ Δεκ 17, 2008 1:08 am
Επικοινωνία:

Re: Δύσκολο πρόβλημα από το cmad

Δημοσίευση από ioannidis007 » Τετ Δεκ 24, 2008 3:30 pm

Μπράβο, σωστοί και οι 2. Congrats κ από εμένα! :D
@feedWARd: Μπορείς να εξηγήσεις λίγο τα highlighted? Βασικά τί κάνουν oι bitwise operators...
http://pastebin.com/m46bec27c

Απάντηση