Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 does anyone have any solutions to this years contest?
Index -> Contests
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
amvbse




PostPosted: Tue Feb 24, 2004 7:51 pm   Post subject: does anyone have any solutions to this years contest?

my "algorithm" fell apart on S3 .. i was wondering how else i couldve gone about it? dependancy algorithm? can anyone post any solutions to some of the other questions?
Sponsor
Sponsor
Sponsor
sponsor
Chimaera




PostPosted: Tue Feb 24, 2004 8:58 pm   Post subject: (No subject)

s3 was the spreadsheet program right? Your best bet for perfect functionality would've been to hardcode it all -.- That's what I did, I set up an array of numbers and then I set an array that declared new arrays for every additional number, it worked with a for loop. I didn't really think too much in terms of making an algorithm persay, but it worked perfectly because all of the calculations took place after I finished 'getting' all the values for the arrays.

S3 probably took me the longest out of all of them but it was probably the easiest one out of all of them too because you knew exactly what had to be done.
Mazer




PostPosted: Tue Feb 24, 2004 9:11 pm   Post subject: (No subject)

Chimaera wrote:
s3 was the spreadsheet program right? Your best bet for perfect functionality would've been to hardcode it all

Am I missing something here? How is your best bet to hardcode anything? Ever? You needed to use recursion for that one. Not that I'm one to be talking about that, I couldn't get mine working correctly and in the end I was considering putting a Sys.Exec call for the shutdown.exe but depending on which teacher was marking my programs, that could've been quite detrimental for me.
Andy




PostPosted: Tue Feb 24, 2004 9:11 pm   Post subject: (No subject)

waa? chimaera, what if u had three cells that linked to each other for ur solution??? for example A1=A2 A2=A3 A3=A1 ur solution wouldnt work then
Chimaera




PostPosted: Tue Feb 24, 2004 9:19 pm   Post subject: (No subject)

i dunno, my style's just to hardcode it, say I had spent more time to think about it like you guys did, then I probably would've come up with a more efficient solution for it. It works because I ran the whole thing through a a crapload of if statements, checking for catenations between the different inputs, checking for the integer right after the string ie. A7+B2+C4, would be taken in as letter A, then 7 is read separately, then the + is read so the program would add whatever comes after it at the end of the program.

ps. I never called it YOUR best bet, but it's MY way of solving problems and it works. That's my really my priority for solving problems. Make sure it works first, then worry about making it efficient and where I can change the code to be better. btw, you sound like my teacher lol.
Tony




PostPosted: Tue Feb 24, 2004 9:58 pm   Post subject: (No subject)

S1 was by far the easiest... you just check if all 3 words have first or last letter the same, if so the answer is "NO", otherwise its "Yes" Laughing but just cuz of the way they wrote the question, I didnt even understand what they were asking at first Confused

S2 - just got to know what you're sorting and how. Such as you have to sort the scores while keeping the list of ranks assigned to each contestant... THEN you also got to count in the ties for the places Rolling Eyes

S3 - recursion, substrings (turing's index helps, but I dont know if that part of the code even works right Rolling Eyes ) and keeping tack of your path to make sure you aren't going in circles.... I donno... mine was buggy

S4 - the question lost me on the part where it said "move in any of 4 directions in 3D space..." I donno... after I was done S1, S2, S5 and had some time left, I chose to just continue with S3 cuz I had some base writen... so not even sure what this question was about

S5 - lol, this is the only one that is similar to questions from previous contests Laughing Just write your maze recursion and let it run wild Laughing
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
amvbse




PostPosted: Tue Feb 24, 2004 10:37 pm   Post subject: (No subject)

could you help me some more on S5 .. I want to make sure I understand that one. I know the recursion for a maze but i cant think of a good way to implement it. I need some practice on recursion.
Tony




PostPosted: Tue Feb 24, 2004 11:51 pm   Post subject: (No subject)

basically you just walk though the maze in all possible ways. such as that at each point you check all around you for possible ways to go. when you reach the end of the "maze" you check if your current gold collected is more then the current maxGold counter and if saw, update it.

the trick here is to not forget to subtract the gold as you go a step back in your recursion.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Sponsor
Sponsor
Sponsor
sponsor
amvbse




PostPosted: Wed Feb 25, 2004 12:21 am   Post subject: (No subject)

can I get this one from you? So I can at look at how you did the recursion, that is if you remember your code. Pretty please.
Tony




PostPosted: Wed Feb 25, 2004 12:39 am   Post subject: (No subject)

its just like any other maze Rolling Eyes
code:

var goTo(x:int, y:int)

if x=finishX and y=finishY then
     put "you have found the exit"
     return
end if

if maze(x+1,y) not="*" then
     goTo(x+1,y)
end if

if maze(x,y+1) not="*" then
     goTo(x,y+1)
end if

end goTo

%start recursion
goTo(startX,startY)
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
bugzpodder




PostPosted: Wed Feb 25, 2004 5:56 pm   Post subject: (No subject)

the first two is sorta trivial as long as you dont have buggy code. my implementation for #4 is go through each cell, if it consists of a sum rather than a value, then check if each cell in the sum have a value in it or not (not means its also a sum). if not just skip it, otherwise give it a value also. if you loop thrugh this 90 times, every cell that still has a sum will be indeterminate. i perfer this implementation because its straightforward and possibily shorter to code and less buggy than recursion. the fourth one, you have to realize (which i didnt) that the ship travels in a straight line rather than teleporting. that means sometimes when its going north 50 light years, it could have reached a spot where it is shortest from the original point. so you have to check more than just the end points. i was naive enough to think that the ship teleports (too much gunbound for me) :S

#5... recursion certainly works, but i aimed for a faster solution using Dynamic Programming (Acutally its more like memorization). it works exactly the same way as #3 does. i was afraid recursion takes too long to run. but i was told that it didnt. Vasilli says he thought up of an algorithm that runs in O(N^3) for N to be the side length of the maze.
bugzpodder




PostPosted: Thu Feb 26, 2004 8:52 am   Post subject: (No subject)

S1:

code:

//Visual C++ 6
#include<iostream>
#include<string>
using namespace std;


bool fixfree(string s1, string s2){
        if (s1.length()>s2.length())
                return fixfree(s2,s1);
        if (s2.substr(0,s1.length())==s1 || s2.substr(s2.length()-s1.length())==s1)
                return false;
        return true;
}

int main(){
       
        int i,N;
        cin>>N;
        string str1,str2,str3;
        for (i=0;i<N;i++){
       
                cin>>str1>>str2>>str3;
                if (fixfree(str1,str2) && fixfree(str1,str3) && fixfree(str2,str3))
                        cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
        }
       
        return 0;
}


S2:
code:

//Visual C++ 6

#include<fstream>

using namespace std;

int main(){
        int N,K,i,j,k,dummy;
        ifstream cin("s2.5.data");
        ofstream cout("s2.out");
        cin>>N>>K;
        //int rank[K][N];
        int tscore[150],worst[150];
        memset(worst,0,sizeof(worst));
        //memset(rank,0,sizeof(rank));
        memset(tscore,0,sizeof(tscore));
        for (i=0;i<K;i++){
                for (j=0;j<N;j++){
                        cin>>dummy;
                        tscore[j]+=dummy;
                }
               
                for (j=0;j<N;j++){
                        dummy=0;
                        for (k=0;k<N;k++)
                                if (tscore[k]>tscore[j])
                                        dummy++;
                        //rank[i][j]=dummy+1;
                        if (worst[j]<dummy+1) worst[j]=dummy+1;
                }
        }
        dummy=-0x7fffffff;
        for (i=0;i<N;i++)
                if (tscore[i]>dummy) dummy=tscore[i];
        for (i=0;i<N;i++)
                if (tscore[i]==dummy)
                        cout<<"Yodeller "<<i+1<<" is the TopYodeller: score "<<dummy<<", worst rank "<<worst[i]<<endl;

        return 0;
}


S3:
code:

//VC++6

#include<fstream>
#include<vector>
#include<string>
using namespace std;

int arr[300][300];
vector<string> str[300][300];


vector<string> tokenize(string str,string ch){
        vector<string> ret;
        int i,j;
        for (i=0;i<str.size();i=j+1){
                j=str.find_first_of(ch,i);
                if (j<0 || j>=str.length() || j==string::npos) j=str.length();
                if (j-i>0) ret.push_back(str.substr(i,j-i));
        }
        return ret;

}

int main(){
        ifstream cin("s3.5.data");
        ofstream cout("s35.out");
        string s;
        int i,j,k,l;
        for (i='A';i<='J';i++)
                for (j='1';j<='9';j++)
                        arr[i][j]=-1;
       
        for (i='A';i<='J';i++)
                for (j='1';j<='9';j++){
                        while(cin.peek()==' ' || cin.peek()=='\n') cin.ignore();
                        if (cin.peek()>='1' && cin.peek()<='9')
                                cin>>arr[i][j]; 
                       
                        else {
                                cin>>s;
                                str[i][j]=tokenize(s,"+");
                        }
                }
        for (k=0;k<100;k++)
                for (i='A';i<='J';i++)
                        for (j='1';j<='9';j++)
                                if (arr[i][j]==-1){
                                        int sum=0;
                                        for (l=0;l<str[i][j].size();l++){
                                                int dummy=arr[str[i][j][l][0]][str[i][j][l][1]];
                                                if (dummy>=0) sum+=dummy;
                                                else break;
                                        }              
                                        if (l==str[i][j].size())
                                                arr[i][j]=sum;
                                }
        for (i='A';i<='J';i++){
                        for (j='1';j<='9';j++)
                                if (arr[i][j]>=0)
                                        cout<<arr[i][j]<<" ";
                                else cout<<"*"<<" ";
                        cout<<endl;
        }

        return 0;
}

S5:DP solution O(M*N*N)

memo[x][y][a][b] contains the best value you can get at (x,y)
if (a,b)=(0,0) that means the best value you can get at (x,y), and you are allowed to go up and down
(1,0) i think is you can only go up
(0,1) is only going down
(1,1) doesnt do anthing (well at any given spot you can always go up and down.).

if you are at the corner its just means that you could go up/down but you are blocked by a wall

proof:

base case: if we update the first row all the way up, it will have the best value for the optimum path, and the next row will have been updated (to the right).

inductive case: suppose we have some cell in a row with the optimum value for some k (in the big loop below)

in the next path (k+1), we make two paths, one up and one down. the optimum path will either go up or down at the k+1 row (going right is considered going down 0 then go right), both of which are considered. then the value to the right is updated.

then at the last spot taking the max of the three values (actually we dont even need to consider [0][0]) to get the correct answer
code:

#include<fstream>

using namespace std;

int M,N;
char arr[110][110];

int memo[110][110][2][2];  //x,y,U,D, 1,1 is useless
bool uparr[110][110];

int max(int a, int b){
        return a>b?a:b;
}
int ck(int a, int b){
        if (a==-1) return -1;
        return a+b;
}
void up(int x,int y, int d1, int d2,int v){
        if (v>memo[x][y][d1][d2]){
                memo[x][y][d1][d2]=v;
                uparr[x][y]=true;
        }
}
void update(int x, int y, int x1, int y1){
       
        if (arr[x][y]=='*' || arr[x1][y1]=='*') return;
        int v=0;
       
        if (arr[x1][y1]!='.') v=arr[x1][y1]-'0';
        if (x==x1){
                up(x1,y1,0,0,ck(memo[x][y][0][0],v));
                up(x1,y1,0,0,ck(memo[x][y][0][1],v));
                up(x1,y1,0,0,ck(memo[x][y][1][0],v));
                up(x1,y1,0,1,memo[x1][y1][0][0]);
                up(x1,y1,1,1,memo[x1][y1][0][0]);
        }
        else if (x1-x==1){
                up(x1,y1,1,0,ck(memo[x][y][0][0],v));
                up(x1,y1,1,0,ck(memo[x][y][1][0],v));
        }
        else{
                up(x1,y1,0,1,ck(memo[x][y][0][0],v));
                up(x1,y1,0,1,ck(memo[x][y][0][1],v));
        }

       

}

int main(){
        ifstream cin("s5.5.data");
        ofstream cout("s55.out");
        int i,j,k;
        while(1){
        cin>>M>>N;
        if (M==0 && N==0) return 0;
        memset(arr,'*',sizeof(arr));
        memset(uparr,0,sizeof(uparr));
        for (i=0;i<110;i++) for(j=0;j<110;j++)
                for (k=0;k<2;k++) memo[i][j][k][0]=memo[i][j][k][1]=-1;
       

        for (i=1;i<=M;i++){
                for (j=1;j<=N;j++)
                        cin>>arr[i][j];
               
        }
       
        memo[M][1][0][0]=memo[M][1][0][1]=memo[M][1][1][0]=memo[M][1][1][1]=(arr[M][1]=='.'?0:arr[M][1]-'0');
        uparr[M][1]=true;
        int ee=true;
        for (k=0;k<100;k++){
                for (i=M;i>=1;i--)
                        for (j=1;j<=N;j++)
                                if (uparr[i][j]){
                                update(i,j,i+1,j);                       
                                update(i,j,i-1,j);
                                update(i,j,i,j+1);
                                uparr[i][j]=false;
                        }
                for (i=1;i<=M;i++)
                        for (j=1;j<=N;j++)
                                if (uparr[i][j]){
                                update(i,j,i+1,j);                       
                                update(i,j,i-1,j);
                                update(i,j,i,j+1);
                                uparr[i][j]=false;
                        }
        }
       
        int retval=max(max(memo[M][N][0][0],memo[M][N][0][1]),memo[M][N][1][0]);
        if (retval==-1) return 0;
        cout<<retval<<endl;
        }       
        return 0;
}
[/code]
bugzpodder




PostPosted: Thu Feb 26, 2004 9:16 am   Post subject: (No subject)

this is solution to s4 but there is a bug and it doesnt work for test case 2. it gives correct ans for all other cases. let me know if you know whats wrong
code:

//visual C++6

#include<fstream>
#include<cmath>
#include<iomanip>
using namespace std;


int sx,sy,sz;
int tx,ty,tz;

int oppo[6]={2,3,0,1,5,4};

double mind;

void ckdist(){
        double s=sqrt((sx-tx)*(sx-tx)+(sy-ty)*(sy-ty)+(sz-tz)*(sz-tz));
        if (s<mind)
                mind=s;

}
void update(int curdir,int dist){
        int i;
        if (curdir==0) for (i=0;i<dist;i++) {sx++; ckdist();}
        if (curdir==1) for (i=0;i<dist;i++) {sy++; ckdist();}
        if (curdir==2) for (i=0;i<dist;i++) {sx--; ckdist();}
        if (curdir==3) for (i=0;i<dist;i++) {sy--; ckdist();}
        if (curdir==4) for (i=0;i<dist;i++) {sz++; ckdist();}
        if (curdir==5) for (i=0;i<dist;i++) {sz--; ckdist();}
        //cout<<"The turtle is at "<<sx<<" "<<sy<<" "<<sz<<endl;

}
int main(){
        ifstream cin("s4.2.data");
        ofstream cout("s42.out");
        int dist;
        int u,d,l,r;
        int curdir;
        char ddd;
        cin>>sx>>sy>>sz>>tx>>ty>>tz;
        mind=sqrt((sx-tx)*(sx-tx)+(sy-ty)*(sy-ty)+(sz-tz)*(sz-tz));
        curdir=0;
        u=4;
        d=5;
        l=1;
        r=3;
        while(1){
                cin>>dist>>ddd;
                if (ddd=='E') break;
                update(curdir,dist);
                if (ddd=='L') {
                        int curdir2=l;
                        l=oppo[curdir];
                        r=curdir;
                        curdir=curdir2;
                }
                if (ddd=='R') {
                        int curdir2=r;
                        r=oppo[curdir];
                        l=curdir;
                        curdir=curdir2;
                }
                if (ddd=='U') {
                        int curdir2=u;
                        u=oppo[curdir];
                        d=curdir;
                        curdir=curdir2;
                }
                if (ddd=='D') {
                        int curdir2=d;
                        d=oppo[curdir];
                        u=curdir;
                        curdir=curdir2;
                }
        }
        cout<<setiosflags(ios::fixed)<<setprecision(2)<<mind<<endl;

        return 0;
}
Paul




PostPosted: Sun Mar 14, 2004 3:16 pm   Post subject: (No subject)

Woot J1:
code:

var tiles: int
put "Enter number of tiles: "
get tiles
put "you can make a square with side length of ",floor(sqrt(tiles))
TheZsterBunny




PostPosted: Wed Mar 24, 2004 8:11 am   Post subject: (No subject)

PB, that answer would lose you marks.

The correct way to do that question is this:

code:

var tiles : int
put "Enter number of tiles: "..
get tiles
put "The square has side length ",floor(sqrt(tiles)),"."


I lost marks on that because i had "square has a side length"

-bunny[/b]
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 18 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: