## 10730 - Antiarithmetic?

Moderator: Board moderators

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

### 10730 - Antiarithmetic?

Judging from the runtimes on this problem, it seems that some people has managed to solve it in subquadratic time. Does anyone have a hint about how to do this, or are the good runtimes just due to better constant factors?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
[c]
state = true;
for(i=0;i<n && state;i++) {
for(j=1;i+j+j<n;j++) {
a = A;
b = A[i+j];
c = A[i+j+j];
if( (b - a)*(c-b) > 0 )
state = false;
}
}
[/c]

This is basically what I applied. It took 0.018 seconds.
Last edited by sohel on Tue Sep 28, 2004 12:41 pm, edited 1 time in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I have a similar question for you: judging from your runtime on 10727, you've found a way to calculate 'a' directly (O(N)) for any given 'b', or vv. I have been looking for that for some time, but gave up. Could you shed a light on that?
I haven't solved 10730 yet, but I'll think about it.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Sorry to disappoint you, but the fast runtime there is simply due to a better search algorithm, namely the Conjugated Gradient Method.

In the regular Gradient Method, we start in some point and reduce the problem to a one-dimensional problem by guessing that the optimum lies in the direction of the gradient and then solve the maximisation problem on this line. Then we reach a new point, and repeat the same process from there, and so on, until we feel that we are done. The Conjugated Gradient Method is similar, the only difference is that we choose the search direction in a smarter way based on the previous search direction. This gives much better convergence properties. For the one-dimensional searches one can usually (as in problem 10727) use Golden Ratio Search.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I see. My search algorithm stinks, but I was hoping you had found a direct formula.
It should be possible by taking the partial differentials of the total likelyhood with respect to a or b (something similar to the least squares method for regression). The exponential functions made it look hopeful, but I got stuck in the mathematics after writing down three pages of derivations... I still believe it can be done.

Re 10730: I don't think there is a subquadratic method, but a lot can be done with the runtime by taking the input restrictions into account. If your runtime is more than say 0.05 seconds, you have not fully understood the problem Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

### 10730 - Antiarithmetic? Always get TLE

anyone who can apply a more effective algorithm?
[cpp]
#include <iostream>
#include <cstring>
using namespace std;
int convert(char* str)
{
int sum = 0;
for(int i = 0;str != '\0' && str != ':';i++)
{
sum = sum * 10 + str - '0';
}
return sum;
}
int find(int *arr,int i,int j)
{
for(int k = 0;k <= j;k++)
{
if(arr - arr[j] == arr[j] - arr[k])
{
return 1;
}
}
return 0;
}
int judge(int *arr,int totalNumber)
{

for(int i = 0;i < totalNumber - 2;i++)
{
if(arr > totalNumber - 3) continue;
for(int j = i + 1;j < totalNumber - 1;j++)
{
if(2 * arr[j] - arr >= totalNumber || 2 * arr[j] - arr < 0) continue;
if(j > totalNumber / 2)
{
for(int k = j + 1;k < totalNumber;k++)
{
if(arr - arr[j] == arr[j] - arr[k])
{
return 1;
}
}
}
else
{
if(!find(arr,i,j)) return 1;
}
}
}
return 0;
}
int main()
{
char line;
char seps[] = " :";
char *token;
int totalNumber;
int arr;
while(cin.getline(line,100000))
{
token = strtok( line, seps );
totalNumber = convert(token);
if(totalNumber == 0) break;
for(int i = 0;i < totalNumber;i++)
{
token = strtok( NULL, seps );
arr = convert(token);
}
if(judge(arr,totalNumber)) cout << "no" << endl;
else cout << "yes" << endl;
}
return 0;
}
[/cpp]
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
You went for an n^3 algm there. Try to go for n^2log(n) one; that got me through.

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
Thanks.Got it
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
n^2 log n is way too much. I did this in the contest in three minutes, with 34 lines. I think that the problem setter did not intend for an n^2 log n algorithm to be acceptable.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

### 10730 Antiarithmatic, I can't understand the solution

Code: Select all

``````
// x[i] is input data
y[x[i]] = i;

for (i=0;i<n;i++) {
for (j=i+1;j<n;j++) {
k = x[j]+x[j]-x[i];
if (k < 0 || k >= n) continue;
if (y[k] > j) {
}
}
}

``````
Finally, I read the solution from waterloo contest site.
But In this code, I can't understand why this solution
could be accepted. Anyone explain this code for me.
Thx.
I love Problem Solving!!!   misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
There is a bug in the code you posted.

Code: Select all

``````      // x[i] is input data
y[x[i]] = i;

for (i=0;i<n;i++) {
for (j=i+1;j<n;j++) {
k = x[j]+x[j]-x[i];
if (k < 0 || k >= n) continue;
if (y[k] > j) {
answer is no // <-- here you reject the input
}
}
}
answer is yes // <-- only now you know that
``````
The idea: y[z] tells us where can we find z in the input permutation. Clearly the permutation is antiarithmetic iff there is no arithmetic subsequence of length 3. Try all possibilities for the first and the second element (x and x[j]). The difference is d = x[j] - x, therefore the third element should be k = x[j] + d = x[j] + x[j] - x. If k is out of bounds, there is no such sequence. Also, k has to occur further to the right than x[j] (i.e. elements x, x[j], k must appear in this order in the input). If it does, we found an arithmetic subsequence and the answer is NO.

After we checked all possibilities for the first two elements of the sequence and never found a sequence of length 3, the answer is YES.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
But I still have a question.

Arithmetic progression means just increase more than three number?
( Or it must increased by same interval? )

Why this test input is antiarithmetic?

6: 2 4 3 5 0 1

firth and third, fourth number is 2 < 3 < 5,
so it's a arithmetic progession, isn't it?
I'm so confusing.
I love Problem Solving!!!   misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
But I still have a question.

Arithmetic progression means just increase more than three number?
( Or it must increased by same interval? )

Why this test input is antiarithmetic?

6: 2 4 3 5 0 1

firth and third, fourth number is 2 < 3 < 5,
so it's a arithmetic progession, isn't it?
Arithmetic progression is a sequence of numbers in which the difference of each two consecutive numbers is the same. In other words, each arithmetic progression is uniquely determined by its first element a and its difference d. (The next elements are a+d, a+2d, etc.)

The sequence 2,3,5 is not arithmetic, as 3-2=1 but 5-3=2.
soyoja wrote:I'm so confusing.
Usually I try not to correct other posters' english, but now I couldn't resist... very probably you wanted to say confused  Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
I think this solution shouldn't be accepted due to TLE (50'000'000 is not what intents to fit). But it works for something like 0.443 sec (I don't remember). This is weak test data.

There is a better approach that works at N+N/2+N/3+N/4+...+0. Though, harmonic series diverge, these floored summands perform at about n*log(n) even for N much bigger than 10'000.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
Destination Goa wrote:I think this solution shouldn't be accepted due to TLE (50'000'000 is not what intents to fit). But it works for something like 0.443 sec (I don't remember). This is weak test data.

There is a better approach that works at N+N/2+N/3+N/4+...+0. Though, harmonic series diverge, these floored summands perform at about n*log(n) even for N much bigger than 10'000.
The judge runs on an 800Mhz computer. 50M operations in 1/2 sec sounds believable to
me. You can find the judges' data at the Waterloo site.

Can you expand on your better approach?