Computer Science Canada

Mock CCC (WCC)
Author:  A.J [ Sun Feb 15, 2009 11:31 am ]
Post subject:  Mock CCC (WCC)
As a practice for the actual CCC, danielG and I made the 'WCC' (Waterloo Computing Competition) for our school. We made a junior and senior set and we presented these questions to our school last friday (day before yesterday). I was wondering if people here are interested in writing the WCC too. The questions are CCC level with CCC formatting abd everything (although I confess that some questions are hard).

I want to make this an official contest here (if there are enough people participating)

I will post the questions here today, and if people seem interested, I'll give a time limit as to when u should submit your solutions to either danielG or me.

Please reply if you have looked at the questions, as we need some feedback so that I can improve on it next year (since danielG's graduating this year)

thanks Smile
Author:  saltpro15 [ Mon Feb 16, 2009 9:32 am ]
Post subject:  RE:Mock CCC (WCC)
wow, I'm reading through the junior one and this is still pretty hard, great job on the questions though, I'm definitely interested, is Turing acceptable?
Author:  A.J [ Mon Feb 16, 2009 10:06 am ]
Post subject:  Re: Mock CCC (WCC)
thanks Smile

yes, turing is definitely allowed

And, yes, the questions are slightly hard.......I am sorry Sad, but danielG and I meant to make them a bit harder than the actual CCC
Author:  saltpro15 [ Mon Feb 16, 2009 10:28 am ]
Post subject:  RE:Mock CCC (WCC)
well it'll be great practice, thanks for taking the time to do this

EDIT:

my Turing is going crazy, want to tell me why this isn't working?
Turing:

var input, output : int

open : input, "WCC2.txt", get

open : output, "OUT2.txt", put

var redcounter : int:= 0

var bluecounter : int := 0

var neck_len : int

var necklace : string


get : input, neck_len

get : input, necklace



for i : 1..neck_len



if necklace = "r" then

    redcounter += 1

else

    bluecounter += 1

end if



end for

put : output, redcounter

put : output, bluecounter


I can't run it to see if it works Sad I think it's right though
Author:  A.J [ Mon Feb 16, 2009 11:38 am ]
Post subject:  Re: Mock CCC (WCC)
please don't post your code on here..............
and I can't help you, sorry Sad, but you can pm me your solutions...

if you have any questions regarding the questions, I can help you.......

I should have mentioned this earlier, but if people really do want to do this contest, then could you refrain from discussing them here?

If more people reply to this thread, I'll post an 'endtime' (most likely sometime next week) so that people can send me their solutions till then and they can discuss the solution after the 'endtime'


EDIT : There are a few questions that might be a bit confusing as they weren't worded properly....If anyone has any questions regarding any of the problems, please let me know. Thanks Very Happy
Author:  chili5 [ Mon Feb 16, 2009 5:34 pm ]
Post subject:  RE:Mock CCC (WCC)
That is excellent!

The junior questions are a bit easy though. Finished the first two questions.
Keep it up though, there are great! Very Happy
Author:  DanielG [ Mon Feb 16, 2009 6:14 pm ]
Post subject:  RE:Mock CCC (WCC)
congrats, none of the juniors in our school got past question 2 (Sadly).
Author:  Crazymik3 [ Mon Feb 16, 2009 7:02 pm ]
Post subject:  RE:Mock CCC (WCC)
Awesome, I'm going to download these and give them a shot to practice for the CCC.
Author:  A.J [ Mon Feb 16, 2009 7:10 pm ]
Post subject:  Re: Mock CCC (WCC)
k, since we do have people interested, how about I make the deadline next Saturday then?

I'll give people the time to finish up their solutions and pm them to me....or email them to me at : amleshjayakumar (at symbol) yahoo.ca (email me preferably)

Good luck!


chili5 wrote:

That is excellent!

The junior questions are a bit easy though. Finished the first two questions.
Keep it up though, there are great! D


thanks for the compliment! danielG and I did take a lot of time making these questions.
do u want to email me your solutions so that I can check them?
Author:  chili5 [ Mon Feb 16, 2009 8:57 pm ]
Post subject:  RE:Mock CCC (WCC)
Great, I sent you my first two. I'll hopefully have a working #4 tomorrow. I am almost there! Smile
Author:  A.J [ Mon Feb 16, 2009 9:59 pm ]
Post subject:  Re: Mock CCC (WCC)
i dont have a java compiler...........so can u send them to me as a txt document so that i can see your code (cuz i cant open what u sent me as a text document for some reason)


good job though!
Author:  chili5 [ Tue Feb 17, 2009 6:31 am ]
Post subject:  RE:Mock CCC (WCC)
Yeah, opening Java files in notepad doesn't work the greatest. :confused:

Thanks, got 2 more to do those were fun! Very Happy
Author:  DemonWasp [ Tue Feb 17, 2009 8:09 am ]
Post subject:  RE:Mock CCC (WCC)
Opening .java files in notepad works just fine, except that many editors use the simple \n endline character, while notepad expects \r\n because it's dumb. Sadly, there's no real way to tell it to be smarter. Try opening the file in a real editor (cough, Vim) and you'll have no such trouble.
Author:  A.J [ Tue Feb 17, 2009 3:43 pm ]
Post subject:  Re: Mock CCC (WCC)
I just clarify that you can submit your solutions how many ever times you want (until u get it right, anyway....)

I am glad people are liking these questions!

If you liked the questions, could you spread the word?

thanks Very Happy
Author:  chili5 [ Tue Feb 17, 2009 5:54 pm ]
Post subject:  RE:Mock CCC (WCC)
The actual CCC questions specify a name of the input file that is expected to be used. How about you add that, to make it seem more real? Smile
Author:  A.J [ Tue Feb 17, 2009 6:25 pm ]
Post subject:  Re: Mock CCC (WCC)
Oh, sorry, I forgot to mention it Embarassed

Yes, I did add file input and output files when I gave this contest for my school to write it....it might have slipped my mind.

For the seniors, it is input from the text file : "sx.txt", where 'x' is the problem number...and output (unlike the actual CCC) is to the screen.

As for the junior, the input and output is from and to the screen.

thanks for reminding me chili5!
Author:  saltpro15 [ Tue Feb 17, 2009 6:28 pm ]
Post subject:  RE:Mock CCC (WCC)
will you take off marks if we used read and write?
Author:  A.J [ Tue Feb 17, 2009 6:37 pm ]
Post subject:  Re: Mock CCC (WCC)
....no, as long as it works
Author:  Zren [ Wed Feb 18, 2009 5:23 am ]
Post subject:  Re: Mock CCC (WCC)
This ought'a help me practice my java skillz. Thanks.

One question about Senior #2 though. Does the "ck n" function check the y or z axis, since depth could either fall under the depth of the water or the depth into the screen or whateverness.

Edit: Nvm, I re-read it and realized you used z as up and down like underwater. It also solves the sample.
Author:  A.J [ Wed Feb 18, 2009 12:00 pm ]
Post subject:  Re: Mock CCC (WCC)
Zren wrote:

This ought'a help me practice my java skillz. Thanks.

One question about Senior #2 though. Does the "ck n" function check the y or z axis, since depth could either fall under the depth of the water or the depth into the screen or whateverness.

Edit Nvm, I re-read it and realized you used z as up and down like underwater. It also solves the sample.


good job, but next time can you NOT post your realisations here?

good job though Very Happy
Author:  A.J [ Wed Feb 18, 2009 6:24 pm ]
Post subject:  Re: Mock CCC (WCC)
k, so far I got one person who sent me his solution to certain questions....aren't there anyone else?

This is good CCC practice....I am just sad that nobody made DanielG and I a practice contest Sad....

so, if anyone have any questions regarding ANY of the questions, please don't hesitate to email me (don't post your questions here, as there are people working on them)

thanks Very Happy
Author:  saltpro15 [ Wed Feb 18, 2009 6:44 pm ]
Post subject:  RE:Mock CCC (WCC)
Q4 of the junior is quite challenging, I doubt I'm going to get this one, great job on the questions though
Author:  chili5 [ Wed Feb 18, 2009 6:47 pm ]
Post subject:  RE:Mock CCC (WCC)
Take a good try at Q4 it isn't that challenging. The only hard ones are 3 and 5. Smile
Author:  A.J [ Wed Feb 18, 2009 6:51 pm ]
Post subject:  Re: Mock CCC (WCC)
saltpro15 wrote:

Q4 of the junior is quite challenging, I doubt I'm going to get this one, great job on the questions though


don't worry, you can do it Smile
and thanks Smile

chili5 wrote:

Take a good try at Q4 it isn't that challenging. The only hard ones are 3 and 5. )


I agree that they are hard, but they are doable Smile

gud luck Smile
Author:  saltpro15 [ Thu Feb 19, 2009 1:39 pm ]
Post subject:  RE:Mock CCC (WCC)
I think I have solved J2 and J3 Very Happy i will pm them to you tonight after DWITE, (i'm on my psp right now lol)
Author:  phleet [ Sat Feb 21, 2009 11:01 pm ]
Post subject:  RE:Mock CCC (WCC)
Questions:

1. For question J3, are similar cycles considered identical?

e.g.

WWBBB
is the same as
BWWBB

2. For question J4, are all team names always a single word?

3. For question J4, if a team takes first place, then retakes it after being bumped to a lower rank, is there name listed twice in the output? I'm assuming that if they raised their score while already in first place, it is only output once.

Edit:

4. For question J4, is it 20 marks/correct test case? I'm guessing it follows the conventions of DWITE itself, but the way the question is written is confusing.

"Finally, O(n) took the lead by submitting a solution for question #2 and achieved a total score of 9 (taking first place from Hanson). "

and yet, Hanson's first submission is: Hanson 1 5
meaning he should have gotten a 10 mark bonus for a perfect first submission, and yet it says below that O(n) surpassed him with a total score of 9? 9 > 10?
Author:  A.J [ Sat Feb 21, 2009 11:43 pm ]
Post subject:  Re: Mock CCC (WCC)
phleet wrote:

Questions

1. For question J3, are similar cycles considered identical?

e.g.

WWBBB
is the same as
BWWBB

2. For question J4, are all team names always a single word?

3. For question J4, if a team takes first place, then retakes it after being bumped to a lower rank, is there name listed twice in the output? I'm assuming that if they raised their score while already in first place, it is only output once.

Edit

4. For question J4, is it 20 marks/correct test case? I'm guessing it follows the conventions of DWITE itself, but the way the question is written is confusing.

"Finally, O(n) took the lead by submitting a solution for question #2 and achieved a total score of 9 (taking first place from Hanson). "

and yet, Hanson's first submission is Hanson 1 5
meaning he should have gotten a 10 mark bonus for a perfect first submission, and yet it says below that O(n) surpassed him with a total score of 9? 9 > 10?


hmm...I guess we didn't catch that.........you are right, hanson remains first

and yes, the team names contain only one word, and u can assume 20 per testcase (sorry about not adding the info in there Sad....)

And for J2, WWBBB is the same as BWWBB.
Author:  phleet [ Sun Feb 22, 2009 1:13 am ]
Post subject:  RE:Mock CCC (WCC)
Still working through the Junior problems.

For J4, is it safe to assume that there will not be three submissions from the same team on the same problem in the input?

J4 Again: Hanson does not remain first. The statement of O(n) taking the lead is correct. The issue I had with that statement was that it said his total score was 9. O(n) should have 190 points. (110 from first submission for perfect entry, and 80 from second submission). At that point, Hanson has 110, having been the first to submit a perfect solution to the first problem.

For J5, it should be made clearer that Ash falls in if he hits a square he's already crossed. The way it's written at the moment makes it seem as if moving towards a square already crossed is an invalid move (making the last move of the test case shown invalid).
Author:  A.J [ Sun Feb 22, 2009 11:17 am ]
Post subject:  Re: Mock CCC (WCC)
phleet wrote:

For J5, it should be made clearer that Ash falls in if he hits a square he's already crossed. The way it's written at the moment makes it seem as if moving towards a square already crossed is an invalid move (making the last move of the test case shown invalid).


Doesn't it already state that? It seems like I posted the wrong version of the WCC then....but as long as you know the updates that we didn't put up there, then its ok Smile
Author:  phleet [ Sun Feb 22, 2009 12:55 pm ]
Post subject:  RE:Mock CCC (WCC)
I realize I may be getting annoying at this point Razz

In S5, there is some conflicting statements.
It initially says to find the number of ways in which Thor can reach his castle _before_ his guests do.

directly after that, it says "we just want to find the number of different ways that Thor?s path has an equal length to that of his guests? path to his castle"

I'm assuming it's actually asking for the number of paths of equal or lesser length than the shortest distance from the Guests' castle.
Author:  A.J [ Sun Feb 22, 2009 1:45 pm ]
Post subject:  Re: Mock CCC (WCC)
thats it, here are the REVISED versions of Senior and Junior WCC (and you want to find the # of paths for Thor that is LESS than that of the guests)
Author:  chili5 [ Wed Mar 18, 2009 2:30 pm ]
Post subject:  RE:Mock CCC (WCC)
Hm, how long is this going to go? I wouldn't mind talking about the questions. Like what is the concepts behind S3? I have no idea how to do those optimal path through a maze questions.
Author:  saltpro15 [ Wed Mar 18, 2009 2:36 pm ]
Post subject:  RE:Mock CCC (WCC)
optimal paths in a maze are usually found with a BFS or a DFS algorithm, by which I mean Best First Search and Depth First Search. There are some excellent articles on them on this site
Author:  A.J [ Wed Mar 18, 2009 3:46 pm ]
Post subject:  RE:Mock CCC (WCC)
well, I think you meant Breadth First Search , but Best First Search exists too.

And as only2 people sent me their solutions in about 1 month, I think it is safe to say that people can discuss the solutions (or ask me for some of them)
Author:  saltpro15 [ Wed Mar 18, 2009 4:21 pm ]
Post subject:  RE:Mock CCC (WCC)
yes A.J. is correct, it's Breadth Embarassed
Author:  chili5 [ Wed Mar 18, 2009 6:20 pm ]
Post subject:  RE:Mock CCC (WCC)
Okay thanks guys! I found a very helpful tutorial on recursion:

http://compsci.ca/v3/viewtopic.php?t=9581

Curious as to how people handled S2.

My solution:

CODE:


import java.io.*;
import java.util.*;
/**
 *
 * @author James
 */
public class s2 {
    public static int nX = 0, nY = 0, nZ = 0; // coordinates
    public static boolean bGood = true; // if a test succeeded = true

    public static void main(String[] args) throws IOException {
        Scanner sin = new Scanner(new FileReader("s2.txt"));
        int nIns; // number of instructions
        String sIns; // the instruction
        int nN; // number of units to move
       

        nIns = sin.nextInt();

        for (int i=0;i<nIns;i++) {
            sIns = sin.next();
            nN = sin.nextInt();
            move(sIns,nN);
        }

        if (bGood = true) {
            System.out.println("Time to go pirating while living in the yellow submarine!");
        } else {
            System.out.println("Oh well, I guess it is back to our ancient Viking ship…");
        }

        sin.close();
    }

    public static void move(String sIns, int nN) {
        if (sIns.equals("fd")) {
            // move forward on x nN units
            nX += nN;
            if (nX >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
           
        } else if (sIns.equals("bk")) {
            nX -= nN;
            if (nX >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if (sIns.equals("rt")) {
            nY += nN;
            if (nY >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if (sIns.equals("lt")) {
            nY -= nN;
            if (nY >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if (sIns.equals("up")) {
            nZ += nN;
            if (nZ >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if(sIns.equals("dn")) {
            nZ -= nN;
            if (nZ >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else {
            if (nZ == nN) {
                bGood = true;
            } else {
                bGood = false;
            }
        }
    }

}


Anybody get anything better?
Author:  Analysis Mode [ Wed Mar 18, 2009 6:37 pm ]
Post subject:  Re: RE:Mock CCC (WCC)
saltpro15 @ Wed Mar 18, 2009 2:36 pm wrote:
optimal paths in a maze are usually found with a BFS or a DFS algorithm, by which I mean Best First Search and Depth First Search. There are some excellent articles on them on this site


Well, you're kind of unclear there. If the maze has one exit, use DFS. If there are multiple exits, use BFS.
Author:  A.J [ Wed Mar 18, 2009 6:55 pm ]
Post subject:  Re: Mock CCC (WCC)
Analysis Mode wrote:

saltpro15 @ Wed Mar 18, 2009 2:36 pm wrote:
optimal paths in a maze are usually found with a BFS or a DFS algorithm, by which I mean Best First Search and Depth First Search. There are some excellent articles on them on this site


Well, you're kind of unclear there. If the maze has one exit, use DFS. If there are multiple exits, use BFS.


Not necessarily, Analysis Mode. You can interchangeably use either (although I am not sure whether that sentence is grammatically correct Laughing). It is the algorithm's complexity and what the question is asking specifically you must take into account.

chili5 wrote:


Curious as to how people handled S2.

My solution:

CODE:


import java.io.*;
import java.util.*;
/**
 *
 * @author James
 */
public class s2 {
    public static int nX = 0, nY = 0, nZ = 0; // coordinates
    public static boolean bGood = true; // if a test succeeded = true

    public static void main(String[] args) throws IOException {
        Scanner sin = new Scanner(new FileReader("s2.txt"));
        int nIns; // number of instructions
        String sIns; // the instruction
        int nN; // number of units to move
       

        nIns = sin.nextInt();

        for (int i=0;i<nIns;i++) {
            sIns = sin.next();
            nN = sin.nextInt();
            move(sIns,nN);
        }

        if (bGood = true) {
            System.out.println("Time to go pirating while living in the yellow submarine!");
        } else {
            System.out.println("Oh well, I guess it is back to our ancient Viking ship…");
        }

        sin.close();
    }

    public static void move(String sIns, int nN) {
        if (sIns.equals("fd")) {
            // move forward on x nN units
            nX += nN;
            if (nX >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
           
        } else if (sIns.equals("bk")) {
            nX -= nN;
            if (nX >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if (sIns.equals("rt")) {
            nY += nN;
            if (nY >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if (sIns.equals("lt")) {
            nY -= nN;
            if (nY >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if (sIns.equals("up")) {
            nZ += nN;
            if (nZ >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if(sIns.equals("dn")) {
            nZ -= nN;
            if (nZ >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else {
            if (nZ == nN) {
                bGood = true;
            } else {
                bGood = false;
            }
        }
    }

}


Anybody get anything better?


Although your code does work (at least I think it should), there is a lot of redundant code. Since the question is asking you to check if the depth matches the given checks, all you really need to store is the 'z' position.....but your method is correst, good job Wink.
Author:  A.J [ Wed Mar 18, 2009 6:55 pm ]
Post subject:  Re: Mock CCC (WCC)
Analysis Mode wrote:

saltpro15 @ Wed Mar 18, 2009 2:36 pm wrote:
optimal paths in a maze are usually found with a BFS or a DFS algorithm, by which I mean Best First Search and Depth First Search. There are some excellent articles on them on this site


Well, you're kind of unclear there. If the maze has one exit, use DFS. If there are multiple exits, use BFS.


Not necessarily, Analysis Mode. You can interchangeably use either (although I am not sure whether that sentence is grammatically correct Laughing). It is the algorithm's complexity and what the question is asking specifically you must take into account.

chili5 wrote:


Curious as to how people handled S2.

My solution:

CODE:


import java.io.*;
import java.util.*;
/**
 *
 * @author James
 */
public class s2 {
    public static int nX = 0, nY = 0, nZ = 0; // coordinates
    public static boolean bGood = true; // if a test succeeded = true

    public static void main(String[] args) throws IOException {
        Scanner sin = new Scanner(new FileReader("s2.txt"));
        int nIns; // number of instructions
        String sIns; // the instruction
        int nN; // number of units to move
       

        nIns = sin.nextInt();

        for (int i=0;i<nIns;i++) {
            sIns = sin.next();
            nN = sin.nextInt();
            move(sIns,nN);
        }

        if (bGood = true) {
            System.out.println("Time to go pirating while living in the yellow submarine!");
        } else {
            System.out.println("Oh well, I guess it is back to our ancient Viking ship…");
        }

        sin.close();
    }

    public static void move(String sIns, int nN) {
        if (sIns.equals("fd")) {
            // move forward on x nN units
            nX += nN;
            if (nX >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
           
        } else if (sIns.equals("bk")) {
            nX -= nN;
            if (nX >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if (sIns.equals("rt")) {
            nY += nN;
            if (nY >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if (sIns.equals("lt")) {
            nY -= nN;
            if (nY >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if (sIns.equals("up")) {
            nZ += nN;
            if (nZ >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else if(sIns.equals("dn")) {
            nZ -= nN;
            if (nZ >= 0) {
                bGood = true;
            } else {
                bGood = false;
            }
        } else {
            if (nZ == nN) {
                bGood = true;
            } else {
                bGood = false;
            }
        }
    }

}


Anybody get anything better?


Although your code does work (at least I think it should), there is a lot of redundant code. Since the question is asking you to check if the depth matches the given checks, all you really need to store is the 'z' position.....but your method is correst, good job Wink.
Author:  chili5 [ Wed Mar 18, 2009 7:03 pm ]
Post subject:  RE:Mock CCC (WCC)
So it would be good to learn both DFS and BFS? I keep thinking they just apply to graphs though.

So really you could have ignored any command that had anything to do with the x or y axis? Smile
Author:  Analysis Mode [ Wed Mar 18, 2009 7:47 pm ]
Post subject:  Re: Mock CCC (WCC)
oh yes you should. Two different concepts, to be applied in different scenarios. Substituting one for the other could lead to TLE.
Author:  saltpro15 [ Wed Mar 18, 2009 8:05 pm ]
Post subject:  RE:Mock CCC (WCC)
Basically, if you're maze is more "open" with more clear space, you want to use a DFS, since it is easier to code and takes less time to write. But, if the maze is cluttered with lots of paths and objects, you have to use BFS, else your program can run for hours on end Very Happy
Author:  Analysis Mode [ Wed Mar 18, 2009 11:04 pm ]
Post subject:  Re: Mock CCC (WCC)
OK. Let me rephrase. If i'm asking you for the shortest path between the start and end of a maze, BFS / Dijkstra's (depending on whether or not edges are weighted (not based on path length)) If i'm asking you if it's possible to reach the end from the start, DFS (connectivity in a graph).

And if there's a lot of open space, definitely not DFS. First off, when you reach the end, it is not guaranteed that you have the optimal answer, whereas BFS does. And the time complexity increases exponentially as the grid size increases (I think).
Author:  A.J [ Wed Mar 18, 2009 11:09 pm ]
Post subject:  RE:Mock CCC (WCC)
I don't think it is exponentially (although I'm notorious for being wrong in my suppositions). And about the DFS/BFS, now it is clearer....I agree with you there. If the graph is weighted, Dijkstra is optimal, although there are other methods.
Author:  DanielG [ Thu Mar 19, 2009 6:08 pm ]
Post subject:  RE:Mock CCC (WCC)
I believe it is in fact exponential, since I can't think of any polynomial equation that would fit for it, I suppose it just has a very small multiplier for the exponent.
Author:  bbi5291 [ Thu Mar 19, 2009 7:45 pm ]
Post subject:  Re: Mock CCC (WCC)
Say there are V vertices and E edges. No two connected vertices can be separated by a distance of more than V-1, so we may initially set all entries of a distance array to V, and then run our DFS. At each point we have the distance to the current vertex; we continue recursing only if this is less than the distance currently stored. Hence each vertex is visited at most V times, and an edge is traversed only when it would lead to a decrease in distance for a vertex, so no more than EV edge traversals can occur. I therefore claim that the runtime of DFS shortest-path is bounded by O(V(E+V)). Compare this however to BFS which runs in guaranteed O(E+V) time, and you can see which one is the obvious choice. However you can see that the running time is still strongly polynomial (and not exponential).
Author:  A.J [ Fri Mar 20, 2009 12:13 pm ]
Post subject:  RE:Mock CCC (WCC)
I agree with Brian. It is not exponential, however the runtime isn't formidable.
Author:  chili5 [ Sat Mar 21, 2009 5:47 pm ]
Post subject:  RE:Mock CCC (WCC)
I get how the DFS applies to a graph. You check one path completely before checking another path. Is the concept the same with mazes?

Can someone point me at a good resource for DFS and BFS? Other than the turing tutorial here which I don't understand very well?
Author:  A.J [ Sat Mar 21, 2009 6:01 pm ]
Post subject:  RE:Mock CCC (WCC)
well, the tutorial here is actually quite good....however, if you would like, I would not mind explaining DFS/BFS to you
Author:  saltpro15 [ Sat Mar 21, 2009 6:54 pm ]
Post subject:  RE:Mock CCC (WCC)
umm guys you lost me with this maze/graph talk...
My understanding is that BFS/DFS is used for questions like these
http://dwite.org/questions/shortest_path_around_v2.html
please correct me, I wish to learn Very Happy
what is an example of a graph problem? like S3 of this year's CCC ?
Author:  A.J [ Sat Mar 21, 2009 7:05 pm ]
Post subject:  RE:Mock CCC (WCC)
@saltpro15 - You shouldn't only use DFS/BFS for questions like those. They have sooo many applications. For example, one example for using BFS is when you want to solve the slide puzzle (or the 8 puzzle, 15 puzzle, etc... it really depends on the size of the board). Your starting point is the current configuration of the board, and your goal is the required endstate. You can BFS outwards, by performing a move on the board (i.e. sliding the squares on the board) to get new configurations of the board, which you will then add to your FIFO queue (i.e. 'first in first out' queue).

As for DFS, there is a small variation of DFS, called DFSID (Depth First Search with Iterative Deepening). In essence it covers the same route BFS covers, but it has its benefits. It is basically DFS'ing to a certain 'depth'. DFSID is very useful when creating AI for games like Chess, where you have to deal with a bunch of moves.

Also, a bit more obvious application, is in graphs. The question you provided in the link, saltpro15, is a shortest path question; but what if the input isn't given to you as a grid, but as a graph (with nodes, edges, starting and ending points). You must first realize that for DFS/BFS to work for such a graph, the distance between any 2 nodes must be the same (otherwise DFS/BFS won't work). If the distances aren't the same, then maybe algorithms like Floyd-Warshall's or Dijkstra's will definitely come in handy (depending on the size of the input).

So, here are some of the other applications of DFS/BFS, saltpro15.
Author:  saltpro15 [ Sat Mar 21, 2009 7:11 pm ]
Post subject:  RE:Mock CCC (WCC)
ok, thanks A.J. , you're basically my CS teacher now haha, I learned DP pretty much just from your DWITE work, good job Wink
Author:  A.J [ Sat Mar 21, 2009 7:36 pm ]
Post subject:  Re: Mock CCC (WCC)
saltpro15 wrote:

ok, thanks A.J. , you're basically my CS teacher now haha, I learned DP pretty much just from your DWITE work, good job Wink

That's flattering, thanks Very Happy
Author:  saltpro15 [ Sat Mar 21, 2009 7:47 pm ]
Post subject:  RE:Mock CCC (WCC)
no problem, you don't graduate this year do you? I still need to learn Dijkstra's lol
Author:  saltpro15 [ Sat Mar 21, 2009 8:03 pm ]
Post subject:  RE:Mock CCC (WCC)
woo 500 bits!

ok that's the last of my off-topic-ness, did anyone ever get J4? I thought I almost had it until I realized I did it wrong, then gave up
Author:  Analysis Mode [ Sat Mar 21, 2009 10:07 pm ]
Post subject:  Re: Mock CCC (WCC)
There are four shortest path algorithms I use:

1) BFS (only in unweighted graphs) O(V+E)
2) Dijkstra's (in any graphs with no negative edge weights) O((E+V) log V) using a heap
3) Floyd-Warshall's (in any graph less then 100 vertices (because of it's time complexity O(V^3))
4) Bellman-Ford (in any graph with negative edge weights but no negative cycles ) O(VE)

It's essential to know the first three, but as for the last one, it isn't that prevalent. I've only had to code it because a problem required it (and it was worth points in my CS class).

And yes, the problem J5/S3 this year was indeed a graph theory problem. Floyd-Warshall's came in handy in the shortest path of it because:

1) It's faster and easier to code than BFS.
2) There were less than 100 people, so time wasn't a problem.

The other parts were basic operations on a graph (stored in an adjacency matrix due to small size). If the graph was bigger, I would've used an adjacency list, in which case I wouldn't have used Floyd's; most likely, my next choice would've been BFS.

Given this graph:

1
/ \
2 3
/ \ / \
4 5 6 7

DFS would visit the nodes in this order:

1, 2, 4, 2, 5, 2, 1, 3, 6, 3, 7, 3, 1 (note I'm including all backtracking)

BFS:

1, 2, 3, 4, 5, 6, 7
Author:  A.J [ Sat Mar 21, 2009 10:27 pm ]
Post subject:  RE:Mock CCC (WCC)
yes, thats true

Floyd Warshall was a good way to go for this years S3/J5
Author:  chili5 [ Sun Mar 22, 2009 5:18 am ]
Post subject:  Re: RE:Mock CCC (WCC)
A.J @ Sat Mar 21, 2009 6:01 pm wrote:
well, the tutorial here is actually quite good....however, if you would like, I would not mind explaining DFS/BFS to you


That would be great! Maybe the tutorial is good, just I don't seem to understand. Sad
Author:  bbi5291 [ Sun Mar 22, 2009 11:17 am ]
Post subject:  Re: RE:Mock CCC (WCC)
A.J @ Sat Mar 21, 2009 7:05 pm wrote:
You shouldn't only use DFS/BFS for questions like those. They have sooo many applications. For example, one example for using BFS is when you want to solve the slide puzzle (or the 8 puzzle, 15 puzzle, etc... it really depends on the size of the board)


Yeah, for the 8 puzzle it's fine, because there are only (I think) 9!/2 = 181440 vertices and about four times as many edges. But for the 15 puzzle the state space is too large, and you're better off using A*, which is like Dijkstra's but uses a heuristic to guess which way to go next, in order to speed up the search. Consider that there are 16!/2 = 10461394944000 configurations and you'll see what I mean.
Author:  A.J [ Sun Mar 22, 2009 1:23 pm ]
Post subject:  Re: Mock CCC (WCC)
bbi5291 wrote:

A.J @ Sat Mar 21, 2009 7:05 pm wrote:
You shouldn't only use DFS/BFS for questions like those. They have sooo many applications. For example, one example for using BFS is when you want to solve the slide puzzle (or the 8 puzzle, 15 puzzle, etc... it really depends on the size of the board)


Yeah, for the 8 puzzle it's fine, because there are only (I think) 9!/2 = 181440 vertices and about four times as many edges. But for the 15 puzzle the state space is too large, and you're better off using A*, which is like Dijkstra's but uses a heuristic to guess which way to go next, in order to speed up the search. Consider that there are 16!/2 = 10461394944000 configurations and you'll see what I mean.


You are right, A* is optimal. However, BFS would also work, eventhough it is too slow. I just meant to give a couple of applications of BFS.
Author:  DanielG [ Mon Mar 23, 2009 10:49 am ]
Post subject:  RE:Mock CCC (WCC)
since when did this change from a discussion of the mock CCC to a discussion on graph search algorithms?
Author:  A.J [ Mon Mar 23, 2009 11:05 am ]
Post subject:  Re: Mock CCC (WCC)
DanielG wrote:

since when did this change from a discussion of the mock CCC to a discussion on graph search algorithms?


Come to think of it...I have NO clue Confused

At least we are still talking about CS, unlike the time when I once was talking to my friends about a CS presentation and it ended up becoming a conversation about cow crap, and then to the fact that Arnold Schwarzenegger marrying his muscles cause he likes them that much....

That night, I didn't sleep well...
Author:  chili5 [ Mon Mar 23, 2009 3:11 pm ]
Post subject:  RE:Mock CCC (WCC)
We were talking about the approach to question 3. Which is how it got on graph search algorithms. :-s
Author:  Fyren [ Sun May 31, 2009 4:55 pm ]
Post subject:  Re: Mock CCC (WCC)
For J5 why cant ash turn and go up then left and continue? I dont see why he cant move after he goes right.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy