Also, all problems are designed with a specific algorithm in mind, leading to a required time complexity.
The secret program inputs are then be designed to be large enough to be solved much much faster than the time limit with the correct complexity, but much much slower than the time limit with the wrong complexity.
You can typically look at the problem specification to see what the maximum input size is - and you should expect that you _will_ get inputs of that size, and do a rough estimate of how many operations that will require with your solution.
I've been in a competition where I used a O(n^2) algorithm where I didn't see the O(n*log n) solution (No it wasn't sorting, it was a Dynamic Programming-problem). I was convinced for a fairly long time that my algorithm was fast enough, so I spent time suboptimizing instead of solving the root problem - the wrong algorithm. With the right algorithm, it passed right away.
That said, some problems are indeed expected to be solved by brute force, or by a combination of brute force and tricks to shrink the search space. These problems can mostly be identified by guarantees of small inputs in the description.
Sure, it's the halting problem. We all know that. But there are several common cases where you can deduce that there is an infinite loop in the code. It won't catch all infinite loops, but that doesn't make it useless.
(Suns Java seems to be good at detecting some of those by default when it complains about unreachable return statement)
Couldn't they put the info both clearly visible in a comment-field an watermarked throughout the sound file?
That way, they can announce that they store the info in the file, people will verify that it's in the comment-field. The trivial hack would simply be to strip the info from the comment-field unknowing of the watermark (that's hard to detect).
Then distributing a file with a modified comment field wouldn't help, since they would also use the watermark to identify the origin.
For a simple, connected, planar graph with v vertices and e edges, the following simple planarity criteria hold: Theorem 1. If v 3 then e 3v - 6
See, it's not "if and only if", it's just "if". It only goes one way. This formula can only prove that a graph is not planar, it can not be used to prove that a graph is planar. You can read more details about it on the wikipedia page i linked.
0) You need the parentheses on function calls.
False, f("a string") is equivalent to f"a string" and f({a = b}) is equivalent to f{a = b}
a) Only data structure is hash tables
False, lua tables contain both a hash table part and a pure array part. The runtime figures out how to store stuff internally. As a lua programmer, you never need to care, but if you're only using positive integer keys between 1 and N, with few gaps, it will most likely be stored as an array.
e) No semicolon separator
False, there is a semicolon seperator, but in most cases, you don't need it. a = 4 b = 6 can only be interpretered in one way so you don't have to write a = 4; b = 6, even though you can, if you want.
i) An extremely quirky stack based interface to C. Some api's pop their arguments some don't. They should do it the Forth way (words consume their arguments) or not automatically pop anything. Pick one, not both. And please, some simple stack operators (swap, drop, dup, roll, etc.)
Lua's popping of arguments is not really a problem, just read the manual, it's very clearly described how they behave.
Also lua does have lots of stack operators, see the manual.
lua_pushvalue(L, -1) would correspond to a dup.
lua_insert(L, -2) would correspond to a swap. If by drop you mean pop off elements from the stack, see lua_pop. I couldn't find a roll operator, but that is just a series of inserts anyway. Other interesting stack operations are lua_remove, lua_replace. I am sure you can find enough stack operators to get by.
Oh, do you also have one of those mouses with a limited amount of clicks built in? My mouse only have about 98712 clicks left. 98711 after I hit submit I suppose. Don't want to waste those precious clicks.
I don't get it, is it supposed to be impossible to game under linux? If the gamer in question is basically just playing the few games that are actually ported to linux, it would not be difficult at all. And for Windows-only games, you can still run the games fine using WineX in many cases. I run Warcraft 3 just perfectly with WineX. I can not tell the difference from playing it under Windows. This is not a boast, I simply used WineX and it worked.
Did you even read the contents of that link?
One time pads are mathematically secure - this doesn't mean that one time pads can be implemented - but the theory behind it is completely sound. You can not crack a one time pad simply because every possible sentence of a given length could be produced by the same cryptotext and you have no idea which one it is.
It's not a question of current technology at all. RTFL.
I was at NWERC '03 in Lund and one of the problems (the one with the train system)
had a badly formed input but since our team assumed at the input was formatted correctly (which was guaranteed by the problem spec.) our
program crashed. We got it right on the first try but we spent a lot of time looking for buggy code and searching for reasons to crash.
We wasted lots of time and didn't complete any more problems but we were close to solve a problem in the last few minutes so we may have gotten two problems solved instead of one if the spec had been correct.
Interestingly enough, the team that won (and came second in the world finals (congrats to Threeheaded monkey!)) had the same problem but also deduced that the input was flawed so they notified the judges. I suppose we would have gotten zero problems solved if it hadn't been for them.
The difference between our stories is that we wouldn't have chance at the top 10 anyway.
I am almost in the same position
as you are in. I bought the
Pinnacle PCTV Rave a few days
ago and started playing with
it today. I got it to work
real reasily in Windows and after
that I tried to get to work in
Linux (Mepis/Debian).
This was a fairly easy process
after a bit of googling on the
setup. Note that I am far from
a Linux expert and I am a bit
proud of myself.
So, after a few hours of
editing/etc/modules and/etc/modules.conf and
running tvtime-scanner
I am now watching TV with
all my available channels, well,
available! The quality is
definitely good enough for everyday
watching. The sound is mono
and I haven't tried recording yet but
I suspect it can't take that many hours
to get the hang of.
(I want to setup a system of auto-recording
stuff I want to see et.c.)
A Good Thing(tm) is that recent Linux Kernels support
this out of the box (I believe it's something like 2.4.22), I didn't have to recompile the kernel or
anything like that.
But the best part is that it only costs 399 SEK
in Sweden which I suppose is something around
$40.
Just trying to use transparent windows in... well, windows distracts me. Why would a transparent monitor be useful?
Don't we want to concentrate on what we're doing anyway? If I'm driving a car, I don't want to browse some news page at the same time and if I am coding something, I don't want to watch the wall behing the monitor.
Transparent transistors are cool and all, and I'm sure we'll see some good applications for it, but I don't think "transparent monitors" in itself will be the next Killer Application.
Invisibility possible now?
on
Mastering Light
·
· Score: 3, Interesting
So, does this mean we can make ourselves invisible? If we would make a suit of frequency shifters we could make the visible light turn into radio waves, let them pass through the body, and then change them back into visible light.
Of course, it would require huge amounts of energy aswell as precision, so it probablly won't happen anytime soon.
Interesting thought, though.
Well sure, now it's a bother to use GPRS over phones, but what about in a year or two? Or five years? We shouldn't automatically dismiss new ideas based on the limitations of technology today.
Slashdot Mirror
Also, all problems are designed with a specific algorithm in mind, leading to a required time complexity.
The secret program inputs are then be designed to be large enough to be solved much much faster than the time limit with the correct complexity, but much much slower than the time limit with the wrong complexity.
You can typically look at the problem specification to see what the maximum input size is - and you should expect that you _will_ get inputs of that size, and do a rough estimate of how many operations that will require with your solution.
I've been in a competition where I used a O(n^2) algorithm where I didn't see the O(n*log n) solution (No it wasn't sorting, it was a Dynamic Programming-problem). I was convinced for a fairly long time that my algorithm was fast enough, so I spent time suboptimizing instead of solving the root problem - the wrong algorithm.
With the right algorithm, it passed right away.
That said, some problems are indeed expected to be solved by brute force, or by a combination of brute force and tricks to shrink the search space. These problems can mostly be identified by guarantees of small inputs in the description.
Fixed it for ya!
You forgot one search/replace!
Pirate: My witty statements always become memes
Guybrush Threepwood: Oh really? To me that just sound like clichés.
Alternative reply: Too bad no one's ever heard of YOU at all.
Bad reply: I am rubber, you are glue.
Sure, it's the halting problem. We all know that. But there are several common cases where you can deduce that there is an infinite loop in the code. It won't catch all infinite loops, but that doesn't make it useless.
(Suns Java seems to be good at detecting some of those by default when it complains about unreachable return statement)
Couldn't they put the info both clearly visible in a comment-field an watermarked throughout the sound file? That way, they can announce that they store the info in the file, people will verify that it's in the comment-field. The trivial hack would simply be to strip the info from the comment-field unknowing of the watermark (that's hard to detect). Then distributing a file with a modified comment field wouldn't help, since they would also use the watermark to identify the origin.
Or am I missing something here?
Sideshow Bob: Attempted murder, now honestly, what is that? Do they give a Nobel Prize for attempted chemistry?
You've gotten it wrong. The formula was right but you're using it badly.
From http://en.wikipedia.org/wiki/Planar_graph
For a simple, connected, planar graph with v vertices and e edges, the following simple planarity criteria hold:
Theorem 1. If v 3 then e 3v - 6
See, it's not "if and only if", it's just "if". It only goes one way.
This formula can only prove that a graph is not planar, it can not be used to prove that a graph is planar. You can read more details about it on the wikipedia page i linked.
You got a few things wrong:
0) You need the parentheses on function calls.
False, f("a string") is equivalent to f"a string" and f({a = b}) is equivalent to f{a = b}
a) Only data structure is hash tables
False, lua tables contain both a hash table part and a pure array part. The runtime figures out how to store stuff internally. As a lua programmer, you never need to care, but if you're only using positive integer keys between 1 and N, with few gaps, it will most likely be stored as an array.
e) No semicolon separator
False, there is a semicolon seperator, but in most cases, you don't need it. a = 4 b = 6 can only be interpretered in one way so you don't have to write a = 4; b = 6, even though you can, if you want.
i) An extremely quirky stack based interface to C. Some api's pop their arguments some don't. They should do it the Forth way (words consume their arguments) or not automatically pop anything. Pick one, not both. And please, some simple stack operators (swap, drop, dup, roll, etc.)
Lua's popping of arguments is not really a problem, just read the manual, it's very clearly described how they behave. Also lua does have lots of stack operators, see the manual. lua_pushvalue(L, -1) would correspond to a dup. lua_insert(L, -2) would correspond to a swap. If by drop you mean pop off elements from the stack, see lua_pop. I couldn't find a roll operator, but that is just a series of inserts anyway. Other interesting stack operations are lua_remove, lua_replace. I am sure you can find enough stack operators to get by.
The expression is clearly stated as an arithmetic question, not an expression in some programming language, so 5 whould be the only valid answer.
Oh, do you also have one of those mouses with a limited amount of clicks built in? My mouse only have about 98712 clicks left. 98711 after I hit submit I suppose. Don't want to waste those precious clicks.
Digital signatures definitely have something to do with cryptography but is in general not related to encryption.
I don't get it, is it supposed to be impossible to game under linux? If the gamer in question is basically just playing the few games that are actually ported to linux, it would not be difficult at all. And for Windows-only games, you can still run the games fine using WineX in many cases. I run Warcraft 3 just perfectly with WineX. I can not tell the difference from playing it under Windows. This is not a boast, I simply used WineX and it worked.
Or was it an attempt at +3 funny?
Did you even read the contents of that link? One time pads are mathematically secure - this doesn't mean that one time pads can be implemented - but the theory behind it is completely sound. You can not crack a one time pad simply because every possible sentence of a given length could be produced by the same cryptotext and you have no idea which one it is.
It's not a question of current technology at all. RTFL.
I was at NWERC '03 in Lund and one of the problems (the one with the train system) had a badly formed input but since our team assumed at the input was formatted correctly (which was guaranteed by the problem spec.) our program crashed. We got it right on the first try but we spent a lot of time looking for buggy code and searching for reasons to crash.
We wasted lots of time and didn't complete any more problems but we were close to solve a problem in the last few minutes so we may have gotten two problems solved instead of one if the spec had been correct.
Interestingly enough, the team that won (and came second in the world finals (congrats to Threeheaded monkey!)) had the same problem but also deduced that the input was flawed so they notified the judges. I suppose we would have gotten zero problems solved if it hadn't been for them.
The difference between our stories is that we wouldn't have chance at the top 10 anyway.
The difference is basically that velocity is a vector and speed is an absolute value. I.e. a velocity consists of a direction and a speed.
I would imagine that going from good to bad is an easier transition than the other way around.
I am almost in the same position as you are in. I bought the Pinnacle PCTV Rave a few days ago and started playing with it today. I got it to work real reasily in Windows and after that I tried to get to work in Linux (Mepis/Debian).
/etc/modules and /etc/modules.conf and
running tvtime-scanner
I am now watching TV with
all my available channels, well,
available! The quality is
definitely good enough for everyday
watching. The sound is mono
and I haven't tried recording yet but
I suspect it can't take that many hours
to get the hang of.
This was a fairly easy process after a bit of googling on the setup. Note that I am far from a Linux expert and I am a bit proud of myself.
So, after a few hours of editing
(I want to setup a system of auto-recording stuff I want to see et.c.)
A Good Thing(tm) is that recent Linux Kernels support this out of the box (I believe it's something like 2.4.22), I didn't have to recompile the kernel or anything like that.
But the best part is that it only costs 399 SEK in Sweden which I suppose is something around $40.
So I guess this really is the current fashion, huh?
(And it will probably make guys resist women.)
Sorry, but you knew these were coming anyway.
Just trying to use transparent windows in ... well, windows distracts me. Why would a transparent monitor be useful?
Don't we want to concentrate on what we're doing anyway? If I'm driving a car, I don't want to browse some news page at the same time and if I am coding something, I don't want to watch the wall behing the monitor.
Transparent transistors are cool and all, and I'm sure we'll see some good applications for it, but I don't think "transparent monitors" in itself will be the next Killer Application.
So, does this mean we can make ourselves invisible? If we would make a suit of frequency shifters we could make the visible light turn into radio waves, let them pass through the body, and then change them back into visible light. Of course, it would require huge amounts of energy aswell as precision, so it probablly won't happen anytime soon. Interesting thought, though.
And 640 billion should be enough for anybody.
Well sure, now it's a bother to use GPRS over phones, but what about in a year or two? Or five years? We shouldn't automatically dismiss new ideas based on the limitations of technology today.