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.
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).
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.
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...
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.
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.
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.
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"
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.
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.
