Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Binary Search Shortlist  (Citit de 6993 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« : Mai 16, 2014, 08:25:41 »

http://www.infoarena.ro/blog/binary-search-shortlist
Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #1 : Mai 16, 2014, 09:24:53 »

#3 The numbers are uniq?
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #2 : Mai 16, 2014, 09:33:26 »

yes, thanks
« Ultima modificare: Mai 16, 2014, 09:38:34 de către Cosmin Negruseri » Memorat
rgrig
De-al casei
***

Karma: 46
Deconectat Deconectat

Mesaje: 144



Vezi Profilul WWW
« Răspunde #3 : Mai 16, 2014, 13:51:48 »

One more:

11. Find some minimal subset A of S that has a monotone property p. The property p is given as a function. It is expensive to call this function, so you want to minimize the number of calls in the worst case. (p monotone = if p holds for a set, it also holds for all supersets; A minimal = A has property p, but no proper subset of A does)

The following solution is too slow because it makes |S| calls even if A is tiny:
Cod:
find(S, p)
  A, B := emptyset, S
  while B not empty
    pick some element x of B
    B := B - {x}
    if not p(A union B):
      A := A union {x}
  return A
« Ultima modificare: Mai 17, 2014, 08:44:38 de către Radu Grigore » Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #4 : Mai 17, 2014, 11:20:29 »

I can do it in k log n queries, where k is the average size of a minimal subset and n is the size of S. I don't think one can solve it faster than k queries.
Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #5 : Mai 17, 2014, 14:09:51 »

First i need to say that #8 is my favourite problem Very Happy
So here it is ...

let's asume that the arrays are indexed from 1 to n, m
O(logK)
First we need to make a quick observation.
The first k elements in the union form a compact section in the 2 arrays.
That means that one array contains at least [k/2] elements.

let x = k/2
Cod:
We compare A[x] with B[x].
If A[x] < B[x] implies the fact that the first x elements from A are in the first k in the union.
if A[x] was not in the first K elements in the union .. then B[x] was .. and B[x] is bigger than A[x], so it's false.

In the first step we move A[1] to A[x + 1] and continue the program
with the A[x + 1] and B[1] as the .front() of the arrays and with k -= x
And .. here it's a C++ code for this.
Cod:
#include <cassert>
#include <ctime>
#include <cstdlib>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

void read_vector(vector<int> &a, ifstream &in);
void read(vector<int> &a, vector<int> &b, int &k);

int solve(vector<int> &a, vector<int> &b, int k) {
int stA = 0, stB = 0;

while (k != 1 and stA < int(a.size()) and stB < int(b.size())) {
int indA = min(k / 2, int(a.size()) - stA);
int indB = min(k / 2, int(b.size()) - stB);

if (a[stA + indA - 1] <= b[stB + indB - 1]) {
stA += indA;
k -= indA;
} else {
stB += indB;
k -= indB;
}
}

if (stA == int(a.size()))
return b[stB + k - 1];
if (stB == int(b.size()))
return a[stA + k - 1];

assert(k == 1);
return min(a[stA], b[stB]);
}

int main() {
vector<int> a, b;
int k;
read(a, b, k);

cerr << solve(a, b, k);
return 0;
}

void read_vector(vector<int> &a, ifstream &in) {
int n;
in >> n;
a.reserve(n);
while (n--) {
int x;
in >> x;
a.push_back(x);
}
return ;
}

void read(vector<int> &a, vector<int> &b, int &k) {
ifstream in("data.txt");
read_vector(a, in);
read_vector(b, in);
in >> k;
in.close();
return ;
}
« Ultima modificare: Mai 17, 2014, 14:23:41 de către Alex Velea » Memorat
rgrig
De-al casei
***

Karma: 46
Deconectat Deconectat

Mesaje: 144



Vezi Profilul WWW
« Răspunde #6 : Mai 17, 2014, 21:12:38 »

Cosmin's solution for #11 is probably O(k + k lg(n/k)), which is the best known.
Lots of problems reduce to #11: http://arxiv.org/abs/1402.3011
Memorat
mening12001
Strain


Karma: -13
Deconectat Deconectat

Mesaje: 14



Vezi Profilul
« Răspunde #7 : Iunie 01, 2014, 14:06:57 »

#3

Cod:
int A[number],leftLimit = 0,rightLimit = A.lenght-1;

while(true)
{
index = random(leftLimit,rightLimit)
if(index == A[index])
break;
if(index < A[index])
rightLimit = index;
else if(index > A[index])
leftLimit = index;
}

cout<<"i="<<index;
Memorat
rgrig
De-al casei
***

Karma: 46
Deconectat Deconectat

Mesaje: 144



Vezi Profilul WWW
« Răspunde #8 : Iulie 06, 2014, 19:06:29 »

In case anyone is curious, I wrote up the solution to my puzzle (#11):
  http://rgrig.blogspot.com/2014/07/minimal-sets-over-monotone-predicates.html
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines