 # ZCO 2016 discussion

Were the tests on the local server really “weak”? If that’s the case, it isn’t really fair.

And what’s the expected cut-off? Will it really be 100? If so, I guess my first and last try for IOI ends here I got an O(N^2 log N) solution for problem 2 (using DP and binary searching). It was taking a maximum of 0.95 seconds on the computer provided at the center but at my home it is running in 0.18 seconds. Does anyone how fast the official grading server(s) is?

how did you guys got to know your marks??
also i want to know that i compiled and run my program for many test cases and it worked alright but during submission of code system took more time to check the code and finally it showed that it doesn’t pass all the test cases. does it mean that i m not going to get any marks for that program???

@hackpert I solved it using Priority Queues.

The idea is that you must have realized that the optimal split is such that the smallest N/2 numbers are in one list and the largest N/2 numbers in the other.

So there were two cases, you could either keep swapping the min in A with the max in B, or vice versa (upto K times). Now It was necessary to get the min of A (and max of B) after swap operations, so I used a Priority Queue. This approach is O(NlogN).

In 2nd question my solution was n*10^5 and then an n^2 dp so there are chances that it can fail on larger test inputs.Also i want to know whether K can be equal to N in 1st question as N distinct swaps would mean just interchanging the 2 arrays?

@pratyush1019: Stealing another INOI seat from a worthy candidate, your girlfriend also must have scored 200 then… right?

3 Likes

Can anybody tell what was the book shelf problem about ? If you remember the statement…

Here is my code for video game challenge…three of the tests work fine but getting wa for rest…I really cant figure out why I am getting WA?

#include
#include
using namespace std;
int main()
{
long long N;
long long H;
cin>>N;
cin>>H;
long long n=1;
long long b=0;
long long a[N];
for(long long i=1;i<=N;i++)
{
cin>>a[i];
}
long long com;
long long m=0;
while(1) {
cin>>com[m];
if(com[m]!=0)
{

``````m++;
}
else if(com[m]==0)
break;
``````

}

`````` for(long long t=0;t<m;t++)
{
switch(com[t])
{
case 1:
{

if(n> 1)
n--;

else
{}

break;
}

case 2:
{
if(n< N)
n++;

else{}
break;
}

case 3:
{
if(b==1)
{
}
else if(b==0)
{
if(a[n]>0)
{
a[n]=a[n]-1;
b=1;
}
else{}
}

break;
}

case 4:
{
if(b==0)
{
}
else if(b==1)
{
if(a[n]<H)
{ a[n]=a[n]+1;
b=0;}

else

{
}

}

break;

}
``````

}

`````` }
``````

for(long long i=1;i<=N;i++)
{
cout<<a[i];

}

}

Hello guyz…
I wrote a code for Bookshelves and it worked for all cases i could think of.
However, when I posted in ZCO practise contest, some of the test cases arent working.
Can someone check the code and tell me the mistake?

Bookshelves ZCO 2016

I coded the same thing but I thought it would time out and didn’t submit it, damn For some reason, I thought the worst case complexity would be 10^5*2500, but now I realize it will be not be so much, because the nos are distinct.

Yeah exactly. I was fixated on that line of the problem statement for a long time before I figured out its purpose. Did you solve the first one?

No I didn’t. What was your algo?

also the system was terrible. dev-cpp used to disappear on minimizing and had to switch the computer twice. :-/

Sort the two arrays and traverse the one with the smaller max value from the end. For each element from the last, eliminate that and its lower_bound in the second array and repeat this till either each element is covered or till k is reached

this explanation is a very crude one as I had coded a lot more conditions. it was perhaps one of those unnecessary conditions that gave me a runtime error in the second subtask

6 1

1 13 13 13 13 13

1 1 1 1 1 14

Haha yeah, you’ve done the 2nd problem anyway, so you’re good to go Hopefully. I missed last year’s INOI by a test case which was used for the final evaluation, so I hope my code doesn’t have any loopholes 