Computer Science Canada

DWITE October 27th - My solutions
Author:  MysticVegeta [ Fri Oct 28, 2005 9:31 pm ]
Post subject:  DWITE October 27th - My solutions
Here are my solutions, please use them as a source, dont copy and paste and say they are yours!!

Please tell me how i could kiss the code. thanks a lot!
Author:  Cervantes [ Fri Oct 28, 2005 10:14 pm ]
Post subject: 
I've only looked at number 4 so far, but one thing that stood out to me was your huge if structures for checking around. Instead, try using two for loops, from -1 to 1 (or from 1 less than the grid coord to 1 greater than it). Keep in mind you'll have to have an if statement to prevent checking when both for loops are at zero.
Author:  MysticVegeta [ Fri Oct 28, 2005 11:54 pm ]
Post subject: 
yeah, I didnt kiss my code, i was in a rush so i did everything i could from the top of my head, i need practise to be more code lines saver, Smile By the ways, i cant see my attachment anymore, waht happened?
Author:  zylum [ Sat Oct 29, 2005 12:24 am ]
Post subject: 
here's a solution to #5:

code:
var file : int
open : file, "DATA51.txt", get
var ret, d1, d2 : int
var s := "123456789"

proc perms (n, cp : string)
    if length (n) = 0 then
        if strint (cp) mod d2 = 0 then
            ret += 1
        end if
    else
        for i : 1 .. length (n)
            perms (n (1 .. i - 1) + n (i + 1 .. *), cp + n (i))
        end for
    end if
end perms

for i : 1 .. 5
    ret := 0
    get : file, d1, d2
    perms (s (1 .. d1), "")
    put ret
end for
Author:  Hikaru79 [ Sat Oct 29, 2005 8:36 am ]
Post subject: 
What exactly do you mean by "kiss my code"? You've used it three times so far, and I still giggle whenever I read it. Does it mean something besides what I think it means? Embarassed
Author:  MysticVegeta [ Sat Oct 29, 2005 9:21 am ]
Post subject: 
KISS - Keep it Simple Student, never heard of it? every teacher says that lol

Anyways, zylum. I cant use that, thats what i did before but it wont give me a perfect, i read your permutations tuts before too. The data file has 5 lines of Data. what if n1 is 9, it takes forever to check for it
it wont execute on time. i know theres some way around it. Even Qiyu spent more than 40 minutes on this problem, rest he took like 10-15 minutes. There is some other way, i think
Author:  Cervantes [ Sat Oct 29, 2005 9:24 am ]
Post subject: 
I was wondering about that too, but I think I've figured it out.
KISS = Keep it Simple, Stupid.

Hard to get because no one would say,
Quote:

yeah, I didnt keep it simple, stupid my code


MysticVegeta wrote:
By the ways, i cant see my attachment anymore, waht happened?

I see your attachment. Confused
Author:  MysticVegeta [ Sat Oct 29, 2005 11:00 am ]
Post subject: 
yeah, now i see it, problem 5 is weird, i think we have to make up the prime factors for the divisor given and then perhaps try it but still confusing.
Author:  zylum [ Sat Oct 29, 2005 12:21 pm ]
Post subject: 
meh, there's only ~360000 permutations of a 9 digit number. thats penuts. its probably that turing is so slow. im sure if you submitted it in c++ it would have been more than fast enough.

i guess ill try to code a faster solution then...
Author:  jamonathin [ Sat Oct 29, 2005 5:25 pm ]
Post subject: 
Cervantes wrote:
I was wondering about that too, but I think I've figured it out.
KISS = Keep it Simple, Stupid.

It is 'Stupid' not 'Student'. Doesn't anyone remember my old signature? . .
Author:  MysticVegeta [ Sat Oct 29, 2005 9:26 pm ]
Post subject: 
jamonathin : our teacher didnt say stupid, because that wouldnt make sense coming from a teacher now would it?

zylum : even C++ will time out. Because there are 5 sets of data. maybe VC++ will compile...?
Author:  JackTruong [ Sun Oct 30, 2005 12:50 am ]
Post subject: 
Problem5 was a tricky one, our initial code (the one we submitted) was actually find the permutation with unique digits, and modulus it to output.

I just worked out another solution, this one's faster, but it won't execute the input of "9 2" in a few seconts.

We had this idea during the competition, but coding it in 14 minutes was a huge task.

Pseudo:
Start with string from 1 to 9, substring it.
Find a multiple of the second number, at or above the string above.
Run a for loop, from the number above, to the reverse of the above string, and incrementing the second number each time.
Run a check for proper digits.
Run a check for unique digits.
Increment a counter.
Output counter.

I typed this post and the "9 2" input is still going. Source code will soon be uploaded to a section of my site dedicated to DWITE; Link..

Other problems are up too, with some partial explanations.
Author:  MysticVegeta [ Sun Oct 30, 2005 10:42 am ]
Post subject: 
wont that time out by substringing the 9 digit string? and reversing it everytime.?
Author:  JackTruong [ Sun Oct 30, 2005 10:56 am ]
Post subject: 
No, it's just a one time event.

Source
Author:  MysticVegeta [ Sun Oct 30, 2005 12:05 pm ]
Post subject: 
I see Jack.
My approach to it is something like this ->

5 12

12345 all divisible by 3 because 1+2+3+4+5 = 15
XXX12 -> XXX satisfies 6 values in each case
XXX24
XXX32
XXX52
So Number of possible values are 6X4= 24

This was the example from the problem.

So my strategy is like this

1) Since we know the divisibility for 2,3,4,5,6,7,8,9,10,11 then we can break up the divisor from 2 - 50 into factors {2..11} where no two factors are alike.

2) Then find the number of possible values by each of the factor ->
Ex: suppose 123456789 is the string and d1 = 10
then,

22 = 5 * 2

XXXXXXX2
XXXXXXX4
XXXXXXX6
XXXXXXX8

Possible values for 2 : (!8)*4 = 40320

XXXXXXX5

8! = 10080

but 5 is not even so intersection of mutiples is 0; so possible number of values is 0, should work with other numbers

EDIT: For prime numbers, http://home.egge.net/~savory/maths1.htm
Author:  zylum [ Sun Oct 30, 2005 1:08 pm ]
Post subject: 
guys... 5*9! is about 1800000, less than 2 million... i tried using java and it ran 9, 2 five times in less than 3 seconds... i doubt that they will use that case five times in a row.. if they use 9, 2 three times and 8,2 twice it will easily run in time... if you were to use c++ which is faster than java then it might even be able to run the worse case in time.
Author:  MysticVegeta [ Sun Oct 30, 2005 5:08 pm ]
Post subject: 
I think this question was a bad example, because clearly other languages will beat turing time by miles!
Author:  JackTruong [ Sun Oct 30, 2005 5:15 pm ]
Post subject: 
My compiler timed out on the 9 2 input.

If only I knew of a regex that check for unique digits, then I can probably shave a few seconds off the execution time.

The Pascal solution is up, I don't understand it at all.
Author:  MysticVegeta [ Sun Oct 30, 2005 6:20 pm ]
Post subject: 
why didnt they put the java solution, they always put both of them..
This is not fair, they should probably increase time limit for turing since it compiles too slow. Same code C++ gets a perfect whereas turing gets 0, unfair!!!!! Crying or Very sad
Author:  jamonathin [ Mon Oct 31, 2005 11:52 am ]
Post subject: 
MysticVegeta wrote:
jamonathin : our teacher didnt say stupid, because that wouldnt make sense coming from a teacher now would it?


Well that all depends on the teacher right? My calculus/geometry teacher is also the Cross Country coach, and he'll tell us that we're the stupidist team he's ever coached, yet the most talented. It all really depends on how comfortable the teacher is.
Author:  MysticVegeta [ Mon Oct 31, 2005 6:18 pm ]
Post subject: 
yeah i guess as you get older, teacher starts becoming/feeling more free towards you. Laughing

:


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

Terms of Use | Privacy Policy