questions about Feb 8,2003 contest

[debr]

I didn't find a better place to post this, so....

This was my first programming contest. It started at 1AM my time,
so I was a bit tired, but it was fun nonetheless.

Here are 3 that I got WA on and my algorithm. If someone finds
a hole in my algorithm or has some tricky input, let me know.

World Cup Noise (Problem G):
This looks like a simple fibonacci problem. out[1] = 2, out[2] = 3, out[3] = 5, out[4] = 8. However, I tried this and got WA. What tricky input am i missing (statement says only positive integer input)?

The Marriage Interview (Problem C)
Here are the outputs my program generates. What tricky input am I missing, or which of these are wrong.

Input:

-1 3 0 3 1 3 2 3 3 3 4 3 5 3
0 1 1 1 2 1 3 1 4 1
0 0 1 0 2 0
61 61

Output:

Case 1: 1
Case 2: 1
Case 3: 1
Case 4: 4
Case 5: 7
Case 6: 13
Case 7: 25
Case 8: 1
Case 9: 1
Case 10: 2
Case 11: 3
Case 12: 4
Case 13: 1
Case 14: 1
Case 15: 1

Make Polygon (B)
Root of problem was to figure out whether angles were interior angles or exterior angles (where you have to do angle = 360 - angle).
I used the sum of (xy[i+1]-x[i+1]y) to determine whether the polygon was clockwise or counterclockwise. I then used this along with the sign of the cross product to see whether I had an interior angle or exterior angle. I tried some pretty simple inputs:

3
0 0 10 0 5 10
3
0 0 5 10 10 0
5
0 0 5 5 10 0 10 10 0 10
5
0 0 0 10 10 10 10 0 5 5

Were there other tricks (self intersecting polygons, etc.)? Are my equations above totally hosed for non-convex polygons?

[Alexander Grushetsky]

For C and G you should use unsigned long long (__int64 for Visual C++ compiler) and out the answer as "%Lu".
Problem B:
angles can be more than 180 (so the max angle can be bigger than 180 too). At first I also check an area of the polygon and if it is negative I invert vertex order.

[debr]

Thx for the unsigned long long stuff. This is a little lame, as the rules stated that all C programs have to comply with ANSI X3.159-1989 which did not include long long and unsigned long long. Anyway, I'll know for next time, and I'll start using these by default so as not to be bit by this again.

[shahriar_manzoor]

Hello,
For problem G you can also use double. While solving a problem you should notice what can be the possible maximum value of the output and so what should be the data type. For Problem C you are not bound to use long long int. U can use your own implemented long number addition scheme So no ANSI violation here . Using always long long is not right. It slows your program down and is a bad programming practice.

[Caesum]

On the subject of when to use bigints/long longs it isnt often clear from the questions themselves. Personally I feel it is just a lame trick to require bigints when a problem doesnt state it, or does not indicate larger values in its given test data.

Having looked at these questions:
Problem C states it uses a 64 bit type, and so you would expect to have to use long long at least.
For Problem G there is an upper bound on the input, and so you should be able to work out an upper bound for the output which will tell you whether unsigned int will suffice or not.

So it doesnt look like there is such a trick with either of these problems.

Actually I like Shahriars questions, he is one of the better problem setters

[Larry]

I agree that it is an important skill to recognize the scope of a problem and realize which data type to use - and you can't use bigint every time because it'll be slow.

However, this favors teams with tons and tons of pre-written code ( or if they're using Java ) if it requires bigint in a time intensive session.

[suman]

Hi,
Actually 64 bit type is built-in in most C++ compilers. I use the following C++ code fragment to use 64 bit type

[cpp]
#ifdef _MSC_VER
typedef _int64 Long;
typedef _int32 Int;
typedef unsigned _int64 ULong;
typedef unsigned _int32 UInt;
#elif __GNUC__
typedef long long Long;
typedef long Int;
typedef unsigned long long ULong;
typedef unsigned long UInt;
#elif __BCPLUSPLUS__
typedef __int64 Long;
typedef __int32 Int;
typedef unsigned __int64 ULong;
typedef unsigned __int32 UInt;
#else
typedef long Long;
typedef int Int;
typedef unsigned long ULong;
typedef unsigned int UInt;
#endif

// From here on Long is 64 bit data type
// and Int is 32 bit
// For MSVC, GCC, and BCC
[/cpp]

For java as you know [java]long[/java] is enough. However as I don't know pascal, I don't know about it in pascal. So I think it is not a problem to use 64 bit data type.


- Suman