Page 4 of 4 FirstFirst ... 234
Results 31 to 39 of 39

Thread: C/C++ Test - Category Looping & Optimising - Level Medium

  1. #31
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    did you go throug it? did you understand?
    if you look at a list of numbers column by column (level by level) you may see why it works.

    you should see in level 0 all letters occur only once( consecutively that is).... [1,1,1,1,1]

    then in level 1 there are 5 A's, 4 B's, 3 C's, 2 D's, 1 E... [5,4,3,2,1] -> cumulative sum from the right.

    then at level 2 there are 15 A's, 10 B's, 6 C's, 3 D's, 1 E... [15,10,6,3,1] -> cumulative sum from the right.

    et cetera, et cetera...

    if you see that you are half way there...

  2. #32
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    looking at a list of numbers you realise that you can jump back to get the value of a number.
    eg
    AAA to AAD = jump back from D to A on level 0

    same as jump D to C = 1
    jump C to B = 1
    jump B to A = 1
    __________+______________
    = 3 ... sum values from D to A in level 0 [1,1,1,1,1]

    same as lookup D = 4 in level 1 [ 5,4,3,2,1]
    - lookup A = 1
    __________________________
    = 3


    now since our numbering starts at 1 rather than 0, 3 maps to 4

    hope you get the point so far

  3. #33
    Join Date
    Jan 2005
    Posts
    3,151
    Rep Power
    0

    Default

    oh wait a min, so A is the smallest char and E is the highest char?
    so if the input was

    3
    AAE

    Then it should calculate 5?

  4. #34
    Join Date
    Jan 2005
    Posts
    3,151
    Rep Power
    0

    Default

    OK, here are my findings:
    I ran nigelts first program in post #6 and it returned:
    Code:
    > cc l.c && ./a.out
    EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
    String found at position 4598126
    1.000 seconds
    confused lost and lonely I ran it on icymint3's last program, it returned:
    Code:
    > cc l.c && ./a.out
    selcount = 2403517
    Program takes 0.0000 seconds.
    Now all of this does not match
    Quote Originally Posted by crosswire
    will give a result of
    Position = 2403193
    Program takes 4 seconds.
    Press any key to continue
    on input
    Code:
    100
    AAAAAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCC  CCCCCCDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDEEEEEEEEEEEE
    What I also find strange is that the second line contains a few whitespaces but
    he uses fscanf(stream, "%s", &S); to read it.

    Please clarify...


    Regards,
    Pogi Tuner.



    I am using cc on Tru64 UNIX where the size of char, int, double, long are 1, 4, 8 and 8 respectively.
    Using alpha processors with the same endian as x86 platforms.

  5. #35
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    the few spaces must be an accident, so just fix the file... remove the spaces.

    the challenge was looping and optimising.
    not reading and concatenating strings until the specified length is met, ok.

    try it again and see if it works. by the way did the explanation help anyone? im too lazy to write a good one.

  6. #36
    Join Date
    Jan 2005
    Posts
    3,151
    Rep Power
    0

    Default

    The problem is a math problem if I am understanding it correctly.

    y'all are using 31bit integers whos value maxes out at 2147483648
    Using the alphabet A to E gives you a base of 5.
    Using
    5^00 1
    5^01 5
    5^02 25
    5^03 125
    5^04 625
    5^05 3125
    5^06 15625
    5^07 78125
    5^08 390625
    5^09 1953125
    5^10 9765625
    5^11 48828125
    5^12 244140625
    5^13 1220703125
    5^14 6103515625
    5^15 30517578125
    5^16 152587890625
    5^17 762939453125
    5^18 3814697265625
    5^19 19073486328125
    5^20 95367431640625
    One can see that the position will overflow at 5 to the 14.
    This means that string EAAAAAAAAAAAAA and above will produce wrong results...

    keep in mind this is all based on my interpretation of what is being asked.

  7. #37
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    yep, your interpretation is wrong. you should try to look at a list of the numbers as they are traversed.

    i suggest running my first code and un-commenting the lines near // have a look
    Cultured in Aggression and Koding like a Warrior!!
    “Common sense is instinct. Enough of it is genius.” - George Bernard Shaw.
    "The significant problems we face cannot be solved by the same level of thinking that created them." - Albert Einstein

  8. #38
    Join Date
    Jan 2005
    Posts
    3,151
    Rep Power
    0

    Default

    y'all suck at problem specification (no offense.)

  9. #39
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    @icymint3

    This was excellent work!

    My internet connection was gone for a while, but I thought about your direct approach and it was truely extra-ordinary, so I had to redo the credits. Now that you have released the logic, I also get a startup grasp on the code, which does not lessen its intricacy from my perspective.

    I will try to dive in some of the other problems that I see posted here.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •