amit taneja
Ranch Hand
Posts: 817
posted 11 years ago
=============================================================
Problem Statement
����
A sequence of integers
(a1, a2, a3, ..., an)
is called arithmetic if a2  a1 = a3  a2 = a4  a3 = ... In order to make the given sequence arithmetic, you are allowed to replace each element with a different integer value (no fractions allowed). Unfortunately, each such replacement has an associated cost of 1. Return the minimum cost required to make the given sequence arithmetic. If the given sequence is already arithmetic, return 0.
Definition
����
Class:
ArithmeticReplace
Method:
howMany
Parameters:
int[]
Returns:
int
Method signature:
int howMany(int[] seq)
(be sure your method is public)
����
Notes

An element can be replaced by a value less than 10000 or greater than 10000.
Constraints

seq will contain between 3 and 50 elements inclusive.

Each element of seq will be between 10000 and 10000 inclusive.
Examples
0)
����
{1,4,7,11}
Returns: 1
Replacing the 11 with a 10 we get an arithmetic sequence.
1)
����
{10,5,0,5,10,15}
Returns: 0
This sequence is already arithmetic.
2)
����
{157, 119, 15, 5, 25}
Returns: 2
Replacing the first two elements with 55 and 35 we get an arithmetic sequence.
3)
����
{1,2,4,7,11,16,22,29,37,46,56,67,79,92,106}
Returns: 13
4)
����
{1,100,10,40,2,200,71,250,99,103,325}
Returns: 7
===============================================
.............
we add solutions...
can anybody make it further correct...
coz we are able to find out the correct result by adding further code to that but that doesn't make the series in AP
see the question is asking that find out how many numbers we should add to make the series to be in AP .. even if we find the anwer we are not able to make the series in AP...
here is my code

import java.util.Arrays;
public class ArithmeticReplace {
int counter = 0;
public int howMany(int[] seq) {
Arrays.sort(seq);
System.out.println("length " + seq.length);
for (int i = 0; i < seq.length; i++)
System.out.print(seq[i] + " ");
int dif = 0;
System.out.println("diff " + dif);
int[] a = new int[seq.length  1];
for (int i = 0; i < seq.length  1; i++) {
// System.out.println("each diff " + (seq[i + 1]  seq[i]));
a[i] = seq[i + 1]  seq[i];
System.out.print(" " + a[i]);
}
System.out.println();
System.out.println("a length " + a.length);
Arrays.sort(a);
for (int i = 0; i < a.length; i++)
System.out.print(" " + a[i]);
int n = 1, k = 1, l = 0;
for (int i = 0; i < a.length  1; i++) {
if (a[i + 1] == a[i]) {
n++;
l = a[i];
} else {
if (n > k) {
k = n;
l = a[i];
}
n = 1;
}
}
System.out.println();
System.out.println("l " + l);
System.out.println("k " + k);
dif = l;
// seq.lengthk*2;
for (int i = 0; i < seq.length  1; i++) {
if (seq[i + 1]  seq[i] != dif) {
counter++;
}
}
// if (counter > 0)
// counter++;
return counter;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Autogenerated method stub
ArithmeticReplace ar = new ArithmeticReplace();
int k = ar.howMany(new int[] {1,100,10,40,2,200,71,250,99,103,325});
System.out.println("k>>>> " + k);
}
}

thanks
[ April 09, 2006: Message edited by: amit taneja ]
[ April 10, 2006: Message edited by: amit taneja ]
Problem Statement
����
A sequence of integers
(a1, a2, a3, ..., an)
is called arithmetic if a2  a1 = a3  a2 = a4  a3 = ... In order to make the given sequence arithmetic, you are allowed to replace each element with a different integer value (no fractions allowed). Unfortunately, each such replacement has an associated cost of 1. Return the minimum cost required to make the given sequence arithmetic. If the given sequence is already arithmetic, return 0.
Definition
����
Class:
ArithmeticReplace
Method:
howMany
Parameters:
int[]
Returns:
int
Method signature:
int howMany(int[] seq)
(be sure your method is public)
����
Notes

An element can be replaced by a value less than 10000 or greater than 10000.
Constraints

seq will contain between 3 and 50 elements inclusive.

Each element of seq will be between 10000 and 10000 inclusive.
Examples
0)
����
{1,4,7,11}
Returns: 1
Replacing the 11 with a 10 we get an arithmetic sequence.
1)
����
{10,5,0,5,10,15}
Returns: 0
This sequence is already arithmetic.
2)
����
{157, 119, 15, 5, 25}
Returns: 2
Replacing the first two elements with 55 and 35 we get an arithmetic sequence.
3)
����
{1,2,4,7,11,16,22,29,37,46,56,67,79,92,106}
Returns: 13
4)
����
{1,100,10,40,2,200,71,250,99,103,325}
Returns: 7
===============================================
.............
we add solutions...
can anybody make it further correct...
coz we are able to find out the correct result by adding further code to that but that doesn't make the series in AP
see the question is asking that find out how many numbers we should add to make the series to be in AP .. even if we find the anwer we are not able to make the series in AP...
here is my code

import java.util.Arrays;
public class ArithmeticReplace {
int counter = 0;
public int howMany(int[] seq) {
Arrays.sort(seq);
System.out.println("length " + seq.length);
for (int i = 0; i < seq.length; i++)
System.out.print(seq[i] + " ");
int dif = 0;
System.out.println("diff " + dif);
int[] a = new int[seq.length  1];
for (int i = 0; i < seq.length  1; i++) {
// System.out.println("each diff " + (seq[i + 1]  seq[i]));
a[i] = seq[i + 1]  seq[i];
System.out.print(" " + a[i]);
}
System.out.println();
System.out.println("a length " + a.length);
Arrays.sort(a);
for (int i = 0; i < a.length; i++)
System.out.print(" " + a[i]);
int n = 1, k = 1, l = 0;
for (int i = 0; i < a.length  1; i++) {
if (a[i + 1] == a[i]) {
n++;
l = a[i];
} else {
if (n > k) {
k = n;
l = a[i];
}
n = 1;
}
}
System.out.println();
System.out.println("l " + l);
System.out.println("k " + k);
dif = l;
// seq.lengthk*2;
for (int i = 0; i < seq.length  1; i++) {
if (seq[i + 1]  seq[i] != dif) {
counter++;
}
}
// if (counter > 0)
// counter++;
return counter;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Autogenerated method stub
ArithmeticReplace ar = new ArithmeticReplace();
int k = ar.howMany(new int[] {1,100,10,40,2,200,71,250,99,103,325});
System.out.println("k>>>> " + k);
}
}

thanks
[ April 09, 2006: Message edited by: amit taneja ]
[ April 10, 2006: Message edited by: amit taneja ]
Thanks and Regards, Amit Taneja
Ryan McGuire
Ranch Hand
Posts: 1143
9
Ryan McGuire
Ranch Hand
Posts: 1143
9
amit taneja
Ranch Hand
Posts: 817
posted 11 years ago
Well  I don't understand that sentence:
How can you find an anwer, which is not making the series in AP?
see the question is asking that find out how many numbers we should add to make the series to be in AP .. even if we find the anwer we are not able to make the series in AP...
How can you find an anwer, which is not making the series in AP?
amit taneja
Ranch Hand
Posts: 817
posted 11 years ago
the orginal problem is within the ================== lines in first post of this thread...
please read carefully and then try to understand what the question is saying ...
please read carefully and then try to understand what the question is saying ...
Thanks and Regards, Amit Taneja
amit taneja
Ranch Hand
Posts: 817
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
posted 11 years ago
So, rather than answering Ryan's question, you simply tried to delete the evidence? No good  we remember what it said earlier. You've asked several past questions from Google CodeJam problem sets which violated their copyright. Why not be honest about where this stuff comes from? If it's from one of their old problem sets, post a link to where it can be viewed. If it's from a new (current) problem set, then please don't post at all.
[amit]: see the question is asking that find out how many numbers we should add to make the series to be in AP
No, it asks how many numbers you should replace. You can make any sequence arithmetic if you replace enough numbers; the trick is to find the minimum required.
[amit]: see the question is asking that find out how many numbers we should add to make the series to be in AP
No, it asks how many numbers you should replace. You can make any sequence arithmetic if you replace enough numbers; the trick is to find the minimum required.
"I'm not back."  Bill Harding, Twister
Ryan McGuire
Ranch Hand
Posts: 1143
9
posted 11 years ago
I had to write the program just so I could see how they came up with 7 for the last example. Oh, I see now... the difference between consecutive terms is 25, starting at 75. So 100, 200, 250 and 325 stay, while the rest get replaced.
(Besides I needed an excuse to used my Mixed class for fractional numbers again. )
I have one algorithm. Has anyone else figure this out yet?
(Besides I needed an excuse to used my Mixed class for fractional numbers again. )
I have one algorithm. Has anyone else figure this out yet?
Ali Hussain
Ranch Hand
Posts: 211
posted 11 years ago
From the format of the problem statement, it seems to be taken from topcoder.com.
Originally posted by Ryan McGuire:
The problem statement isn't another copyrighted one that shouldn't be reproduced, is it?
From the format of the problem statement, it seems to be taken from topcoder.com.
 SCEA, SCJD, SCBCD, SCWCD, SCMAD, SCJP, ICAD (WebSphere), Lotus Principal CLP, Lotus CLP, Lotus CLS
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
posted 11 years ago
Ryan and Steve: yeah, I had made a quick solution similar to what Steve describes. There are various optimizations that can be made along the way, but it's still fundamentally an O(n^3) algorithm as far as I can tell. I don't think it's quite as inelegant or trivial as stave makes it sound, but it does feel like there ought to be some more clever solution possible. There's a certain temptation to apply an FFT or something to try to find the strongest underlying patterns more quickly. Which is probably overkill, but oh well. More to the point, I don't think it would actually work. But there's a lingering feeling that something similar might. Unfortunately, I don't see a specific avenue to pursue. So for now, I'll content myself with O(n^3), I guess.
"I'm not back."  Bill Harding, Twister
Ryan McGuire
Ranch Hand
Posts: 1143
9
posted 11 years ago
Rather than figuring out all the values in the modified sequence, I just figure out the slope and yintercept implied by each pair of points. If the slope is an integer (i.e. differenceBetweenTwoValues % distanceBetweenThem == 0) then I save that slope/intercept pair. The slope/intercept pair that's used between the most pairs is the one that would be used for the "repaired" sequence (if I bother to figure it out).
For example...
Original sequence: {20,24,29,32}
slope=4, intercept=20 is used between 3 pairs: 2024, 2432, and 2032.
slope=noninteger between 2029, so ignore it.
slope=5, intercept=19 is used between 1 pair : 2429
slope=3, intercept=23 is used between 1 pair : 2932
Since (4, 20) is the most popular pair, it would be used for the final sequence.
BUT... I don't even need to figure out what the new sequence is. Rather than comparing old values and new values, I can determine how many values would have to change with the following equation:
NumberOfReplacements = sequenceLength  (sqrt(8*Pairs + 1) + 1)/2
where "Pairs" is the number of pairs in the original sequence that used the most popular slope/intercept pair (3 in the example above).
Let's see... 8*3 = 24. 24+1 = 25. sqrt(25) = 5. 5+1=6. 6/2=3. 43=1. So the return value is 1. (I love the quadratic equation.)
Since I don't calculate the whole new sequence implied by each pair, my alg is only O(n^2).
[ April 20, 2006: Message edited by: Ryan McGuire ]
For example...
Original sequence: {20,24,29,32}
slope=4, intercept=20 is used between 3 pairs: 2024, 2432, and 2032.
slope=noninteger between 2029, so ignore it.
slope=5, intercept=19 is used between 1 pair : 2429
slope=3, intercept=23 is used between 1 pair : 2932
Since (4, 20) is the most popular pair, it would be used for the final sequence.
BUT... I don't even need to figure out what the new sequence is. Rather than comparing old values and new values, I can determine how many values would have to change with the following equation:
NumberOfReplacements = sequenceLength  (sqrt(8*Pairs + 1) + 1)/2
where "Pairs" is the number of pairs in the original sequence that used the most popular slope/intercept pair (3 in the example above).
Let's see... 8*3 = 24. 24+1 = 25. sqrt(25) = 5. 5+1=6. 6/2=3. 43=1. So the return value is 1. (I love the quadratic equation.)
Since I don't calculate the whole new sequence implied by each pair, my alg is only O(n^2).
[ April 20, 2006: Message edited by: Ryan McGuire ]
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
posted 11 years ago
Ah, nicely done. I had started down a similar route, but I was considering only slopes, not intercepts. When I saw this was insufficient, I jumped to considering all points, when I should have considered slope plus intercept. Seems obvious in retrospect.
The one advantage I can see for my solution is that it doesn't require any substantial memory or other storage, as I don't need to keep cumulative counts for a bunch of different slope/intercept pairs. In most cases this is a minor issue, as memory is cheap. But since the memory usage in your solution is O(n^2) (right?), in some situations it may be necessary to switch to a less memoryintensive algorithm. Though of course you could also use a database of some sort instead, ultimately relying on some filebased storage I assume.
Anyway, good job.
The one advantage I can see for my solution is that it doesn't require any substantial memory or other storage, as I don't need to keep cumulative counts for a bunch of different slope/intercept pairs. In most cases this is a minor issue, as memory is cheap. But since the memory usage in your solution is O(n^2) (right?), in some situations it may be necessary to switch to a less memoryintensive algorithm. Though of course you could also use a database of some sort instead, ultimately relying on some filebased storage I assume.
Anyway, good job.
"I'm not back."  Bill Harding, Twister
It is sorta covered in the JavaRanch Style Guide. 