Mystery in MAXRECT

general
1

Can somebody explain…???
during the contest when i submitted the soltion for this problem i scored 0.655pts (when i used FAST INPUT) and for the same code i got 0.87pts (when i removed FAST INPUT) from my code…
Check it out…http://www.codechef.com/OCT12/status/MAXRECT,blacklisted

2

Your fast input routine doesn’t handle negative inputs correctly (I believe it treats ‘-’ as a very large digit). -1 in the input translates to a larger positive value in your internal representation.

I hope this helps…

1 Like
3

Your fast input doesn’t handle negative numbers.

1 Like
4 
inline L inp()
{
    L noRead=0;
    char p=getchar_unlocked();
    for(;p<33;)
    {
     p=getchar_unlocked();
    };
    while(p>32)
    {
     noRead = (noRead << 3) + (noRead << 1) + (p - '0');
     p=getchar_unlocked();
    }
    return noRead;
};

In the above function you have used for fast input the , which always take ‘-’ s ASCII value and manipulates the actual data to be taken . . This must be the reason which caused for the change…!!

1 Like
5

@bcurcio and renze…thanks…:)…but i m still wondering why it gave correct answer than…??

6

Your program regarded negative values as (different) positive values. This will influence the result of your program. However, as long as the actual value (as seen by the judge) is positive, the program will not be disqualified.

There are probably test cases where your program (with fast input) will fail, but your program was lucky enough not to encounter any of them…

1 Like
7

As you have used the bit shift operators with on Signed Long data type , possibly chances are there for the generation of the negative number let suppose 3<<31 will give you ‘-2147483648’ , because in this case the sign bit has changed which results in the gen of negative number …!! So it depends on range of the given data , so even ‘-’ valued huge numbers like -(2^30) range of numbers can be possibly be negative number . !! So your function do’s 2 things …!!

  1. It will surely take +ve numbers as positive .
  2. If given data is negative it may be negative or positive
    so ultimately decrease the negativeness of data… which will decrease your score !!
8

I had a look at the ascii table. Contrary to what I thought, ‘-’ is ascii code 45 (3 smaller than ‘0’), so ‘-’ is probably handled as a digit with value -3. As the ‘-’ is always in front, it will become a negative number, but not the same as the input.