|
As a gamer, I'd ask myself what the optimal buying/selling moment is, and would try a naive approach in finding it. That means, look at what day today is, and see if selling today has an advantage over tomorrow, if tomorrow is a valid selling day. That prolly means coming up with a way to get a "score" for each day and calculating it. Can you express a MP in coins-value? If yes, then you could calculate the items "coins value for a given day".
It does sound a bit strange that I can keep the item longer than the store is opened, or that the store only sells a single item per day.
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
|
|
|
|
|
A tree that has N nodes is given. Nodes have weights between -1000 and 1000. That is asked from me is to find maximum of multiplication of subtree nodes. Do you have any idea/algorithm to solve this problem?
Example tree and solution are given here: http://i.stack.imgur.com/5k83f.jpg[^]
|
|
|
|
|
Calculate all the products in post-order, keep track of the max.
|
|
|
|
|
Can you explain an example ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
I am trying to find all subtrees of n-ary tree. Only BFS or DFS does not work. Because the tree is not binary. For example:
1
/ \
2 3
/ \ /|\
4 6 5 7 8
/ \
9 10
I want to show all subtrees including this one
1
/ \
2 3
\ |
6 7
How can I extract this subtree from original one?
|
|
|
|
|
That's not a normal definition of "subtree". See: Tree (data structure) Terminology[^]
In any case, you can make your own traversal algorithm, that at each node, returns the set of that node with all of the combinations of the descendents.
So at your node 3, it would return:
(3)
(3 (5))
(3 (5 (9)))
(3 (5 (10)))
(3 (7))
(3 (8))
The three forms including node 5 are from the same process applied recursively to that node.
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
So I have a data set comprising of 20000 data points. Each data point consists of 200 features representative of a discrete sampling over a series of features describing the data point which can represent one of 16 cases or an unknown case. The data is classified using a Neural Network. The first problem i'm having is I am wondering if there is an algorithm or method of deciding which of the 200 features is most important so I can reduce the amount of data I am working with. My second problem is that half the data collected refer to an unknown case so it is classified as 0, while for the other cases there may be 20 data sets referring to case 1 and 2500 referring to case 9. Is there an algorithm to deal with this skew in the data because training the network is essentially setting all the weights to point to the 0 case because the 0 case can be any value that isn't explicitly one of the other cases.
|
|
|
|
|
Not really an answer but: If you really want to learn about Machine Learning and Classification systems, check out the Free, introductory Machine Learning online course from Caltech![^]
It won't give you the code, but you'll learn lots about how to do it yourself!
If you try taking the course, I suggest using Octave (a free Matlab-compatible system)[^] for practicing and homework.
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
Sweet, I'll definately check it out I had taken a previous one on coursera but that's about the extent of my knowledge.
|
|
|
|
|
By using 9 numbers which are 1 to 9 you should find the number of ways to get N using multiplication and addition.
For example, if 100 is given, you would answer 7.
The reason is that there are 7 possible ways.
100 = 12+3×4+5+6+7×8+9
100 = 1+2×3+4+5+67+8+9
100 = 1×2+34+5+6×7+8+9
100 = 12+34+5×6+7+8+9
100 = 1×2×3+4+5+6+7+8×9
100 = 1+2+3+4+5+6+7+8×9
100 = 1×2×3×4+5+6+7×8+9
If this question is given to you, how would you start?
|
|
|
|
|
I would start to doubt the assignment, or the teacher. This is more like a Code Fight challenge, or a Hackathon activity. Not a programming assignment.
There is no way, a beginner (if asked at even a Bachelors level) would be able to create a program, that takes an input (100) and creates a list. Would be much complex, and would take a lot of time.
The sh*t I complain about
It's like there ain't a cloud in the sky and it's raining out - Eminem
~! Firewall !~
|
|
|
|
|
To start with, I would think about a brute force approach, and narrow it down by adding more rules.
Make your algorithm start with 123456789
In the next iteration, make your algorithm obtain: 12345678*9
Next obtain, 12345678+9
and 1234567*89, 1234567+89, 1234567*8*9, 1234567*8+9,... and so on
If you write an algorithm to fill this series, you can easily see that there are 3^8 possibilities! It might look long enough but it actually is not! I took "three" because there are three possible states: 1. No operation, 2. addition, 3. multiplication. And there are 8 ways you can insert the arithmetic symbols, which is always in-between two numbers.
Now, though the value 3^8 = 6561 is very less, computing huge values won't do any good. What other information do we have? There can't be a '-' sign! That's a good clue. Because, now we know for sure that the value can't reduce and computing values such as 12345*6789 can't be always feasible. So, if there is a number in the expression greater than the required number, from your example, if there is a number greater than 100 in the expression, you don't have to compute the expression to know it is not equal. Simply checking for the "greater than" would help.
Now, we have made the problem shorter, starting with an inefficient brute force algorithm! Now lets make it even shorter. Did you observe that if the entered number is 100, the first few elements in the series would definitely not hold? Let's create a function,
term f(int x) // returns the term, given the term number.
to which if you pass on the term-number you could automatically obtain the element in O(1) time. I call it O(1) because the moment you convert the base-10 number passed on as an integer to the function f to a base-3 number, you have your term! Now each digit of the newly obtained number either becomes + or * or "nothing", and with this we may construct our term. Let's now define rules to skip every term containing numbers greater than 100. To do this, lets speculate and find the term that is at the 1000'th place in the series. Depending on whether the series is greater or lesser, move forwards or backwards in the series (if you are willing to find at-least one solution, or switch to brute force if you want to find all the possible answers).
This is how I would start with the problem. And I would write a quick code and test my hypothesis, and add on more rules to it and make it even more optimized.
|
|
|
|
|
I see that numbers are in order is it allowed to change order ?
Like using 100 = 1×2+38+4+5+6×7+9
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
modified 8-Oct-15 18:01pm.
|
|
|
|
|
ppolymorphe wrote: is it allowed to change order I'd guess not, or else the original solution would have had more than 7 possibilities. If they can, then the possible solution space is over 300000 times bigger!
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
I do not know why order can not be changed. If we change order, mostly we get different result, because multiplication precedes summation. Of course, here are some options as X*1+2+3 or X*3+2+1 and so on. But if we mix multiplication and summation, then results are different. If we will follow standard rules then mentioned X examples are the same option/solution.
EDIT
I mean X*1+2+3 or X*1+3+2 not mixing multiplication with summation
modified 16-Oct-15 11:32am.
|
|
|
|
|
The issue comes with the adjacency "operator" where adjacent digits of the input sequence can be interpreted as a multi-digit number. In the original example there was:
100 = 12+34+5×6+7+8+9
where the 1 and 2 were combined into 12 and the 3 and 4 were combined into 34.
If the order could be rearranged, then there are more possible multi-digit numbers:
51, 72, 43, etc.
This increases the complexity of the problem space and the number of possible solutions.
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
I have been reading this:https://en.wikipedia.org/wiki/Dijkstra's_algorithm[^]. It says,
Dijkstra's original algorithm does not use a min-priority queue and runs in time O(|V|^2) (where |V| is the number of nodes). The idea of this algorithm is also given in (Leyzorek et al. 1957). The implementation based on a min-priority queue implemented by a Fibonacci heap and running in O(|E|+|V|\log|V|) (where |E| is the number of edges) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.
But whether or not we use a min-priority queue, shouldn't it be O(|V|^2) ?
Lets consider the situation where every node in the graph is connected to every other node. And each of this node is double ended (i.e., if there is a link from A to B then there is also a link from B to A). If we were to make the algorithm update the distance of every node (from the source) then shouldn't we obviously be checking |V| nodes for each node in the graph? We need to compulsorily check each node for every other node we visit!
Now following this algorithm from Wikipedia:
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // Initialization
3
4 create vertex set Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // Unknown distance from source to v
9 prev[v] ← UNDEFINED // Predecessor of v
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // The main loop
15 u ← Q.extract_min() // Remove and return best vertex
16 for each neighbor v of u: // only v that is still in Q
17 alt = dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist[], prev[]
We can obviously see that the loop continues until all nodes in Q are visited. During each visit, every neighbor of v is checked. So this clearly checks every other node in the graph for each node that's visited (if we assume that every node is connected to every other node). So now we have,
O(|V|^2)
instead of,
O(|E|+|V|log|V|)
Where did I go wrong?
|
|
|
|
|
I guess, by know I got to know the answer myself! The mistake I initially did was, I neglected the |E| in O(|E|+|V|log|V|). In the worst case, we can consider O(|E|) to be O(|V|^2). But still, we treat |E| as a separate variable because, |E| <= (|V|^2- |V|)/2. Though there is an upper bound for |E|, it is still independent of |V|. I have explained this well in my blog: http://www.creativitymaximized.com/2015/10/shortest-path-algorithm-elaborated.html[^]
|
|
|
|
|
Hello,I understand Shell Sort definition but I can not understand
this C# code:
public void shellSort()
{
int inner, outer;
long temp;
int h = 1;<br />
while(h <= nElems/3)
h = h*3 + 1;
while(h>0)<br />
{
for(outer=h; outer<nElems; outer++)
{
temp = theArray[outer];
inner = outer;
while(inner > h-1 && theArray[inner-h] >= temp)
{
theArray[inner] = theArray[inner-h];
inner -= h;
}
theArray[inner] = temp;
} // end for
h = (h-1) / 3;<br />
} // end while(h>0)
} // end shellSort()
please help me thx!
|
|
|
|
|
Member 11760977 wrote: but I can not understand
this C# code:
You'll have to give us a specific question if we're going to help you.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Member 11760977 wrote: but I can not understand this C# code:
Why don't you let the code show you how it works ?
Use the debugger ! You will see the code doing its stuff. Run the code step by step and inspect variables.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
|
Why do you give me this link ?
I know how it works !
My previous message was giving a way to see the program doing its stuff.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Quisiera saber quien tiene el algoritmo de Ford y Fulkerson , he estado buscando en varias paginas este algoritmo, pero no logro conseguir.Si alguien lo puede conseguir lo antes posible o hacerlo estaría muy agradecido.
|
|
|
|
|
This is an English language site. You'll get few responses for postings in other languages.
Bing Translator:
I would like to know who has the algorithm of Ford and Fulkerson, I've been searching several pages this algorithm, but I can not get. If someone can obtain as soon as possible or make it I would be very grateful.
Ford--Fulkerson_algorithm[^] on Wikipedia has an explanation as well as a Python implementation. For other languages, you're on your own...
(This "smells" a bit like homework. If so, you really need to do it yourself!)
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|