Page 1 of 1
Foundation Contest 2004
Posted: Tue May 04, 2004 3:44 pm
by shihabbd81
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.
Posted: Tue May 04, 2004 9:06 pm
by Cosmin.ro
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).
Posted: Tue May 04, 2004 11:10 pm
by Adrian Kuegel
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.
Posted: Wed May 05, 2004 9:04 am
by Cosmin.ro
I liked problem F the most
Posted: Wed May 05, 2004 9:21 am
by Andrey Mokhov
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.
Posted: Wed May 05, 2004 1:08 pm
by Per
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.
Posted: Wed May 05, 2004 1:26 pm
by shihabbd81
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.
Posted: Thu Aug 19, 2004 7:37 pm
by bugzpodder
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. [edit] 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.
Foundation-acm Contest - II
Posted: Sat Nov 20, 2004 4:07 pm
by anupam
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.
Posted: Sat Nov 20, 2004 4:24 pm
by Moni
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.
Posted: Sun Nov 21, 2004 1:24 am
by bugzpodder
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.
Posted: Sun Nov 21, 2004 8:29 am
by shamim
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.
Re: Foundation-acm Contest - II
Posted: Sun Nov 21, 2004 1:13 pm
by shihabbd81
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..
..............................