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

Username:   Password: 
 RegisterRegister   
 Complete CCC 2006 Junior Analysis
Index -> Contests
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
MysticVegeta




PostPosted: Fri Mar 03, 2006 8:38 pm   Post subject: Complete CCC 2006 Junior Analysis

Since the other thread is mostly of Senior, I made one more, dont sue me lol. The problem set of this year was relatively easy, no recursions/advanced algorithms.

Problem 1:
Difficulty: Average Grade 10 student must be able to get this.
The Problem 1 was a joke. Give 16 items, count the total calories.
Strongest Implementation: Lets create 16 variables Rolling Eyes I mean 1 1..16 array. Now, let the 1st 4 elements be calories of burger, let the next 4 be of side orders, next 4 of drinks and the last 4 of desserts. Take input #1 (a), then totalCalories = calorieArray (a)
#2, totalCalories += calorieArray (a+4)
#3, totalCalories += calorieArray (a+8)
#4, totalCalories += calorieArray (a+12)
Output the answer.
Time Taken: 3 minutes (reading inc.)

Problem 2:
Difficulty: Average Grade 10 student must be able to get this.
This problem was pretty much a joke. Given 2 ints (m, n), m and n represent an array of numbers from 1 to m and 1 to n respectively. How many combinations create the sum "10".
Well before we get into nested loops, if m > 9 then m = 9, if n > 9, n = 9, we do that because if m is >= 10, then how the hell can we add a # to it to get 10 when n != 0?
After that, we put nested loop, x : 1 to m, and y : 1 to n, if x + y = 10, counter += 1.
Output counter.
Time Taken: 5 minutes (reading inc.)

Problem 3:
Difficulty: Average Grade 10 or 11 student must be able to get this.
Wow, this problem was an insult to difficulty level 3. If you are in grade 10 and you didnt get that, I am gonna smack ya @$$! joking lol. Anyways, This problem is somewhat long to explain so I am just gonna attach it, look at the attachment for the problem.
Keypoints: Each letter takes 1 second to type.
A pause of 2 second occurs when the next letter in the input string falls under the same number. for example: "abba", the a takes 1 second, then we need pause for 2, the b takes 2 seconds (index of 2 in string "abc"), then we need pause of 2, the the b again 2 second, then pause then a. Total 12 seconds.
Not at all confusing once you get used to it. First we create an array 1..8 to store the letters in groups i.e. ("abc", "def", "ghi"...) All we have to do is get the inputs in flex array. Run a loop from 1 to arrayslength - 1 (-1 because we dont need the word "halt" in) Now run a loop from 1 to length(input(x)) then finally 1 more loop from 1 to 8 to check under which group of letters does the character fall in. so it will look something like this:
code:

%Note: PseudoCode
var groupOfLetters : array 1..8 of string := init ("abc", "def", "ghi"...)
for x : 1..upper(inputs)-1
     for y : 1..length(inputs(x))
            for z : 1..8
                    Code here.
            end for
     end for
end for

Code here: ok, so now we check for the characters index in each of the string of the array. For eg: in "abba" when z = 1, it will find the index of 1 for the character "a" in stirng "abc" , so we add +1 to counter. Similarly for b, it will add 2 since its the 2nd letter in the string "abc". But wait are we done? We still need to figure out the pause. damn, so now, you add one if structure in the z loop,
code:
if (y not= length(inputs(x)) and index(groupOfLetters(z), input(x)(y+1) >= 1) then
count+=2
end if

This checks if the next letter is in the same element of the array, if it is, +2 is added to the counter for pause.

Output counter.
Time take: 14 minutes (reading inc.)


Problem 4:
Difficulty: Above Average Grade 10 student must be able to get this.
I will not lie, this problem pissed me off for 1 whole damn hour. I dont know what the hell but it was confusing and not hard. Read it carefully, The algorithm I used in attached on a scanned paper below. After looking at it, here is the steps to implement it.
-> Make an array 1..7 of boolean, set all to true, telling us that it is possible to do every task right now.
-> Make an empty string called ans = ""
-> Make an infinite loop
-> At the beginning set all elements in boolean array to true
-> Then we set booleanArray ( strint ( ans (x) ) to false, <- think about this, we dont want to do the job again do we?
-> Set all booleanArray ( y ( x ) ) only if the X (x) is not in ans. Kinda hard to tell but I will try. you see, look at the diagram, the Y's of the USED X's is free so we dont want to turn that to false! Like for example, say #3 is the first instruction to be processed, so that will free instruction 4 and 5 (3, 4) & (3, 5) we dont set 4 and 5 to false now because the instruction 3 has been used and they are now free to get done. However, we dont set them to true either! Because you see there exists one more pair (1, 4) and 1 has not been done, so we cannot do 4, because we have to do 1 BEFORE 4. See what I mean? Look at the diagram for a better understanding.
-> Store the index of true elements of the boolean Array in a new flexible array.
-> Now, if the size of flexible array is 0 that means that all elements have been set to false, which means they are interdependant on each other and hence cannot be processed. so we output "NOT POSSIBLE. GOING TO BED." or w/e the thing says and then exit the loop.
-> On the other hand, if there are more than 1 elements then you need to process the smallest one first. so sort the array and add the first element to the variable ans.
-> If anslength = 7 put ans, exit, all instructions have been processed.

I know I suck at explaning this but I tried my best.
Time Taken: 1 hour (reading inc.)

Problem 5:
Difficulty: Above Average Grade 10 student with knowledge of 2D arrays must be able to get this.
See Attachment.
Wow this problem really sucks for a J5. First I looked a board and pieces, I was excited that "Finally! 1 more recursion problem!!!!" But as I read the rules, what the hell? this problem is way easier than J4. I am not kidding. If you know how to use 2D arrays well, this is a no timer. Reading it takes 15 minutes -_- Understanding its concept takes less than 5 minutes. They made the rules sound so godly but they failed. They use such a complicated way of explaning the rules. damn, I was like "What the hell?"
The point is that if black moves, and places a piece, say like this:

0 0 0 0
0 2 1 H
0 0 1 0

H is where he places the piece, 1 is white piece, 2 is black piece, then the board results in this:

0 0 0 0
0 2 2 2
0 0 1 0

Notice the piece in the left has been turned black but the piece diagonally below didnt because the piece in left was in middle of 2 black pieces, here is one more example:

Original:

0 1 0 0 0
0 0 0 0 0
2 1 1 H 0
0 0 1 0 0
0 1 0 1 0
2 0 0 2 0

Next:

0 1 0 0 0
0 0 0 0 0
2 2 2 2 0
0 0 2 0 0
0 2 0 1 0
2 0 0 2 0

See how the pieces changed? But the one beneath it didnt change because there is an empty square (0) between them.

Same applies when white moves, except they change to white (duh)

A simple procedure with left, right, down, up, nw, ne, sw, se checks would do good, but after checking each of the directions, we need to have a boolean saying whether its turnable or not. A simple "down" check example is:

code:
    %Down Movement
    for x : r + 1 .. 8
        exit when grid (x, c) = "0"
        if grid (x, c) = t then
            turnable := true
            exit
        end if
    end for
    if turnable then
        for x : r + 1 .. 8
            exit when grid (x, c) = t
            grid (x, c) := t
        end for
        turnable := false
    end if


r = row of inserted piece
c = col of it
t = turn

now, we run a loop for x : col + 1..8 (+1 because we dont want to count the original cell) turnable is originally false. So if we encounter a space, we exit immediately turnable is false so we ignore the next part. However on the other hand if we encounter another piece with the same color as the one just inserted, we set turnable to true and exit. Because now we know there are no spaces in middle and that the pieces in the middle are covered by 2 of same color. Then we run a loop and change the color of each piece until we find the piece that original had set turnable to true.

repeat this for 8 sides and voila we are done Razz
I am expecting you already know black starts first.

Time taken: 40 minutes (reading inc.)

Total time taken: 2 hours 12 minutes.



J4.jpg
 Description:
 Filesize:  396.28 KB
 Viewed:  10192 Time(s)

J4.jpg



Problem J5 (part 3).JPG
 Description:
 Filesize:  280.28 KB
 Viewed:  10188 Time(s)

Problem J5 (part 3).JPG



Problem J5 (part 2).JPG
 Description:
 Filesize:  266.24 KB
 Viewed:  10188 Time(s)

Problem J5 (part 2).JPG



Problem J5 (part 1).JPG
 Description:
 Filesize:  277.49 KB
 Viewed:  10189 Time(s)

Problem J5 (part 1).JPG



Problem J4 (part 3).JPG
 Description:
 Filesize:  226.8 KB
 Viewed:  10190 Time(s)

Problem J4 (part 3).JPG



Problem J4 (part 2).JPG
 Description:
 Filesize:  212.33 KB
 Viewed:  10194 Time(s)

Problem J4 (part 2).JPG



Problem J4 (part 1).JPG
 Description:
 Filesize:  140.4 KB
 Viewed:  10193 Time(s)

Problem J4 (part 1).JPG



Problem J3.JPG
 Description:
 Filesize:  291.62 KB
 Viewed:  10194 Time(s)

Problem J3.JPG


Sponsor
Sponsor
Sponsor
sponsor
xXInsanityXx




PostPosted: Sat Mar 04, 2006 11:34 am   Post subject: (No subject)

GOOD JOB Very Happy

My code
Problem 1
code:

% Problem 1
var burger : array 1 .. 4 of int := init (461, 431, 420, 0)
var side : array 1 .. 4 of int := init (100, 57, 70, 0)
var drink : array 1 .. 4 of int := init (130, 160, 118, 0)
var dessert : array 1 .. 4 of int := init (167, 266, 75, 0)

var calorie : int := 0
var x : int

put "Welcome to Chip's Fast Food Emporium"
put "Please enter a burger choice: " ..
get x
calorie+= burger (x)
put "Please enter a side order choice: " ..
get x
calorie+= side (x)
put "Please enter a drink choice: " ..
get x
calorie+= drink (x)
put "Please enter a dessert choice: " ..
get x
calorie+= dessert (x)

put ""
put "Your total Calorie count is ", calorie,"."


Problem 2
code:

% Problem 2
var m, n,out: int
var counter: int:= 0

put "Enter m: "..
get m
put "Enter n: "..
get n

if m > 9 then m := 9
end if

if n > 9 then n := 9
end if

for x: 1..m
for y: 1..n
if x + y = 10 then
counter+= 1
end if
end for
end for

if counter = 1 then
put "There is 1 way to get the sum 10."
else
put "There are ",counter," ways to get the sum 10."
end if


This is Redundant, Its the way i did it i wouldnt reccomend it Very Happy
Problem 3
code:

var word, tic : flexible array 1 .. 1 of string
var ans, count : flexible array 1 .. 1 of int
var numpad : array 2 .. 9 of string := init ("abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
var one, two, three, four : string
one := "adgjmptw"
two := "behknqux"
three := "cfilorvy"
four := "sz"

var counter : int := 0

loop
    counter += 1
    new word, counter
    new ans, counter
    new tic, counter
    new count, counter
    get word (counter)
    ans (counter) := 0
    count (counter) := 0
    tic (counter) := ""
    if word (counter) = "halt"
            then
        exit
    end if

    % first num finder
    for x : 1 .. length (word (counter))
        if index (one, word (counter) (x)) > 0
                then
            ans (counter) += 1
        elsif index (two, word (counter) (x)) > 0
                then
            ans (counter) += 2
        elsif index (three, word (counter) (x)) > 0
                then
            ans (counter) += 3
        elsif index (four, word (counter) (x)) > 0
                then
            ans (counter) += 4
        end if
    end for
    % num convert
    for y : 1 .. length (word (counter))

        for d : 2 .. 9
            if index (numpad (d), word (counter) (y)) > 0
                    then
                tic (counter) += intstr (d)
            end if

        end for

    end for
% Pause Counter
    for y : 1 .. length (word (counter))
        if y not= length (word (counter))
                then
            if tic (counter) (y) = tic (counter) (y + 1)
                    then
                count (counter) += 1
            end if
        end if

    end for
    % halt exit


end loop


for x : 1 .. counter - 1
    put ans (x)+ (count (x) * 2 )
    % put tic (x)
end for
cool dude




PostPosted: Sat Mar 04, 2006 11:55 am   Post subject: (No subject)

can someone post the code for 4 and 5 because those were the only ones i had trouble with.
MysticVegeta




PostPosted: Sat Mar 04, 2006 11:59 am   Post subject: (No subject)

No sorry I cant post
cool dude




PostPosted: Sat Mar 04, 2006 2:34 pm   Post subject: (No subject)

MysticVegeta wrote:
No sorry I cant post


if u can't post please don't reply Twisted Evil
zylum




PostPosted: Sat Mar 04, 2006 5:39 pm   Post subject: (No subject)

The easy way to solve J4 is to realize that there are only 7 tasks. So after you get the extra constraints, you can try all possible combinations of the tasks and see if they meet the constraints. You can generate all possible combinations using my permutations code in my recursion tutorial

code:
var list : array 1 .. 15, 1 .. 2 of int := init (1, 7, 1, 4, 2, 1, 3, 4, 3, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
var x, y, N : int := 5

proc search (s, c : string)
    if length (s) = 0 then
        for i : 1 .. length (c) - 1
            for j : i + 1 .. length (c)
                for k : 1 .. N
                    if list (k, 1) = strint (c (j)) & list (k, 2) = strint (c (i)) then
                        return
                    end if
                end for
            end for
        end for
        for i : 1 .. length (c)
            put c (i), " " ..
        end for
        break
    else
        for i : 1 .. length (s)
            search (s (1 .. i - 1) + s (i + 1 .. *), c + s (i))
        end for
    end if
end search

loop
    get x, y
    exit when x = 0 & y = 0
    N += 1
    list (N, 1) := x
    list (N, 2) := y
end loop
search ("1234567", "")
put "Cannot complete these tasks. Going to bed."
MysticVegeta




PostPosted: Sat Mar 04, 2006 7:45 pm   Post subject: (No subject)

cool dude wrote:
MysticVegeta wrote:
No sorry I cant post


if u can't post please don't reply Twisted Evil


Yes, not reply and make you wonder forever why I am not posting the code.

@zylum: dude, why not avoid recursion when it can be done using simple loops and if structures?
zylum




PostPosted: Sun Mar 05, 2006 12:48 pm   Post subject: (No subject)

well it took me 5 minutes to code where as it took you over an hour. why think about the loops and decision structures when you can easily create all possibilities by simply using standard code. all i did was collect the extra constraints, copy and paste my permutations code and alter it slightly to meet the requirements of the problem. thats why you should start collecting some standard algorithms, it will make these contests a lot easier.

lets see your code.
Sponsor
Sponsor
Sponsor
sponsor
MysticVegeta




PostPosted: Sun Mar 05, 2006 2:03 pm   Post subject: (No subject)

code:
var t1, t2 : flexible array 1 .. 0 of int

var orig1 : array 1 .. 5 of int := init (1, 1, 2, 3, 3)
var orig2 : array 1 .. 5 of int := init (7, 4, 1, 4, 5)

var possibleTasks : flexible array 1 .. 0 of int
var tDone : array 1 .. 7 of boolean

var ans : string := ""

var minTask := 10000

%Main Getting part
for x : 1 .. 5
    new t1, x
    new t2, x
    t1 (x) := orig1 (x)
    t2 (x) := orig2 (x)
end for
loop
    new t1, upper (t1) + 1
    new t2, upper (t2) + 1
    get t1 (upper (t1))
    get t2 (upper (t2))
    exit when t1 (upper (t1)) = 0
end loop

%Setting the boolean array to true
proc fSet
    for x : 1 .. 7
        tDone (x) := true
    end for
end fSet

%Setting the done tasks false
proc setDoneTasksFalse
    for x : 1 .. length (ans)
        tDone (strint (ans (x))) := false
    end for
end setDoneTasksFalse

%Setting the T's tasks false since they cant be done
proc setNotPossibleFalse (ans : string)
    for x : 1 .. upper (t2) - 1
        if index (ans, intstr (t1 (x))) <= 0 then
            tDone (t2 (x)) := false
        end if
    end for
end setNotPossibleFalse

%Decorating as req.
proc formatAns (ans : string)
    var a2 : string := ""
    for x : 1 .. length (ans)
        a2 += ans (x) + " "
    end for
    put skip, a2
end formatAns

% Main Loop
loop
    fSet
    setDoneTasksFalse
    setNotPossibleFalse (ans)

    free possibleTasks     % left tasks
    for x : 1 .. 7
        if tDone (x) then
            new possibleTasks, upper (possibleTasks) + 1
            possibleTasks (upper (possibleTasks)) := x
        end if
    end for

    minTask := 1000

    if (upper (possibleTasks) = 0) then     % NO SPACE IS LEFT THAT MEANS THEY ARE DEPENDANT ON EACH OTHER
        put skip, "Cannot complete these tasks. Going to bed."
        exit
    end if

    for x : 1 .. upper (possibleTasks)
        minTask := min (minTask, possibleTasks (x))
    end for

    ans += intstr (minTask)

    if length (ans) = 7 then
        formatAns (ans)
        exit
    end if
end loop


lol 5 minutes is a really good time for it, It woulda taken more than an hour to get the recursion right. Anyways, so yeah. nice timing you made on it I guess.
Cervantes




PostPosted: Sun Mar 05, 2006 2:22 pm   Post subject: (No subject)

MysticVegeta wrote:
@zylum: dude, why not avoid recursion when it can be done using simple loops and if structures?

Avoid recursion? What's wrong with recursion?

We have another contestant for the challenge.
MysticVegeta




PostPosted: Sun Mar 05, 2006 6:06 pm   Post subject: (No subject)

There is nothing wrong with it, but it should be noted that, if recursions are used for things that can be done without it easily there are certain disadvantages:

1) Recursion is slow
2) Recursion is more confusing than loops
3) Might lead to stack overflow when certain parametres have been forgetten to implement into it.
Cervantes




PostPosted: Sun Mar 05, 2006 8:28 pm   Post subject: (No subject)

MysticVegeta wrote:

1) Recursion is slow
2) Recursion is more confusing than loops
3) Might lead to stack overflow when certain parametres have been forgetten to implement into it.

1) No it's not.
2) It's a different way of thinking about things. If you had learned recursion before loops, you might say loops are more confusing than recursion. Being open to new possibilities is essential.
3) Not if you're using tail-call recursion. I haven't looked at this problem, but I doubt you'd overflow the stack with it. I assume zylum didn't, and look how much more consice his program is.
thegoose




PostPosted: Mon Mar 06, 2006 8:03 am   Post subject: (No subject)

Cervantes wrote:

1) No it's not.
2) It's a different way of thinking about things. If you had learned recursion before loops, you might say loops are more confusing than recursion. Being open to new possibilities is essential.
3) Not if you're using tail-call recursion. I haven't looked at this problem, but I doubt you'd overflow the stack with it. I assume zylum didn't, and look how much more consice his program is.

1). Procedural calls are far more expensive than other commands, so recursive programs do tend to be slower than iterative ones. When a constant advantage is crucial, it's often better to avoid recursion to speed up runtime.
2). Recursive thinking generally tend to be easier than thinking about the problem iteratively.
3). Overflow does happen. This is why DFS (deep first search) is often coded iteratively than recursively when data is large.
MysticVegeta




PostPosted: Mon Mar 06, 2006 2:32 pm   Post subject: (No subject)

thegoose wrote:

2). Recursive thinking generally tend to be easier than thinking about the problem iteratively.


Well that depends on what programming level you are at. If you have came across loops before recursions (almost all do) then using recursion might be more confusiing
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 1  [ 14 Posts ]
Jump to:   


Style:  
Search: