|
Member 10566089 wrote: I can't find an algorithm that solves this problem in O(n). Do you have any idea?
You have not been told it is possible, you are asked if it is possible or not. If you don't find an algorithm, the answer is 'no'.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Show what you have done so far. We will not write it for you.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
int l, l_max, u_max, u;
int A[N+1] = l_max= l =1;
u_max= u =1;
int i;
for (i=2;i<N;i++)
{
if (A[i] >= A[u])
u = i;
else if (A[i] < A[l])
{
if (u-l > u_max-l_max)
{
l_max = l;
u_max = u;
}
l = u = i;
}
}
if (u-l > u_max - l_max)
{
l_max = l;
u_max = u;
}
printf("%d %d", l_max,u_max);
But doesn't work with arrays like {1,10,5,5,5,5,1,9}
public static void main(String[] args) {
int [] arr=
int N=arr.length;
LinkedList <Subarray> subarrays=new LinkedList<Subarray> ();
Subarray s=new Subarray();
s.setStart(0);
s.setEnd(0);
for (int i=1;i<N;i++)
{
if (arr[i] < arr[i-1])
{
s.setEnd(i-1);
subarrays.add(s);
s=new Subarray();
s.setStart(i);
s.setEnd(i);
}
}
s.setEnd(N-1);
subarrays.add(s);
Iterator<Subarray> iterator = subarrays.iterator();
s=iterator.next();
Subarray nxt;
while (iterator.hasNext()) {
nxt=iterator.next();
if (arr[nxt.getEnd()]>=arr[s.getEnd()] && arr[s.getStart()]<=arr[nxt.getStart()])
nxt.setStart(s.getStart());
s=nxt;
}
iterator = subarrays.iterator();
s=iterator.next();
while (iterator.hasNext())
{
nxt=iterator.next();
if ((nxt.getEnd()-nxt.getStart()) > (s.getEnd()-s.getStart())){
s=nxt;
}
}
System.out.print("+s.getStart()+""+s.getEnd());
}
}
But doesn't work with {2,15,6,10,3,20}
public static void main(String[] args) {
int [] input=
int max = input.length - 1;
int[] aux = new int[input.length];
for(int i = input.length; i>0; i--){
if(input[i-1] > input[max])
{
max = i - 1;
}
aux[i-1] = max;
}
int l = 0;
int u = 0;
max = 0;
int lMax = 0;
int uMax = 0;
for (int i=0;i<aux.length;i++)
System.out.print(aux[i]+" ");
for(int i = 0; i< input.length; i++){
System.out.println(""+input[i]+",l: "+l+",u: "+u);
if (input[i] >= input[l] && aux[l] >= i)
{
u = i;
}
else
{
if(u-l > max)
{
lMax = l;
uMax = u;
max = u-l;
}
l = i;
u = i;
}
}
if(u-l > max){
lMax = l;
uMax = u;
}
System.out.println("l "+l+" u "+u);
}
But doesn't work with {1,2,3,4,5,15,4,-1,18}
|
|
|
|
|
Why do you have 3 different programs ?
Are you rewriting a new program every time the previous one don't work ?
Advice: Take a sheet of paper and simulate how your program should behave and how variables evolve over execution. And validate that you find the right answer.
If the simulation don't endup with the answer, algorithm is wrong.
if the simulation is ok, use the debugger to check that the program conform to simulation, if not, it will help you to find the reason.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Yes, I wrote the code and discovered that there is a type of array for which the algorithm gives the wrong answer.
|
|
|
|
|
Hi,
SOLVED.
Thanks.
modified 12-Apr-17 15:00pm.
|
|
|
|
|
(Accounts payable and receivable) "Aging" has to do with "Invoice dates" and "Due Dates" and payment terms.
Your concept of "aging" makes no sense; particularly when you start talking in terms of "years".
And when you start using the wrong term for a given accounting concept, you are in for a lot of pain (through misunderstandings).
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Excuse my lack of understanding of the accounting "Aging" method but somehow my accounting person is calling it "Aging". I hope I was able to explain and communicate my requirement on what I'm trying to achieve. I would appreciate some help with this.
Thanks.
|
|
|
|
|
You might be "forecasting"; but nailing one small amount to a given month is meaningless unless it has some significance to it, like "Mother's Day".
If anything, the accounting person may also be "depreciating" or modeling the life cycle of a marketing campaign or product.
Maybe it's all on a "need to know" basis...
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
public static int LastIndexOf<T>(this IReadOnlyList<T> s, IReadOnlyList<T> t, int startIndex,
IEqualityComparer<T> comparer) where T : IEquatable<T>
{
Validate(s, t, startIndex);
if (t.Count == 0) return 0;
if (s.Count == 0 || s.Count < t.Count) return -1;
if (comparer == null) comparer = EqualityComparer<T>.Default;
if (t.Count == 1) return LastIndexOf(s, t[0], startIndex, comparer);
var table = BuildTable(t, comparer);
var i = 0;
while (startIndex - i >= 0)
{
if (comparer.Equals(t[t.Count - i - 1], s[startIndex - i]))
{
if (i == t.Count - 1)
return startIndex - t.Count + 1;
i++;
}
else
{
if (table[i] > -1)
{
startIndex -= i;
i = table[i];
}
else
{
startIndex--;
i = 0;
}
}
}
return -1;
}
Full source code can be seen here[^].
The method works like String.LastIndexOf which searches string from the last character. The BuildTable method is exactly same with normal KMP algorithm.
I'm not sure if this is the best solution though.
|
|
|
|
|
I would have just reversed the 2 strings and compared those.
(KMP: Keep Me Partying).
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
If y'all don't mind, I'd love some input on this idea I have laid out below and an algorithm/process to make it come to life.
When you were a child did you ever making up a language with your friend so that when you wrote messages to each other only you two would be able to understand it? It was always simple stuff like a = "1", b = "!", c = "+", and etc. Basically, I want to mimic the thought process used to create a made-up language, but on a more complicated level. I would like to create a learning agent that will find correlations between a set of number strings and a set of common English words, so that the number strings and English words can be translated to and from one another. For example:
The agent would take in a set of strings of numbers like this: 010001110100111111, 10011101110, and 0111100101100000. And a set of English words like this: "banana", "apple", and "pear".
After reviewing both groups of data, the agent could match the numbers/letters like this: a = 10, b = 0100, e = 01110, l = 0011, n = 101, p = 0111, and r = 0111111
So that when translated, the numbers from above are as follows: 0100011110100111111 = "bear", 10011101110 = "ape", and 101011100111100011 = "nepal". And, when translated the words from above are as follows: "banana" = 0100101011010110, "apple" = 100111011101101110, and "pear" = 011101110100111111.
What are your thoughts on this idea? I know it would be a complicated process, if it's even possible at all. Would it be beneficial to include letter frequency statistics? Or even weight the words, for example weight "the" higher than "cat" since "the" is used so often in conversation. I realize that inevitably there would most likely be some number-to-word translations that would just result in garbage, but I hope that I could create this agent in such a way that those results don't happen very often. Would supervised learning pertain to a problem like this?
Thank you for your input! Also, this is just for a personal project - no assignments or projects or anything. I just think it'd be cool.
|
|
|
|
|
Since everything in a computer is a bunch of 0s and 1s, this already exists. For example banana = 011000100110000101101110011000010110111001100001.
|
|
|
|
|
Hi Richard, thank you for the response! I know that it's possible to translate strings into binary, as you have above, but I would like to create a new and different kind of "language" to translate strings to. I hope that makes sense?
Basically what I would like to achieve is a program that takes a string, translates that string to binary (a string of 0s and 1s), and then translates that binary string into a new string so as to make the original message look totally different. It's really like a secret code in a way! (I'm really into spy movies, so I love stuff like this haha)
The program would work like this, for example:
1. "hello world" would be translated to binary "011010000110010101101100011011000110111100100000011101110110111101110
0100110110001100100"
2. the binary string is then translated to the new string using the new translation formula created with the intelligent agent, such that (for example) "0110..." = "goodbye space"
So, I want to see if I can create an intelligent agent that can find a new correlation between a long binary string and common English words. I hope that makes sense!
|
|
|
|
|
You're talking about a cipher.
Specifically, you're talking about a sort of steganography, the classic method of hiding a message in plain sight. This can apply to text or images or even audio.
There's your google keywords. Go forth and enjoy!
"There are three kinds of lies: lies, damned lies and statistics."
- Benjamin Disraeli
|
|
|
|
|
Sweet, thank you so much!
|
|
|
|
|
Sometimes you just "go"; it's an iterative process that might lead (nowhere?).
Seems I would be looking at "primitives" and "building blocks" (in this case).
Starting with "tokens".
Then cataloging "nouns", "verbs", prepositions, etc.
Can't very well translate "verbs" to "nouns", for example.
Perhaps some readings on compilers and interpreters; particularly the "lexical analysis" phase.
|
|
|
|
|
Thank you so much for your input! I'll definitely do some research on these points.
|
|
|
|
|
It depends what you mean by "intelligent agent". As it stands you cannot 'correlate' between two distinct phrases, even going via a binary array.
|
|
|
|
|
I think I understand what you're saying.
To clarify I've been researching if it's possible to use machine learning to find a plausible cipher that would translate binary strings to different English words. And I'm definitely still researching haha
So do you mean that it's impossible to do so? I understand if so, because most of the ideas that I've had thus far are essentially rule-based algorithms.
|
|
|
|
|
There are already many ciphers around, but they are all two-way. You cannot just feed a lot of binary strings in and expect proper words to come out.
|
|
|
|
|
Can someone send me a code with an implementation of the original version of Tiny Encryption Algorithm with simple encryption and decryption of texts. Thank you!
|
|
|
|
|
All you had to do is writing 'Tiny Encryption Algorithm' in Google...how sad...
Skipper: We'll fix it.
Alex: Fix it? How you gonna fix this?
Skipper: Grit, spit and a whole lotta duct tape.
|
|
|
|
|
No Repost !
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
I'm a student currently taking up a Thesis subject, and our Research Title is "An Investigative study of Tiny Encryption Algorithm Security and Encryption Level". We're searching for some programs with an implementation of TEA (original version) with simple encryption and decryption of texts in C/C++/PHP. Can you help me?
|
|
|
|
|