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 » Tue Sep 10, 2013 8:36 am

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 » Wed Sep 11, 2013 12:34 am

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!

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

Re: 11683 - Laser Sculpture

Post by uDebug » Tue Dec 24, 2013 12:45 pm

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 » Wed Feb 19, 2014 10:22 pm

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;
}

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

Re: 11683 - Laser Sculpture

Post by uDebug » Thu Feb 20, 2014 7:08 am

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 » Mon May 18, 2015 7:56 pm

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 » Fri Sep 25, 2015 7:55 am

@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)”