11499 - Longest Increasing Sequence

[898989]

Can any body give me hints for this problem.

I stopped coding as I realized my order is big. I thought in trying all rectangles (each rectangle start at first row & end at last col), and for each rectangle I do a sliding window in Order (rectangle size). But I believe this is much.

Code: Select all

		for (int c1 = 0; c1 < m; ++c1) {
			for (int c2 = c1+1; c2 < m; ++c2) {
				int windowLastElement = 1000*1000*10;
				int startIdx = -1;
				
				// do sliding window
				for (int i = 0; i < n; ++i) {
					for (int j = c1; j <= c2; ++j) {
						
					}
				}
				
			}
		}

Thanks in advance.

[Leonid]

I know O(n^3) solution. But is it enough for given constraints?...

[Leonid]

I know O(n^3) solution. But is it enough for given constraints?...

I've just submitted O(n^3) solution and it is working fine in less than 1.5 sec.
Still I'm wondering if it possible to issue a O(n^2 * log(n))?

My idea is:
1. for each M(i, j) find the length of longest increasing sequence in row i starting at column index j: L(i, j). This can be done in O(n^2)
2. Then, consider each element M(i, j) in top-down, left-right order.
2.1 Keep track of the maximal lengths of longest increasing sequences for each M(i - k, j).
2.2 then for each element M(i - k, j) in down-top order starting at M(i, j) consider the maximal length LL of the longest sequence starting at M(i, j). LL <= L(i, j). In other words try to extend as many elements as you can in the sequence of length L(i, j) starting at M(i,j) to as far as you can upwards. This can be done in linear time O(n)

[898989]

Thanks so much for your reply. I got it AC.

I did not understand ur 2, 2.1, 2.2 points, BUT point 1 helped me to convert my N^4 to N^3

My idea was
1. PRECOMPUTE lis[j], which is the length of longest increasing seqeunce at row i (only), starting from j. -> O(N^3)
2. For each 2 column, assume ur new rectangle is n*(c2-c1+1). [as in my code (there were a bug)] --> O(N^2)
2.1 Do a sliding window (means iterate) and catch the largest number of row contiguous and are lis -> O(n) thx for ur precomputation
2.2 always maximize
3. display answer.

Thanks so much for your help

[Sanjary Rahman]

I am trying since last 3 days after this single problem....please please help me out!!! Why I'm getting WA??

Here's my Code:

int n,m;
int lis[605][605];
int Sequence[605][605];
int LIS_LIS()
{
for(int a=0;a<n;a++)
{
for(int b=0;b<m-1;b++)
{
int cn=1;
for(int c=b;c<m-1;c++)
{
if(Sequence[a][c]<Sequence[a][c+1]) cn++;
else break;
}
lis[a]=cn;
}
lis[a][m-1]=1;
}
int maxx=0,count,sn=0;
for(int j=0;j<m;j++)
{
count=1;sn=1;
for(int i=1;i<n;i++)
{
if(Sequence[j]>Sequence[i-1][j] && Sequence[j]>Sequence[i-1][j+lis[j]-1] && lis[j]==lis[i-1][j])
{
count++;
maxx=max(lis[i-1][j]*count,maxx);
}
else
{
maxx=max(lis[i-1][j]*count,maxx);
count = 1;
}
if(Sequence[j]>Sequence[i-1][j])
{
sn++;
maxx=max(sn,maxx);
}
else
{
maxx=max(sn,maxx);
sn = 1;
}
maxx=max(sn,maxx);
maxx=max(lis[i-1][j]*count,maxx);
}
}
return maxx;
}



int main() {
while(sf("%d %d",&n,&m)==2)
{
if(n==0 || m==0) break;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&Sequence[j]);
}
}
int res = LIS_LIS();
cout<<res<<endl;
}
return 0;
}

[brianfry713]

Post the full code, that won't compile without any includes. Also use the code blocks.

[Sanjary Rahman]

Post the full code, that won't compile without any includes. Also use the code blocks.

Sorry,,,, here is my full code....

Code: Select all

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>
#include<ctime>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

#define pf printf
#define sf scanf
int n,m;
int lis[605][605];
int Sequence[605][605];
int LIS_LIS()
{
    for(int a=0;a<n;a++)
    {
        for(int b=0;b<m-1;b++)
        {
            int cn=1;
            for(int c=b;c<m-1;c++)
            {
                if(Sequence[a][c]<Sequence[a][c+1]) cn++;
                else break;
            }
            lis[a][b]=cn;
        }
        lis[a][m-1]=1;
    }
    int maxx=0,count,sn=0;
    for(int j=0;j<m;j++)
    {
        count=1;sn=1;
        for(int i=1;i<n;i++)
        {
            if(Sequence[i][j]>Sequence[i-1][j] && Sequence[i][j]>Sequence[i-1][j+lis[i][j]-1] && lis[i][j]==lis[i-1][j])
            {
                count++;
                maxx=max(lis[i-1][j]*count,maxx);
            }
            else
            {
                maxx=max(lis[i-1][j]*count,maxx);
                count  = 1;
            }
            if(Sequence[i][j]>Sequence[i-1][j])
            {
                sn++;
                maxx=max(sn,maxx);
            }
            else
            {
                maxx=max(sn,maxx);
                sn  = 1;
            }
            maxx=max(sn,maxx);
            maxx=max(lis[i-1][j]*count,maxx);
        }
    }
    return maxx;
}



int main() {
    while(sf("%d %d",&n,&m)==2)
    {
        if(n==0 || m==0) break;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                sf("%d",&Sequence[i][j]);
            }
        }
        int res = LIS_LIS();
        cout<<res<<endl;
    }
    return 0;
}

[brianfry713]

Input:

Code: Select all

6 10
638804 630059 737788 -744162 -656196 -21999 368450 226310 -418400 -101966
-409778 -809356 -713256 338807 -768893 913229 118261 479565 273235 844540
-873133 848348 -697920 -805724 378204 -849751 -685990 -739601 -388928 -400357
-430699 -232698 -770299 -692912 23140 -426495 802515 -90984 799815 -615886
-675525 -92537 -425242 -388780 -236305 323291 41874 881956 320282 -684892
-756080 447149 -836545 -454000 -841149 -940916 213675 -527139 -163091 -657827
7 7
109475 819632 -769277 -349960 -89437 -966763 559056
-289623 -582648 883532 -864735 509536 12177 -101040
-167173 -945950 298341 -846892 -630842 542261 -882318
50039 -394313 -206041 626549 -663213 266821 -536543
-321040 -143249 -612908 -694140 -323618 -382185 -44099
586945 168478 32382 -185252 -896745 -84087 467439
612792 928090 -633601 -36956 -500435 664740 633578
9 1
-731315
-563813
-152461
62645
-419839
184326
-153109
561044
-619288
3 8
-313428 -102551 83376 -840102 1820 -748146 192281 -666007
-644891 -891807 801432 -514674 -446291 -832170 965796 570700
-650004 599373 -43151 -408152 -614516 393036 439387 448129
1 2
-704981 -948334
1 1
999803
7 3
600604 -114254 -67220
852458 -921974 266773
-275007 -296354 68205
210319 774781 753461
176115 862906 -379118
292913 -180246 212730
678397 -269784 169542
7 4
-689320 -543605 272505 -650045
-27519 789733 593229 -96558
390337 -521025 -646353 760220
74427 620421 -514788 -704502
206051 -787043 -412296 476937
389072 -549390 -902181 199410
270364 827975 -122193 -999421
4 6
738844 308197 495579 11349 -824423 -531941
318507 768807 888927 -291157 -234793 -757426
-530937 -642941 -619580 -45725 169984 -896104
167232 757688 -901742 73729 -274277 -803923
8 5
-975948 668372 -485908 538995 -292446
-747064 364617 -796868 781711 540194
188618 100217 826426 77544 809061
109058 837544 -204451 466118 -264611
-732751 -363899 356711 951908 -88786
454970 25636 636938 -831528 816201
-849550 -290050 -998003 -335458 -751056
-290448 434904 613561 430110 216614
0 0

AC output:

Code: Select all

4
5
4
4
1
1
4
4
4
4