New Monthly Contest!

This is a discussion on New Monthly Contest! within the Contests Board forums, part of the Community Boards category; Originally Posted by treenef I have a challenge for you. Nothing to do with the above Personally i'm not interested ...

  1. #31
    former member Brain Cell's Avatar
    Join Date
    Feb 2004
    Posts
    472
    Quote Originally Posted by treenef
    I have a challenge for you. Nothing to do with the above
    Personally i'm not interested , i came to this thread for PJYelton's contest not your challenge. Why didn't you start your own thread?
    My Tutorials :
    - Bad programming practices in : C
    - C\C++ Tips
    (constrcutive criticism is very welcome)


    - Brain Cell

  2. #32
    Registered User
    Join Date
    Dec 2004
    Posts
    465
    For me I think its less of an algorithm problem and more of not knowing how to tell the program to do it.
    My computer is awesome.

  3. #33
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    This posts contains potential spoilers as I worked out by hand the problem. It is in fact solvable. The logic is contained here. I've changed my text color to that of the background color (as it appears to me). It was just such a long post, I couldn't bear not to post it. The following is basicly a brain dump (like a stack dump, but with more null pointers being dereferenced) of me proving it couldn't be done, and in fact finding out it could. Ignore this post, or don't.

    The mods can delete this at the request of PJYelton if they would prefer.

    (****SPOILER ALERT****)


    It's broken because you can't reverse-engineer the problem. You don't know what the sample output will be, because there should be none. The big one is still broken for reasons I have described. One more try:

    You have nine white pearls.
    You have tirteen gold pearls.
    You place a gold pearl every eleven spaces. (That is to say, there are 10 spaces between every gold pearl, wrapping in a circle.
    There are a total of 22 segments to fill. Fill it.

    Here, I'll do it for you:
    Code:
    1234567890g1234567890g
    There you go. It's broken. This one is unsolvable.

    Remember, you cannot start with the end result and go backwards. You must work forewards, because you have no idea what the end result will be. Given the fact that you have 22 pearls, and the 11th pearl will be a gold one, you cannot possibly reconstruct the necklace.

    Think again to your problem description. You are not asking us to pull apart a necklace. You are asking us to assemble one. Look at the above code block, and you'll see for yourself it can't be done.

    It doesn't work if you use a single one, and slide them on one at a time wrapping, and it doesn't work if you do it as a "full empty" necklace as shown above.

    The problem is, you're all solving "how do I take this necklace apart", which is not what you're supposed to be solving. You're supposed to be solving "given a handful of crap, put this necklace together again, without knowing what it is supposed to look like".

    It's like an algebra problem.
    Code:
    x = y + z5;
    Solve for the actual number that z is. You can't do it. There isn't enough information provided. Try it. Grab a handfull of any two items. Any number of either of them, and roll a dice for K. Or just make up a number. Let's assemble this necklace.

    Put one item "on the necklace".
    Now, what's the next item you put on? Is it white, or gold? Who knows! We don't. There is no way of telling what item goes on next. You can disassemble a necklace, but you cannot put it back together.
    Code:
    5,4,4
    
    1234
    wwggwwwgg <-- Do the count.
        1234
    wwgwwwgg <-- We now have this.
    234   1
    wwgwwwg
      1234
    wwwwwg
    
    wwwww
    Ok. Then the reverse of that would be:

    "Start with all the white beads on the thread."
    "Start counting until you reach K-1. Insert a bead there."
    "Repeat this until you run out of gold beads. This is the finished necklace."
    Code:
    wwwww <-- start out with all of the white pearls on.
    
    123 <-- Move K-1 spaces. Insert one bead after this.
    www_ww
    
    3    12
    w_wwgww <-- Skip this bead and start counting again.
      1234
    wgwwg_ww
    3      12
    w_gwwggww
    
    wggwwggww
    That should be the same pattern as above, right? Well it is, but it's rotated slightly. But, since the pattern repeats the same, it is in fact the same necklace.

    Now let's try the big one.
    Code:
    wwwwwwwww <-- nine white
    
    1 23456789 <-- K = 11, K -1 = 10, 0 = 10th count
    0
    w_wwwwwwww
    
       12345678
    90 
    wg_wwwwwwww
    
       12345678
    90
    wg_gwwwwwwww
        123456789
    0
    w_gggwwwwwwww
      1234567890
    wggggwwwwwww_w
    
    234567890     1
    wggggwwww_wwwgw
    
    67890      12345
    wgggg_wwwwgwwwgw
    
          1234567890
    wgggggwwwwgwwwgw_
    
    1234567890
    wgggggwwww_gwwwgwg
    890         1234567
    wgg_gggwwwwggwwwgwg
    
        1234567890
    wggggggwwwwggw_wwgwg
    
    67890           12345
    wgggg_ggwwwwggwgwwgwg
    
          1234567890
    wgggggggwwwwggwg_wwgwg
    
    wgggggggwwwwggwggwwgwg
    We have a winner!

    “ggggwgwgwwggwggwwwwggg”
    “wgggggggwwwwggwggwwgwg”

    No, we actually don't. If we left shift this four places, to make the large block of Gs match:
    Code:
    ggggwgwgwwggwggwwwwggg
    wgggggggwwwwggwggwwgwg
    
    ggggwgwgwwggwggwwwwggg
    gggggggwwwwggwggwwgwgw
    
    ggggwgwgwwggwggwwwwggg
    ggggggwwwwggwggwwgwgwg
    
    ggggwgwgwwggwggwwwwggg
    gggggwwwwggwggwwgwgwgg
    
    ggggwgwgwwggwggwwwwggg
    ggggwwwwggwggwwgwgwggg
    It doesn't match up at all. It's not the same necklace. But is it reversed from left to right? You know those crazy necklaces, you never can tell which is the front, unless they've got a pendant...

    “ggggwgwgwwggwggwwwwggg”
    “wgggggggwwwwggwggwwgwg”

    Code:
    wgggggggwwwwggwggwwgwg
    gwgwwggwggwwwwgggggggw (right?)
    “ggggwgwgwwggwggwwwwggg”
    “gwgwwggwggwwwwgggggggw”

    Now we right shift it to line up the block of Gs...
    Code:
    ggggwgwgwwggwggwwwwggg
    gwgwwggwggwwwwgggggggw
    
    ggggwgwgwwggwggwwwwggg
    wgwgwwggwggwwwwggggggg
    
    ggggwgwgwwggwggwwwwggg
    gwgwgwwggwggwwwwgggggg
    
    ggggwgwgwwggwggwwwwggg
    ggwgwgwwggwggwwwwggggg
    
    ggggwgwgwwggwggwwwwggg
    gggwgwgwwggwggwwwwgggg
    
    ggggwgwgwwggwggwwwwggg
    ggggwgwgwwggwggwwwwggg
    Now we have a winner. So do we have to count backwards when we reassemble? Looks like it.


    That was fun, wasn't it?

    Quzah.
    Hope is the first step on the road to disappointment.

  4. #34
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by treenef
    Basically, it's about algebra. Ever since I was in high school I always found it strange that you could use a calcultor to solve questions like :

    5+10=15

    where as something like:

    5x+10x=15x

    would be impossible. Similarly, trying to rearrange a simple equation to find 'x' was not possible using a calculator or a computer program
    You haven't ever used a scientific calculator, have you? Wrong thread for this post.

    Mmmmm watermellon...

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #35
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Ok, I think I see where the problem is. Unfortunately I only have a couple of seconds so I can't look at my original post to see if I was unclear. The general gist of my problem is, you have numWhite, numGold, and K, what does the original necklace look like? And heres the important part, it doesn't have to perfectly match what a real life person would do with real life pearls, just get it done however. With that, I'll leave the rest of my explanation to a PM to you personally Quzah

  6. #36
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    LOL,


    ok guys sorry about posting my thread in the wrong section, but I'm relatively new to this. I guess that's why it hasn't really captured your attention- or then again maybe you don't really care! lol.

  7. #37
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    Sent you a PM with my entry for the easy problem.
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  8. #38
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    I sent you a PM with my entry for the easy problem.
    Micko

  9. #39
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Ok, I tehse are the people I have received entries from so far:

    Lithorien
    Brain Cell
    Quzah
    Jawib
    Micko

    Remember, if anyone needs a hint on the first two let me know.

  10. #40
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Mine wasn't an actual entry. It was just showing you that the 9, 13, 11 (or whatever it was) didn't work. And in fact, it doesn't with that algorithm. Because there are 22 total steps, and if you step ahead 11 spaces, you end up just walking over over what you've already done on the second pass, so it doesn't give you the output. The rest of the test cases so far work. The ones that won't with that one are when (W + G) % K == 0.

    I may send one in just for kicks, but I'll be out of town soon so I may not get around to it.

    Quzah.
    Hope is the first step on the road to disappointment.

  11. #41
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    All right, the contest is over. Over the next couple of days I will be testing the entries I have and post the results.

    Since this is the first time I've ever done this, any suggestions/criticisms are welcome! Don't worry, I can take it No one submitted a entry for the medium or hard questions, I'm a little curious why. Were they too hard, too confusing, unable to use vectors, run out of time? Same with the "easy" problem, would you prefer that be a medium instead and make a simpler one? Any feedback is great, even if you didn't submit an entry

  12. #42
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    I think the problem was that the medium/hard were too hard. The idea of the easy you had being the medium would do well I think. I don't think the use of vectors was an issue. As for me, the primary factor isn't difficulty because I can deal with that, but rather time. <- My $.02

  13. #43
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313
    The medium/hard were very hard. I couldn't figure them out. :/

  14. #44
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I thought the hard one should actually be quite easy. All you do is find the biggest range, and split it in half, and there's your bet.

    1 to 1000

    First guy bets 500.
    Second guy bets 250.
    Third guy bets 750.
    Fourth guy bets 125.

    This should effectively "win" every time, or rather, give you the best odds.

    Quzah.
    Hope is the first step on the road to disappointment.

  15. #45
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Not quite that easy, for example, say you are picking first out of 3 people on range 1-1000. If you pick 500 you are actually very poorly off. The second one to pick will pick 501, NOT 750 since he knows that the best number for player 3 to pick is 499. If he had picked 750 he'd have a lower chance of winning than if he picked 501. Since you picked 500, player 2 picked 501, player 3 picked 499, you would have only a 1 in 1000 chance of winning which is very bad.

    Likewise, in the example you gave, why would player 4 pick 125? Why not 249? Knowing this, second guy would probably have to pick a better number than 250, etc etc

Page 3 of 4 FirstFirst 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. May Monthly Contest Results
    By PJYelton in forum Contests Board
    Replies: 28
    Last Post: 05-27-2005, 01:43 AM
  2. May monthly contest
    By PJYelton in forum Contests Board
    Replies: 43
    Last Post: 05-18-2005, 06:37 PM
  3. Results of March Monthly Contest
    By PJYelton in forum Contests Board
    Replies: 23
    Last Post: 04-17-2005, 09:46 AM
  4. WANTED: Contest Master
    By kermi3 in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-23-2003, 09:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21