11683 - Laser Sculpture

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

Moderator: Board moderators

Post Reply
Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

11683 - Laser Sculpture

Post by Yusif »

I got WA, please help!

Code: Select all

AC, thanks to Brian.
Last edited by Yusif on Thu Sep 12, 2013 10:32 am, edited 1 time in total.

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

Re: 11683 - Laser Sculpture

Post by brianfry713 »

Input:

Code: Select all

9 9
5 4 5 9 0 6 8 8 2
1 6
0 0 0 0 1 0
9 3
0 5 5
3 10
1 2 1 2 2 2 3 2 2 0
3 8
2 3 0 0 3 1 3 3
2 6
2 0 1 1 1 0
4 2
3 2
4 1
0
2 9
2 1 0 1 0 2 1 2 1
5 8
5 0 5 3 5 5 3 1
4 6
3 1 1 4 1 3
7 8
1 2 2 3 1 0 5 7
1 9
0 1 0 1 1 1 0 1 0
1 6
1 0 1 1 1 1
8 1
6
5 9
2 2 0 3 0 5 1 1 5
3 10
1 2 0 2 1 1 2 2 1 3
5 4
2 4 5 3
2 10
2 0 2 2 1 0 2 0 2 0
8 3
7 7 1
0 0
AC output:

Code: Select all

20
2
9
6
6
3
2
4
5
11
6
9
4
1
2
12
6
5
8
7
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11683 - Laser Sculpture

Post by uDebug »

These are some great test cases! Thanks for sharing brianfry713!
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 11683 - Laser Sculpture

Post by Repon kumar Roy »

My code is getting TLE ,,,, Any idea to improve my code ...

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>

using namespace std;

/*------- Constants---- */
#define MX 10001
#define ll long long
#define ull unsigned long long

/* -------Global Variables ------ */
ll x,y;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))


/*------ template functions ------ */
template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline T extended_euclid_returning_gcd(T a,T b){ T t,d; if(b==0){d = a;x=1;y=0;} else {extended_euclid_returning_gcd(b, a%b); t=x; x=y;y = t-(a*y/b);}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
ll power ( ll a, ll b){ ll x=1; while(b--) x*=a; return x;}

int final[MX],initial[MX];
int main()
{
    
    int hieght,col,i,flag;
    while (scanf("%d%d",&hieght,&col)==2) {
        if(hieght+col==0) break;
        for (i=0; i<col; i++) {
            scanf("%d",&final[i]);
            initial[i]=hieght;
        }
        flag=1;
        int start=0;
        while (flag) {
            flag=0;
            for(i=0;initial[i]==final[i] && i<col;i++);
            for (; i<col; i++) {
                if(initial[i]==final[i])break;
                else {
                    flag=1;
                    initial[i]--;
                }
            }
            start++;
        }
        printf("%d\n",start-1);
    }
    return 0;
}

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11683 - Laser Sculpture

Post by uDebug »

Repon kumar Roy wrote:Any idea to improve my code ...
It's possible to solve this problem in O(n) - instead of O(n^2).

Try to think of how to calculate the heights of the columns in one loop.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 11683 - Laser Sculpture

Post by Shahidul.CSE »

Getting Runtime Error for following code, what's the reason for RTE?

Code: Select all

#include <iostream>
#include <string.h>
#include <cstdio>
#include <stdio.h>
#include <cstring>
using namespace std;
int struc[10002][10002];
int main()
{
    int H, L, h, i, j, cnt;
    while(scanf("%d %d",&H, &L)!=EOF)
    {
        if(H==0 && L==0)
            break;
        for(i=0;i<L;i++)
        {
            scanf("%d",&h);
            for(j=H-1;j>=H-h;j--)
                struc[j][i]=1;
            for(;j>=0;j--)
                struc[j][i]=0;
        }

        cnt=0;
        for(i=0;i<H;i++)
        {
            for(j=0;j<L;j++)
            {
                if(struc[i][j]==0)
                {
                    cnt++;
                    while(struc[i][j]==0)
                        j++;
                }
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

robin_0
New poster
Posts: 7
Joined: Tue Apr 28, 2015 9:47 am

Re: 11683 - Laser Sculpture

Post by robin_0 »

@Sahidul.CSE
you have used a lot of memory my friend

int struc[10002][10002];

and again you'll get a TLE unless you upgrade your algorithm
:D :)

Post Reply

Return to “Volume 116 (11600-11699)”