Finanza Creativa (bilancio) 80/100

[alenygam_real]

Oggi mi trovo alle prese con il problema bilancio. Purtroppo la mia soluzione fa solo 80/100 e va in timeout nell’ultimo subtask. È da 3 ore che provo a ottimizzarla ma non sono arrivato ad una soluzione concreta

Questo è il mio codice attuale.

#include <stdio.h>
#include <assert.h>
#include <algorithm>

#define MAXN 1000000

using namespace std;

void bianchetta(int N, int K, int U[], int C[]) {
	int Ci = 0;
	int lastIndex = -1;
	while (Ci < N - K) {
		int minIndex = lastIndex + 1;
		int end = min(lastIndex + 1 + K, N - (N - K - Ci));
		for (int i = end; i > lastIndex; i--) {
			minIndex = U[i] <= U[minIndex] ? i : minIndex;
		}
		C[Ci] = U[minIndex];
		lastIndex = minIndex;
		Ci++;
	}
}


int U[MAXN], C[MAXN];

int main() {
    FILE *fr, *fw;
    int N, K, i;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    assert(2 == fscanf(fr, "%d%d", &N, &K));
    for(i=0; i<N; i++)
        assert(1 == fscanf(fr, "%d", &U[i]));

    bianchetta(N, K, U, C);
    for(i=0; i<N-K; i++)
        fprintf(fw, "%d ", C[i]);
    fprintf(fw, "\n" );
    fclose(fr);
    fclose(fw);
    return 0;
}

[v.bizzarri]

L’ho risolto anni fa e non ricordo tutto ma una idea è quella di far si che la sequenza che rimane cominci il più possibile con le cifre più piccole presenti nella sequenza originale.
Potrebbe servire un array cifre[10][] con le posizioni degli zeri, degli uni, …
Nel primo esempio
5 2
1 9 5 0 3
non posso far iniziare la sequenza finale con 0 (serviva un K=3) mi devo accontentare di farla iniziare per 1 e con K che rimane 2 da qui posso raggiungere lo 0 e lo faccio ma K va a 0 e mi tengo tutto il resto dopo lo 0; quindi 103.

[alenygam_real]

Ho appena provato ad implementare la tua soluzione, ma l’esercizio purtroppo sigh fa ancora 80/100. Credo che peró al posto della funzione search che ho implementato io si possa usare la ricerca binaria

#include <stdio.h>
#include <assert.h>
#include <vector>

#define MAXN 1000000

using namespace std;

int arrivedIndex[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

int search(int key, vector<int> arr, int lastIndexTaken, int end) {
	for (int i = arrivedIndex[key]; i < (int)arr.size() && arr[i] <= end; i++) {
		if (arr[i] > lastIndexTaken) {
			arrivedIndex[key] = i + 1;
			return arr[i];
		}
	}
	return -1;
}

void bianchetta(int N, int K, vector<int> U[], int C[]) {
	int lengthLeft = N - K;
	int lastIndexTaken = -1;
	int Ci = 0;
	while (lengthLeft > 0) {
		int end = N - lengthLeft;
		for (int i = 0; i < 10; i++) {
			int index = search(i, U[i], lastIndexTaken, end);
			if (index != -1) {
				lastIndexTaken = index;
				C[Ci] = i;
				Ci++;
				lengthLeft--;
				break;
			}
		}
	}
}


int C[MAXN];
// No two items in matrix are the same, because they are indexes
// Also every subarray is automatically sorted for the same reason.
vector<int> U[10];

int main() {
    FILE *fr, *fw;
    int N, K, i;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    assert(2 == fscanf(fr, "%d%d", &N, &K));
    for(i=0; i<N; i++) {
	int tmp;
	assert(1 == fscanf(fr, "%d", &tmp));
	U[tmp].push_back(i);
    }

    bianchetta(N, K, U, C);
    for(i=0; i<N-K; i++)
        fprintf(fw, "%d ", C[i]);
    fprintf(fw, "\n" );
    fclose(fr);
    fclose(fw);
    return 0;
}

[alenygam_real]

Sono riuscito ad implementarlo con la ricerca binaria, ma purtroppo questo esercizio mi da ancora 80/100, nonostante gli altri test case siano piú veloci adesso. Secondo me si deve trovare un modo per escludere alcune i da questo loop.

for (int i = 0; i < 10; i++) {
			int index = search(i, U[i], lastIndexTaken, end);
			if (index != -1) {
				lastIndexTaken = index;
				C[Ci] = i;
				Ci++;
				lengthLeft--;
				break;
			}
		}

Il fatto é che purtroppo non mi viene in mente nulla…

Questa é la mia implementazione della ricerca binaria (iterativa)
La ricerca binaria viene effettuata su ogni sotto array che contiene gli indici delle varie cifre.

int lastIndexesByKey[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

int search(int key, vector<int> arr, int lastIndexTaken, int end) {
	int left = lastIndexesByKey[key];
	int right = (int)arr.size() - 1;
	while (left <= right) {
		int mid = (right + left) / 2;

		int val = arr[mid];
		int prevVal = mid > 0 ? arr[mid - 1] : lastIndexTaken;
		if (val > lastIndexTaken && prevVal <= lastIndexTaken && val <= end) {
			lastIndexesByKey[key] = mid + 1;
			return val;
		}

		if (val <= lastIndexTaken) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return -1;
}

[v.bizzarri]

Se ho visto bene la bianchetta termina solo quando lengthLeft diventa 0 ma dovrebbe terminare anche quando ho tolto K cifre!

esempio
5 2
2 2 0 3 3

tolgo le prime 2 K va a 0 e termino subito stampando ciò che rimane della stringa iniziale.
Controlla se il tuo fa così o meno.

[alenygam_real]

Il mio algoritmo risolve correttamente il problema, ma purtroppo é lento. Implementando la funzione che quando ho eliminato abbastanza cifre prende le restanti mi da pure degli output sbagliati, e non mi avvicina ad una soluzione 100/100

[v.bizzarri]

Io suggerivo un algoritmo che termina quando si verifica uno dei due, inoltre

@alenygam_real

Implementando la funzione che quando ho eliminato abbastanza cifre prende le restanti mi da pure degli output sbagliati,

prendo prima quelli che ho già selezionato (se ce ne sono) e poi eventualmente i restanti.
esempio
7000 2
5 1 5 1 8 8 8 8 8 …
scarto il 5 e seleziono un 1 k va a 1
scarto il 5 e seleziono un 1 k va a 0
esco per k=0
e stampo 1 1 8 8 8 …
mentre
6 3
1 1 4 1 5 5
prendo il primo 1 K rimane 3
prendo il secondo 1 K rimane 3
scarto il 4 k va a 2
prendo il terzo1 K rimane 2
ma ho trovato N-K cifre esco
e stampo solo quelle prese cioè
1 1 1

[alenygam_real]

Mi sono fatto aiutare da un altro al di fuori dal forum, e mi sono accorto di aver seguito un approccio abbastanza diverso da quello ottimale.
La nuova idea risolutiva è:

• Inizializzo C[0] = U[0]
• Itero per il resto dell’Array U
• Controllo se il valore di U che sto prendendo in considerazione é minore dell’ultimo C che ho preso, e per ognuno che é minore diminusco K di 1
• Se non ho preso tutti i valori da prendere, C attuale = U attuale, altrimenti diminuisco K di 1
• stampo C

Questa soluzione fa 100/100, e questo è il codice per essere più comprensibile

#include <iostream>
#include <vector>

using namespace std;

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, K;
	cin >> N >> K;

	vector<int> U(N);

	vector<int> C(N-K);

	for (int i = 0; i < N; i++) {
		cin >> U[i];
	}

	int len = N - K - 1;
	C[0] = U[0];
	int Ci = 0;

	int i = 1;
	while (i < N) {
		while (Ci >= 0 && U[i] < C[Ci] && K > 0) {
			Ci--;
			K--;
		}
		if (Ci < len) {
			Ci++;
			C[Ci] = U[i];
		} else {
			K--;
		}
		i++;
	}

	for (int c: C) {
		cout << c << " ";
	}

	return 0;
}

[v.bizzarri]

La tua soluzione modificata in modo da verificare le due condizioni può essere questa:

#pragma GCC optimize ("Ofast") 
#pragma GCC optimization ("unroll-loops")
#include <stdio.h>
#include <vector>
#define MAXN 1000000

using namespace std;
// No two items in matrix are the same, because they are indexes
// Also every subarray is automatically sorted for the same reason.
int cfmin, cfmax;
int U[10][MAXN];
int C[MAXN];
int ct[10];
int arrivedIndex[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
int rim;
int start;
int V[MAXN];
int search(int key,  int lastIndexTaken, int end) {//vector<int> //int arr[],
	int* arr = U[key];
	for (int i = arrivedIndex[key]; i <ct[key]  && arr[i] <= end; i++) {//(int)arr.size()
		if (arr[i] > lastIndexTaken) {
			arrivedIndex[key] = i + 1;
			return arr[i];
		}
	}
	return -1;
}

void bianchetta(int N, int K) {//, vector<int> U[], int C[]
	int lengthLeft = N - K;
	int lastIndexTaken = -1;
	int Ci = 0;
	while (lengthLeft > 0 && rim) {
		int end =  N - lengthLeft; //oppure end=start + rim; vanno bene entrambe
		for (int i = cfmin; i <=cfmax; i++) {
			int index = search(i,  lastIndexTaken, end);//U[i],
			if (index != -1) {
				lastIndexTaken = index;
				rim -= index - start;
				start = index + 1;
				C[Ci] = i;
				Ci++;
				lengthLeft--;
				break;
			}
		}
	}
	for (int i = 0; i < Ci; i++)
		printf("%d ", C[i]);
	int resto = N - K - Ci;
	for(int i=N-resto;i<N;i++)
		printf("%d ", V[i]);
}

int main() {
	FILE* fr, * fw;
	int N, K, i;

	fr = fopen("input.txt", "r");
	fw = freopen("output.txt", "w",stdout);
	fscanf(fr, "%d%d", &N, &K);
	rim = K;
	for (i = 0; i < N; i++) {
		int tmp;
		fscanf(fr, "%d", &tmp);
		U[tmp][ct[tmp]++]=i;
		V[i] = tmp;
	}
	while (!ct[cfmin])
		cfmin++;
	cfmax = 9;
	while (!ct[cfmax])
		cfmax--;
	bianchetta(N, K);//, U, C)
	//for (i = 0; i < N - K; i++)
	//	fprintf(fw, "%d ", C[i]);
	//fprintf(fw, "\n");
	fclose(fr);
	fclose(fw);
	return 0;
}

e fa 100/100, poi per andare più veloci servono le funzioni di fast I/O e magari anche la ricerca binaria.

[alenygam_real]

Si impara qualcosa di nuovo ogni giorno