-RISOLTO-Dubbi su Gift Delivery (pasi)


#1

Ciao, ho provato a risolvere pasi, tuttavia quando lo sottopongo mi da corretti solo gli esempi, i primi testcase sono sbagliati e poi iniziano ad andare tutti fuori tempo. Potreste aiutarmi a capire dove sbaglio, o nel caso scrivendo un indizio o la soluzione stessa?
Il mio approccio è stato:
K è un numero pari poichè se fosse dispari non potrei tornare giusto al quartiere generale se non saltando dei turni in qualche posto, il che abbasserebbe il numero massimo di regali. Calcolo quindi il percorso lungo K/2 che mi da un numero maggiore di regali. Faccio uso di una funzione ricorsiva, questa per ogni mossa dovrebbe “abbassarmi la complessità del problema”, in quanto va a trovare il percorso migliore lungo K/2-1, poi K/2-2 e così via evitando di ripetere calcoli in più.
Il mio codice è questo(chiedo scusa che posto il codice in maniera così cruda ma essendo nuovo non sono ancora pratico di come si fanno “box” in cui scrivere il codice):

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXN 100

// V e' la mia matrice, K,R,C dal testo
int V[MAXN][MAXN];
int K,R,C,x,y;

// definisco la funzione ricorsiva che non cerca OGNI mezzo cammino disponibile
// ma riduce la complessita' del problema riducendo il numero di strade da vedere in
// quanto gia' percorse
float fun(int n, int r, int c, float current_somma){
	float m1,m2,m3,m4;
	// se ho finito il cammino ritorno la somma e tolgo la meta' dell'ultimo poiche' esso verra' visitato una
	// volta sola, togliendone meta' quando alla fine moltiplico per due i conti tornano
	if(n==0)return current_somma-V[r][c]/2.0;
	// metto a 0 i quattro cammini cosi' poi posso confrontarli senza if per vedere se sono stati calcolati
	m1=m2=m3=m4=0;
	// per ogni strada disponibile che posso prendere mi chiedo, rchiamando fun, quale sia il percorso migliore lungo n-1
	// cosi' facendo non guardo ogni percorso ma cerco via via la strada che mi aumenta maggiormente la somma
	if(r<R-1)
		m1=fun(n-1,r+1,c,current_somma+V[r+1][c]);
	if(r>0)
		m2=fun(n-1,r-1,c,current_somma+V[r-1][c]);
	if(c<C-1)
		m3=fun(n-1,r,c+1,current_somma+V[r][c+1]);
	if(c>0)
		m4=fun(n-1,r,c-1,current_somma+V[r][c-1]);
	
	// cerco il maggiore delle quattro strade
	m1= m1>m2?m1:m2;
	m1= m1>m3?m1:m3;
	m1= m1>m4?m1:m4;
	return m1;
}

float main(){
	int i,r,c,j;
	// prendo gli input
	scanf("%d %d %d %d %d",&R,&C,&r,&c,&K);
	for(i=0;i<R;++i)
		for(j=0;j<C;++j)
			scanf("%d",&V[i][j]);
	y=r-1;
	x=c-1;
	// stampo il risultato che e' il doppio della meta' del percorso che vado a cercare
	printf("%d\n",(int)(2*fun(K/2,r-1,c-1,0)));
	return 0;
}

#2

(ti ho modificato il post, per mettere i blocchi di codice bisogna racchiuderli tra 3 “backtick” :arrow_right: ` :arrow_left: vedi per esempio https://github.com/adam-p/markdown-here/wiki/Markdown-Cheatsheet#code-and-syntax-highlighting)


#3

Anche se l’ idea fosse giusta, non riusciresti mai ottenre 100/100 in quanto K <= 10^9 e K/2 rime sempre alto mandando l’ algoritmo fuori tempo.
Ti invito anche a vedere le assunzioni sul numero massimo di regali in una cella 0<=g<=10^9 . Il riusltato quindi potrebbe essere superiore al valore massimo rappresentabile per l’ int.
Prova a simulare un percorso con k <= 20 in un campo 4 * 4.
Btw buon anno !


#4

Grazie, in effetti avevo considerato solo che N,M≤100, considerando però che l’algoritmo si basa su K ho sbagliato alla grande. In questo caso non riesco a pensare ad una soluzione, avevo pensato a cercare la coppia più grande di numeri vicini in modo da fare avanti ed indietro su quelle due caselle però non ero sicuro se la strada per arrivare alle due caselle potesse influire significativamente. Potresti darmi qualche indizio sulla soluzione?
Buon anno anche a te~


#5

Sapendo che babbo faccia avanti e indietro su due caselle basta trovare il percorso che ti porti a quelle due celle massimizzando i guadagni.
Una volta ottenuto il percorso che massimizza i guadagni e le due celle che formano il ciclo dovresti riuscire ad ottenere la soluzione.
spoiler:

Per farlo potresti provare a lanciare la tua funzione ricorisva utilizzando la dp in modo tale da non ricalcolare riusltati ottenuti dalle precedenti chiamate.
Come detto prima alla funzione non puoi passare un valore K alto altrimenti andrebbe fouri dai limiti di tempo e anche di memoria.
Devi trovare un valore che ti permette di trovare il ciclo.


#6

Quindi alla fine bisogna effettivamente cercare la strada migliore per loopare sulla coppia maggiore. Grazie mille, ci lavoro su allora.


#7

Mi permetto di precisare che, indicando con X ed Y le caselle sulle quali verrà eseguito il ciclo di lunghezza 2 e Vx e Vy i regali che vengono distribuiti rispettivamente nelle caselle X e Y, non è corretto assumere che il percorso per arrivare alla cella X(o Y dipende da quale è più vicina allo start) deve essere di lunghezza minima.
Quella strategia è un’euristica che qui sulla piattaforma ti garantisce 20/100 ma che si può dimostrare sia sbagliata.
Un controesempio è:

3 4 2 1 16
8 8 8 8
0 2 2 10
1 1 1 10

Quindi, indicando con MaxX(Z) il numero di regali che si possono rilasciare dalla cella X, con un ciclo di lunghezza 2, compiendo un percorso di lunghezza Z: quindi Z/2 volte i regali che rilasci in X e Z/2 volte i regali che rilasci nel vicino più conveniente, bisogna trovare il percorso lungo L tale che il valore del percorso*2(andata e ritorno) + MaxX(K-2L) sia massimo possibile.
Con valore del percorso intendo la somma dei regali rilasciati in ogni cella del percorso.

Fabio.


#8

Non so se il problema sia legato ai test case deboli, però credo che la lunghezza del percorso per raggiungere il ciclo di lunghezza 2 sia minore di N + M.

La soluzione prevista è O( NM(N+M) )?


#9
6 4 6 1 30
100 100 100 100 
100 1 1 100
100 1 1 100
100 1 1 100
100 1 1 102
0   1 1 102

La soluzione è 2914=22* 100 + 7 * 102, dove il primo prodotto è il percorso(di lunghezza 11>6+4) ed il secondo è il ciclo da 2.
Ma in realtà nei tc ci sono casi in cui la lunghezza è maggiore di N+M