Problemi con chess tournament

Aiuto
#1

Buonasera a tutti,
stavo provando a risolvere l’esercizio chess tournament solo che non riesco a totalizzare 100/100.
Il primo tentativo che ho svolto mi risolve a 58/100 perchè mi da fuori tempo massimo (ecco il codice):

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;


int main() {
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N;
    int n = 0;
    int max = 0;
    fin >> N;
    vector<int> S;
    for (int i = 0; i < N; i++) {
        int a;
        fin >> a;
        S.push_back(a);
    }


    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
            n = abs(S[i] - S[j]) + abs(i - j);
            if (n > max) {
                max = n;
            }
        }
    }
    fout << max;

Allora ho ragionato sulla soluzione e ho visto che il risultato si poteva scrivere come l’elemento massimo (max) - elemento minimo (min) più la differenza dei due indici ed ho scritto questo:

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;


int main() {
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N;
    int n = 0;
    int max = 0;
    fin >> N;
    vector<int> S;
    for (int i = 0; i < N; i++) {
        int a;
        fin >> a;
        S.push_back(a);
    }

    int minIndex = 0;
    int maxIndex = 0;
    int min = S[0];
    int max = S[0];


    for (int i = 0; i < N; i++) {
        if (max < S[i]) {
            max = S[i];
            maxIndex = i;
        }
    }
    for (int i = N - 1; i >= 0; i--) {
        if (min > S[i]) {
            min = S[i];
            minIndex = i;
        }
    }
    n = abs(max-min) + abs(maxIndex-minIndex);
    fout << n;

Ma questa volta mi da 25/100 perchè il subtask 2 presenta alcuni test case con output errato mentre l’ultimo subtask da tutti output errati. Sapreste dirmi dove sbaglio?
Grazie Mille!

#2

Il massimo di |i-j| + |S[i]-S[j]| non è detto che sia quello che calcoli tu, che è |i_{S_max}-i_{S_min}| + |S_max - S_min|. Provalo per esempio su 0, 2, 1, 1.

#3

ok quindi se ho capito bene il problema è che non sto considerando quali dei due numeri sia a destra/sinistra rispetto all’altro giusto?
Ho provato ad aggiungere la seguente parte di codice:

for (int i = N - 1; i >= 0; i--) {
        if (max2 < S[i]) {
            max2 = S[i];
            maxIndex2 = i;
        }
    }
    for (int i = 0; i < N; i++) {
        if (min2 > S[i]) {
            min2 = S[i];
            minIndex2 = i;
        }
    }
    n2 = abs(max2-min2) + abs(maxIndex2-minIndex2);

    if (n > n2) {
        fout << n;
    }
    else {
        fout << n2;
    }

che controlla il vettore al contrario in modo che calcoli sia se il massimo si trova a destra si a sinistra del minimo (in pratica per essere sicuro di trovare la massima distanza dei due indici) ma mi da sempre 25/100 con quasi i medesimi testcase sbagliati… allora mi sa che non ho ben capito cosa intendi :sweat_smile:

#4

Ho fatto un’altra modifica poichè mi sono reso conto che inizializzare tutto a 0 e S[0] non era corretto in quando se il numero era a fine ciclo ed era uguale per esempio a S[0] l’indice non cambiava per cui sono bloccato a questo punto:

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;


int main() {
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N;
    fin >> N;
    vector<int> S;
    for (int i = 0; i < N; i++) {
        int a;
        fin >> a;
        S.push_back(a);
    }

    int minIndex = N - 1;
    int maxIndex = 0;
    int min = S[N - 1];
    int max = S[0];
    int n = 0;
    
    int minIndex2 = 0;
    int maxIndex2 = N - 1;
    int min2 = S[0];
    int max2 = S[N - 1];
    int n2 = 0;


    for (int i = 0; i < N; i++) {
        if (max < S[i]) {
            max = S[i];
            maxIndex = i;
        } 
    }
    for (int i = N - 1; i >= 0; i--) {
        if (min > S[i]) {
            min = S[i];
            minIndex = i;
        }
    }
    n = abs(max-min) + abs(maxIndex-minIndex);
    for (int i = N - 1; i >= 0; i--) {
        if (max2 < S[i]) {
            max2 = S[i];
            maxIndex2 = i;
        }
    }
    for (int i = 0; i < N; i++) {
        if (min2 > S[i]) {
            min2 = S[i];
            minIndex2 = i;
        }
    }
    n2 = abs(max2-min2) + abs(maxIndex2-minIndex2);

    if (n > n2) {
        fout << n;
    }
    else {
        fout << n2;
    }

ma non si smuove da 25/100.

#5

Ciao, no, il problema è che non è detto che |i-j| e |S[i]-S[j]| abbiamo il massimo sulla stessa coppia di indici (i, j). Il tuo algoritmo trova la coppia (i_{S_{max}}, i_{S_{min}}) che rende massimo il modulo |S[i]-S[j]|, ma questa coppia non è (necessariamente) quella che rende massima la somma |i-j| + |S[i]-S[j]|.

Nel caso 0, 2, 1, 1 per |i-j| hai i valori

\begin{matrix} & 0 & 1 & 2 & 3\\ 0 & 0 & 1 & 2 & 3\\ 1 & 1 & 0 & 1 & 2\\ 2 & 2 & 1 & 0 & 1\\ 3 & 3 & 2 & 1 & 0 \end{matrix}

(ad esempio: per (i, j) = (1, 3) il valore di |i-j| è 2), mentre per |S[i]-S[j]| hai i valori

\begin{matrix} & 0 & 2 & 1 & 1\\ 0 & 0 & 2 & 1 & 1\\ 2 & 2 & 0 & 1 & 1\\ 1 & 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 0 & 0 \end{matrix}

(ad esempio per (i, j) = (1, 3) il valore di |S[1] - S[3]| è 1) e pertanto la somma |i-j| + |S[i]-S[j]| è

\begin{matrix} 0 & 1 & 2 & 3\\ 1 & 0 & 1 & 2\\ 2 & 1 & 0 & 1\\ 3 & 2 & 1 & 0 \end{matrix} + \begin{matrix} 0 & 2 & 1 & 1\\ 2 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 \end{matrix} = \begin{matrix} 0 & 3 & 3 & 4\\ 3 & 0 & 2 & 3\\ 3 & 2 & 0 & 1\\ 4 & 3 & 1 & 0 \end{matrix},

da cui vedi che il massimo per |i-j| + |S[i]-S[j]| è 4 e si ottiene per la coppia (i, j) = (0, 3), mentre il massimo per S[i]-S[j] è 2 e si ottiene per la coppia (i, j) = (0, 1), per la quale però |i-j| + |S[i]-S[j]| = 3 < 4. Vedi quindi che la coppia che rende massimo il modulo |S[i]-S[j]| non è necessariamente la coppia che rende massima la somma di moduli |i-j| + |S[i]-S[j]|.

In conclusione, non puoi risolvere il problema massimizzando |S[i]-S[j]| senza tener conto dei corrispondenti valori di |i-j|.

D’altra parte, se vuoi risolvere il problema in O(n), dato che in O(n^2) vai in TLE, devi trovare il modo di diagonalizzare \max_{(i, j)}(|i-j|+|S[i]-S[j]|) riscrivendolo in termini di funzioni di una sola variabile, in modo da fare un solo ciclo anziché due cicli annidati come nella tua prima soluzione, che è corretta, ma che va fuori tempo massimo perché O(n^2).

#6

Il suggerimento è quello di calcolare abs(S[i] - S[j]) + abs(i – j) > 0 senza ricorrere alla funzione abs() per cui matematicamente si producono 4 possibilità:

S[i] + i > S[j] + j per trovare la somma max{}

S[i] + i < S[j] + j per trovare la somma min{}

S[i] – i > S[j] – j per trovare la differenza max{}

S[i] – i < S[j] – j per trovare la differenza min{}

In questa maniera si ottiene lo stesso risultato con un’unica scansione del vettore S[].