Complete CCC 2006 Junior Analysis

MysticVegeta · **Posted:** Fri Mar 03, 2006 8:38 pm

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.

xXInsanityXx · **Posted:** Sat Mar 04, 2006 11:34 am

GOOD JOB

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 · **Posted:** Sat Mar 04, 2006 11:55 am

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

MysticVegeta · **Posted:** Sat Mar 04, 2006 11:59 am

No sorry I cant post

cool dude · **Posted:** Sat Mar 04, 2006 2:34 pm

MysticVegeta wrote:

No sorry I cant post

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

zylum · **Posted:** Sat Mar 04, 2006 5:39 pm

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 · **Posted:** Sat Mar 04, 2006 7:45 pm

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 · **Posted:** Sun Mar 05, 2006 12:48 pm

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.

MysticVegeta · **Posted:** Sun Mar 05, 2006 2:03 pm

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 · **Posted:** Sun Mar 05, 2006 2:22 pm

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 · **Posted:** Sun Mar 05, 2006 6:06 pm

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 · **Posted:** Sun Mar 05, 2006 8:28 pm

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 · **Posted:** Mon Mar 06, 2006 8:03 am

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 · **Posted:** Mon Mar 06, 2006 2:32 pm

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

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