11790 - Murcia's Skyline

[anis_cuet016]

hey " suneast " dats ok .......
Happy Coding ........

[arifcsecu]

in dp branch , i know much about LIS LCS LDS.
To anis,
in this problem maximum length of the sequence is not necessary. So instead of maximum length, you have to find maximum sum LIS .
In the same loop , you can find LDS also.

If u need any more hints, just reply here.

[anis_cuet016]

hellow arifcsecu ...

thankz for the reply, i solved that problem already, can u discuss about this problem

using 0log(n) algorithm i.e using binary search for LIS/LDS can u find all the possible sub-sequence in the whole sequence .... i could only derive the longest one (which is actually common !!!!! ) but not the others .......

[adnim]

Well, there's one thing very easy to misunderstand.
Following is part of the statement :

We say the skyline is increasing if the longest increasing subsequence of buildings is bigger or equal than the longest decreasing subsequence of buildings; in other case, we say it is decreasing. A subsequence is a subset of the original sequence, in the same order. The length of a subsequence of buildings is the sum of the widths of its elements

The point is, here the longest increasing subsequence doesn't really mean what is always called LIS. Instead, it stand for the largest one of the sums of buildings' widths, whose heights form increasing sequences. Interestingly the sequence can be empty when all widths are negative.
So this problem is much more easy than LIS. while calculating, buildings with non-positive width can be skipped.
My AC code uses array of size 20000, took 0.084s with O(n^2).
Hope it helps.

[VitezVojko]

I really want to know, what on earth am i doing wrong, to get RTE. Please if anybody can help me

Code: Select all

//deleted code

[brianfry713]

Why did you comment out return 0 at the end?

[VitezVojko]

I saw somewhere, this was just a try.
with return 0 is also RTE.

[brianfry713]

Next time use the existing thread:
http://acm.uva.es/board/viewtopic.php?t=50432

In there you can see that the number of buildings might be up to 10000. You only allocate space for 100.

[VitezVojko]

Oh, thats the catch
That was confusing becouse in problem there werent bounds for n.
thank you alot and sorry that i created new post

[Mukit Chowdhury]

In this problem array of 1500 elements is enough... no need to check negative number ... My algo is of O(n*n) and Accepted in 0.068 second...

[brianfry713]

Input:

Code: Select all

100
6
5 8 4 5 6 4
5 9 7 8 4 6
6
1 3 10 7 7 3
7 3 9 4 7 3
3
7 1 8
3 8 1
4
1 9 4 8
6 9 5 3
1
4
4
10
10 10 4 10 2 5 1 6 6 10
5 9 1 5 2 4 4 6 3 2
9
10 7 5 6 4 9 6 8 7
10 10 2 3 1 10 3 4 6
3
8 10 2
9 6 6
6
3 7 5 9 9 6
1 7 8 2 2 2
5
6 2 4 5 9
4 2 1 4 2
2
6 1
8 10
4
10 4 6 3
5 1 3 6
9
8 9 8 3 3 1 6 7 1
2 4 8 5 9 1 3 3 10
3
3 2 9
7 9 6
4
4 9 1 4
1 1 3 8
5
2 8 3 3 1
9 7 1 2 9
3
2 4 5
3 1 10
6
9 7 9 7 6 2
4 8 8 8 6 5
7
7 5 10 5 6 1 10
7 5 2 10 1 4 9
6
6 1 10 10 2 1
4 1 1 5 4 6
4
7 1 4 4
9 8 3 5
7
3 9 4 9 10 10 6
10 1 7 8 5 2 7
3
7 6 3
7 6 2
7
8 4 6 10 8 6 8
2 1 10 9 9 6 4
8
10 4 6 7 3 9 8 5
2 7 2 5 7 10 7 1
9
2 3 6 1 7 9 4 6 4
2 10 4 8 1 2 6 5 2
5
10 3 2 7 5
8 9 7 9 9
4
2 1 1 7
7 1 1 1
9
3 4 1 1 6 4 2 4 10
5 8 6 4 9 4 1 3 1
5
10 7 1 7 3
8 9 6 9 4
2
8 1
2 5
3
7 9 9
4 8 5
4
3 8 2 4
8 1 6 7
7
7 10 2 9 8 6 9
2 3 1 7 8 6 3
9
10 2 4 2 10 9 8 4 5
1 1 3 3 4 8 8 5 9
2
8 2
4 7
2
7 2
3 7
5
6 2 5 4 8
3 5 10 6 4
8
4 9 6 2 4 1 3 10
8 7 9 3 9 2 4 6
3
10 10 9
7 4 4
2
3 8
1 8
2
10 9
6 8
1
7
2
4
3 7 3 6
8 4 10 5
8
1 2 4 9 10 9 8 3
7 1 9 10 6 5 7 3
4
5 6 6 1
4 5 6 4
5
6 1 9 6 6
4 1 6 6 2
8
1 10 5 10 2 9 3 7
5 7 4 2 7 6 6 7
9
2 9 6 5 7 7 3 7 3
5 3 3 10 3 7 3 9 7
8
6 10 9 8 10 6 7 7
4 2 9 6 9 8 3 10
1
2
9
7
8 4 7 1 4 7 10
10 3 7 5 5 10 8
3
7 1 7
5 5 9
7
6 9 4 4 7 2 4
4 6 9 1 10 1 4
9
1 10 10 8 10 5 10 10 4
3 6 1 3 7 5 3 3 5
6
5 9 9 9 1 5
2 5 10 5 9 10
2
3 4
8 8
1
9
5
1
1
6
4
1 1 8 2
4 4 8 3
8
10 10 2 3 8 5 7 5
7 1 8 7 1 3 5 7
8
9 1 6 6 10 3 9 1
1 3 9 6 5 9 4 7
5
2 3 7 9 9
3 2 7 4 3
4
10 2 1 5
6 8 8 7
5
4 10 6 8 3
10 7 10 3 1
1
7
4
10
2 3 2 10 2 1 3 9 1 10
8 7 4 10 2 3 7 2 8 3
3
5 1 1
5 3 6
2
3 1
4 10
7
8 5 2 8 5 7 10
6 5 3 3 3 6 10
8
5 3 10 10 1 10 8 6
5 4 1 8 10 5 2 3
8
2 7 4 4 9 2 7 2
1 8 5 2 8 7 9 9
7
8 7 2 9 7 2 8
3 7 8 4 9 4 8
6
4 9 10 7 9 5
7 2 7 10 2 2
1
5
4
7
1 4 5 4 10 9 5
4 6 6 8 5 4 9
8
4 10 3 2 6 9 2 8
1 6 7 5 6 10 6 8
1
8
4
8
2 3 4 9 7 7 9 6
2 10 4 8 1 2 8 9
4
2 3 1 8
5 7 5 7
10
6 8 9 7 3 10 7 7 1 7
2 9 6 3 1 3 6 3 10 6
9
2 7 3 4 8 9 6 5 10
1 3 1 10 9 10 8 4 6
9
9 7 6 2 8 10 2 3 2
1 4 9 3 4 3 1 8 9
6
5 1 5 3 1 1
4 5 7 4 5 8
4
7 1 3 7
9 1 5 4
9
4 7 9 1 9 3 9 9 6
5 9 4 4 5 5 5 3 6
3
5 2 2
3 9 4
10
9 6 8 7 8 9 7 6 9 10
1 5 5 3 6 7 9 8 4 5
6
6 4 4 3 2 5
10 4 1 10 9 7
1
10
8
8
9 5 2 5 6 3 10 8
6 7 1 7 5 6 9 6
3
1 9 7
4 3 4
7
3 9 5 6 6 3 8
2 8 2 5 2 5 4
4
2 9 8 7
10 2 10 3
7
3 5 3 6 5 1 4
2 5 1 9 6 9 6
6
9 4 6 8 5 3
5 4 9 1 4 7
4
2 2 3 4
2 2 7 4
8
10 4 5 2 2 1 5 8
6 3 10 10 8 5 9 4
7
10 3 10 5 5 9 3
3 9 10 7 1 3 1
8
3 5 3 1 1 3 7 5
7 10 10 5 10 4 7 5

AC output:

Code: Select all

Case 1. Decreasing (23). Increasing (19).
Case 2. Increasing (19). Decreasing (19).
Case 3. Decreasing (11). Increasing (9).
Case 4. Increasing (15). Decreasing (14).
Case 5. Increasing (4). Decreasing (4).
Case 6. Decreasing (17). Increasing (14).
Case 7. Decreasing (30). Increasing (20).
Case 8. Increasing (15). Decreasing (15).
Case 9. Decreasing (15). Increasing (11).
Case 10. Increasing (9). Decreasing (8).
Case 11. Decreasing (18). Increasing (10).
Case 12. Decreasing (14). Increasing (6).
Case 13. Decreasing (31). Increasing (15).
Case 14. Decreasing (16). Increasing (15).
Case 15. Increasing (11). Decreasing (9).
Case 16. Decreasing (18). Increasing (16).
Case 17. Increasing (14). Decreasing (10).
Case 18. Decreasing (27). Increasing (16).
Case 19. Decreasing (21). Increasing (20).
Case 20. Decreasing (15). Increasing (9).
Case 21. Decreasing (17). Increasing (13).
Case 22. Increasing (30). Decreasing (15).
Case 23. Decreasing (15). Increasing (7).
Case 24. Decreasing (24). Increasing (20).
Case 25. Increasing (24). Decreasing (20).
Case 26. Increasing (23). Decreasing (18).
Case 27. Decreasing (26). Increasing (18).
Case 28. Increasing (8). Decreasing (8).
Case 29. Increasing (23). Decreasing (14).
Case 30. Decreasing (23). Increasing (15).
Case 31. Decreasing (7). Increasing (5).
Case 32. Increasing (12). Decreasing (8).
Case 33. Increasing (15). Decreasing (14).
Case 34. Decreasing (24). Increasing (13).
Case 35. Decreasing (29). Increasing (17).
Case 36. Decreasing (11). Increasing (7).
Case 37. Decreasing (10). Increasing (7).
Case 38. Increasing (19). Decreasing (19).
Case 39. Decreasing (29). Increasing (23).
Case 40. Decreasing (11). Increasing (7).
Case 41. Increasing (9). Decreasing (8).
Case 42. Decreasing (14). Increasing (8).
Case 43. Increasing (2). Decreasing (2).
Case 44. Increasing (15). Decreasing (14).
Case 45. Increasing (33). Decreasing (21).
Case 46. Increasing (10). Decreasing (10).
Case 47. Decreasing (12). Increasing (10).
Case 48. Increasing (25). Decreasing (20).
Case 49. Increasing (24). Decreasing (23).
Case 50. Decreasing (27). Increasing (22).
Case 51. Increasing (9). Decreasing (9).
Case 52. Increasing (28). Decreasing (22).
Case 53. Increasing (14). Decreasing (10).
Case 54. Decreasing (20). Increasing (19).
Case 55. Decreasing (19). Increasing (13).
Case 56. Decreasing (20). Increasing (19).
Case 57. Increasing (16). Decreasing (8).
Case 58. Increasing (5). Decreasing (5).
Case 59. Increasing (6). Decreasing (6).
Case 60. Increasing (12). Decreasing (11).
Case 61. Increasing (23). Decreasing (20).
Case 62. Decreasing (26). Increasing (17).
Case 63. Increasing (16). Decreasing (7).
Case 64. Decreasing (22). Increasing (15).
Case 65. Increasing (23). Decreasing (18).
Case 66. Increasing (4). Decreasing (4).
Case 67. Increasing (25). Decreasing (25).
Case 68. Decreasing (11). Increasing (6).
Case 69. Decreasing (14). Increasing (10).
Case 70. Increasing (22). Decreasing (14).
Case 71. Decreasing (19). Increasing (15).
Case 72. Decreasing (26). Increasing (17).
Case 73. Increasing (25). Decreasing (18).
Case 74. Increasing (19). Decreasing (19).
Case 75. Increasing (4). Decreasing (4).
Case 76. Increasing (21). Decreasing (18).
Case 77. Decreasing (24). Increasing (23).
Case 78. Increasing (4). Decreasing (4).
Case 79. Increasing (26). Decreasing (19).
Case 80. Increasing (19). Decreasing (12).
Case 81. Decreasing (25). Increasing (20).
Case 82. Increasing (37). Decreasing (22).
Case 83. Decreasing (31). Increasing (16).
Case 84. Decreasing (19). Increasing (12).
Case 85. Decreasing (14). Increasing (10).
Case 86. Increasing (19). Decreasing (15).
Case 87. Decreasing (12). Increasing (9).
Case 88. Increasing (26). Decreasing (24).
Case 89. Decreasing (33). Increasing (17).
Case 90. Increasing (8). Decreasing (8).
Case 91. Increasing (22). Decreasing (19).
Case 92. Increasing (8). Decreasing (7).
Case 93. Decreasing (18). Increasing (13).
Case 94. Increasing (20). Decreasing (15).
Case 95. Decreasing (24). Increasing (16).
Case 96. Decreasing (25). Increasing (14).
Case 97. Increasing (13). Decreasing (7).
Case 98. Decreasing (31). Increasing (23).
Case 99. Increasing (19). Decreasing (18).
Case 100. Decreasing (30). Increasing (24).

[ehsanulbigboss]

Passes all input data provided by Brian Fry, but still WA!

Code: Select all

#include <bits/stdc++.h>
using namespace std;

int n, ans[2000];

int main()
{
    int test, t=0;

//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    scanf("%d", &test);
    while (test--)
    {
        scanf("%d", &n);

        vector <int> wd(n), hi(n), lis(n);
        for (int i=0 ; i<n ; i++) scanf("%d", &hi[i]), lis[i] = 1;
        for (int i=0 ; i<n ; i++) scanf("%d", &wd[i]), ans[i] = wd[i];

        int inc = 0;
        for (int i=0 ; i<n ; i++)
        {
            for (int j=0 ; j<i ; j++)
            {
                if (hi[j] < hi[i])
                {
                    if (lis[i] < lis[j] + 1 && ans[i] < ans[j] + wd[i]) lis[i] = lis[j] + 1, ans[i] = ans[j] + wd[i];
                    else if (lis[i] == lis[j] + 1 && ans[j] + wd[i] > ans[i]) ans[i] = ans[j] + wd[i];
                }
            }
            inc = max(ans[i], inc);
        }

        int dec = 0;
        reverse(hi.begin(), hi.end());
        reverse(wd.begin(), wd.end());
        for (int i=0 ; i<n ; i++) lis[i] = 1, ans[i] = wd[i];

        for (int i=0 ; i<n ; i++)
        {
            for (int j=0 ; j<i ; j++)
            {
                if (hi[j] < hi[i])
                {
                    if (lis[i] < lis[j] + 1 && ans[i] < ans[j] + wd[i]) lis[i] = lis[j] + 1, ans[i] = ans[j] + wd[i];
                    else if (lis[i] == lis[j] + 1 && ans[j] + wd[i] > ans[i]) ans[i] = ans[j] + wd[i];
                }
            }
            dec = max(ans[i], dec);
        }

        if (inc >= dec) printf("Case %d. Increasing (%d). Decreasing (%d).\n", ++t, inc, dec);
        else printf("Case %d. Decreasing (%d). Increasing (%d).\n", ++t, dec, inc);
    }
    return 0;
}

[lighted]

u can just asume that N is not larger than 10000
I solved this PRO use O(N^2) BRUTE FORCE...

In this problem array of 1500 elements is enough... no need to check negative number ... My algo is of O(n*n) and Accepted in 0.068 second...

Number of buildings N is at most 1121.

[Mukit Chowdhury]

Number of buildings N is at most 1121.

So you did binary search on the size of array!!!