Diana and Numbers: aiuto

[gaetanoM]

Sto provando a risolvere il problema in questione ma al massimo arrivo a 35%.

Qualcuno sa spiegarmi come mai sui casi di test funziona, su altri casi di test che mi trovo da solo funziona ma sul server di test… non va.

Se devo togliere una sola cifra la tolgo il più a sinistra possibile tale che la successiva sia maggiore. Nel caso devo togliere due cifre … ci sto provando ma senza successo!
Se devo togliere due cifre che mi danno 2 posso togliere due 1 oppure due 4 oppure due 7 oppure un 1 e un 3 e cosi via. Scelgo sempre la cifra piu a sinistra tale che la successiva sia maggiore, ma non mi va. Riesco con una approccio brute force ad arrivare al 35% O(n^2) ma mi va in TLE.

Qualche idea su come togliere due cifre?

Grazie

Il mio codice completo:

#include <bits/stdc++.h>

using namespace std;

//#pragma GCC optimize ("O3")

vector<int> normalize(vector<int>& digits) {
    int first_non_zero = 0;
    while (first_non_zero < digits.size() && digits[first_non_zero] == 0) {
        first_non_zero++;
    }
    if (first_non_zero == digits.size()) {
        return {0};
    }
    return vector<int>(digits.begin() + first_non_zero, digits.end());
}

bool isNumericallyGreater(const vector<int>& a, const vector<int>& b) {
    if (a.size() > b.size()) {
        return true;
    } else if (a.size() < b.size()) {
        return false;
    } else {
        for (int i = 0; i < a.size(); i++) {
            if (a[i] > b[i]) {
                return true;
            } else if (a[i] < b[i]) {
                return false;
            }
        }
        return false;
    }
}

pair<int, int> getIdxOnLeft(const vector<int> & first, const vector<int> & second, const vector<int> & digits) {
	int digitsLen = (int)digits.size();
	int len = (int)first.size();
	int idxFirst = -1, idxSecond = -1;
	
	for (int i = 0; i < len; i++) {
		int idx = first[i];
		if (idx < digitsLen - 1 && digits[idx] < digits[idx + 1]) {
			idxFirst = idx;
			break;
		}
	}
    if (idxFirst == -1 && len > 0) {
    	idxFirst = first[len - 1];
	}
	
	len = (int)second.size();
	for (int i = 0; i < len; i++) {
		int idx = second[i];
		if (idx < digitsLen - 1 && digits[idx] < digits[idx + 1]) {
			idxSecond = idx;
			break;
		}
	}
    if (idxSecond == -1 && len > 0) {
    	idxSecond = second[len - 1];
	}
	return make_pair(idxFirst, idxSecond);
}

pair<int, int> getIdxOnLeft(const vector<int> & first, const vector<int> & digits) {
	int digitsLen = (int)digits.size();
	int len = (int)first.size();
	int idxFirst = -1, idxSecond = -1, i;
	
	for (i = 0; i < len; i++) {
		int idx = first[i];
		if (idx < digitsLen - 1 && digits[idx] < digits[idx + 1]) {
			idxFirst = idx;
			break;
		}
	}
    if (idxFirst == -1 && len > 1) {
    	idxFirst = first[len - 1];
    	idxSecond = first[len - 2];
    	return make_pair(idxFirst, idxSecond);
	}
	
	for (; i < len; i++) {
		int idx = first[i];
		if (idx < digitsLen - 1 && digits[idx] < digits[idx + 1]) {
			idxSecond = idx;
			break;
		}
	}
    if (idxSecond == -1 && len > 1) {
    	idxSecond = first[len - 2];
	}
	return make_pair(idxFirst, idxSecond);
}

string solve(string num) {
    vector<int> digits;
	vector<vector<int>> freq(10);
    int sum = 0;
    for(int i = 0; i < num.length(); i++) {
    	int val = num[i] - '0';
        digits.push_back(val);
        sum += digits.back();
        freq[val].push_back(i);
    }

    if (sum % 3 == 0) {
        vector<int> normalized = normalize(digits);
        if (normalized.size() == 1 && normalized[0] == 0) {
            return "0";
        }
        string result;
        for (int digit : digits) {
            result += to_string(digit);
        }
        return result;
    }

    int remainder = sum % 3;
    vector<int> pos;
    for (int i = 0; i < digits.size(); i++) {
    	int val = digits[i] % 3;
        if (val == remainder) pos.push_back(i);
    }

    vector<int> best = {-1};
    auto construct = [&](unordered_set<int> remove) {
        vector<int> res;
        for (int i = 0; i < digits.size(); i++) {
            if (remove.find(i) == remove.end()) {
                res.push_back(digits[i]);
            }
        }
        res = normalize(res);
        if (res.size() == 1 && res[0] == 0 && sum % 3 != 0) {
            res = {-1};
        }
        if (res != vector<int>{-1} && (best == vector<int>{-1} || isNumericallyGreater(res, best))) best = res;
    };

	int digitsLen = (int)digits.size();
	int len = (int)pos.size();
	bool done = false;
	for (int i = 0; i < len; i++) {
		int idx = pos[i];
		if (idx < digitsLen - 1 && digits[idx] < digits[idx + 1]) {
			construct({idx});
			done = true;
			break;
		}
	}
    if (done == false && len > 0) {
    	construct({pos[len - 1]});
	}

    if (remainder == 2) {
    	// 1 4 7
    	if (freq[1].size() > 1) {
    		auto ret = getIdxOnLeft(freq[1], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
    	if (freq[4].size() > 1) {
    		auto ret = getIdxOnLeft(freq[4], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
    	if (freq[7].size() > 1) {
    		auto ret = getIdxOnLeft(freq[7], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
		if (freq[3].size() > 0 && freq[5].size() > 0) {
			auto ret = getIdxOnLeft(freq[3], freq[5], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
		if (freq[5].size() > 0 && freq[9].size() > 0) {
    		auto ret = getIdxOnLeft(freq[5], freq[9], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
    }
    if (remainder == 1) {
    	// 2 5 8
    	if (freq[2].size() > 1) {
    		auto ret = getIdxOnLeft(freq[2], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
    	if (freq[5].size() > 1) {
    		auto ret = getIdxOnLeft(freq[5], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
    	if (freq[8].size() > 1) {
    		auto ret = getIdxOnLeft(freq[8], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
		if (freq[1].size() > 0 && freq[3].size() > 0) {
    		auto ret = getIdxOnLeft(freq[1], freq[3], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
		if (freq[4].size() > 0 && freq[6].size() > 0) {
    		auto ret = getIdxOnLeft(freq[4], freq[6], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
		if (freq[7].size() > 0 && freq[9].size() > 0) {
    		auto ret = getIdxOnLeft(freq[7], freq[9], digits);
    		if (ret.first != -1 && ret.second != -1)
    			construct({ret.first, ret.second});
		}
    }
     
    if (best == vector<int>{-1}) {
        return "-1";
    }

    string result;
    for (int digit : best) {
        result += to_string(digit);
    }
    return result;
}

int main() {
	// decommenta le due righe seguenti se vuoi leggere/scrivere da file
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    string num;
    cin >> n;
    for(int i = 0; i < n; i++) {
    	cin >> num;
    	cout << solve(num) << endl;
	}
    
    return 0;
}

[qwfwq]

Invece di procedere con il valore di ogni cifra per calcolarne la frequenza, freq[val].push_back(i), prova con la frequenza relativa al resto di ogni cifra freq[val%3].push_back(i). In questo modo
sommando le cifre della stringa se la somma %3 è uguale a 1 devi rimuovere o una cifra % 3 = 1 oppure 2 cifre % 3 = 2, se invece la somma % 3 è uguale a 2 o una cifra % 3 = 2 oppure 2 cifre % 3 = 1 e le cifre da rimuovere le puoi determinare dalla frequenza dei resti.

[gaetanoM]

grazie di cuore per la risposta. In una precedente versione del programma avevo esattamente fatto questo: calcolato due vettori con i resti a 1 e 2 (i soli possibili) Togliere una sola cifra non è un problema, in quanto credo bisogna togliere quella che è minore rispetto alla successiva. Questo lo si fa in O(n). Il guaio è quando si devono togliere due cifre: esempio 100888 il resto della somma modulo 3 è 1, ma non si puo togliere 1 bensi due 8 solo in questo modo otteniamo 1008 invece di 888. Il metodo brute force usato è banale ma ha una complessità di O(n^2): impraticabile. Vado in TLE per 0,09 secondi. Trattasi di due for uno dentro l’altro. Ciò che mi hai suggerito lo apprezzo moltissimo e ti sono grato. Purtroppo il problema è come ridurre la complessità quando devo togliere due cifre. Tra un po aggiusto la domanda con il vecchio codice, dove anzichè utilizzare freq uso due vettori che fanno esattamente quanto da te suggerito.

Sono circa 3 mesi che ci sto sbattendo, ma non mi arrendo. O forse no!?!?!?

Il vecchio codice: 35% ma TLE

#include <bits/stdc++.h>

using namespace std;

//#pragma GCC optimize ("O3")


vector<int> normalize(vector<int>& digits) {
    int first_non_zero = 0;
    while (first_non_zero < digits.size() && digits[first_non_zero] == 0) {
        first_non_zero++;
    }
    if (first_non_zero == digits.size()) {
        return {0};
    }
    return vector<int>(digits.begin() + first_non_zero, digits.end());
}

bool isNumericallyGreater(const vector<int>& a, const vector<int>& b) {
    if (a.size() > b.size()) {
        return true;
    } else if (a.size() < b.size()) {
        return false;
    } else {
        for (int i = 0; i < a.size(); i++) {
            if (a[i] > b[i]) {
                return true;
            } else if (a[i] < b[i]) {
                return false;
            }
        }
        return false;
    }
}

string solve(string num) {
    vector<int> digits;
    int sum = 0;
    for (char c : num) {
        digits.push_back(c - '0');
        sum += digits.back();
    }

    if (sum % 3 == 0) {
        vector<int> normalized = normalize(digits);
        if (normalized.size() == 1 && normalized[0] == 0) {
            return "0";
        }
        string result;
        for (int digit : digits) {
            result += to_string(digit);
        }
        return result;
    }

    int remainder = sum % 3;
    vector<int> pos1, pos2;
    for (int i = 0; i < digits.size(); i++) {
        if (digits[i] % 3 == remainder) pos1.push_back(i);
        if (digits[i] % 3 == (3 - remainder)) pos2.push_back(i);
    }

    vector<int> best = {-1};
    auto construct = [&](unordered_set<int> remove) {
        vector<int> res;
        for (int i = 0; i < digits.size(); i++) {
            if (remove.find(i) == remove.end()) {
                res.push_back(digits[i]);
            }
        }
        res = normalize(res);
        if (res.size() == 1 && res[0] == 0 && sum % 3 != 0) {
            res = {-1};
        }
        if (res != vector<int>{-1} && (best == vector<int>{-1} || isNumericallyGreater(res, best))) best = res;
    };

    for (int pos : pos1) {
        construct({pos});
    }

	// qui ho una complessità quadratica: da diminuire
    if (pos2.size() >= 2) {
        for (int i = 0; i < pos2.size(); i++) {
            for (int j = i + 1; j < pos2.size(); j++) {
                construct({pos2[i], pos2[j]});
            }
        }
    }

    if (best == vector<int>{-1}) {
        return "-1";
    }

    string result;
    for (int digit : best) {
        result += to_string(digit);
    }
    return result;
}

int main() {
	// decommenta le due righe seguenti se vuoi leggere/scrivere da file
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    string num;
    cin >> n;
    for(int i = 0; i < n; i++) {
    	cin >> num;
    	cout << solve(num) << endl;
	}
    
    return 0;
}

[qwfwq]

Non è molto chiaro la procedura di rimozione delle cifre con resto 1 0 2 e comunque non ho approfondito il codice in questione.
Ad ogni modo, dovendo rimuovere una o due cifre, serve un ciclo per rimuovere ogni cifra, partendo da sinistra, che sia minore di quella che segue e nel caso in cui non è possibile farlo basta semplicemente rimuovere l’ultima da destra.

[gaetanoM]

Ti ringrazio, ma provando anche così mi va in TLE per 0,09 secondi. Il tuo suggerimento è valido, il mio codice è errato.

Grazie ancora