Tag Info

New answers tagged

1

Newer answer I will outline a simple attack. Of course the answer is data-dependent; every answer to OP's question has to be data-dependent. Let's define a function IndexOf(sequence, query) which returns: k if Compare(sequence[k], query) == EQ, k + 0.5 if Compare(sequence[k], query) == LT and Compare(query, sequence[k+1]) == LT other values, such as -1 ...


19

The normal merge sort algorithm - merge step with normally apply n + m -1 comparisons, where one list is of size n and and the other list is of size m. Using this algorithm is the most simplest approach to combine two sorted lists. If the comparisons are too expensive you could do two things - either you minimize the number of comparisons or you minimize ...


1

OK, so I feel I've done enough research to at least begin to move things in a helpful direction. The term for what you are looking for generally is a "perfect hash function", with the addition that you want some potentially manageable degree of randomness. In general the state of the art is that you use an algorithmic method that generates a mapping, and ...


1

I won't present an efficient algorithm. You may have a look at zero-supressed decision diagrams (ZSDD / ZDD) to enumerate all paths and represent every path in a compact form. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems by Shin-ichi Minato (NTT LSI Laboratories) since you now have a compact representation you can search for the ...


1

Shortage is not an issue. Economy works the way it is exactly because there is shortage. Without shortage, you cannot have an economy. If there is shortage of a highly desired item because its production rate is too low, people will bid up, raising the price, making the highly desirable item inaccessible to less wealthy players. At that point, you can ...


0

Use the "Polygon Method" described here: http://nrich.maths.org/1443 That method will give you nine rounds of five games each, with each team playing once per round (in your case of having 10 teams).


3

Virtual economies can be very hard to get right. Fortunately, by not having players selling items they've crafted/looted themselves you've simplified the problem somewhat: you can control supply, which will allow you to prevent the massive deflation in item values that can occur when they're produced in much higher volumes than they're consumed. A couple of ...


2

Without knowing much about the intended game; I'd give each attribute a weighting factor such that the price is the sum of each "attribute * weighting factor". For example, let's say (for weapons) you have the 4 attributes durability, slice damage, bash damage and speed. You might decide to assign weights like this: 3 coins per point of durability 10 ...


0

The basic approach would be; for each row: Load the entire row into "SIMD register 1" (MMX, SSE, AVX, Neon, whatever) Copy it into "SIMD register 2" Multiply "SIMD register 2" by 0.2 (pity it's not 25%...) Subtract "SIMD register 2" from "SIMD register 1" Shift "SIMD register 2" right by 1 element Add "SIMD register 2" to "SIMD register 1" Store "SIMD ...


1

Do you know where the majority of time is being spent? There could be all sorts of ways to speed this up. There's not enough code to know for sure, unless you're specifically asking only about the math. Computers are extremely good at math, so the problem is likely somewhere else than the actual computation of the data. For example, in one toolkit I know ...


3

This is the subset sum problem. The subset sum problem is NP-complete. In general the solution requires an exhaustive search, so the run time complexity is O(2^N) where N is the number of values in the set. Alternatively, if the desired sum S is small, dynamic programming can be used with a run time complexity of O(NS).


-1

Ugh, so many of these answers are missing the point. 1) What the hacker did had nothing to do with encryption. 2) What the hacker did had nothing to do with time (the time stamp, etc). What the hacker did was Publicly Sign the release document. When you PGP sign something (an e-mail, a word document, etc), you create a hash which is the sum of the hash of ...


0

I probably missed something regarding this case? I think the bit you are missing is a trusted entity. When you hash the file with the content you want to certify, you can show to the world that you are the owner of this document, without disclosing this document. This is all very well, but how can you prove you had this document at some specific time ...


0

I would like to offer you my solution for this by recognizing that: All appointments, single or re-occurring, have at least a date Under reasonable settings, re-occurring appointments often have a pattern In my solution, you will have for each appointment a start date and an end date. In the case of single appointment, you can leave the end date the same ...


1

In one of Tom Kyte's books he described a company with this exact problem. They did what you did and the performance was terrible. His recommendation was to store each instance of a recurring appointment in the database up to some point in the future. This solved all their performance problems with appointment searches. Yes, there may be hundreds of ...


4

It seems to me that your problem is in your first sentence: Our company implemented a calendar system a few months back with recurring appointments, using iCal strings to store the recurring appointment criteria. Having to scan all records to determine date ranges is simply not scalable. In essence, you're using your database as a flat file, so of ...


0

This is a different take on valenterry's answer. Here's how you would do it using PGP: Generate a public/private key pair. You keep the private key and you make sure it stays secret. You encrypt your idea with your public key: P(idea) You put P(idea) somewhere that is trusted(not by you, but in general) and will log the time. When you need to prove ...


2

There is, and in fact there are programs in real life that solve the halting problem for other problems all the time. They are part of the operating system you are running your computer on. Undecidability is a weird claim that only says that there isn't such a program that works for ALL other programs. One person correctly stated that the halting proof ...


20

It's possible to hash the data you wish to timestamp and turn it into a Bitcoin address. This is known as trusted timestamping. By making a small payment (a satoshi, or 0.00000001 BTC) to it, the payment is stored on the blockchain along with the address you paid to. Since only the hash is stored on the Bitcoin blockchain, no one can tell what data you ...


1

A very simple way to establish that you are the first one to publish something, without revealing who you are immediately but having the option to do this later: Publish it on a well known public source (there everyone can see that you published it) In this publication, add a line: Originally published on dd/mm/yyyy by the owner of xxx@gmail.com No need ...


37

In days of old, scientists would publish anagrams of their work to be able to say "I thought of this idea." (look at the 'history' and 'establishment of priority' sections) The thing is, they wanted to be able to take credit for it, but also give other scientists to publish their results if they had other ideas without building on the original idea. For ...


30

You can do that quite easy. If you have a plaintext text, secret key S and public key P you do S(text) and get the cipher. Now you can publish cipher and P but not S. Therefore, everyone can decrypt the cipher with P by doing P(cipher). If you now want to prove, that you are the one who created the cipher (and therefore the original text), you can either ...


4

Believe it or not, this problem is solvable in time O(n). First, let m be the median of the array. For a pair (x, y) that are next to each other, define the contribution of x from that pair to be: def contribution (x, y, m): if m < x: if x < y: return 0 elif y < m: return x - m else: ...


4

In order to attach your own license to code, you must own the copyright. Generally speaking, that means that it must be code that you have written. As an example, there are libraries out there already that provide some capability I want in my program. I have two choices: I can either live with the license that the library provides, or I can write my own ...


4

Your code needs to be released under the GPLv3 as you believe it is a derivative work of the algs4.jar implementation. Other projects utilizing your code will likely need to be released as GPLv3. Most larger applications just incorporate code from smaller projects, and treat the smaller code base as part of the larger. That will trigger the "viral" aspect ...


2

For date of birth and people in general, one will need to validate if that person exists and if thier address is valid. You can do both of these using 3rd party services that will: Validate if the person is a real person Validate and standardize address information You can do this yourself using algorithms that you have mentioned, but why re-invent the ...


0

n appears to be a free parameter in the equation for M^{n}_D. That is, this equation is defining N difference matrices for n=1:N, quoting from the paper: "The difference matrices M^{n}_D represent the N possibilities to match the point sequences onto each other."


1

You can store the value as a number if you have a datatype that can represent more than choicescount possible values. In the case of 340, this is the number 12,157,665,459,056,928,801 which is just under 64 bits. So, you could hypothetically store this in a Unit64 (docs). This isn't a good idea. As soon as you add another question, you will overflow ...


3

An int represents a fixed number of bits (usually 32 or 64). This is a measure of information content; it is fundamentally impossible to store more than this number of yes/no decisions in it. With three-way decisions the arithmetic becomes slightly more involved because they represent fractional numbers of bits (two three-way questions contain slightly more ...


2

While it would result is much more code, there's nothing inherently wrong with adding "nextLeft, nextDown, etc." to your keys. You'll be able to 100% ensure which key is next when navigating, so all of the guess work is gone. If you insist on a solution that uses solving, give each key an x offset and width, then when down is pressed, move to the key whose ...


0

This sort of spatial query is routinely handled by spatially enabled databases like mysql, postgres, oracle and sql server. I'm sure there are others I'm leaving out. The search then becomes a sql query using whatever geometry type is defined for your database. The particular topic you're interested in is called a nearest neighbor query. Check out this ...


-1

My guess learning about hashes is not the same of learning about random number generators (rng) but its very similar field in a way of knowing what differ a real random number from a pseudo-random and the quality about randomness. You probably know about xor-ing an image to hide any kind of data that you could extract from it, so, thats my guess. You need ...


1

In the classic version(k = 1, solve for best path), the key insight used is as follows. 1) In computing best path for cell (i, j) (best[i][j] is the cost of best path from top-left to (i, j)), we notice that this path could either come from it's left or upper neighbor. Thus we do (leaving aside corner cases for a moment) best[i][j] = min(best[i][j-1], ...


0

This is likely not the best way, but given there are no other answers, here is a way. The problem of finding the k-th optimal path is AFAIK not very well studied for matrices, but is quite common in graphs. In fact, Wikipedia has some examples of how it can be done in a weighted directed graph. Hence a solution that transforms you matrix to a graph and ...


1

My thought is to set the duplicate numbers to negative and then count only the positives It sounds like you're using negatives as an "isDuplicate" flag. This is a great example of the difference between competitive programming and professional programming. In a competitive environment, you're trying to optimize the time it takes to write the program. ...


2

It's possible that heuristics exist which improve your success rate, and if they exist, it's possible that you can program something that will find them. But for a game this small you're almost certainly better off programming a complete search and looking at the solutions that pop up. Then, when you compare what works and what doesn't, your human brain ...


1

I would consider using a standard keyword search with the nouns and verbs from your query as a way of generating a shortlist of possible results and then using an NLP parser (e.g. Stanford Core NLP) to preform a more detailed analysis on each contender in order to filter them to only exact matches. Assuming a reasonable corpus size and that the queries use ...


1

We're currently building a web service to solve problems like this (with very complex rules, including negative rules - things not happening). Unfortunately it's in private beta right now and we're capped on users. However, hopefully I can share the details on how to build a much simpler version (minus negation). As you outlined as your data grows it will ...


0

I created a partitioning program with space usage O(1) but running time O(N^2). You can find the source code here. In the comments there is a good explanation of the shuffling algorithm used. The key part of this program is the shuffling step, which is the step that takes O(N^2) time. Doc Brown asked "how can you shuffle N elements in less than O(N) ...


1

In the end the runtime [seconds] of the implementation of an algorithm is the deciding factor but the coefficients and the big-O notation help you in inventing efficient algorithms. The big-O notation tells you how the algorithm behaves if the number of inputs/.. n changes dramatically (orders of magnitude). You mostly use it in a relative sense, i.e. ...


0

Actually generating random non-overlapping groups in a random order would be a pain in the neck. For example, you'd selected a random "start"; then search existing groups to make sure start is usable and find the "highest possible end" for that start; then select a random "end" that's between "start" and "highest possible end". As long as you're selecting a ...


0

What matters is subjective. However, you are correct that the coefficients are not of the first order of significance. The coefficients are often ignored mostly because there isn't as much potential to improve an algorithm by worrying about them. Consequently, I wouldn't mind reworking code to get n^2 down to n*log(n). But going from 2n*log(n) to ...


4

Yes, constant factors matter very much in practice. Big-O notation is only the first step(albeit highly useful) in measuring the performance of an algorithm/program. An algorithm that takes only n^2 steps is certainly preferable to one that takes 2*n^2 steps, all things else being equal.


0

Welcome to the classic use case for Linear Programming and it's more straitlaced cousin, Constraint Programming. More specifically it's an example of a convex hull in the form of a combination. You'd use Linear Programming (possibly via constraint programming) to solve the problem of finding the area of a convex hull that fits your constraints. There are ...


1

Here is a simple improvement which will most probably meet your time constraints. For every divisor i of N, there is also a corresponding divisisor N/i. And to find all pairs of divisors, you need only to loop from 1 to the square root N. So try something along the lines of int maxD = (int)Math.sqrt(input); int sum=1; for(int i = 2; i <= ...


1

A much more efficient way would be to factorize the number into prime factors (using existing libraries, although I do not know one by heart). Say the factorization is a HashMap<Integer,Integer> factorization where each prime factor is mapped to its multiplicity, then one can compute your sum as follows. int N = 84684684; //your integer ...



Top 50 recent answers are included