Editorial for ARITHMETIC PROGRESSION

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

uses math;
const fi='';
maxn=100010;
var n,i,re,nn:longint;
a,b,l,r,d,c:array[0..maxn] of longint;
f:array[1..maxn,1..100] of longint;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
i:=l; j:=r; x:=a[(i+j) shr 1]; t:=d[(i+j) shr 1];
repeat
while (a[i]<x) or ((a[i]=x) and (d[i]<t)) do inc(i);
while (a[j]>x) or ((a[j]=x) and (d[j]>t)) do dec(j);
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=d[i]; d[i]:=d[j]; d[j]:=y;
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

procedure edit;
var i:longint;
begin
c[0]:=-maxlongint;
for i:=1 to n do
begin
if a[i]>c[nn] then
begin
r[nn]:=i-1;
inc(nn);
c[nn]:=a[i];
l[nn]:=i;
end;
b[d[i]]:=nn;
end;
r[nn]:=n;
end;

function bs(ll,rr,val:longint):longint;
var mid,i,l,r:longint;
begin
bs:=0; l:=ll; r:=rr;
while l<=r do
begin
mid:=(l+r) shr 1;
if d[mid]<val then l:=mid+1
else r:=mid-1;
end;
for i:=mid+1 downto mid-1 do
if (i>=ll) and (i<=rr) and (d[i]<val) then exit(d[i]);
end;

procedure pr;
var i,j,dif,x,y:longint;
begin
for i:=1 to n do
begin
x:=b[i];
for j:=x-1 downto 1 do
begin
dif:=c[x]-c[j];
if dif>100 then break
else
begin
y:=bs(l[j],r[j],i);
if y=0 then continue;
f[i,dif]:=max(f[i,dif],f[y,dif]+1);
re:=max(re,f[i,dif]);
end;
end;
end;
end;

begin
assign(input,fi); reset(input);
for i:=1 to n do
begin
end;
sort(1,n);
edit;
pr;
writeln(re+1);
close(input);
end.


#include <bits/stdc++.h>
#define X first
#define Y second
const int N = 100005;
const int oo = 1000000009;
const int lim = 100;
using namespace std;
int n, res, f[N], b[N];
pair<int, int> a[N], u;
int main()
{
scanf("%d", &n);
int i, j, pos, res = 0, v;
for(i=1; i<=n; i++) {
scanf("%d", &v);
a[i] = make_pair(v, i);
}
sort(a+1, a+n+1);

for(j=1; j<=lim; j++) {
pos = 0; for(i=1; i<=n; i++) f[i] = 1;
for(i=2; i<=n; i++) {
u = pair<int, int> (a[i].X - j, a[i].Y);
while (pos < n && a[pos + 1] <= u) pos++;
if (a[pos].X == u.X && a[pos].Y < u.Y)
f[i] = f[pos] + 1;
res = max(res, f[i]);
}
}
printf("%d", res);
return 0;
}


Code mẫu của RR

{\$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=100001;
hashkey=100003;
type
list=^node;
node=record
u:longint;
next:list;
end;
var
f1,f2:text;
kq,n:longint;
a:array[1..MAXN] of longint;
h:array[0..hashkey] of list;
d:array[1..MAXN,1..100] of longint;
procedure openF; inline;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
close(f1); close(f2);
end;
procedure inp; inline;
var
i:longint;
begin
for i:=1 to n do
end;
function find(x:longint):longint; inline;
var
p:list;
u:longint;
begin
p:=h[abs(x) mod hashkey];
while p<>nil do
begin
u:=p^.u; p:=p^.next;
if a[u]=x then exit(u);
end;
exit(0);
end;
procedure push(x:longint); inline;
var
p:list;
u,gt:longint;
begin
gt:=abs(a[x]) mod hashkey;
p:=h[gt];
while p<>nil do
begin
u:=p^.u;
if a[u]=a[x] then begin p^.u:=x; exit; end;
p:=p^.next;
end;
new(p); p^.u:=x; p^.next:=h[gt]; h[gt]:=p;
end;
procedure solve; inline;
var
i,csc,k:longint;
begin
kq:=1;
for csc:=1 to 100 do d[1,csc]:=1;
push(1);
for i:=2 to n do
for csc:=1 to 100 do
begin
k:=find(a[i]-csc);
if k>0 then d[i,csc]:=d[k,csc]+1
else d[i,csc]:=1;
push(i);
kq:=max(kq,d[i,csc]);
end;
end;
procedure ans; inline;
begin
writeln(f2,kq);
end;
begin
openF;
inp;
solve;
ans;
closeF;
end.


Code mẫu của hieult

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
//#include <conio.h>

//double const PI=4*atan(1);

using namespace std;

struct so{
int gt,tt;
};

bool cmp1(so A1,so A2){
return A1.gt<A2.gt;
}

bool cmp2(so A1,so A2){
return A1.tt<A2.tt;
}

int n,f[100011][102],g[10111111],tong,kq;
so A[111111];

int main(){
// freopen("LEM5.in","r",stdin);
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d",&A[i].gt);
A[i].tt = i;
}
sort(A+1,A+n+1,cmp1);
tong = A[1].gt; A[1].gt = 0;
// for(int i = 1;i<=n;i++) printf("%d ",A[i].gt);
for(int i = 1;i<n;i++){
if(A[i+1].gt-tong-A[i].gt>100)
tong+=A[i+1].gt-tong-A[i].gt-101;
A[i+1].gt-= tong;
}

sort(A+1,A+n+1,cmp2);
// for(int i = 1;i<=n;i++) printf("%d ",A[i].gt);

memset(g,0,sizeof(g));
kq = 0;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=100;j++){
if(A[i].gt-j>=0 &&g[A[i].gt-j]>0)
f[i][j] = f[g[A[i].gt-j]][j]+1;
else f[i][j] = 1;
kq = max(kq,f[i][j]);
// printf("%d\n",kq);
}
g[A[i].gt] = i;
}
printf("%d",kq);
// getch();
}


Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<map>
#include<vector>
#define MAXN   100100
#define MAXD   100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
int a[MAXN],pos[MAXN];
map<int,pair<vector<int>,int> > haveVal;
int f[MAXN][MAXD];
int n;
void init(void) {
scanf("%d",&n);
FOR(i,1,n) scanf("%d",&a[i]);
}
bool CompPos(const int &x,const int &y) {
return (a[x]<a[y]);
}
bool findVal(int &id,int val) {
while (id>=1 && a[pos[id]]>val) id--;
return (id>=1 && a[pos[id]]==val);
}
void prepare(void) {
FOR(i,1,n) pos[i]=i;
sort(pos+1,pos+n+1,CompPos);
FOR(i,1,n) haveVal[a[i]].fi.push_back(i);
for (map<int,pair<vector<int>,int> >::iterator it=haveVal.begin();it!=haveVal.end();it++) it->se.se=0;
FOR(i,1,n) {
int curPos=pos[i];
int prevPos=pos[i-1];
int id=i;
FOR(k,1,MAXD) {
}
}
}
int getLastPos(int i,int j) {
while (id<cur.size() && cur[id]<i) id++;
return (id==0?-1:cur[id-1]);
}
void optimize(void) {
int res=0;
FOR(i,1,n) FOR(j,1,MAXD) {
int k=getLastPos(i,j);
if (k<1) f[i][j]=1; else f[i][j]=f[k][j]+1;
res=max(res,f[i][j]);
}
printf("%d\n",res);
}
int main(void) {
init();
prepare();
optimize();
return 0;
}