Ciao a tutti, sto provando a svolgere ois_wine sulla piattaforma di allenamento.
Volevo ottenere 70 / 100 (subtask 2 e 3) con un programma che utilizza due algoritmi diversi in base all’input (controlla se tutti i valori di V sono uguali a 1), tuttavia i testcase 006 e 007 sembrano non rispettare le condizioni riportate nel testo.
Ciao, puoi postare il tuo codice? Magari c’è qualche problema di overflow considerando che K potrebbe non stare in un int.
Ciao, ho ricontrollato e corretto. Grazie mille! Se sei riuscito a completarlo, potresti darmi un suggerimento per ottenere 100?
quoto (20 caratteri)
Hint1:
Ribalta il problema: dato un costo x, sia count(x) il numero di tour con costo minore o uguale a x.
Sai trovare count(x) con complessità O(NlogN)?
Hint2:
Il costo c del tour che occupa la posizione K nell’ordinamento è il minore tale che count(c) \ge K
Hint3:
Puoi trovare c tramite una binary search.
Hint4:
Una volta che conosci c devi capire come ottenerlo, ma ci potrebbero essere più modi…
Il problema ora è questo: considerando solo i tour di costo c, ordinati secondo la posizione del loro primo vigneto, quale di questi occupa la posizione K - count(c-1)?
2 Mi Piace
Binary search sul risultato della binary search: 2 libri
Letteralmente un mst (dna): 4 libri
(so che i libri sono indicatori di conoscenze richieste e non difficolta’ pero’ rimane il wtf)
1 Mi Piace
Beh ha senso considerando che i libri si basano sulle tecniche da conoscere e non sulla difficoltà effettiva (syllabus). Ci sono spesso problemi da 2 libri che non risolve nessuno ed in effetti sembra strano 
PS: non avevo visto l’edit
Update:
Il codice sono piuttosto sicuro che dia il risultato corretto ma da’ solo un subtask nell’ultimo testcase fuori tempo
Non credo che sia dovuto a un loop che non si chiude perche’ facendo un po’ di stress testing noto che c’e’ sempre un risultato, anche con k = 1 o k = n(n+1)/2
Il tempo maggiore e’ intorno agli 0.9 secondi quindi credo sia realmente un problema di tempo
La complessita’ e’ O(n * log(n) * log(maxn)), con maxn = (1 << 48)
Inutile dire che mi scoccia abbastanza lasciare un problema con 70 punti dopo 3 giorni di lavoro con un solo testcase fuori tempo
Cose che ho provato:
- Fast input
- Ottimizzazioni di compiler
- Sostituire
/2con>> 1
#include <bits/stdc++.h>
#define BUF_SZ 1 << 20
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
ll n, m, l, r, k;
vi v, p;
ll counts(ll x) {
// conta tutte le sequenze di valore <= x
ll res = 0;
for (int i = 0; i <= n; i++) {
// d e' il primo elemento da cui parte una sequenza <= x che finisce in i
int d = lower_bound(p.begin(), p.end(), p[i]-x) - p.begin();
// aggiungi al risultato tutte le sequenze che finiscono in i
res += i - d;
}
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
v.resize(n+1); p.resize(n+1);
for (int i = 1; i <= n; i++) cin >> v[i];
// p e' un semplice prefix sum array
for (int i = 1; i <= n; i++) p[i] = p[i-1] + v[i];
// assumendo v[i] <= 1e9 e n <= 2*1e5, la somma non eccede (1 << 48)
l = 0; r = (1LL << 48);
// binary search sul risultato di counts
// m essendo il termine di mezzo finisce per rappresentare il risultato della ricerca
do {
m = (l+r) / 2;
if (counts(m) < k) l = m+1;
else r = m;
} while (l != m);
// riduco il problema alla k-esima sequenza di lunghezza m
k -= counts(m-1);
for (int i = 0; i <= n; i++) {
// per ogni elemento i cerco se esiste una sequenza di quella stessa lunghezza
// essendo ogni v[i] > 0 puo' esistere una sola sequenza per ogni iterazione
auto low = lower_bound(p.begin(), p.end(), m+p[i]);
// se l'elemento va oltre l'array oppure non esiste nell'array si salta
if (low == p.end() or *low != m+p[i]) continue;
if (k == 1)
cout << i << " " << (low - p.begin() - 1) << endl;
k--;
}
}
Qualsiasi suggerimento anche non inerente e’ gradito
Edit: ho risolto, il problema era che per qualche motivazione a me ignota k diventava <= 0 or >= n, per cui non veniva trovata alcuna soluzione
Non saprei aiutare chi avra’ il mio stesso problema perche’ io stesso non so cosa sia successo
Grazie mille dell’aiuto
Quel testcase è un corner case, ho provato ad aggiungere al tuo programma una piccola parte che lo gestisce a parte ed ha funzionato.
In particolare il testcase incriminato è stato risolto in 72ms.
A dire il vero una volta con un paio di accorgimenti:
r=p[n],
e
aveva fatto 100 (ma solo una volta) anche senza la gestione specifica…
Comunque grazie, così ho fatto 100 anch’io.
1 Mi Piace
Salve, ho scritto questo codice per risolvere wine, ma va oltre time limit… come dovrei fare?
Come posso migliorarlo?
// NOTE: it is recommended to use this even if you don't understand the following code.
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
// input data
int N;
long long K;
vector<int> V;
struct bottega{
int inizio;
int fine;
int valore = 0;
};
vector<bottega> posti;
int main() {
// uncomment the following lines if you want to read/write from files
ifstream cin("input.txt");
ofstream cout("output.txt");
ios_base::sync_with_stdio(false);
int i = 0;
cin >> N >> K;
V.resize(N);
bottega all;
for(i = 0; i < N; i++){
cin >> V[i];
all.valore = V[i];
all.fine = i;
all.inizio = i;
posti.push_back(all);
}
int j;
int ultimasoluzione = 0;
for(i = 0; i < N; i++){
ultimasoluzione = posti[i].valore;
for(j = i + 1; j < N; j++){
all.valore = ultimasoluzione + V[j];
all.fine = j;
all.inizio = i;
ultimasoluzione = all.valore;
posti.insert(posti.begin() + i + 1, all);
}
}
auto comparator = [](bottega a, bottega b){
return a.valore < b.valore;
};
sort(posti.begin(), posti.end(), comparator);
//for(i = 0; i < posti.size(); i++) cout << " " << posti[i].valore;
cout << posti[K - 1].inizio << " " << posti[K - 1].fine << endl;
}