## Foundation Contest 2004

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

shihabbd81
New poster
Posts: 7
Joined: Sun Apr 13, 2003 8:39 am
Location: Buet, Bangladesh
Contact:

### Foundation Contest 2004

Hello All,

Thank to all for participating in the last contest (FOUNDATION-ACM CONTEST). Here goes some discussion about the problems:

(A) Can you solve it?
Problemsetter: Anupam Bhattacharjee

This is the easiest problem. Just derive a formula. Dont try to simulate.

(B) Easy Combination
Problemsetter: Anupam Bhattacharjee

This is one of the moderate problems. Use Bigint and derive combinatorial formula and use DP.

(C) Floor Tiles
Problemsetter: Yin Zhao (aka Bugz Podder)

This may be the hardest problem. Use DP.

(D) Menu
Problemsetter: Adrian Kuegel

This is one of the moderate problems. Use DP (something like 0/1 knapsack).

(E) What is the Card?
Problemsetter: Miraj Hasnaine & Anupam Bhattacharjee

This is also a moderate problem. Use mathematics to simulate it (need basic card game concept).

(F) Optimal House Placement
Problemsetter: Adrian Kuegel

This is one of the hard problems. Optimization problem.

(G) Chocolate Box
Problemsetter: A. K. M. Saifun Nabi

This is one of the easy problems. You need basic probability concepts.

(H) Danger Point
Problemsetter: Enamul Haque

This is one of the moderate problems. You may use formula or binary search.

(I) Determinate Prime
Problemsetter: Hasan Shihab Uddin

Though this problem seems easy it is one of the hardest problem (as there are many special cases). Read the problem description carefully.

-----------------------
Your inspiration is the best gift to us

Foundation Contest Team.

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
Some of the moderates seemed harder than the hard ones , more code, more bugs. I did the hard ones except the last one, I can't see any dp for the Floor Tiles problem i just used 2 for loops and tested if that rectangle can be filled with dominoes in O(1).

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I agree, that some moderate problems are harder if you don't know similar problems. Anyway, I think there was no really hard problem in our problemset, as also the result shows.

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
I liked problem F the most

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Hi!

First of all thanks to problemsetters for arranging such a nice contest!

I think all of the given problems were solvable during contest. I liked problem C most as I was quite afraid of it firstly but then after thinking of it with Ulan for about hour we decided that some heuristic can be applied. The heuristic was guessed after three or four submissions.
This may be the hardest problem. Use DP
By the way is it really can be solved by DP?? I am not sure about correctness of our heurestic but DP for cases like 1000x1000...

Best regards,
Andrey.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
I'm not sure what your heuristic was, but there is a pretty simple criterion that can be used to check if a certain dimension is possible. And it is not terribly hard to prove that it is both sufficient and necessary.

shihabbd81
New poster
Posts: 7
Joined: Sun Apr 13, 2003 8:39 am
Location: Buet, Bangladesh
Contact:
Per wrote:I'm not sure what your heuristic was, but there is a pretty simple criterion that can be used to check if a certain dimension is possible. And it is not terribly hard to prove that it is both sufficient and necessary.
By the way is it really can be solved by DP?? I am not sure about correctness of our heurestic but DP for cases like 1000x1000...
I have described it in my view. Better the problemsetters discuss about individual problems. Same problem may seem different categories for different people.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
as the problemsetter for Problem C, certainly my intent for this problem is not a DP solution (I for-one does not know and doubt the existance of such a solution). As previously mentioned, there is a simple but non-trivial criterion for this.  although in a way, I guess you could say this criterion is a form of DP since you build the final problem from smaller sets of problems. [/edit]

The intent for this problem is quiet unique... I expected solvers to write a routine to verify a certain non-trivial fact, then using this fact to derive a mathematical criterion which solves this problem. In the actual solution to this problem however, the verifying routine is no where to be found.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

### Foundation-acm Contest - II

Hello All,

Thank to all for participating in the 2nd contest of us (FOUNDATION-ACM CONTEST-II).
As usual, here goes some discussion about the problems:

(A) Back to Intermediate Math
Problemsetter: Anupam Bhattacharjee
This is the easiest problem. Simple Geometric.

(B) Repeated Josephus
Problemsetter: Anupam Bhattacharjee
This is the second easy problem. Use concept of Josephus problem.

(C) Mystical Matrix
Problemsetter: Yin Zhao (aka Bugz Podder)
Seeming Hard One

(D) Determine The combination
Problemsetter: Shihab Uddin
This is another easy problem. Use DP (may use recursion with hard pruning)

(E) God! Save me
Problemsetter: Anupam Bhattacharjee
This is a moderate problem. Use probabilty concept of mathematics.

(F) Mathemagicland
Problemsetter: Yin Zhao (aka Bugz Podder)
This is one of the hardest problems. Better BUGZ discuss it

(G) Collector's Problem
Problemsetter: Adrian Kuegel
I request Adrian to discuss the problem.

(H) Again Prime? No time.
Problemsetter: Anupam Bhattacharjee
I think this is another easy problem. Just use the concept of Combinatorics.

(I) Global Positioning System
Problemsetter: Shihab Uddin
Hard one I think. Should have concept of the geometry of world.

(J) Send More Money
Problemsetter: Enamul Haque Moni
Easy to understand but may face hard to solve (actually this is a NPC problem). The problem is welknown as CSP.

-----------------------
Again thanking you.
Your inspiration is the best gift to us

Foundation Contest Team.
"Everything should be made simple, but not always simpler"

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
Hmm....I'm back again after a long hibarnation

Seems our team have arranged an error free contest participated by lots of well wishers

Anyway...thanks to the uva, and you participants....hope to do better next time...with new flavours

Moni.
We are all in a circular way, no advances, only moving and moving!

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
not quiet. There is a problem with the Time limit for F. My solution runs in ~2.5 seconds where as the time limit for it was 1 seconds (there is only one person who submitted a solution, and he was the top guy so it didnt affect the rankings). I apologize for this. However, when it is moved to the problem set you get 10 seconds which should be enough.

But I am sure that a lot of people is able to write more efficient code than I could. Plus I used a brute force algorithm. there should be optimizations that can be done (math related)
And since no one got it right yet, I am not sure if there are any errors involved in my (relatively large) judge solution.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
First of all, thanks a lot to the members of Foundation for arranging such a lovely contest. It is defenitely inspiring to see that retired problem solvers from Bangladesh, along with some of the best solvers from the world did not end their connection wiht this site. They are now arranging contest for us, thus keeping us even more active in problem solving.

Good Luck to your team and waiting for your next contest.

shihabbd81
New poster
Posts: 7
Joined: Sun Apr 13, 2003 8:39 am
Location: Buet, Bangladesh
Contact:

### Re: Foundation-acm Contest - II

anupam wrote:(D) Determine The combination
Problemsetter: Shihab Uddin
This is another easy problem. Use DP (may use recursion with hard pruning)
Nothing more to say about this problem.
anupam wrote:(I) Global Positioning System
Problemsetter: Shihab Uddin
Hard one I think. Should have concept of the geometry of world.
Probably seems very hard...but i think not so...
Should I increase acceptable error from 1 min??

Thanks to all again.

Shihab Uddin..
..............................