Page 1 of 1

11683 - Laser Sculpture

Posted: Tue Sep 10, 2013 8:36 am
by Yusif
I got WA, please help!

Code: Select all

AC, thanks to Brian.

Re: 11683 - Laser Sculpture

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

Re: 11683 - Laser Sculpture

Posted: Tue Dec 24, 2013 12:45 pm
by uDebug
These are some great test cases! Thanks for sharing brianfry713!

Re: 11683 - Laser Sculpture

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

Re: 11683 - Laser Sculpture

Posted: Thu Feb 20, 2014 7:08 am
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.

Re: 11683 - Laser Sculpture

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

Re: 11683 - Laser Sculpture

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