(Please forgive me for my poor English.)
First,use Hash to record ai
Then,enumerate i,j as the first and the second items in the arithmetic sequence.check if 2*a[i]-a[j] exists.If it exists,we stop it immediately because the arithmetic sequence has been found.Otherwise,we find the arithmetic as brute force and mark the longest arithmetic sequence.
At last,it's easy to restore the arithmetic sequence.
So we can solve it in O(n^2).

Edited by author 20.08.2021 13:43

Give some tests, please

In this problem, all the operations should be done on the SAME computer, but I could NOT understand this from the statement, until I read the forum.
This problem is quite easy: simple bruteforce could AC in short time, but I think this bug in statement have made this problem SEEMS hard (only 100+ ACed now).

Please, fix it.

Не подскажете 38-тест?

Damn, i used min(xa, xb) <= x_h <= max(xa, xb) and got WA5, then I wrote min(xa, xb) <= x_h && x_h <= max(xa, xb) and got AC

Similar to page scheduling. Used two sets to simulate the process. :)

Getting WA #9. My solution is bruteforce after dividing the lines

give me some tests
thanks.

The problem can be solved using brute force solution

Make difference array, where dif[i] = i - a[i]

Try
7 10
1 2
1 3
1 4
5 6
5 7
8 9
8 10
8 11
12 13
12 14
This test changed my solution totally. Hope it helps you:)

Can the mouse go under the furniture? I mean, can it's way cross the polygons?

Actually, you can solve it as a graph problem, where numbers 0, 1, ..., n are vertices, which connected like: 0-1, 1-2, ...

I was able to solve it just by computing matrix determinant. Nothing to do with graphs, just taking advantage of matrix sparsity.

WA #3: 1 1 -> 2
WA #5: 2 1 -> 3
WA #7: 5 3 -> 29
WA #8: 6 5 -> 63
WA #9: 5 1 -> 13

This is the case of a particularly small competition!

If the starting point A is a station but you go by feet, is the station a visited station. For example, what is the solution for the following:
100 101
3
0 0
0 10
1 0
1 2
2 3
0 0
0 0
1 0

If you have TL on test 21, 49 or 50 you should use gets. I get AC with 0.3 s.

Can you give me any hint or any tests?

Thanks in advance.

Well, here are some hints:
1. Use DFA. If you do'nt know what it is, visit this page http://en.wikipedia.org/wiki/Deterministic_finite_automaton (pay attention to the table of states)

2. use getc() instead of cin>>ch or cin.getch() or whatever you use (for C++/C only)

3. Try this:
3
outputoutputinputon

inputone

Edited by author 13.06.2007 17:36