New Monthly Contest!

This is a discussion on New Monthly Contest! within the Contests Board forums, part of the Community Boards category; range=1000, prevGuesses=(), numAfter=2 returns 750 Wouldn't 251 have the same chance of winning, for symmetry reasons? EDIT: NM, I understand ...

  1. #16
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    range=1000, prevGuesses=(), numAfter=2 returns 750
    Wouldn't 251 have the same chance of winning, for symmetry reasons?

    EDIT: NM, I understand now.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  2. #17
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    >>Wouldn't 251 have the same chance of winning, for symmetry reasons?<<

    Thats a good question that others might be curious about so I'll answer it anyways. The answer is no symmetry does not apply in this case. If you chose 251, player 2 would choose 750, then player 3 again having a choice between any number between 252 and 749 will choose the lowest one, being 252. Your winning chances in this scenario are much lower than the one in the example where you choose 750.

    I've also made a small change in the easy problem allowing you to use c-strings instead of the string class if you want to in regards to a PM I received. I figured that a number of people who are just starting out C++ will be unfamiliar with strings and I'd prefer them not to have to worry about learning them just to send in code. Just be sure it is null terminated!

    [edit] Oops, guess I'm past the deadline for editing posts, I can't update the easy problem [/edit]

  3. #18
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by PJYelton
    She does however remember a curious fact. She remembers starting at a particular pearl and counting “K” times to the first gold pearl. She plucked it off, then continued counting “K” more times and again hit another gold pearl. She continued this pattern and every time she hit a gold pearl, never once a white pearl, until all the gold ones were removed.

    ...snip...

    For example, say she tells you that there were 5 white pearls, 4 gold pearls, and K was 4. Then her original necklace would look like this where ‘w’ stands for white and ‘g’ stands for gold:

    “wwggwwwgg”

    Reasoning:
    Your example invalidates itself.

    She remembers starting at a particular pearl and counting “K” times to the first gold pearl.

    “wwggwwwgg”
    Your example does not fit your given output. It cannot possibly be the first gold pearl with the input you've given. Not in that exact setting. You would have to shift your output.

    "wwwggwwgg"

    That would fit. Unless you don't really care what the starting point is, so long as some place in the string it matches up. If that's the case, then this is also a valid answer to your problem:

    "ggwwggwww"

    originalNecklace(9,13,11) returns “ggggwgwgwwggwggwwwwggg”
    No it doesn't. It returns this:
    “wwwwwwwwwwgwwwwwwwwwwg”

    Here's why:

    Start out blank:
    “wwwwwwwwwwwwwwwwwwwwww”

    Move out 11, and place one there:
    “wwwwwwwwwwgwwwwwwwwwww”

    Move out 11, and place one there:
    “wwwwwwwwwwgwwwwwwwwwwg”

    Move out 11, and... oops:
    “wwwwwwwwwwgwwwwwwwwwwg”

    [edit]
    There may be a way to get the output you want. I don't think your parameters will fit still though. If you're reconstructing, and starting from scratch, your wrap around will be different. However, your output still won't give you what you want, and you still won't encounter the "first gold pearl" like you have stated. That part of your example is incorrect, which leads to false assumptions in the rest of your logic.
    [/edit]

    Quzah.
    Last edited by quzah; 03-04-2005 at 09:02 AM.
    Hope is the first step on the road to disappointment.

  4. #19
    former member Brain Cell's Avatar
    Join Date
    Feb 2004
    Posts
    472
    I just sent PJyelton a PM saying the same thing.
    My Tutorials :
    - Bad programming practices in : C
    - C\C++ Tips
    (constrcutive criticism is very welcome)


    - Brain Cell

  5. #20
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well let's try again, this time, only using the pearls available, and not starting with a blank full list.

    I still don't believe you can get the required output. Here's my "in the edit-post box" try, which now has turned into a seperate post:

    originalNecklace(9,13,11) returns “ggggwgwgwwggwggwwwwggg”
    No, there isn't. Your last example is broken. Even if you started looping on reconstruction, you cannot get the output you want. Here's why:

    1) There are only ever nine white pearls here in this example.
    2) There are only ever thirteen gold ones. Let's build a necklace:

    Nine white go on first:

    wwwwwwwww

    Now we're out of white, so we have to wrap around 2 places.

    wwwwwwwww

    Ok, now I'm on the eleventh white pearl. Do I insert before or after it?
    Let's try after:

    wwgwwwwwww
    wwgwgwwwwww
    wwgwggwwwwww
    wwgwgggwwwwww
    wwgwggggwwwwww
    wwggwggggwwwwww
    wwggwggggwwwwwgw
    wwggwggggwgwwwwgw
    wwggwgggggwgwwwwgw
    wwggwgggggwgwwwwggw
    wwggwggggggwgwwwwggw
    wwgggwggggggwgwwwwggw
    wwgggwggggggwggwwwwggw

    Let's see if that output fits, shall we?


    “ggggwgwgwwggwggwwwwggg” //origional
    “wwgggwggggggwggwwwwggw” //mine, computed by hand

    Nope. Doesn't work. Just compare the longest run of 'g', followed by the pattern after it. Now, I could be off here, after all, you try manually wrapping around in the context of this posting box, and getting it right.

    But if I'm incorrect in my doing it by hand, that would be the solution. However, again, this doesn't really fit the origional described rules. For one, we still have the problem of the "first pearl encountered", which breaks the whole thing.

    However, we have problems here too. Here they are:
    1) Do we insert before or after the stopping space?
    2) Does the new pearl you've just inserted constitute the "1" step, or is it not counted?

    There's simply not enough information in this one case to solve the problem. We could guess, but that doesn't tell us for sure. For starters, she has absoultely no idea what the thing even looked like, so we don't, and can't, use "sample output" to test our fomulae, because there is none. So you can't rely on that.

    So, excluding sample output, because that wouldn't be available, combine with not knowing if we insert before or after, and not knowing if we count the newly placed pearl, leaves this example unsolvable, or at best, incorrect.

    I mean, we already know that it can't be correct if we're leaving out a bunch of pearls. That means we have to know if we insert before or after, or what is counted or not. Furthermore, we cannot use sample output to give us this information, because in this scenario, there is no "sample output", because she again doesn't remember what it looks like.


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

  6. #21
    former member Brain Cell's Avatar
    Join Date
    Feb 2004
    Posts
    472
    Quote Originally Posted by quzah
    2) Does the new pearl you've just inserted constitute the "1" step, or is it not counted?
    It should'nt be counted in my opinion.

    Lets say we call the function with the following arguments :
    Code:
    originalNecklace(1, 3, 1)
    If we count the pearl we've just inserted , it would look like this :

    gwww

    you simply insert a 'g' then insert another 'g' on top of it and same thing with the third one wich wouldn't make sense because the function call asked for 3 gold not 1.


    man ... you gotta have lots of free time to make a colorful reply like that
    My Tutorials :
    - Bad programming practices in : C
    - C\C++ Tips
    (constrcutive criticism is very welcome)


    - Brain Cell

  7. #22
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Your example does not fit your given output. It cannot possibly be the first gold pearl with the input you've given. Not in that exact setting. You would have to shift your output.

    "wwwggwwgg"

    That would fit. Unless you don't really care what the starting point is, so long as some place in the string it matches up. If that's the case, then this is also a valid answer to your problem:

    "ggwwggwww"
    LOL, ok, you got me. Basically when I saw this problem it was very technical and since I didn't want to scare people off I decided to write a small little story to go along with it, thus the necklaces and the pearls. Unfortunately I missed the little mistake you pointed out.

    To clarify, the FIRST pearl she runs into isn't necessarily the first one she plucks out of the necklace. She starts at the beginning and counts to k, plucks off a gold pearl, counts to k again, plucks off a gold pearl, continues to do this until there are no more gold pearls.

    Unless you don't really care what the starting point is, so long as some place in the string it matches up. If that's the case, then this is also a valid answer to your problem:

    "ggwwggwww"
    Yes, starting place does matter, you must start from the beginning of the string. Sorry if I didn't clarify that.

    This is the nuts and bolts of the problem: You have a string of pearls in a circle, you start at the beginning (in this case the beginning of the string) and count k times and take a gold pearl. You continue to do this numGold times until there are no more gold pearls. Now given k, numGold, and numWhite, what did the original necklace look like?

    As for the second post, I can safely say that working backwards and inserting is not the best solution since not only do you have to tackle whether or not inserting before or after is correct, but you also have to figure out the correct spot to start from. You start from index 0 when you start taking away gold pearls, but you can end anywhere. You'd have to define precisely what the exact opposite of counting and taking out pearls is which would include inserting before or after, which direction to count, and whether or not to count the newly inserted pearl.

    Lets use your method on something like (4,3,5). You would get "wgggwww" which clearly isn't correct since even if you could start anywhere, you still couldn't find a spot where you count to five, pluck a gold, count to five, pluck a gold, then count to five and pluck a gold. The correct answer is wggwgww.

    There is a much simpler solution to this problem that involves no backtracking at all.
    Last edited by PJYelton; 03-04-2005 at 11:16 AM. Reason: added quote tags

  8. #23
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by PJYelton
    Yes, starting place does matter, you must start from the beginning of the string. Sorry if I didn't clarify that.
    I did start at the beginning of the string. However, again, you have no actual string. You must recreate one. If you use a "field of blanks", then the output I listed is a valid solution. It is exactly the same as yours, since this is in fact a circular necklace, except it's rotated slightly.

    However, I suspect that your actual answer for that example is in fact wrong. Here's my spur of the moment attempt to prove it. We will work with the output, and do as you suggest:

    originalNecklace(5,4,4) returns “wwggwwwgg”
    First, we count ahead four places:

    “wwggwwwgg”

    Now we remove this pearl. This shortens the string by one. We're now here:

    “wwgwwwgg”

    “wwgwwwg”

    Oops. Your program just broke. You cannot be "removing one pearl" from the string, and have the output you expect. It's impossible. She didn't have that output, because had she actually removed the pearls, the string would shorten itself, and on the third attempt, it breaks by stopping on a white pearl.

    Also, aside from the broken example that I've shown, everything else is solvable with the exact same circular pattern, slightly shifted. (Check your PM.)

    It doesn't matter that starting place, because as you've stated, it's a circle. Since it is circular, the output text would also be circular. So as long as the pearl pattern itself is correct, the necklace itself is correct. Besides, necklaces always slide around when worn anyway.


    Quote Originally Posted by PJYelton
    This is the nuts and bolts of the problem: You have a string of pearls in a circle, you start at the beginning (in this case the beginning of the string) and count k times and take a gold pearl. You continue to do this numGold times until there are no more gold pearls. Now given k, numGold, and numWhite, what did the original necklace look like?
    That's easy enough, again, check your PM.

    Quote Originally Posted by PJYelton
    As for the second post, I can safely say that working backwards and inserting is not the best solution since not only do you have to tackle whether or not inserting before or after is correct, but you also have to figure out the correct spot to start from. You start from index 0 when you start taking away gold pearls, but you can end anywhere. You'd have to define precisely what the exact opposite of counting and taking out pearls is which would include inserting before or after, which direction to count, and whether or not to count the newly inserted pearl.
    There is no "correct spot to start from". Just start from the beginning and build the string. However, you cannot with the information you provide, not for all of your cases. As stated, it is an impossibility to get the output you provide with her trying to assemble a new necklace by hand. You cannot get the output you state. Why? Well she only has nine white pearls. Therefore, you cannot plunk them all down and still move two "non existant white pearls" in play. They don't exist, therefore, the necklace couldn't have been made.

    The only way to fix that, is to grab all the pearls randomly, and from a bag, start laying them out until you're at the 11th position, and then start counting for K. You can't however. Again, since you have no output to work from (remember, you don't actually know what the necklace looks like), you have no idea of knowing when you've got them all shuffled around in the right order. Like so:

    ggwwwgwwwwg....

    There. We randomly throw out pearls until we hit K, and now we place one gold one. We contunue to randomly throw out pearls until we hit K2. What happens if we've used up all of our whites, or golds, before we hit K2? Or K3? Well then you have to go steal one from some place else, and subsitute it with something.

    So you now must create an index of ones you can't steal from. Then you repeat moving through N times and hope your output lines up with something you can't check against.

    Quote Originally Posted by PJYelton
    Lets use your method on something like (4,3,5). You would get "wgggwww" which clearly isn't correct since even if you could start anywhere, you still couldn't find a spot where you count to five, pluck a gold, count to five, pluck a gold, then count to five and pluck a gold. The correct answer is wggwgww.

    There is a much simpler solution to this problem that involves no backtracking at all.
    No, my method gives me:

    "wgwwgwg"

    Which clearly is correct. [edit]...wrong...wft...lol...[/edit]
    Quote Originally Posted by PJYelton
    The correct answer is wggwgww.
    Your answer is clearly wrong. Here's why:

    Code:
    wggwgww
    12345
    
    wggwgww
    345  12
    
    wggwgww
    5  1234
    Which clearly is wrong. Now look at my output, which is correct.
    [edit](Well it should have been. I've been tweaking this so much trying to get the third one fixed, I'll have to go over it again. Anyway, for this one, my output is wrong apparently. (Anyone have a shoehorn? I seem to have a food in my mouth. It looks like we're both wrong.))[/edit]

    Quzah.
    Last edited by quzah; 03-04-2005 at 11:54 AM.
    Hope is the first step on the road to disappointment.

  9. #24
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by quzah
    I seem to have a food in my mouth.
    It's perfectly fine to have food in your mouth. It's called eating.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  10. #25
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Hah. Ok, I found out why that was wrong. I had been changing the starting value of a counter to try and get it shifted correctly. Here's the "real" correct output:
    Code:
    gwgwgww
    I've resent you a PM with the "real" working version.

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

  11. #26
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    I'll admit a certain amount of ignorance. I read the whole thread, but some of the details seem over my head.
    Quote Originally Posted by quzah
    No, my method gives me:

    "wgwwgwg"

    Which clearly is correct.
    That's what I got too. It works, depending on how you count. Remove the red, start the next pass through at the blue.
    Code:
    wgwwgwg
    12345
    
    wgwwwg
    45 123
    
    wwwwg
    12345
    As you can see, this works if you fall back to the previous pearl after removal. I fail to see how "gwgwgww" can work using any counting method. Using a fall-back counting:
    Code:
    gwgwgww
    12345
    
    gwgwww
    45 123
    That leads to removing a white. Using a step-forward method:
    Code:
    gwgwgww
    12345
    
    gwgwww
    345 12
    
    gwwww
    45123
    This also leads to removing a white.

    edit: If you want a step-forward solution, you can use "wggwgww" as PJYelton suggested.
    Code:
    wggwgww
    12345
    
    wggwww
    345 12
    
    wgwww
    45123
    Last edited by pianorain; 03-04-2005 at 12:22 PM.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  12. #27
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by quzah
    originalNecklace(5,4,4) returns “wwggwwwgg”
    First, we count ahead four places:
    “wwggwwwgg”
    Now we remove this pearl. This shortens the string by one. We're now here:
    “wwgwwwgg”
    “wwgwwwg”
    Actually, it works.
    Code:
    wwggwwwgg
    1234
    
    wwgwwwgg
       1234
    
    wwgwwwg
    234   1
    
    wwwwwg
      1234
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  13. #28
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313
    PJY is correct in his reasoning in the inital problem. When the contest is over, if he doesn't, I'll release my source so ya'll can see why.
    Last edited by Lithorien; 03-04-2005 at 12:42 PM. Reason: I gave away the algorithm.

  14. #29
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Heh, it took me a while to figure out the algorithm, even though I developed the solutions for both originalNecklace(5,4,4) and originalNecklace(4,3,5). I wasn't exactly sure how I was doing it; it just worked when I was finished with it.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  15. #30
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    LOL, this is turning into the most complicated "easy" problem of all time

    Quzah, I admit that I'm a little confused with where you stand at this point since you've corrected yourself a couple of times, so if I say something you already know just bear with me. Also, I'm at work and can't test your code until tonight sometime.

    First, we count ahead four places:

    “wwggwwwgg”

    Now we remove this pearl. This shortens the string by one. We're now here:

    “wwgwwwgg”

    “wwgwwwg”
    You have a mistake here (which might be the counting error you mentioned). You counted 5 as the distance between your first and second gold pearl, thus you took out the wrong one.

    Like pianorain's example, you have to remember that when you find your gold pearl, you must remove it. Your examples keep the gold pearl there thus it gets counted again. However, pianorain starts the count again from the previous pearl when you are instead supposed to start from the next pearl. Lets go to my example of (4,3,5). With my answer of wggwgww:
    Code:
    12345
    wggwgww
    345  12
    wggwgww
    45 1 23
    wggwgww
    Notice how you have to skip the third gold pearl the second time through the string?

    It doesn't matter that starting place, because as you've stated, it's a circle. Since it is circular, the output text would also be circular. So as long as the pearl pattern itself is correct, the necklace itself is correct. Besides, necklaces always slide around when worn anyway.
    LOL true, I'd prefer if you assume she counted from the beginning of the C++ string that is returned from the function when plucking the pearls so that everyone has the same answer.

    Quzah, I admit to being rather confused with your example of why the (9,13,11) is broken. If you follow my above example with the answer “ggggwgwgwwggwggwwwwggg” it works, counting to 11, taking away the gold pearl from the string, rinse repeat 13 times.
    Last edited by PJYelton; 03-04-2005 at 01:05 PM.

Page 2 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