Size contest

This is a discussion on Size contest within the Contests Board forums, part of the Community Boards category; I recently stumbled across this problem: https://www.spoj.pl/problems/SUMITR/ and had a fun-yet-frustrating time solving it in C/C++ on the gcc compiler. ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    50

    Size contest

    I recently stumbled across this problem: https://www.spoj.pl/problems/SUMITR/ and had a fun-yet-frustrating time solving it in C/C++ on the gcc compiler. I got my code to 253 bytes when all whitespace is removed.

    The code I'm attaching doesn't have all whitespace removed for clarity purposes (the code gets accepted, so don't download if you don't want to be spoiled). I'm really curious if someone can come up with less hackish approaches or more hackish ones that can reduce the size even further.

    One problem is that you cannot read the contents of a test case using cin, because cin is slower than scanf on that site, so you have to use scanf, which requires a few extra characters.

    So basically, the contest is to get that problem accepted using C/C++ and their gcc compiler. Let's see who can do it using the fewest bytes!

    For clarity, I suggest you attach your code with whitespace and indentation.
    Attached Files Attached Files

  2. #2
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    The problem needs more explanation as there are at least 3 mutually exclusive ways of interpretting what sum is wanted.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    50
    I'll try.

    You're given a triangle of numbers, let's take the second example:
    1
    1 2
    4 1 2
    2 3 1 1

    You start from the first element of the first row (1). You can go to the element below it (1) or to the element below it and one step to the right (2). From these, you can do the same thing. Out of all possible such paths, choose the one with the sum of elements maximised. Output that sum.

    For the example, the path would be made up of the numbers 1 1 4 3, resulting in a sum of 1+1+4+3=9.
    Last edited by Sfel; 02-13-2009 at 11:10 PM. Reason: spelling

  4. #4
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Oh that's simple, now define the array in which the numbers are held. Then just find the largest element in each row.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,955
    Quote Originally Posted by abachler
    Oh that's simple, now define the array in which the numbers are held. Then just find the largest element in each row.
    The rules on how to traverse the path means that that will not work for all cases since it may come up with an invalid path.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    50
    Yes. For example:
    7
    1 4
    5 2 3

    You would select 7 + 4 + 5 = 16, but this is invalid.
    The correct paths are: 7 1 5, 7 1 2, 7 4 2, 7 4 3, with the max being 7 + 4 + 3 = 14

    To find out if your solution is good you can solve this first https://www.spoj.pl/problems/SUMTRIAN/ and reduce the file size after.

  7. #7
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Here's my try. I registered and it got accepted. 191 characters in total, but I bet there are better ways than this.

    Warning: this contains a spoiler. That's why I changed the text color to the background color. To actually view it, select it.

    I challenge everyone to do a better job .

    Code:
    
    #define Z(a)scanf("%d",&a);
    int r,b[101],i,j,m,o,p,z,y;main(){for(Z(r)r--;){for(y=i=!Z(m)i++<m;)for(j=b[i]=o=0;j++<i&&Z(z))b[j]=((p=b[j])>o?b[j]:o)+z,o=p,b[j]>y&&(y=b[j]);printf("%d\n",y);}}
    
    *edit*
    2 characters less now (so score 189):
    Code:
    
    #define Z(a)scanf("%d",&a);
    int r,b[101],i,j,m,o,p,z,y,x;main(){for(Z(r)r--;){for(y=i=!Z(m)i++<m;)for(j=b[i]=o=0;j++<i&&Z(z))x=b[j]=((p=b[j])>o?b[j]:o)+z,o=p,x>y&&(y=x);printf("%d\n",y);}}
    
    *edit*
    -4 for 185:
    Code:
    
    #define Z(a)scanf("%d",&a);
    r,b[101],i,j,m,o,p,z,y,x;main(){for(Z(r)r--;){for(y=i=!Z(m)i++<m;)for(j=b[i]=o=0;j++<i&&Z(z))x=b[j]=((p=b[j])>o?b[j]:o)+z,o=p,x>y&&(y=x);printf("%d\n",y);}}
    
    I even got it accepted without the "=0" but I'm not sure if that's legal or just luck... So I won't count this -2 :P
    Last edited by EVOEx; 02-21-2009 at 06:09 AM.

  8. #8
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    I've done this challenge on project euler before. First off, they have a small triangle in which you can really test all possibilities, but then higher up, there's another version of the same challenge with a 100 line triangle.

    Depending on whether or not they use a large triangle for testing purposes, the brute-force method might be feasible. But for a 100 line triangle, there are 2^99 possibilities. That's about 20 billion years to to test all paths even with 10^12 paths checked per second.

    There is an easy way to do this. Just takes some time to figure out. Starting at the top and always choosing the path with the highest number will not do.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  9. #9
    Registered User
    Join Date
    May 2006
    Posts
    50
    EVOEx: ~180 characters is really nice, guess that makes your solution the best so far . Good job.

    IceDane: I know the PE problem, but there was no size restriction there. I think the problem is rather trivial without a source size restriction, but with one it becomes rather interesting, since there are both math-related facts you can notice to reduce the size and various programming tricks.

  10. #10
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    Quote Originally Posted by Sfel View Post
    EVOEx: ~180 characters is really nice, guess that makes your solution the best so far . Good job.

    IceDane: I know the PE problem, but there was no size restriction there. I think the problem is rather trivial without a source size restriction, but with one it becomes rather interesting, since there are both math-related facts you can notice to reduce the size and various programming tricks.
    I think putting a size restriction on the code removes the interesting part from it, as it only results in code without any whitespace at all and so on. It's pretty much golfing. Someone posting some really different method of doing would be far more interesting, using some probability math or something similar(Just throwing ........ out there).
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  11. #11
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by IceDane View Post
    I think putting a size restriction on the code removes the interesting part from it, as it only results in code without any whitespace at all and so on. It's pretty much golfing. Someone posting some really different method of doing would be far more interesting, using some probability math or something similar(Just throwing ........ out there).
    Hmmm I don't like size restrictions too much either. I do, however, like golfing (in the programming sense), where the contest is actually to make it as small as possible. Unfortunately, there aren't many of these contests... So I just made it a challenge for myself to see how good I could do here.

  12. #12
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I had done it on Project Euler too.

    Anyway, I got it down to 255 bytes and accepted with a lousy 0.73 seconds but I'm happy.

    Code:
    #include <cstdio>
    #define R(x)scanf("%d",&x);
    int main(){int a[5000],n,m,k,i,j,p;R(n)while(n--){R(m)k=m*(m+1)/2;for(i=0;i!=k;++i)R(a[i])i=k-m;j=i- --m;while(m){for(p=0;p!=m;++p)a[j+p]+=a[i+p]>a[i+p+1]?a[i+p]:a[i+p+1];i=j;j-=--m;}printf("%d\n",a[0]);}}
    
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  13. #13
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by anon View Post
    I had done it on Project Euler too.

    Anyway, I got it down to 255 bytes and accepted with a lousy 0.73 seconds but I'm happy.

    Code:
    #include <cstdio>
    #define R(x)scanf("%d",&x);
    int main(){int a[5000],n,m,k,i,j,p;R(n)while(n--){R(m)k=m*(m+1)/2;for(i=0;i!=k;++i)R(a[i])i=k-m;j=i- --m;while(m){for(p=0;p!=m;++p)a[j+p]+=a[i+p]>a[i+p+1]?a[i+p]:a[i+p+1];i=j;j-=--m;}printf("%d\n",a[0]);}}
    
    Some hacks to make it even smaller:
    - Drop the include . (-18 chars)
    - Drop the "int" before main (-4 chars)
    - Move all variable declarations to outside the main function, then you can drop the int there (-4 chars)
    - Something I didn't even do in my code: Take on of the variables and remove it, together with the comma. Then, move it inside the parenthesis of main. Eg: main(m). This saves on comma (-1 char)

    So with just a few basic hacks, you can manage to save 27 chars .
    Also, the space you need for "- --m" can probably be removed by changing the "i=k-m" to "i=k-m--" and changing " --m" to "m".

    Just some funny tricks you can ignore if you don't give a damn, though :P
    Also, to use these tricks, you MUST compile it with a C compiler. It's NOT valid C++ .

  14. #14
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I have shortened it by 19 bytes without any tricks by simplifying the processing loop (one non-nested loop with a simple if condition to adjust one of the counters - the other counter just can go from x to y).

    These kinds of obfuscation contests are not really my cup of tea, though. So I did manage to squeeze it into the limit, fine.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  15. #15
    Registered User
    Join Date
    May 2006
    Posts
    50
    I'm not really a big fan of them either, I just thought this was a simple problem and it would be fun to try to squeeze into this limit. Doesn't serve any real purpose but...

    Also, it's a shame there aren't more contests here, of any kind. Here, even if you have no idea where to start, you can see what others did and learn from them. On online judge sites or project euler, there is little opportunity to learn things. You're either very good already in which case only a few problems will be of interest or just starting, in which case the learning curve will be really really steep.

    Not to mention that all PE problems and online judge problems are targeted more towards mathematics, rather than programming. At least this challenge requires a (little) more in-depth grasp of the language to be able to reduce the size. This section could offer what other sites don't.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Heapsort
    By xENGINEERx in forum C Programming
    Replies: 2
    Last Post: 03-30-2008, 07:17 PM
  2. Generic heapsort
    By Sephiroth1109 in forum C Programming
    Replies: 15
    Last Post: 12-07-2007, 05:14 PM
  3. Invalid conversion from 'void*' to 'BYTE' help
    By bikr692002 in forum C++ Programming
    Replies: 9
    Last Post: 02-22-2006, 10:27 AM
  4. An exercise in optimization
    By Prelude in forum Contests Board
    Replies: 10
    Last Post: 04-29-2005, 03:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21