I am trying to solve this SPOJ problem http://www.spoj.com/problems/BAISED/ .
My Approach
for all elements in the preferred_position array
if(position>0&&position<=n)
if(position is unoccupied)
allocate position for user
else
reach the first free position in the array
for all elements whose preferred position is already filled
search both directions left,right to find nearest free_position
I tried many test cases and got them right and I don't know where i failed and getting Wrong answer. And i chose this problem based on greedy tag and i really don't know where to apply greedy technique. Can anyone please throw some light?
Where i will be wrong? Here's a link to the code ideone.com/O4ood1
It was very painful to read your code.. and you solution is not right 100%, because:
there could be very big numbers bigger than 10^10 and what are you doing wrong - it's decrease such number by one until you reach n, your life it is too short to wait when your solution will find the result for test with such big numbers... (if you want a[i] became less or equal than n, why simply not to write a[i] = n)
while(t2>n)
{
t2--;
cnt1++;
}
I ran your code on the same test case two times, but in the second run I change the order of given numbers in test and your solution shows different answers:
I delete reading the strings for easier debugging.. so I provide test without names of teams
First run on test:
1
10
2 3 4 5 6 7 8 9 7 6
And your solution shows that result is 6 ( what is wrong answer)
Second run: Lets change swap last two numbers and get
2 3 4 5 6 7 8 9 6 7
And your solution shows that answer is 8 (Fortunately it is right answer)
Suppose there are two unplaced numbers a[6] = 6 and a[9] = 9, and there are two free places 1 and 8,
your solution will take 6 go two steps right and will put 6 in position 8, then will take 9 and put in position 1.
If you draw lines from start position of your number to its destination you will see that line from 9 to 1 fully cover line from 6 to 8... Looks like not optimal.
So you should try to avoid this overlapping.
Now draw lines from 6 to 1 and from 9 to 8, there is not overlapping and now it is optimal.
So to avoid overlapping you can for example to sort rest of your numbers.