Easter eggs
Back to Programming Languages forum
Can someone write me, what's i do wrong:
take the last position like start position, where everything is 0.
We begin to apply to this condition each peak of the Graph given in the task.
1.If the peek has already been applied, then the second time does not need to be applied. Mutually exclusive movements.
2.If the position already existed, then there is no need to write down the path to it, since we have a shorter distance.
3.As soon as the desired state is met, we display the solution that led us to it.
What did I do wrong? with small graph working, with task condition: 5 minutes - TT
bad case of bruteForce?:D Yes, I can stay PC for night while it find 2^20 decisions, but i hope admin don't wanna this:D
was thinking about go from zero point and use flip if this eggs have not need color, but its create cycles)=
Andrey, Hi!
I'm not sure I completely understand your approach, but let's note that:
- order in which eggs are touched doesn't matter
- no egg should be touched more than once
is no need to write down the path to it
to be honest, you are never asked about paths, as "order doesn't matter"... it seems you needn't traverse a graph.
I can stay PC for night while it find 2^20 decisions
There are only 2^20 ways to touch eggs, which is just about 1 million. Checking every of them is easy... So I don't think it should take all night. You probably spent too much time on some unnecessary auxiliary work?
P.S. I won't be surprised if more clever solution exists. Or rather I vaguely suspect there is O(N^3) solution or something like this, solving system of linear equations in GF2, but I'm too stupid to solve it myself. Perhaps I should try once more.
tnx Rodion, you confirmed my words, it means I was moving in the right direction, I just did too much additional calculations
Fuh... Two night i sleep with nightmare about easter eggs and try finding another solution, deeper and deeper went to theory of graphs, it wasdisgusting.
but thinking that in theory we have one of solutions. I find some material about this theme, but didn't wanted try them before find more humanity solution:D
tnx one more time, you save my brain
it was a very difficult problem to me, I tried graphs to genetic algorithms... I ended applying like a brute force solutions by testing all the subsets possibles because the order is not important. I am not proud but it worked pretty fast
Mooninvader, don't sure, but think that it will be interesting for u in this problem: http://people.csail.mit.edu/nbenbern/CoinFlipping.pdf
This paper seems to be quite long and a bit confusing for my aging mind :)
I dare to elaborate solution I meant - not invented by myself definitely - I believe someone implemented it.
It's just a linear equations system :)
Really, let's denote wether we touch i-th egg with value Xi set to 0 or 1. Let's denote as Yj the state
of j-th egg after all necessary touches (flips). For example if 3-rd egg is flipped when touching 1-st, 2-th or
5-th egg, it makes an equation
Y3 = (X1 + X2 + X5) mod 2 = 1 * X1 + 1 * X2 + 0 * X3 + 0 * X4 + 1 * X5 | mod 2
So we can write N equations for N variables (Xs), to solve which of variables should be set to 1 and which
should not.
We know how to solve linear equations systems in no harder than O(N^3) time... So the only remaining question is
how to solve linear equation system in modular arithmetic (which I leave to those curious to investigate). Probably
we should once have "advanced" problem version on larger input set.
I vote that "advanced" version should exist!