ECOO 2010 Finals

Shah-Cuber · **Posted:** Sat May 01, 2010 3:00 pm

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 Smile

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 · **Posted:** Sat May 01, 2010 3:59 pm

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 · **Posted:** Sat May 01, 2010 4:35 pm

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. Sad

zle · **Posted:** Sat May 01, 2010 6:09 pm

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 Razz

[/list][/list]

A.J · **Posted:** Sat May 01, 2010 6:38 pm

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:

cplusplus:

#include <iostream>
#include <cmath>
using namespace std;
int d(int x)
{
int temp = 0;
for (int i = 1; i <= floor(sqrt(x)); i++)
{
if (x%i==0)
{
if ((x/i)!=i) temp += ((x/i)+i);
else temp += i;
}
}
temp -= x;
return temp;
}

int main()
{
freopen("DATA41.txt", "r", stdin);
int x, sod;
for (int ii = 0; ii < 5; ii++)
{
cin >> 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) <= deg)
{
ans = up;
done = 1;
}
if (abs(x - temp2) <= deg)
{
ans = down;
done = 1;
}
if (done)
{
cout << ans << " is friendly to " << x << " of degree " << deg << endl;
break;
}
}
}
return 0;
}

saltpro15 · **Posted:** Sat May 01, 2010 7:01 pm

can someone post code for Q1?

zle · **Posted:** Sat May 01, 2010 7:24 pm

http://codepad.org/39QyU8tQ

Here's our solution for Q1 (Connect the Dots). It's on codepad because I am a fan of syntax highlighting. We started with trig, went to sorting by y values (high to low on the left side, low to high on the right side), got zero test cases (wooo!), went back to trig, realized you had to use slopes and not just y values, and got it perfect (without the first try bonus, of course).

Shah-Cuber · **Posted:** Sat May 01, 2010 7:37 pm

All of the following solutions are in java.

Problem One

code:

import java.util.*;
import java.io.*;

class Q1 {
public static void main (String[] args) throws IOException {
Scanner s = new Scanner (new File ("DATA11.txt"));
for (int u=0;u<5;u++){
int num =s.nextInt();
int []x = new int [num];
int []y = new int [num];
double []d = new double [num];
int sumx=0;
int sumy=0;
for (int i=0;i<num;i++){
x[i] = s.nextInt();
y[i] = s.nextInt();
sumx+=x[i];
sumy+=y[i];
}
double avgx = (double)sumx/num;
double avgy = (double)sumy/num;

for (int i=0;i<num;i++){
double temp = Math.atan ((double)Math.abs(y[i]-avgy)/(double)Math.abs(x[i]-avgx))*180/Math.PI;
if (x[i]>avgx){
if (y[i]>avgy)
d[i]=270+temp;
else
d[i]=270-temp;
}
else{
if (y[i]>avgy)
d[i]=90-temp;
else
d[i]=90+temp;
}
}

int down=0;
int up=0;

for(int i = 0; i < num-1; i++){
for(int j = 0; j < num-1; j++){
if(d[j] > 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<num-1;i++){
down+=x[i]*y[i+1];
up+=x[i+1]*y[i];
}
down+=x[num-1]*y[0];
up+=x[0]*y[num-1];

System.out.println ("The area of the "+num+" sided polygon is "+(double)Math.abs(down-up)/2);
}
}
}

Problem Two (Not a solution! But still got 4/5 LOOOOL, yea this is funny & rushed Razz

)

code:

import java.io.*;
import java.util.*;

class Q2 {
public static void main (String[] args) throws IOException {
Scanner s = new Scanner (new File ("DATA21.txt"));
for (int o=0;o<5;o++){
int v = s.nextInt();
int x = s.nextInt();
int d = 250-x;
int day = 0;
int sum = 0;

if (d<0){
v=-v;
d=-d;
}

if (v>0){
for (int i=1;i<=v;i++){
day+=1;
sum+=i;
}
}

else {
for (int i=v;i<0;i++){
day+=1;
sum+=i;
}

}

d-=sum;
if (d<0){
v=0;
d=-d;
day-=1;
}

int counter = 1;
int dtemp=d;

while (dtemp>0){
dtemp -= (v+counter)*2;
counter+=1;
day+=2;
}
dtemp+=v+counter;

if (dtemp<0)
{counter-=1;day-=2;}
else{
day-=1;
}

if (dtemp!=0){
day+=1;
}

if (day<20){
day=20;
}

System.out.println ("Estimated time of arrival is in "+day+" days");
}
}
}

Problem 3

code:

import java.io.*;
import java.util.*;

class Q3 {
public static void main (String[] args) throws IOException {
BufferedReader s = new BufferedReader (new FileReader ("DATA31.txt"));
perm("");
for(int pp = 0; pp < 5; pp++){
char[][] map = new char[5][5];
for(int j = 0; j < 5; j++){
map[j] = s.readLine().trim().toCharArray();
}

for(int j = 0; j < arr.size(); j++){
map[0][0] = arr.get(j).charAt(0);
map[0][2] = arr.get(j).charAt(1);
map[0][4] = arr.get(j).charAt(2);
map[2][0] = arr.get(j).charAt(3);
map[2][2] = arr.get(j).charAt(4);
map[2][4] = arr.get(j).charAt(5);
map[4][0] = arr.get(j).charAt(6);
map[4][2] = arr.get(j).charAt(7);
map[4][4] = arr.get(j).charAt(8);
if(isValid(map)){
for(int k = 0; k < 5; k++){
for(int l = 0; l < 5; l++){
System.out.print(map[k][l]);
}
System.out.println();
}
System.out.println();
break;
}
}
}
}
static ArrayList<String> arr = new ArrayList<String>();

static void perm(String cur){
if(cur.length() == 9){
arr.add(cur);
}
for(int i = 1; i <= 9; i++){
if(cur.indexOf(String.valueOf(i)) == -1){
perm(cur + String.valueOf(i));
}
}
}

static boolean isValid(char[][] map){
for(int i = 0; i < 5; i+=2){
if(!proc(map[i])){
return false;
}
}
for(int i = 0; i < 5; i+=2){
char[] jj = new char[5];
for(int j = 0; j < 5; j++){
jj[j] = map[j][i];
}
if(!proc(jj)){
return false;
}
}
return true;
}

static boolean proc(char[] a){
if(a[1] == '+'){
if((Integer.valueOf(String.valueOf(a[0])) + Integer.valueOf(String.valueOf(a[2])))%10 == Integer.valueOf(String.valueOf(a[4]))){
return true;
}
}
else if(a[1] == '-'){
if((Integer.valueOf(String.valueOf(a[0])) - Integer.valueOf(String.valueOf(a[2]))+10)%10 == Integer.valueOf(String.valueOf(a[4]))){
return true;
}
}
else if(a[1] == '*'){
if((Integer.valueOf(String.valueOf(a[0])) * Integer.valueOf(String.valueOf(a[2])))%10 == Integer.valueOf(String.valueOf(a[4]))){
return true;
}
}
return false;
}
}

Problem 4

code:

import java.io.*;
import java.util.*;

class Q4 {
static int odd = 9999999;
public static void main (String[] args) throws IOException {
Scanner s = new Scanner (new File ("DATA41.txt"));
for (int j = 0; j < 5; j ++){
int n = s.nextInt();
int sn = sod(n);
int best = 0;
int bestd = 999999;

for (int a = n; a < 2*n; a ++){
int sa = sod(a);
int t = deg(n,sn,a,sa);
if (t < bestd){
bestd = t;
best = a;
}
}
for (int a = n; a > n/odd; a --){
int sa = sod(a);
int t = deg(n,sn,a,sa);
if (t < bestd){
bestd = t;
best = a;
}
}

System.out.println(best + " is friendly to " + n + " of degree " + bestd);
}
}
static int sod (int n ){
int sum = 1;

for (int i = 2; i*i<=n; i ++){
if (n%i==0){
int a = n/i;
if (a < odd)
odd = a;
if ( a == i){
sum+=i;
}
else{
sum+= a + i;
}
}

}
return sum;
}

static int deg (int a, int da, int b , int db){
return ((int)Math.max(Math.abs(a - db),Math.abs(b - da)));
}
}

I'm also going to add the other 3 problems in .jpg format for those who don't have it.

Cyril · **Posted:** Sat May 01, 2010 7:53 pm

We also considered a fast greedy thing like that, but for some reason I was convinced that there'd be some annoying cases where it fails. Evidently, greedy worked. Nice solution!

corriep · **Posted:** Sun May 02, 2010 6:59 am

A.J @ Sat May 01, 2010 6:38 pm wrote:

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:

ARE YOU SERIOUS?! We failed that question because we put equals to instead of less than or equals to

I am pissed! >:|

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

bbi5291 · **Posted:** Sun May 02, 2010 10:08 am

Cyril @ Sat May 01, 2010 3:59 pm wrote:

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.

Oh, stop that already. You won ECOO fair and square. The outcome of CCC stage 2 might be a better indicator of who the better coder is, but that is surprisingly irrelevant in the grand scheme of things.

Cyril · **Posted:** Sun May 02, 2010 1:37 pm

Luck is fair and square; I don't deny that. However, I maintain that it doesn't prove anything about coding ability, and I must make sure it's obvious as to which team was the best, as opposed to which team performed the best.

saltpro15 · **Posted:** Sun May 02, 2010 1:51 pm

corriep @ Sun May 02, 2010 wrote:

ARE YOU SERIOUS?! We failed that question because we put equals to instead of less than or equals to

I am pissed! >:|

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

so basically we lost 200 points because of atan vs atan2 and < vs <= . I really hate programming sometimes...

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members