10730  Antiarithmetic?
Moderator: Board moderators
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?
[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)*(cb) > 0 )
state = false;
}
}
[/c]
This is basically what I applied. It took 0.018 seconds.
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)*(cb) > 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
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 onedimensional 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 onedimensional searches one can usually (as in problem 10727) use Golden Ratio Search.
In the regular Gradient Method, we start in some point and reduce the problem to a onedimensional 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 onedimensional 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
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
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[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]
[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]
"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
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius

 New poster
 Posts: 43
 Joined: Fri Jun 25, 2004 9:37 pm

 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) {
answer is no, else answer is yes
}
}
}
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!!!
There is a bug in the code you posted.
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.
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
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.

 Experienced poster
 Posts: 106
 Joined: Sun Feb 17, 2002 2:00 am
 Location: Seoul, South Korea
 Contact:
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.
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.
I love Problem Solving!!!
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.)soyoja wrote: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?
The sequence 2,3,5 is not arithmetic, as 32=1 but 53=2.
Usually I try not to correct other posters' english, but now I couldn't resist... very probably you wanted to say confusedsoyoja wrote:I'm so confusing.

 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.
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 toDestination 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.
me. You can find the judges' data at the Waterloo site.
Can you expand on your better approach?