Προς το περιεχόμενο

Αλγόριθμος ζάρι


k33theod

Προτεινόμενες αναρτήσεις

  • Απαντ. 33
  • Δημ.
  • Τελ. απάντηση

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Το πρόβλημα είναι ενδιαφέρον, γιατί έχει και την ιδιότητα του non-transativity, δηλαδή αν πχ έχουμε 3 σετ A,B,C μπορεί το A να νικάει το B, το Β να νικάει το C αλλά το C να νικάει το A. Είσαι σίγουρος ότι το πρόβλημα λύνεται για n (arbitrary) αριθμό από έδρες και ότι έχει και global optimum?

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Μήπως καλύτερη λύση θα ήταν να κάνεις ένα simulation με το ζάρι του 1ου παίχτη στις 100 φορές , να βρείς τις πιθανότητες για κάθε έδρα και μετα να υπολογίσεις τις δικές σου?

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

@tsofras: οι πιθανότητες είναι για τον κάθε ένα συγκεκριμένες, νίκες / αριθμό γεγονότων. Οι νίκες είναι βέβαια πάντα σε συνδυασμό με τον αντίπαλο και ισχύει αυτό που λέει ο iceblade (non-transative)

 

@iceblade: δεν μιλάει νομίζω πουθενά για global optimum, έχεις input και με βάση αυτό φτιάχνεις ένα σετ που θα πάρει το καλύτερο δυνατό αποτέλεσμα (μερικές φορές είναι αδύνατη η νίκη έτσι και αλλιώς).

 

Γμτ έχω δουλειά...

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δε θα σου δώσω τον αλγόριθμο, αλλά θα σου εξηγήσω το σκεπτικό.

 

Ο αντίπαλος έχει ένα ζάρι [1,2,3,4,5,6] όπου το άθροισμα είναι 21.

Άρα εσύ, πρέπει να μοιράσεις το 21 με τέτοιιο τρόπο, ώστε να έχεις 50% +1 πιθανότητες να τον κερδίσεις.

 

Άρα, με τις έξι έδρες, το 50% + 1 είναι 4 έδρες. Που σημαίνει ότι χρειάζεσαι 4 καλύτερες από του αντιπάλου.

Θα πάρεις λοιπόν τις υπόλοιπες, 2 εδώ (5, 6), θα τις φέρεις στη μονάδα και θα μοιράσεις τις υπόλοιπες μονάδες (4, 5 αντίστοιχα) στις έδρες σου, κατά τέτοιο τρόπο ώστε όλες να είναι +1 από τη επόμενη μεγαλύτερή του, εδώ δηλαδή το 4.

 

πχ το 4 σου, θα το κάνεις 5 (υπόλοιπο 8 μονάδες)

το 3 σου θα το κάνεις 5 (υπόλοιπο 6 μονάδες)

Το 2 σου θα το κάνεις 5 (υπόλοιπο 3 μονάδες)

Το 1 σου θα το κάνεις 4 (υπόλοιπο 0 μονάδες)

 

Άρα έχεις [4,5,5,5,1,1] εναντίον [1,2,3,4,5,6]

  • Like 1
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Αυτά που λες  (  [4,5,5,5,1,1] εναντίον [1,2,3,4,5,6]  ) έχουν ίδιες πιθανότητες έτσι όπως το βλέπω / υπολογίζω τουλάχιστον και δεν ισχύει αυτή η λογική σε όλο το φάσμα των πιθανών συνδυασμών.

 

Το σκορ σου προέρχεται από συνδυασμό νικών και αποφυγής ήττας, δεν γίνεται να το προσδιορίσεις μόνο με 50%+1 νίκες γιατί είναι αδύνατο σε πολλές περιπτώσεις οπότε πρέπει να πας για το μεγαλύτερο αριθμό που θα προκύπτει από το νίκες - ήττες με τον συγκεκριμένο αντίπαλο.

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Aν μας πεις πως το υπολογίζεις, θα καταλάβουμε το σκεπτικό σου :)

 

Εδώ έχουμε:

1: 5 ήττες, 1 ισοπαλία

1: 5 ήττες, 1 ισοπαλία

4: 3 νίκες, 1 ισοπαλία, 2 ήττες

5: 4 νίκες, 1 ισοπαλία, 1 ήττα

5: 4 νίκες, 1 ισοπαλία, 1 ήττα

5: 4 νίκες, 1 ισοπαλία, 1 ήττα

 
Άρα, στο σύνολο έχεις 6 ισοπαλίες, 15 ήττες, 15 νίκες, που σημαίνει 50%-50%. Το αναφέρει ο TS ότι αν οι τιμές είναι συνεχόμενες, δεν μπορείς να κερδίσεις. Επίσης, αναφέρει ότι οι τιμές δεν είναι συγκεκριμένες ανά έδρα. Άρα, θα μπορούσε το ζάρι να είναι [6,6,6,6,6,6], όπου δε θα κερδίσεις ποτέ.
 
Το σκεπτικό της άσκησης, επειδή αρκετοί από εμάς την έχουμε κάνει στο Πανεπιστήμιο, είναι να βρει τον αλγόριθμο που του δίνει το αποτέλεσμα κι όχι να κερδίζει πάντα. Για αυτό δεν του έγραψα τον αλγόριθμο καθαυτόν, αλλά το έδωσα μια κατεύθυνση.
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Sorry  δεν το είδες ίσως αλλά είπα πως το υπολογίζω λίγο πριν. Νόμιζα ότι ενοούσες πως δεν ήταν 50-50 το συγκεκριμένο παράδειγμα, γιαυτό το ανέφερα, συμφωνούμε σε αυτό.

 

Εγω καταλαβαίνω ότι ο στόχος δεν είναι να βρεις τον τρόπο υπολογισμού των πιθανοτήτων αλλά να βρεις αντίπαλο με τις καλύτερες δυνατές πιθανότητες με βάση το input που σου δίνει.

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Γιατι να εχεις μεγαλυτερες τιμες στις μισες εδρες; Ο σκοπος ειναι να εχεις μεγαλυτερη πιθανοτητα απο τον αντιπαλο.

 

Αυτο που θες ειναι περισσοτερες εδρες νικης απο τον αντιπαλο. Για να το πετυχεις αυτο, θες μια εδρα που να χανει απο ολες τις εδρες του αντιπαλου.

Πχ αν ο αντιπαλος εχει 1,2,3,4 και εσυ 1,2,3,4

Τοτε οι πιθανότητες ειναι 50-50

Εαν ομως εχεις 1,3,3,3

Τοτε εχεις 50% να κεδρισεις και 25% να χασεις.

Δεν είναι έτσι decideWinner ([1,3,3,3],[1,2,3,4])

(6, 6) To ζάρι [1,2,3,4] απ' ότι φένεται δεν χτυπιέται 
Η decideWinner όπως την έδωσε ο alou 

Δε θα σου δώσω τον αλγόριθμο, αλλά θα σου εξηγήσω το σκεπτικό.

 

Ο αντίπαλος έχει ένα ζάρι [1,2,3,4,5,6] όπου το άθροισμα είναι 21.

Άρα εσύ, πρέπει να μοιράσεις το 21 με τέτοιιο τρόπο, ώστε να έχεις 50% +1 πιθανότητες να τον κερδίσεις.

 

Άρα, με τις έξι έδρες, το 50% + 1 είναι 4 έδρες. Που σημαίνει ότι χρειάζεσαι 4 καλύτερες από του αντιπάλου.

Θα πάρεις λοιπόν τις υπόλοιπες, 2 εδώ (5, 6), θα τις φέρεις στη μονάδα και θα μοιράσεις τις υπόλοιπες μονάδες (4, 5 αντίστοιχα) στις έδρες σου, κατά τέτοιο τρόπο ώστε όλες να είναι +1 από τη επόμενη μεγαλύτερή του, εδώ δηλαδή το 4.

 

πχ το 4 σου, θα το κάνεις 5 (υπόλοιπο 8 μονάδες)

το 3 σου θα το κάνεις 5 (υπόλοιπο 6 μονάδες)

Το 2 σου θα το κάνεις 5 (υπόλοιπο 3 μονάδες)

Το 1 σου θα το κάνεις 4 (υπόλοιπο 0 μονάδες)

 

Άρα έχεις [4,5,5,5,1,1] εναντίον [1,2,3,4,5,6]

είναι επίσης λάθος το [1,2,3,4,5,6] δεν νικιέται

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

είναι επίσης λάθος το [1,2,3,4,5,6] δεν νικιέται

Την εκφώνιση της άσκησης τη διάβασες;

Βάζει ότι θέλεις στις έδρες.

Θα μπορούσε να βάλει [6,6,6,6,6,6].

Νικιέται;

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Μέχρι στιγμής έχω γράψει αυτό σε python το οποίο είναι λάθος τελικά 

χτυπάει σε τεστ.

def winning_die(a):
  lena=len(a)
  a.sort()
  b=[i for i in a]
  count1=a.count(1)
  k=count1+(len(-count1)//2
  l=0+count1
  awins,bwins=decideWinner (a,
  for i in range(30):
    if awins>=bwins:
      change_die(
      awins,bwins=decideWinner(a,
    else:
      return b  
  return []

def decideWinner (a,:
  awins = 0
  bwins = 0
  for i in range(len(a)):
    for j in range(len():
      if(a[i] > b[j]):
        awins +=1
      elif a[i] < b[j]:
        bwins +=1
    
  return awins, bwins

def change_die(a):
  max_count=1
  max_count_index=0
  count1=a.count(1)
  k=count1+(len(a)-count1)//2
  for i in range(len(a)):
    if a.count(a[i])>=max_count:
      max_count=a.count(a[i])
      max_count_index=i
  index_to_reduce=0
  for i in a:
    if i>1:
      index_to_reduce=a.index(i)
      break
  if max_count>1:
    a[max_count_index]+=1
    a[index_to_reduce]-=1
  else:
    a[k]+=1
    a[index_to_reduce]-=1
  return a

Ετσι αποφάσισα να χρησιμοποιήσω τον εξής αλγόριθμο

αλλάζω το αρχικό ζάρι ένα στοιχείο κάθε φορά κατά 1 και βρίσκω ποια αλλαγή μου δίνει μέγιστο ώφελος αδιαφορόντας για το άθροισμα

στη συνέχεια στο νέο ζάρι αφαιρώ ένα από κάθε στοιχείο κάθε φορά ώστε να είμαι στο ίδιο άθροισμα και ελέγχω πάλι

άν βγάλω νικητή είναι οκ αλλιώς συνεχίζω

 

η συνάρτηση μου για το μέγιστο benefit είναι αυτή

def increase_die(a,:#ίδιο α και β 
  awins,bwins=decideWinner (a,
  max_benefit=bwins-awins
  index_to_increase=0
  for i in range((len()):
    b[i]+=1
    awins,bwins=decideWinner (a,
    b[i]-=1
    if bwins-awins>max_benefit:
      index_to_increase=i
      max_benefit=bwins-awins
  b[index_to_increase]+=1 
  return b

Την εκφώνιση της άσκησης τη διάβασες;

Βάζει ότι θέλεις στις έδρες.

Θα μπορούσε να βάλει [6,6,6,6,6,6].

Νικιέται;

Βασίλη το [6,6,6,6,6,6] νικιέται ας σου φένεται παράδοξο

decideWinner ([6,6,6,6,6,6],[4, 6, 6, 6, 7, 7])
(6, 12)
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δοκιμάζω και μια άλλη προσέγγιση, προσπαθώντας να υπάρχει μια λογική (πάνω κάτω αυτό που λέει και ο Zaytsev αλλά με συγκεκριμένο στόχο) αλλά θέλει αρκετή δουλειά και την προσέγγιση που θα έχεις στις υπόλοιπες περιπτώσεις, μέχρι να το ξαναπιάσω ίσως κάποιος ενδιαφέρεται.

 

Η λογική είναι ότι στοχεύεις το μεσαίο (ή το μεσαίο + 1 σε ζυγό αριθμό στοιχείων) νούμερο και βλέπεις αν μπορείς να έχεις πάνω από τα μισά στοιχεία μεγαλύτερα. Αυτό, μάλλον, με κάποιες προϋποθέσεις σου εξασφαλίζει ότι κερδίζεις... 

let createWinner = (loser) => {
	let length = loser.length,
		isEven = length % 2 === 0,
		total = 0, midNumber = 0, remainingNumbers = 0, targetNumber = 0;

	loser.map((num) => total += num);
	loser.sort( (a, => a - ;
	
	!isEven ? midNumber = (length - 1) / 2
			: midNumber = length / 2;

	remainingNumbers = length - midNumber;
	targetNumber = loser[midNumber] + 1;

	let easyWin = (midNumber * targetNumber + remainingNumbers) <= total;
	let winner = [];

	if (easyWin) {
		let remainder = total;
		for (let i=0;i<midNumber;i++) {
			winner.push(targetNumber);
			remainder -= targetNumber;
		}
		for (let ii = 1; ii <= remainingNumbers; ii++) {
			if (ii === remainingNumbers) {
				winner.push(remainder);
			} else if (remainder > (targetNumber + remainingNumbers - 1)) {
				winner.push(targetNumber);
				remainder -= targetNumber;
			} else {
				winner.push((remainder - remainingNumbers) + 1);
				remainder -= ((remainder - remainingNumbers) + 1);
			}
		}

		return winner;
		
	} else {
		//...
	}



}
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δεν άντεξα το έλυσα με πουστιά βάζοντας μια εξαίρεση στο κώδικα για το σφάλμα που έπαιρνα μιας και ήταν στο τελευταίο test. 

Τώρα μπορώ να δώ τις λύσεις των άλλων

Μόλις βρώ πως γίνονται τα spoiler θα ποστάρω μερικές

και για να μην ανυσηχούμε

Users attempted: 170 Users succeeded: 92

 

Δοκιμάζω και μια άλλη προσέγγιση, προσπαθώντας να υπάρχει μια λογική (πάνω κάτω αυτό που λέει και ο Zaytsev αλλά με συγκεκριμένο στόχο) αλλά θέλει αρκετή δουλειά και την προσέγγιση που θα έχεις στις υπόλοιπες περιπτώσεις, μέχρι να το ξαναπιάσω ίσως κάποιος ενδιαφέρεται.

 

Η λογική είναι ότι στοχεύεις το μεσαίο (ή το μεσαίο + 1 σε ζυγό αριθμό στοιχείων) νούμερο και βλέπεις αν μπορείς να έχεις πάνω από τα μισά στοιχεία μεγαλύτερα. Αυτό, μάλλον, με κάποιες προϋποθέσεις σου εξασφαλίζει ότι κερδίζεις... 

let createWinner = (loser) => {
	let length = loser.length,
		isEven = length % 2 === 0,
		total = 0, midNumber = 0, remainingNumbers = 0, targetNumber = 0;

	loser.map((num) => total += num);
	loser.sort( (a, => a - ;
	
	!isEven ? midNumber = (length - 1) / 2
			: midNumber = length / 2;

	remainingNumbers = length - midNumber;
	targetNumber = loser[midNumber] + 1;

	let easyWin = (midNumber * targetNumber + remainingNumbers) <= total;
	let winner = [];

	if (easyWin) {
		let remainder = total;
		for (let i=0;i<midNumber;i++) {
			winner.push(targetNumber);
			remainder -= targetNumber;
		}
		for (let ii = 1; ii <= remainingNumbers; ii++) {
			if (ii === remainingNumbers) {
				winner.push(remainder);
			} else if (remainder > (targetNumber + remainingNumbers - 1)) {
				winner.push(targetNumber);
				remainder -= targetNumber;
			} else {
				winner.push((remainder - remainingNumbers) + 1);
				remainder -= ((remainder - remainingNumbers) + 1);
			}
		}

		return winner;
		
	} else {
		//...
	}



}

Αυτό που λέει ο Zaytsev αν και φαίνεται λογικό δεν ισχύει και νομίζω άδικα θα κουραστείς 

winning_die([2, 2, 5, 5, 5, 5]) == [3, 3, 3, 3, 6, 6] Το δεύτερο νικάει το 1ο αν και χάνει σε 4 έδρες και κερδίζει σε 2

decideWinner([2, 2, 5, 5, 5, 5],[3, 3, 3, 3, 6, 6])
(16, 20) 
Αν καταλαβαίνω καλά την πρότασή του. 
Νομίζω ότι ο μόνος τρόπος για να προσεγγιστεί το πρόβλημα είναι μέσω της decideWinner
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!

Δημιουργία νέου λογαριασμού

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
  • Δημιουργία νέου...