« first day (875 days earlier)      last day (4298 days later) » 

Xeo
Xeo
@Mysticial We're more than 15 helpful regulars in here. :P
The second most I've pulled off is probably +8 on the Loop question.
I don't think this maximum reduction approach is gonna work. Too many cases.
@StackedCrooked lol one of my teacher uses emacs iirc
see? combinatorial explosion
what did I say?
:P
@nneonneo Yeah, I was hoping to find a non-explosive approach.
01:01
oh shit pun
But we just proved that it doesn't exist with the circle example you gave.
I'm looking at even nastier examples in a text editor @_@
But yes, that question has shit all over it...
user1357851
NVM
@Telkitty?
@nneonneo Actually, regardless of polygon or islands or not. You always attack from the edges of the whole system.
So it wouldn't matter.
Since the entire system fits into a square of N x N squares. The system MUST always have at least one convex "pattern".
And I think the square corner and the snipped corners are the only convex patterns that need to be attacked.
In other words, (disregarding degenerate cases), there is always a square or snipped corner somewhere.
The diagonal example that I gave is not convex since it must wrap around somewhere.
Here's another convex case:
00000
00111
01111
11111
Possibly worse than the snipped corner.
user1357851
@nneonneo there is always the brute force
user1357851
if you do not want to think
01:10
@Telkitty: 1 ≤ n,m ≤ 1000, so bruteforce is O(k^1000000)
so no, brute force is not an option
that convex case doesn't need the top row..?
Was just trying trying to make it easier for me to visualize.
that one takes 2?
@Rapptz?
@Rapptz We're not trying to completely clear it. We're trying to find all the maximum reductions.
00000
00#11
01111
11111
^^ What are the all the maximum reductions to remove the #?
# + 1?
user1357851
01:13
@nneonneo how about bomb the ones with the biggest number? Choose the one with the biggest number and bombing it, knowing if that is reduced to zero then everything around it would be too? Someone gives me the drawback? Like bomb one with the biggest number until it becomes less than some other number then switch to the other number
Fuck, there's an exponentially large number of them depending on the neighboring numbers.
Actually it can be just #
There's 5 different (maximal) places you can nuke. And depending on the rest of the puzzle, how you split them matters. And there's and exponential number of combinations to the size of the neighbors.
# is 0 <= # <= 9 right?
@Telkitty That's not optimal.
user1357851
01:15
@Mysticial why?
@Rapptz I think so.
@Telkitty Fails for 09090
Your algorithm would need 18 bombs.
user1357851
no
user1357851
I said until it becomes smaller than some other number
It would still need 18, since then you switch off between them.
user1357851
while in that case I will re-write the matrix so each entry is the sum of itself and its surrounding numbers
01:19
in Java, 6 mins ago, by SpicyWeenie
@Code-Guru Are you just collecting code from other users or are you actually trying to help, because I'm weary (and others should be) of users always requesting code to be posted
In the meantime:
-1
Q: Is the universe really 13.7 billion years old?

Muste HassanWe know that the sun is approximately 4.5 billion years old, and it still have 4 billion years until it runs out of fuel and die. And we know that the sun is not a first generation star which means that before our sun even started to form, other stars formed, went through their full life cycle an...

user1357851
then do the same
user1357851
so 09090 will become 9 9 18 9 9
@Telkitty That's one of the existing answers on the question. It's not optimal when you have more complicated patterns of islands.
Xeo
Xeo
@Mysticial Aside from off-topicness, the OP has a wrong assumption about the lifetime. :s
01:20
pop quiz: what's the solution to
0 3 1 3 0
3 1 6 1 3
1 6 3 6 1
3 1 6 1 3
0 3 1 3 0
is it 12 again? if it's less than 12, I will probably shoot myself
not literally
user1357851
yeah 6 + 3 + 3
if it's more than 12 I will also be mad.
Xeo
Xeo
12 sounds good, just bomb the enclosed '1's 3 times each
I can't do better than 12.
user1357851
0 3 1 3 0
3 (1 )6 (1) 3
1 6 3 6 1
3 (1) 6 (1) 3
0 3 1 3 0
01:22
@Telkitty: you missed the two threes on either side of row 2
yeah I get 3 x 4
not.. 3 + 3 + 6
but same thing
much bigger than 5x5 and I think people are going to start having trouble with them
user1357851
wait need my coffee, obviously I am dumb without it :p ... see what I meant >_<
01:24
...
Perhaps this OP is trying to troll us by saying it's not NP. :)
And not linking us to the actual question.
If it's a troll, it's a pretty good troll... Hat's off to him/her.
lol
anyone have FireFox installed with the default bookamrks still there?
some people's children...
@Mysticial: ooh, the tinfoil hat. I like this approach.
01:36
@nneonneo hmm?
the troll comment suggests the "tinfoil hat approach" to algorithms programming
:)
but yeah, it might well be someone fishing for an efficient algorithm to something hard
lol
You know what?
user1357851
@Mysticial why? you only need to compute once and update once everytime you bomb something. so the expense of the solution is O(N)
I want to perform a move operation on my windows oem edition.
But it doesn't work.
@Mysticial what?
01:39
@StackedCrooked windows oem? do a trash operation instead :E
Xeo
Xeo
@Mysticial Not yet, but very soon?
This problem (when all numbers are reduced to 1) is a special case of the Set Covering Problem.
It's a move from one VMWare Fusion to Parallels.
That doesn't say much though.
Yeah, it doesn't say much at all
01:40
The "special case" might be enough to reduce it from NP-hard to polynomial.
yeah
technically....every single NP-or-less problem is a special case of that problem :)
(or can be somehow reduced to that problem)
@nneonneo Can we combine multiple bombs to produce "arbitrary" coverage? That would let us reduce it to the Set Covering Problem itself.
Or wait... that's counter productive...
You can tell I'm not an algorithms guy.
:P
what you want to do is reduce the SCP to the bomb problem
if you can do that then you prove it's NP-complete, then you're done
actually
...
01:44
SCP has arbitrary coverage. The bomb problem is only adjacent coverage. That's the key difference.
yes, I know. I feel like there might actually be a reduction somewhere
not necessarily to SCP
Xeo
Xeo
I feel like I should learn what this P, NP, NP-hard and NP-complete stuff is all about...
@Xeo lol
P: easy problems. NP: easy and hard problems. NP-hard: hard and very hard problems. NP-complete: hard problems.
@nneonneo not quite
01:46
yeah, I know
absolute gross oversimplification
P: easy problems
NP: easy and hard
NP-complete: hard to find, easy to verify:
NP-hard: hard to find, hard to verify
o.o
At least that's what I was taught in school. Might be worded differently though.
noo.
01:48
so they lied?
NP-complete is the intersection of NP and NP-hard
you can reduce any problem in NP to a problem in NP-hard
Then where does the categorization of of NP problems that are easy/hard to verify?
NP-hard includes every NP-complete problem, but also includes silly things like the halting problem
Oh your right...
this easy hard thing is silly
let me be a bit more specific
01:49
yes it is
@Xeo, pay attention :)
If you're not so bright then they're all hard.
there are two parts to a problem: finding the solution and checking the solution
P, NP, etc. deal with how hard it is to both find and check the solution
P means there is some way to find the solution in polynomial time
NP means there's some way to check the solution in polynomial time
every P problem is NP because you can "check" the solution by simply looking for it
(s/a/the/g because P and NP deal with binary decision problems)
Xeo
Xeo
So far I'm with you.
now, there's this notion of "reducing" a problem
that is, problem A can be "reduced" to problem B
01:53
Wait, SCP optimization is "hard" to verify isn't it?
if you can use a solution for problem B to solve problem A, through a reduction
"The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard."
so what's a reduction? basically, if you have some instance of problem A, you can turn it into an equivalent instance of problem B, in polynomial time
What is polynomial time?
it means, given some notion of the "size" of the problem, your algorithm runs in time proportional to some fixed polynomial in the input size
so, quadratic, cubic, quartic, etc.
but the exponent has to be fixed
Xeo
Xeo
@StackedCrooked I've been keeping the instances of that word in my head as "expand later", I first want to understand the P,NP, etc stuff. :)
Exponential time would not be polynomial time.
P = Polynomial
NP = non-Polynomial
doesn't get any easier to memorize that
01:57
NP doesn't stand for non polynomial!
user1357851
O(N^2) O(N^3) etc
it's a common misconception
:)
@Mysticial actually, isn't NP non deterministic Polynomial? :S
NP stands for "nondeterministic polynomial"
@nneonneo ssshshhh it isn't proved yet, But don't confuse him anymore.
user1357851
01:58
I figure you are not really a software developer
ok
@Telkitty: what, me?
I write programs
ignore telkitty
user1357851
You didn't know the big O notation
so if we have a reduction from problem A to problem B
then problem A can't be any "harder" than problem B
That's enough.
01:59
P -- the set of all problems we can find a solution for in polynomial time

« first day (875 days earlier)      last day (4298 days later) »