37ος ΠΔΠ Α' Φάση
Ψάχνοντας τους ανταγωνιστές (finding)

Επεξήγηση εκφώνησης

Σε έναν δρόμο έχουμε τις θέσεις \(1, 2, \ldots , N\) και δύο σπίτια σε δύο άγνωστες θέσεις \(A\) και \(B\) (με \(A < B\)). Σκοπός είναι να βρούμε τις θέσεις \(A\) και \(B\). Ο περιορισμός που έχουμε είναι ότι σε κάθε βήμα μπορούμε να κάνουμε μία ερώτηση της μορφής query(X) που μας επιστρέφει το άθροισμα των αποστάσεων από το \(X\) στα \(A\) και \(B\), δηλαδή

Βέλτιση λύση (100%)

Ξεκινάμε με κάποιες βασικές παρατηρήσεις:

Παρατήρηση 1η: Αν διαλέξουμε ένα \(X\) που είναι αριστερά του \(A\) (και του \(B\)), τότε έχουμε ότι

Παρατήρηση 2η: Αν διαλέξουμε ένα \(X\) που είναι δεξιά του \(A\) και αριστερά του \(B\), τότε έχουμε ότι

(Παρατηρήστε ότι αυτή η τιμή είναι ανεξάρτητη του \(X\))

Παρατήρηση 3η: Αν διαλέξουμε ένα \(X\) που είναι στα δεξιά του \(B\) (και του \(A\)), τότε έχουμε ότι

(Αυτή την παρατήρηση δεν θα την χρειαστούμε, αλλά την βάζουμε για να καταλάβουμε τι γίνεται σε όλο τον δρόμο)

Επειδή, το \(X\) μας είναι πάντα γνωστό (εμείς το διαλέγουμε), οι τιμές της πρώτης και τρίτης παρατήρησης μας δίνουν το άθροισμα \(A + B\) και οι τιμές της δεύτερης παρατήρησης μας δίνουν την διαφορά \(B - A\). Αν γνωρίζουμε το άθροισμα και την διαφορά δύο αριθμών, τότε μπορούμε να βρούμε τους αριθμούς (θα δούμε τις λεπτομέρειες παρακάτω).

Ας δούμε πρώτα πώς θα βρούμε κάποια \(X\) της πρώτης και δεύτερης παρατήρησης. Για το πρώτο είναι απλό, το \(X = 1\) είναι στα αριστερά (ή πάνω στο) \(A\) και λαμβάνουμε ότι

Για το δεύτερο, είναι λίγο πιο πολύπλοκο. Παρατηρούμε ότι από την πρώτη ερώτηση που κάναμε έχουμε ότι \(A + B = d_1 + 2\), δηλαδή ξέρουμε το άθροισμά τους. Αλλά το άθροισμα, θα είναι σίγουρα στα δεξιά του \(B\), επομένως δεν μας βοηθάει. Αλλά, ο μέσος όρος \((A + B)/2\) είναι μεταξύ τους.¹ Επομένως, έχουμε ότι

Αφαιρώντας κατά μέλη τις σχέσεις για τα \(d_1\) και \(d_2\), έχουμε ότι

Αντίστοιχα, προσσθέτοντας κατά μέλη τις δύο σχέσεις, έχουμε ότι

Δηλαδή με δύο ερωτήματα βρίσκουμε τις θέσεις \(A\) και \(B\):

#include "findinglib.h"

#include <iostream>

int main() {
   bool more_testcases = true;
   while (more_testcases) {
      int d1 = query(1);
      int d2 = query(d1/2 + 1);
      
      int A = (d1 - d2) / 2 + 1;
      int B = (d1 + d2) / 2 + 1;
      more_testcases = answer(A, B);
   }
   return 0;
}

Στα τρία πρώτα testcases που έχουμε πρόσβαση στην διαφορά \(D = B - A\), χρειαζόμαστε μόνο το πρώτο query. Άρα, αλλάζουμε τον κώδικα ως εξής:

#include "findinglib.h"

int main() {
   bool more_testcases = true;
   while (more_testcases) {
      int d1 = query(1);
      int d2 = (getSubtask() <= 3) ? getD() : query(d1/2 + 1);
      
      int A = (d1 - d2) / 2 + 1;
      int B = (d1 + d2) / 2 + 1;
      more_testcases = answer(A, B);
   }
   return 0;
}

Αυτή η λύση λαμβάνει το 100%.

Λύση με δυαδική αναζήτηση

Χρησιμοποιώντας τις παραπάνω τρεις παρατηρήσεις, μπορούμε να δούμε ότι η συνάρτηση query(X) είναι αρχικά φθίνουσα και μετά αύξουσα. Επομένως, μπορούμε να χρησιμοποιήσουμε δυαδική (ή τριαδική) αναζήτηση για να βρούμε τα σημεία \(A\) και \(B\). Θα δούμε δύο μορφές για αυτή.

1η Μορφή: Έχουμε ότι query(X) > query(X+1) αν και μόνο αν \(X < A\). Επομένως, για να βρούμε το \(A\) αρκεί να βρούμε το πρώτο σημείο που δεν ικανοποιείται αυτή η σχέση.

#include "findinglib.h"

#include <map>

std::map<int, int> queries;

// Αποφεύγουμε να κάνουμε δύο φορές το ίδιο query.
int do_query(int X) {
   if (queries.find(X) == queries.end()) queries[X] = query(X);
   return queries[X];
}

int main() {
   bool more_testcases = true;
   while (more_testcases) {
      int N = getN();
      queries.clear();
      int query_1 = do_query(1);
      int st = 1, en = N - 1;
      while (st < en) {
         int md = (st + en) / 2;
         int query_md = do_query(md);
         int query_md_plus = do_query(md + 1);
         if (query_md > query_md_plus) st = md + 1; 
         else en = md;
      }
      int A = st;
      int B = query_1 + 2 - A;
      more_testcases = answer(A, B);
   }
   return 0;
}

Η λύση αυτή χρησιμοποιεί το πολύ 21 queries και περνάει τα υποπροβλήματα 4,5,6.

2η Μορφή: Από τις παρατηρήσεις, έχουμε ότι

αν και μόνο αν \(X \leq A\). Επομένως, ξανά μπορούμε να βρούμε το \(A\) ως το πρώτο σημείο που δεν ικανοποείται αυτή η σχέση. Παρατηρήστε ότι σε κάθε επανάληψη κάνουμε μόνο ένα query (αντί για 2).

#include "findinglib.h"

int main() {
   bool more_testcases = true;
   while (more_testcases) {
      int N = getN();
      int query_1 = query(1);
      int st = 1, en = N;
      while (st < en) {
         int md = (st + en + 1) / 2;
         int query_md = query(md);
         if (query_md == query_1 - 2 * (md - 1)) st = md; 
         else en = md - 1;
      }
      int A = st;
      int B = query_1 + 2 - A;
      more_testcases = answer(A, B);
   }
   return 0;
}

Η λύση αυτή χρησιμοποιεί το πολύ 11 queries και περνάει τα υποπροβλήματα 4,5,6,7.

Άλλες λύσεις

Μπορούμε επίσης να βρούμε αυτά τα σημεία με γραμμική αναζήτηση (με \(N\) queries) και με την μέθοδο sqrt (σε περίπου \(\sqrt{N}\) queries).