OIS_Wine Subtask 2

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)?

1 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)

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 :sweat_smile:
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 /2 con >> 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;

}