 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
does anyone have any solutions to this years contest?       Author Message
amvbse Posted: 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?    Chimaera Posted: 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  Posted: 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 Posted: 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 Posted: 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  Posted: 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" but just cuz of the way they wrote the question, I didnt even understand what they were asking at first 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 S3 - recursion, substrings (turing's index helps, but I dont know if that part of the code even works right ) 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 Just write your maze recursion and let it run wild  Tony's programming blog. DWITE - a programming contest. amvbse Posted: 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  Posted: 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. Tony's programming blog. DWITE - a programming contest.    amvbse Posted: 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  Posted: Wed Feb 25, 2004 12:39 am   Post subject: (No subject)

its just like any other maze 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) Tony's programming blog. DWITE - a programming contest. bugzpodder  Posted: 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  Posted: Thu Feb 26, 2004 8:52 am   Post subject: (No subject)

S1:

 code: //Visual C++ 6 #include #include 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>str1>>str2>>str3;                 if (fixfree(str1,str2) && fixfree(str1,str3) && fixfree(str2,str3))                         cout<<"Yes"<

S2:
 code: //Visual C++ 6 #include 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,worst;         memset(worst,0,sizeof(worst));         //memset(rank,0,sizeof(rank));         memset(tscore,0,sizeof(tscore));         for (i=0;i>dummy;                         tscore[j]+=dummy;                 }                                 for (j=0;jtscore[j])                                         dummy++;                         //rank[i][j]=dummy+1;                         if (worst[j]dummy) dummy=tscore[i];         for (i=0;i

S3:
 code: //VC++6 #include #include #include using namespace std; int arr; vector str; vector tokenize(string str,string ch){         vector ret;         int i,j;         for (i=0;i=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=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<

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 ) to get the correct answer
 code: #include using namespace std; int M,N; char arr; int memo;  //x,y,U,D, 1,1 is useless bool uparr; 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],v));                 up(x1,y1,0,0,ck(memo[x][y],v));                 up(x1,y1,0,0,ck(memo[x][y],v));                 up(x1,y1,0,1,memo[x1][y1]);                 up(x1,y1,1,1,memo[x1][y1]);         }         else if (x1-x==1){                 up(x1,y1,1,0,ck(memo[x][y],v));                 up(x1,y1,1,0,ck(memo[x][y],v));         }         else{                 up(x1,y1,0,1,ck(memo[x][y],v));                 up(x1,y1,0,1,ck(memo[x][y],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]=memo[i][j][k]=-1;                 for (i=1;i<=M;i++){                 for (j=1;j<=N;j++)                         cin>>arr[i][j];                         }                 memo[M]=memo[M]=memo[M]=memo[M]=(arr[M]=='.'?0:arr[M]-'0');         uparr[M]=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],memo[M][N]),memo[M][N]);         if (retval==-1) return 0;         cout<
[/code] bugzpodder  Posted: 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 #include #include using namespace std; int sx,sy,sz; int tx,ty,tz; int oppo={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>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< Paul  Posted: 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  Posted: 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: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First        Page 1 of 2  [ 18 Posts ]
Goto page 1, 2  Next
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: