501 - Black Box

[sclo]

This problem is easy to do with stl sets. Much easier than implementing some tree datastructure ourselves. As Abenego says, just be careful with the iterators. We need to adjust the iterator if we insert an element before the position that the iterator points at.

[shahriar_manzoor]

With the advent of STL I guess the definition of hard problem is changing fast...

[Darko]

You mean that setting a hard problem is harder? You think that is a bad thing?

You can see the evolution of the concept of "hardness" on UVa sets - check I (I/O sensitive), then check CIX (real problem-solving set). During the last contest I didn't even want to try to do B because I saw who set it. I didn't want to go through the pain of guessing EPS or rounding methods or if it is 4 or 6 digits or if it will time out or whatever. But then I saw that a lot of people got it, so I solved it in Java in the first try. I might say I was very pleasently surprised. It was an easy problem after all (as it should have been).

The thing is - we are supposed to find new and better ways how to solve certain problems, not reinvent the wheel all the time. That's why STL (or Java's libraries) is a good thing.

You can still take a poke at those libraries, too. There is that problem with substrings, for instance, that you won't be able to solve using built-in functions, you have to implement your own algorithm. That sort of hardness I like. What about Abednego's contest? STL made it easy or something?

Another thing people like to do to make problems "harder" - if intended solution was supposed to be nlogn and someone gets by with n^2 (in C, heavily optimized), it doesn't make the problem harder if you just increase the size of the input. In the process you might force some Java solutions to time out, although they are nlogn (but Java I/O is extremely slow here).

Sorry, just felt like taking this off my chest, while you are here.

Darko

[shahriar_manzoor]

The four and six digit error was not intensional. Originally the problem set was four digit. But when I added an special judge I had to make it six digit but forgot to change the sample output.


The problem often is that when I write an alternate solution to a problem and the problem is correct there is no problem but when someone has to change a lot then it is possible that there is still some error. That was the case with B and C.

In my time Black Box was a quiet hard problem, now it is no more, that is what changing definition is all about

About the java solution being timed out: problems don't have solution written in java so always it is hard to guess java time. And as the processing power of UVa online judge is slow so we cannot be generous about time limits, not that we don't want to be. We are a poor judge (Not topcoder) where there are dozens of ultra fast machine to compile and judge and so the time limit is very high.

[sumankar]

The thing you guys missed out was, even STL takes learning. It doesn't
happen *just-like-that*. So, I feel its a good thing that people are learning STL even if its only to make life (read UVA-hard problems) easy.

[shahriar_manzoor]

I think I never critisized STL I just said the definition is changing. For example suppose there is a problem in a contest that is just to sort 10 numbers and also suppose pascal does not have built in qsort function. So the C/C++ users will have a great advantage over pascal users.

I early contests we had problems like generating permutation in lexicographic order but now we won't see it because using STL it is nothing, so the evolution is there. So now the question comes to mind as problemsetter is: will the problems that allow STL people too much advantages be considered in a contest (I know in world finals before 1990 recursive problems were not allowed because at that time pascal and fortran was the languages and fortran did not allow recursion)?

That is what I was thinking about not all contests will be like Abednego's contest (there will always be some easy common algo contests) and I think in the upcoming wf warmups stl users won't get any significant advantages other than doing common things fast.

[fernando]

i have tried this problem and i always get WA. Basically i am using a STL multiset and an iterator to the current element, whenever i a process a GET command i just print the content of the iterator and increment the iterator, and whenever i insert an element less than the element currently pointed by the iterator, i decrement the iterator, is my approach correct?

[bakalar]

Never mind, it got accepted.

The problem comes from NEERC' 1996 regionals. You can use the tests at http://www.acm.inf.ethz.ch/ProblemSetAr ... NERC/1996/ as a last resort.

[stcheung]

I got WA enough times dealing with the multiset iterator manipulation that I feel like giving a few hints, now that I finally got accepted:

You can definitely solve this problem with C++ STL multiset in less than 1 second. So if you still get TLE, most likely each time you do a GET, you are resetting your iterator to the beginning of your multiset and incrementing it one by one until you arrive at the proper position. This will take way too long. You should instead remember your iterator's position, and manipulate it accordingly when new elements are inserted to your multiset. To be precise, you need to decrement it when you are inserting an element that's smaller than what your iterator is pointing to.

To answer Fernando's question, the hint is to not instantly increment the iterator after you do a GET operation. In other words, after you do a GET, leave you iterator alone. Then decrement the iterator each time you are inserting a new element that's strictly smaller than what your iterator is currently pointing to. Then when it's finally time for another GET operation, now do the iterator increment.

[augustotorres]

Hi there!

I just cant understand why i'm getting WA for this problem . I'm using STL's multiset, and keep track of my iterator whenever i insert an element smaller than the one pointed by it.

Here's my code:

#include <stdio.h>
#include <set>
#include <iostream>

using namespace std;

int A[30001];
int G;
int M;
int N;

main()
{
int K,i,ant;
multiset<int> mapa;
multiset<int>::iterator cur;
FILE *in = stdin; //Quick change to input from file
fscanf(in,"%d",&K);
while(K>0)
{
fscanf(in,"%d %d",&M,&N);
for(i=0;i<M;i++) fscanf(in,"%d",&A);
ant = 0;
mapa.clear();
cur = mapa.begin();
for(i=0;i<N;i++)
{
fscanf(in,"%d",&G);
for(;ant<G;ant++)
{
mapa.insert((A[ant]));
if((*cur)>A[ant]) cur--;
}
cur++;
printf("%d",*cur);
printf("\n");

}
if(K!=1)printf("\n");
K--;
}
return 0;
}

Thanks

[augustotorres]

Hi there!

I just cant understand why i'm getting WA for this problem . I'm using STL's multiset, and keep track of my iterator whenever i insert an element smaller than the one pointed by it.

Here's my code:

#include <stdio.h>
#include <set>
#include <iostream>

using namespace std;

int A[30001];
int G;
int M;
int N;

main()
{
int K,i,ant;
multiset<int> mapa;
multiset<int>::iterator cur;
FILE *in = stdin; //Quick change to input from file
fscanf(in,"%d",&K);
while(K>0)
{
fscanf(in,"%d %d",&M,&N);
for(i=0;i<M;i++) fscanf(in,"%d",&A);
ant = 0;
mapa.clear();
cur = mapa.begin();
for(i=0;i<N;i++)
{
fscanf(in,"%d",&G);
for(;ant<G;ant++)
{
mapa.insert((A[ant]));
if((*cur)>A[ant]) cur--;
}
cur++;
printf("%d",*cur);
printf("\n");
}
if(K!=1)printf("\n");
K--;
}
return 0;
}

Thanks

[ioriyagami]

it is strange that i use vector<int> and get AC but if i use an int array ,i get an WA.i 've found that those two code must be different during the running of the program:

Code: Select all

int a[30005];
for(i = 0;i < m;++i)
		{
			int * pp = lower_bound(a, a + i, a[i]);
			int pos = pp - a;
			int temp = a[i];
			memcpy(a + pos + 1, a + pos, sizeof(int) * (i - pos));
			a[pos] = temp;
			while(j < n && b[j] == i + 1)
			{
				++k;
				printf("%d\n",a[k]);
				++j;
			}
		}

and

Code: Select all

vector<int>s;
for(i = 0;i < m;++i)
		{
			vector<int>::iterator it = lower_bound(s.begin(), s.end(), a[i]);
			s.insert(it, a[i]);
			while(j < n && b[j] == i + 1)
			{
				++k;
				printf("%d\n",s[k]);
				++j;
			}
		}

who can tell me the difference ???
thanks!!

[helloneo]

Hello..~
I use STL multiset.. and adjusting iterator approach as people said above there.. but it got me WA..
Can anybody give me some hints..?
Thanks..

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include<set>
using namespace std;
#define INF 999999999
multiset<int> s;
int arr[30010];
int size[30010];
int main()
{
        int t, n, m;
        int i, j, k, l;
        int temp, fl;
        scanf("%d", &t);
        while (t--) {
                scanf("%d%d", &m, &n);
                for(i = 1;i <= m; i++)
                        scanf("%d",&arr[i]);
                for(i = 1; i<= n; i++)
                        scanf("%d",&size[i]);

                s.clear();
                multiset<int>::iterator it;

                s.insert(arr[1]);
                it = s.begin();
                temp = *it;
                j = 2;
                for (i = 1; i <= n; i++) {
                        if (i != 1)
                        it++;
                        k = size[i];
                        while (j <= k) {
                                s.insert(arr[j]);
                                if (arr[j] < temp) {
                                        it--;
                                        temp = *it;
                                }
                                j++;
                        }
                        printf("%d\n", *it);
                }
                if (t)
                printf("\n");
        }
        return 0;
}

[rio]

Heres a testcase which your code doesn't work.
INPUT

Code: Select all

1

9 5
1 -8 3 5 1 0 4 2 1
1 3 3 6 8

OUTPUT

Code: Select all

1
1
3
1
2

I used an approach using two heaps, and it runned at 0.334 sec without optimiazation.
----

[vecKt]

ok, i don't get it... my code works on all examples, still i get WA

Code: Select all

#include <iostream> 
#include <string> 

#define MAX 300000

typedef struct heap

        {

             int data[MAX];

             int n;

        };





int initHeap(heap *h)

{

    h->n = 0;

	return 0;

}



int heapify(heap *h, int root, bool sorttype)

{

    int tmp;

    int i = root*2+1; // left child

     

    if ((i+1 < h->n) && ((h->data[i] > h->data[i+1]) ^ sorttype))

       i++;

    if ((h->data[root] <= h->data[i]) ^ sorttype)

       return 0;

    tmp = h->data[root]; //swap

    h->data[root] = h->data[i];

    h->data[i] = tmp;



    if (i*2+1 < h->n) heapify(h, i, sorttype);



	return 0;

}



int insertToHeap(heap *h, int x, bool sorttype) // sorttype: 1 = max, 0 = min

{

    int i, tmp;

    h->data[h->n] = x; //insert

    i = h->n++;

    while((i > 0) && ((h->data[i] < h->data[i/2]) ^ sorttype)) //heapify

    {

             tmp = h->data[i]; //swap

             h->data[i] = h->data[i/2];

             h->data[i/2] = tmp;

             i /= 2; // parent

    }

    return 0;

}    



int deleteFromHeap(heap *h, bool sorttype)

{

    int x = h->data[0];

    h->data[0] = h->data[--h->n];

    

    heapify(h, 0, sorttype);



    return x;

}



int printHeap(heap *h)

{

    for (int i = 0; i < h->n; i++) printf("%i, ",h->data[i]);

    printf("\n");

	return 0;

}           





int reversePrintHeap(heap *h)

{

    for (int i = 0; i < h->n; i++) printf("%i, ",h->data[h->n-i-1]);

    printf("\n");

	return 0;

}           

int get(heap *A, heap *B) {

    int x;

    

    x = deleteFromHeap(B, false);

    insertToHeap(A, x, true);

    return x;

}



int add(heap *A, heap *B, int x) {

    int tmp;

    insertToHeap(B, x, false); // 

    if (A->n > 0)

       if (A->data[0] > B->data[0])

       {

            tmp = deleteFromHeap(B, false);

            insertToHeap(B, deleteFromHeap(A, true), false);

            insertToHeap(A, tmp, true);

       

       }

    return 0;

}



int main(void)

{

    heap heapA, heapB;

    int k, i, j;

    int K, M, N, A[MAX], u[MAX];





   // scanf("%d",&K); //no. of datasets


std::cin >> K;


	for (j = 0; j < K; j++) {

		//scanf("%d %d",&M, &N);

		std::cin >> M;
		std::cin >> N;


		for (i = 0; i < M; i++)

//			scanf("%d",&A[i]);

		std::cin >> A[i];


		for (i = 0; i < N; i++)

//			scanf("%d",&u[i]);

		std::cin >> u[i];		


		initHeap(&heapA);

		initHeap(&heapB);



		for (i = 0, k = 0; i < M; i++)

		{

			add(&heapA, &heapB, A[i]);



			for ( ; u[k] == i+1; k++) {
std::cout << get(&heapA, &heapB);
std::cout << "\n";
}

//				printf("%d\n",get(&heapA, &heapB)); // 1 1 1 2

		}



		//printf("Heap: ");

		//reversePrintHeap(&heapA);

	

	//	printHeap(&heapB);

	//	printf("\n");

std::cout << "\n";

	}

//scanf("%d",&i);

    return 0;

} 

any ideas?