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?Originally Posted by treenef
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
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.
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:
There you go. It's broken. This one is unsolvable.Code:1234567890g1234567890g
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.
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.Code:x = y + z5;
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.
Ok. Then the reverse of that would be:Code:5,4,4 1234 wwggwwwgg <-- Do the count. 1234 wwgwwwgg <-- We now have this. 234 1 wwgwwwg 1234 wwwwwg wwwww
"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."
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.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
Now let's try the big one.
We have a winner!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
ggggwgwgwwggwggwwwwggg
wgggggggwwwwggwggwwgwg
No, we actually don't. If we left shift this four places, to make the large block of Gs match:
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...Code:ggggwgwgwwggwggwwwwggg wgggggggwwwwggwggwwgwg ggggwgwgwwggwggwwwwggg gggggggwwwwggwggwwgwgw ggggwgwgwwggwggwwwwggg ggggggwwwwggwggwwgwgwg ggggwgwgwwggwggwwwwggg gggggwwwwggwggwwgwgwgg ggggwgwgwwggwggwwwwggg ggggwwwwggwggwwgwgwggg
ggggwgwgwwggwggwwwwggg
wgggggggwwwwggwggwwgwg
ggggwgwgwwggwggwwwwgggCode:wgggggggwwwwggwggwwgwg gwgwwggwggwwwwgggggggw (right?)
gwgwwggwggwwwwgggggggw
Now we right shift it to line up the block of Gs...
Now we have a winner.Code:ggggwgwgwwggwggwwwwggg gwgwwggwggwwwwgggggggw ggggwgwgwwggwggwwwwggg wgwgwwggwggwwwwggggggg ggggwgwgwwggwggwwwwggg gwgwgwwggwggwwwwgggggg ggggwgwgwwggwggwwwwggg ggwgwgwwggwggwwwwggggg ggggwgwgwwggwggwwwwggg gggwgwgwwggwggwwwwgggg ggggwgwgwwggwggwwwwggg ggggwgwgwwggwggwwwwgggSo 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.
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.
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
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.
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
I sent you a PM with my entry for the easy problem.
Micko
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.
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.
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
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
The medium/hard were very hard. I couldn't figure them out. :/
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.
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
