-----------------------------------

Shah-Cuber

Sat May 01, 2010 3:00 pm


ECOO 2010 Finals

-----------------------------------

Well, that was fun.

Congrats to Don Mills CI #1 for winning this years ECOO finals, with an amazing score of 563 and an astounding time of 47 min for all 4 questions. Also, congratulations to Woburn CI #1 and Lisgar CI, both earning 2nd place with a score of 542. It was exciting to say the least.

Thank you York University and all ECOO delegates & coaches for making this event possible.

If anyone cares, our school finished 9th (A.Y Jackson #1). Our score break down was: 110, 80, 110, 110.
It was cool meeting some of you there & hopefully next year too :)

Now to discuss the questions.
I'm mainly interested in question #2.
Did anyone else use a weird heuristic DP approach? I wanna know what the best solution was ...

For those that don't have the question at hand, I posted a .jpg version of it.


-----------------------------------

Cyril

Sat May 01, 2010 3:59 pm


RE:ECOO 2010 Finals

-----------------------------------

Ah, it was luck. Woburn had computer troubles and SM (I'm introducing this as an abbreviation for Stupid Mistakes). Brian will claim that I'm being modest, but we shall see at Stage 2.

For #2, we used BFS. The axes are independent. Define p(v,t) as the shortest time to get from 0 to t, starting with velocity v. The answer is just max(p(v,250-x),p(0,105)).

To compute p(v,t), keep a queue of triples: (pos, vel, time). Push (0,v,-1). Then, loop this:

Pop front triple f, and if f.pos = t and f.vel = 0, return time. Otherwise, push (f.pos+f.vel, f.vel, f.time+1), (f.pos+f.vel+1, f.vel+1, f.time+1), and (f.pos+f.vel-1, f.vel-1, f.time+1).

Slooooooow. Our cheap way around this was to keep a table of (pos, vel) visited before. As for bounds, |pos| < 50000 and |vel| < 500 gave the correct answers, so we used a heuristic (i.e. stupid gambling) and hoped for small test data.

As Brian suggested, the optimal solution is probably A* search.


-----------------------------------

saltpro15

Sat May 01, 2010 4:35 pm


RE:ECOO 2010 Finals

-----------------------------------

Used next_permutation + bash for Q3.

Something went wrong with my function for finding sum of divisors for Q4 and it only got 60/100.

Used atan instead of atan2 for Q1, a teammate changed that on the car ride home and it would've worked perfectly >.> 

Did not attempt Q2.  

We fail. :(


-----------------------------------

zle

Sat May 01, 2010 6:09 pm


Re: ECOO 2010 Finals

-----------------------------------

We (well, two other team members) treated x and y separately, calculated the sequence of velocities needed to get to Wonderland in that one dimension and returned the maximum of the lengths of the two sequences. Interestingly, since the starting y coordinate and ending y coordinate are constant, sequence to reach the target in the y dimension is also constant. 

I read through their code; it looks like these were the key points:
* at some point, your velocity must go to zero
* between initial velocity and stopping (v=0), you have to travel some distance
* in the ideal solution, you will overshoot once only if the distance from initial velocity to stopping is greater than distance from starting point to Wonderland

* if velocity a is the maximum speed reached, you will travel at least a units
* if velocity a is not the maximum speed, you will travel at least 2a units
* if by travelling a units you overshoot the target, you will never reach that speed in the optimal solution
* if you can go faster without overshooting, you're not looking at the optimal solution

They handled the case of necessary overshooting by calling the function again with v=0, stopping point as the new starting point and distance to travel being the distance from stopping point to target. 

...It's faaaaast. Test cases run under a second on my computer.

What I want to know is how everyone else did question 4 (the sum of numbers thing). We ended up scrapping most of our code and hacking together a brute force solution in the last ten minutes that only worked for values under 20000, hahaha. It feels like we missed something really, really obvious...seemed like everyone else got 110 on that question early on :P[/list][/list]


-----------------------------------

A.J

Sat May 01, 2010 6:38 pm


RE:ECOO 2010 Finals

-----------------------------------

For the Almost Amicable Numbers question, you basically span outwards from sod(x) looking for a number y such that distance from x to sod(y) is smaller than the distance from y to sod(x). Our code was as follows:

#include 
#include 
using namespace std;
int d(int x)
{
    int temp = 0;
    for (int i = 1; i > x;
        sod = d(x);
        int ans = 0, m = 9999;
        for (int deg = 0;; deg++)
        {
            bool done = 0;
            int up = sod + deg, down = sod - deg;
            int temp = d(up), temp2 = d(down);
            if (abs(x - temp)  d[j+1]){
                     double tmp = d[j];
                     d[j] = d[j+1];
                     d[j+1] = tmp;
                     int tmp1 = x[j];
                     x[j] = x[j+1];
                     x[j+1] = tmp1;
                     tmp1 = y[j];
                     y[j] = y[j+1];
                     y[j+1] = tmp1;
                  }
               }
            }
         	
            for (int i=0;i:|

Also, Cyril, stop being so modest! You won, be proud!

so basically we lost 200 points because of atan vs atan2 and < vs