|
How can this be done?
Polynomial
Please, any assistance would be appreciated :/
modified 24-Mar-16 13:07pm.
|
|
|
|
|
Look up GF(2k) multiplication and division. Various implementations are also easily findable with google once you know that keyword.
|
|
|
|
|
Thank you! Found several pages of information. Now just have to study it 
|
|
|
|
|
Not sure what you want to do. Do you have more details ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Here is the algorithm I'm stuck on (and sorry it's not in proper pseudocode):
a = number to be converted
b = base to be converted from
c = base to be converted to
d = number of places in a (can use builtins such as len(str(a))
e = a - (a modulo (d * b)) to establish top digit
f = e floor divided by c to establish number of digits in
output number (works even if c > b)
g = e modulo c for first digit or output number
...and this is where I get stuck
Please help.
|
|
|
|
|
Help with what? What is the assignment?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Where did you find this ?
Google not working ?
What test dataset have you tried ?
What is your language ?
You are wrong at step e ...
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Hi!! I got some information related on this as below but I was wondering what sort of problems exactly does this Fiestel Cipher Algorithm solves? Any ideas and resources specifically on problems aim to solve would be appreciated. Cheers!!
Related infos but did not exactly get regarding problems aim to solve:
• A Feistel network is a symmetric structure used in the construction of block ciphers. A block cipher is a deterministic algorithm operating on fixed-length groups of bits, called blocks. Block ciphers are important elementary components in the design of many cryptographic protocols, and are widely used to implement encryption of bulk data.
• Data Encryption Standard (DES) was the result of a research project lead by Horst Cipher in IBM which resulted in a cipher known as Lucifer.
• As with most encryption schemes, DES expects two inputs - the plaintext to be encrypted and the secret key. The manner in which the plaintext is accepted, and the key arrangement used for encryption and decryption, both determine the type of cipher it is. DES is therefore a symmetric, 64 bit block cipher as it uses the same key for both encryption and decryption and only operates on 64 bit blocks of data at a time5 (be they plaintext or ciphertext).
|
|
|
|
|
It does not solve problems, it is an algorithm for encrypting and decrypting information to allow for secure storage. transmission etc.
|
|
|
|
|
But surely storing and transmitting data securely is a problem that needs to be solved, and an encryption algorithm is a solution to that problem?
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
|
Recently, a question on QA here about implementing a Rock-Scissors-Paper (RSP) game [^], to which I responded, left me with a curiosity to see how efficiently/tersely I could implement the possible analysis of the result of game play.
Which got me interested in the more general question of how, given a complex matrix of values and criteria which can be expressed in typical De Morgan table form can be ... possibly ... analyzed by code in such a way that either an optimal implementation of the matrix (code-generation) is generated, or, some set of heuristics is generated that the programmer can interpret and use to write optimized code.
To use the RSP possible outcomes as a simple example, and excluding the obvious condition that if two "players" select the same "object," the game is a tie:
assume 0 => Rock , 1 => Scissors, 2 => Paper
0 1 true ... rock breaks scissors => player1 wins
1 2 true
2 0 true
0 2 false ... paper covers rock => player1 loses
1 0 false
2 1 false
Of course, it's straightforward to write a simple switch statement, or if/else/ chain to "solve" this.
"Eyeballing" such a table, and looking for "patterns" in the outcomes, the mind may naturally think about various boolean operations like XOR, or using modulo some number, looking for "heuristics;" look for "threshold" values that can "prune" the possible comparison matrix.
Looking further than this simple example, one can think about the complexity of an airfare reservations system where there might be twenty different factors resulting in the selection of the final airfare price from some list of pricing levels.
And, of course, the programmer will (hopefully) have (or create somehow) some clear description of the "business rules" that describe the calculation process.
Let's say the outcome in the airfare scenario is a matrix of 1000 combinations (to be conservative). To our brains it's pretty easy to look at the criteria and use the business rules to select the criterion (like passenger Age) that may have the most "impact" on the matrix of combinations: i.e., you'd want to first "prune" the matrix by a switch statement using Age as the selector.
And, it would be logical, as you eyeball the criteria to consider those with the fewest number of "states" and use testing those in the "outer" switch statements to reduce computation.
However, an interesting complication may be that some criterion with only one, or a few states may be, in practice, rarely of predictive value: that, imho, takes you into the analysis of the criterion based on context (world-knowledge, statistics of use, etc.). I want to exclude that from this post.
Then there are the interactions of variables; in the airfare scenario a discount for early booking may not apply to the fare calculation for accompanied children between age 5~11, for example. While some variables may be inherently "binary," such as, perhaps, the need for a wheelchair, many variables may have a number of "levels," like, for example, age broken out by infant, child, teen, adult, senior.
I'm sure that Decision Table theory which has been around for so long has generated some algorithms/heuristics for analyzing complex boolean matrices and optimizing code.
Appreciate your thoughts !
«I want to stay as close to the edge as I can without going over. Out on the edge you see all kinds of things you can't see from the center» Kurt Vonnegut.
modified 1-Nov-15 2:33am.
|
|
|
|
|
Problems of this sort I usually approach by first doing some data / frequency analysis.
Then start "slicing" (usually) from the variable that has the least unique values for a given context.
e.g. If I wanted to select all males in California, would I first slice on "gender" or on "State" (of residence)? The point is, it's hard to generalize on strategies and it all "depends". (This also applies to complex SQL queries which the "optimizer" isn't getting quite right since the optimizer depends on an a particular "execution plan").
|
|
|
|
|
I don't use a standard way to deal with this problem.
My solution is always context dependent and language dependent. No heuristics will do it for me.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
I know the brute force method. can someone help me find a good solution!!
Input Format
The first line contains an integer, T, which is the number of test cases. T test cases follow, each having a structure as described below:
The first line contains two space-separated integers, R and C, indicating the number of rows and columns in the grid G, respectively.
This is followed by R lines, each with a string of C digits, which represent the grid G.
The following line contains two tab-separated integers, r and c, indicating the number of rows and columns in the pattern grid P.
This is followed by r lines, each with a string of c digits, which represent the pattern P.
Constraints
1≤T≤5
1≤R,r,C,c≤1000
1≤r≤R
1≤c≤C
example
INPUT
2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99
output
Yes
No
pls help!!
|
|
|
|
|
Member 12083453 wrote: I know the brute force method. can someone help me find a good solution!!
Solution to what problem ?
You describe the data used, but not the problem you try to solve.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
This is quite straightforward. Read the control numbers and extract the remaining data sets based on those numbers.
|
|
|
|
|
Your description of the data's internal structure does not match the data shown.
"The first line contains an integer, T, which is the number of test cases."
The data shows #2, but it appears you have four test cases.
You need to carefully re-edit the question so your description is clear and the data "matches."
What makes you think that this there is an algorithm possible here which is anything beyond a series of steps to read the data and process it into some kind of objects-in-code ?
Try posting this question on QA, but only post it when you have code to show, and specific questions.
«I want to stay as close to the edge as I can without going over. Out on the edge you see all kinds of things you can't see from the center» Kurt Vonnegut.
|
|
|
|
|
A very stupid question. I have a problem where the scenario is similar to playing a game with the character may buy/ sell magic items one at a time in the inventory store; and the magic item may generate e.g. MP according to the purchased item. Each item can be sold after buying that item (the player can't sell the item that he/she didn't purchase). Also each day the inventory store may sell an item (so player can only decide buy it or not). The last constraint is a fixed time (e.g. 10 days) the player/ character can keep the item purchased.
I search on the internet, it seems this can be solved by dynamic programming or greedy algorithm. But I can't figure out the solution because many examples on the internet e.g. activities selection are different from this one. For instance I understand the following one, but can't map that to the question I have.
http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/
A sample data for this question:
- the inventory store will sell items for 8 days.
- initially the player/ character keeps 10 coins.
- the player/ character can keep the item for 20 days.
For each day the item to be sold
day 1: the item costs 9 coins with 2 MP generated per day; the inventory store will buy it back with 1 coin.
day 2: the item costs 10 coins with 1 MP generated per day; the inventory store will buy it back with 9 coins.
day 3: the item costs 2 coins with 2 MP generated per day; the inventory store will buy it back with 1 coin.
day 4: the item costs 11 coins with 4 MP generated per day; the inventory store will buy it back with 7 coins.
day 5: no item available.
day 6: the item costs 12 coins with 3 MP generated per day; the inventory store will buy it back with 1 coin.
day 7: no item available.
day 8: the item costs 20 coins with 4 MP generated per day; the inventory will buy it back with 5 coin.
Can anyone suggest some hints (e.g. how to divide the problem into sub ones) or point me to the doc that may have better explanation regarding to this question?
Many thanks
|
|
|
|
|
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
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
