11790 - Murcia's Skyline

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

Moderator: Board moderators

anis_cuet016
New poster
Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

Re: 11790 - Murcia's Skyline

Post by anis_cuet016 » Sun Aug 08, 2010 1:41 pm

hey " suneast " dats ok ....... :D
Happy Coding ........ :wink:

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11790 - Murcia's Skyline

Post by arifcsecu » Mon Sep 06, 2010 9:22 pm

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.
Try to catch fish rather than asking for some fishes.

anis_cuet016
New poster
Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

Re: 11790 - Murcia's Skyline

Post by anis_cuet016 » Mon Sep 13, 2010 7:05 pm

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

User avatar
adnim
New poster
Posts: 3
Joined: Fri Jan 13, 2012 4:21 pm

Re: 11790 - Murcia's Skyline

Post by adnim » Tue Jan 17, 2012 8:30 pm

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. :P
clock ticks life away

VitezVojko
New poster
Posts: 7
Joined: Sun Apr 15, 2012 4:45 pm

11790 - Murcia's Skyline

Post by VitezVojko » Sun Apr 15, 2012 4:51 pm

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
Last edited by VitezVojko on Tue Apr 17, 2012 8:55 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11790 RTE

Post by brianfry713 » Tue Apr 17, 2012 1:09 am

Why did you comment out return 0 at the end?
Check input and AC output for thousands of problems on uDebug!

VitezVojko
New poster
Posts: 7
Joined: Sun Apr 15, 2012 4:45 pm

Re: 11790 RTE

Post by VitezVojko » Tue Apr 17, 2012 6:45 pm

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11790 RTE

Post by brianfry713 » Tue Apr 17, 2012 7:52 pm

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.
Check input and AC output for thousands of problems on uDebug!

VitezVojko
New poster
Posts: 7
Joined: Sun Apr 15, 2012 4:45 pm

Re: 11790 RTE

Post by VitezVojko » Tue Apr 17, 2012 8:54 pm

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
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11790 - Murcia's Skyline

Post by Mukit Chowdhury » Wed Mar 13, 2013 5:50 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11790 - Murcia's Skyline

Post by brianfry713 » Tue Jul 08, 2014 6:53 am

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).
Check input and AC output for thousands of problems on uDebug!

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

Re: 11790 - Murcia's Skyline

Post by ehsanulbigboss » Sun Dec 27, 2015 7:04 pm

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11790 - Murcia's Skyline(TLE)

Post by lighted » Sat Jul 22, 2017 8:43 pm

suneast wrote:
Thu May 20, 2010 4:38 pm
u can just asume that N is not larger than 10000 :D
I solved this PRO use O(N^2) BRUTE FORCE...
Mukit Chowdhury wrote:
Wed Mar 13, 2013 5:50 pm
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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11790 - Murcia's Skyline(TLE)

Post by Mukit Chowdhury » Wed Nov 01, 2017 7:11 pm

lighted wrote:
Sat Jul 22, 2017 8:43 pm
Number of buildings N is at most 1121.
So you did binary search on the size of array!!! :P

Post Reply

Return to “Volume 117 (11700-11799)”

Who is online

Users browsing this forum: No registered users and 1 guest