Imprimă pagina - Binary Search Shortlist

Titlul: Binary Search Shortlist
Scris de: Cosmin Negruseri din Mai 16, 2014, 08:25:41

http://www.infoarena.ro/blog/binary-search-shortlist

Titlul: Răspuns: Binary Search Shortlist
Scris de: Alex Velea din Mai 16, 2014, 09:24:53

#3 The numbers are uniq?

Titlul: Răspuns: Binary Search Shortlist
Scris de: Cosmin Negruseri din Mai 16, 2014, 09:33:26

yes, thanks

Titlul: Răspuns: Binary Search Shortlist
Scris de: Radu Grigore din 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

Titlul: Răspuns: Binary Search Shortlist
Scris de: Cosmin Negruseri din 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.

Titlul: Răspuns: Binary Search Shortlist
Scris de: Alex Velea din Mai 17, 2014, 14:09:51

First i need to say that #8 is my favourite problem :D
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 ;
}

Titlul: Răspuns: Binary Search Shortlist
Scris de: Radu Grigore din 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

Titlul: Răspuns: Binary Search Shortlist
Scris de: Andrei Geogescu din Iunie 01, 2014, 14:06:57

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;

Titlul: Răspuns: Binary Search Shortlist
Scris de: Radu Grigore din 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

infoarena

Comunitate - feedback, proiecte si distractie => Blog => Subiect creat de: Cosmin Negruseri din Mai 16, 2014, 08:25:41