10730 - Antiarithmetic?

[Per]

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]

[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.

[little joey]

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]

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]

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]

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[100000];
char seps[] = " :";
char *token;
int totalNumber;
int arr[10010];
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]

[mido]

You went for an n^3 algm there. Try to go for n^2log(n) one; that got me through.

[Morning]

Thanks.Got it

[Andrew Neitsch]

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]

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, else answer is yes 
            }
         }
      }

I received TLE and wrong answer by Online Judge several times.
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.

[misof]

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]

Thank you for your answer ^^.
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
Answer -> Yes

firth and third, fourth number is 2 < 3 < 5,
so it's a arithmetic progession, isn't it?
I'm so confusing.

[misof]

Thank you for your answer ^^.
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
Answer -> Yes

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.

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]

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]

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?