Hello guys,
I’m trying to solve the problem “Electrical Power Line”. It’s actually a simple problem using loops, but that seems to be too slow because at some test cases I get the message “Execution timed out”. I’m trying to find some kind of formula but I haven’t found one yet.
How can I solve this problem?
My code:
#include <stdio.h>
#include <assert.h>
#define MAXN 100000
int N, i, count, days;
int H[MAXN];
int main() {
assert(1 == scanf("%d", &N));
for(i=0; i<N; i++)
assert(1 == scanf("%d", &H[i]));
days=0;
for(int i = 0; i < N; i++){
count = 0;
for(int j = 0; j < N-1; j++){
if(H[j]<H[j+1]){
H[j]=H[j+1];
count++;
}
}
if(count==0){
break;
}else{
days++;
}
}
printf("%d\n", days); // print the result
return 0;
}
Well, as you figured out even though the approach is correct is too slow. Just to put some numbers your approach is O(N^2), we can expect that what slows down the algorithm is the inner for, cause we need to reduce the complexity somehow to something less than O(N^2).
Your appoach is the traduction of the problem to code, but try to think more generally about the structure of the problem, do you really need to manually go through each element each time? isn’t there a more straightforward way to know how many days a certain section needs to be increasing(as the problem asks).
So the solution you may want is 1-loop, that checks sequences, for now I’ll stop here as hints, if you need more hints just ask.
io ne voglio un altro ahahaha , penso di aver capito ciò che intendi, quel che volevo fare era cercare la sequenza di numeri crescenti con differenza maggiore tra il primo numero di questa sequenza e l’ultimo (quindi vedendo il primo caso di esempio la sequenza sarebbe “1 2 3”, e quindi il risultato 3-1) però non so implementarlo
Nel problema il valore numerico delle altezze non è usato per calcolare la soluzione, nel senso che alzare una torre di 1 unità o 100 è la stessa cosa, quindi non per forza bisogna fare 3-1, ovviamente se le torri crescono di 1, quindi 1 2 3 4 … si, ma non è garantito.
Un altro hint per l’implementazione può essere: andare in un verso è uguale ad andare in quello opposto(inteso scorrere dal primo elemento all’ultimo contro scorrere dall’ultimo al primo)? o in altre parole vedi se uno dei due modi ti viene più facile? altro hint più informativo in particolare in uno dei due modi la soluzione è trovare la sequenza più lunga avente una caratteristica.
1 Mi Piace
ok nulla sono stupido io, rileggendo la traccia mi sono accorto che dice che se H[i]<H[i+1] in un giorno fa H[i]=H[i+1] e non H[i]++, ora provo ad implementarlo e vedo un po’ .
Ho provato a risolverlo da quando ho risposto prima ad ora e sono riuscito a fare solo 10 punti, quel che ho pensato è stato di vedere il vettore al contrario e quando un elemento è maggiore di quello prima (H[i]>H[i-1]) si salva il valore di quella i, e la confronta con tutto quello prima, quindi se ad esempio ho 5 1 2 7 1, lui arriva a vedere che 7 è maggiore di 2 (quindi salva l’inizio della sequenza i=3) e poi la finisce quando vede che H[i] non è più maggiore di ciò che ha prima oppure arriva a controllare la cella 0, e a quel punto il risultato è la i di inizio della sequenza meno quella di fine.
So sicuramente che alcuni casi risultano sbagliati perchè non ho messo un controllo per vedere se una sequenza dura più o meno di una che viene controllata dopo perchè non riesco a farlo.
Sto ragionando bene o mi sto perdendo di nuovo? Questo è il programma in caso servisse:
#include <stdio.h>
#include <assert.h>
// constraints
#define MAXN 100000
// input data
int N, i,j=0,r=0,min=0;
int H[MAXN],V[MAXN];
int main() {
// uncomment the following lines if you want to read/write from files
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
assert(1 == scanf("%d", &N)); //0 1 2 3 4
for(i=0; i<N; i++) //5 1 2 7 1
assert(1 == scanf("%d", &H[i]));
for(i=N-1,r=i;i>=0;i--){
if(H[r]>H[i-1] && r!=0){
if(min==0){
min=i-1;
}else{
min=i;
}
}else{
r--;
}
}
if(r==-1) r=0;
printf("%d\n", r-min); // print the result
return 0;
}
1 Mi Piace
Ci sono un paio di errori ma sei sulla strada giusta, una cosetta al volo è r non decrementarlo di 1, spostalo direttamente su i o i-1, se vedi una sequenza e finisce e ne vedi un’altra r deve saltare all’inizio di quella dopo(dopo temporalmente ma nel nostro caso sarà prima in termini di indici). Per il resto attento a come usi gli indici “i” e “r” e va bene. Btw potevi al posto di usare gli estremi e calcolare la differenza usare una variabile che ogni sequenza parte da 0 e la usi come contatore facendo +1 per ogni elemento.
1 Mi Piace
ok grazie ancora, domani proverò : )