10730 - Antiarithmetic?

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10730 - Antiarithmetic?

Post by Per » Tue Sep 28, 2004 11:03 am

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?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Sep 28, 2004 12:37 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Sep 28, 2004 12:41 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

Post by Per » Tue Sep 28, 2004 3:17 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 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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Sep 28, 2004 5:46 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 :wink:

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

10730 - Antiarithmetic? Always get TLE

Post by Morning » Sat Oct 02, 2004 8:15 pm

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]
"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

Post by mido » Sat Oct 02, 2004 10:44 pm

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

Post by Morning » Sun Oct 03, 2004 7:36 am

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

Post by Andrew Neitsch » Mon Nov 01, 2004 10:34 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

Post by soyoja » Fri Jan 21, 2005 8:48 am

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.
I love Problem Solving!!! :) :) :)

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Fri Jan 21, 2005 3:00 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:

Post by soyoja » Mon Jan 24, 2005 4:22 am

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.
I love Problem Solving!!! :) :) :)

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Mon Jan 24, 2005 12:20 pm

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?
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 :lol: :lol:

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Sat Feb 12, 2005 11:38 pm

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:

Post by gvcormac » Mon Feb 14, 2005 1:30 am

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?

Post Reply

Return to “Volume 107 (10700-10799)”