103 - Stacking Boxes

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

Moderator: Board moderators

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

I think that many internal computations with shorts are actually computed in 32-bit ints (as the judge's platform is 32-bit), this makes computation in ints a bit faster -- you don't have to convert from shorts to ints and back.

I made a test on my machine (x86, linux, gcc 3.3.5) with the following two programs:

Code: Select all

signed short x=0,y=47,z;

int main(void) {
  for (int i=0; i<100000000; i++) {
    x++; z=x%y;
  }
  return 0;
}
and

Code: Select all

int x=0,y=47,z;

int main(void) {
  for (int i=0; i<100000000; i++) {
    x++; z=x%y;
  }
  return 0;
}
The runtimes for the first code:

Code: Select all

user    0m3.333s
user    0m3.345s
user    0m3.329s
And for the second code:

Code: Select all

user    0m3.162s
user    0m3.157s
user    0m3.172s
Thus it looks like ints may be faster after all :)

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Code: Select all

#include <cstdio>

int main(){
#ifdef INT
        int a, b, c, acc = 0;
#else
        short a, b, c, acc = 0;
#endif
        a = 81, b = 83, c = 7821;


        for(int i = 0; i < 100000000; ++i){
                acc = (acc + a * b) % c;
        }

#ifdef INT
        printf("%d\n", acc);
#else
        printf("%hd\n", acc);
#endif
}
Compiled with no optimization (like OJ does):

g++ 3.4.4:
shorts: 3.073s
ints: 3.127s

g++ 3.3.3:
shorts: 3.068s
ints: 3.118s

g++ 2.95:
shorts: 2.847s
ints: 3.078s

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

Your code on my machine (g++ 3.3.5 as mentioned above, no optimalizations either)
without #define INT:

Code: Select all

user    0m3.520s
user    0m3.505s
user    0m3.496s
with #define INT:

Code: Select all

user    0m3.473s
user    0m3.493s
user    0m3.494s
the same setup, g++ 3.4.4
without #define INT:

Code: Select all

user    0m3.431s
user    0m3.447s
user    0m3.439s
with #define INT:

Code: Select all

user    0m3.503s
user    0m3.499s
user    0m3.501s
Well, I think that the correct conclusion is that the difference between using ints and shorts is too small to be significant :D

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Do not post ACC code !

Post by Sedefcho »

Hardi,

Why do you post your code provided that it is Accepted ?!

That's not a good practice. You should remove it actually.

Posting ACC code makes no sense, just spoils the problem.

Regards !

wrcstar
New poster
Posts: 2
Joined: Mon Oct 03, 2005 7:09 pm

103 need help!

Post by wrcstar »

I got a WA in 103 task why? Please help me....


program Task103;

uses Strings;

var boxes : array [1..30] of array [1..10] of integer;
graph : array [1..30] of array [1..30] of integer;
max_chain : array [1..30] of integer;
current_chain: array [1..30] of integer;
box_count,dimension,code,max_chain_length,current_chain_length : integer;
i,j,k : integer;
str,tmp : string;


procedure dimension_bublesort(box : integer);
var i, j , tmp : integer;
begin
for i := 1 to dimension-1 do begin
for j := dimension downto i+1 do
if(boxes[box,j] < boxes[box,j-1])then begin
tmp := boxes[box,j];
boxes[box,j] := boxes[box,j-1];
boxes[box,j-1] := tmp;
end;
end;
end;

function nest_box(a, b : integer):boolean;
var i : integer;
begin
for i := 1 to dimension do
if(boxes[a,i] >= boxes[b,i])then begin
nest_box := false;
Exit;
end;
nest_box := true;
end;

procedure compare_length;
var i:integer;
begin
if(max_chain_length < current_chain_length) then begin
max_chain_length:=current_chain_length;
for i:=1 to current_chain_length do max_chain:=current_chain;
end;
end;

procedure find_chain(box:integer);
var i:integer;
begin
current_chain_length:=current_chain_length+1;
current_chain[current_chain_length]:=box;
for i:=1 to box_count do begin
if(graph[box,i] = 1) then begin
find_chain(i);
compare_length;
current_chain_length:=current_chain_length-1;
end;
end;
end;

begin
while not EoF(input) do begin
ReadLn(box_count,dimension);
for i:=1 to box_count do begin
ReadLn(str);
for j:=1 to dimension-1 do begin
k:=1; tmp:='';
while(str[k] <> ' ') do begin
tmp:=tmp + str[k];
k:=k + 1;
end;
Val(tmp,boxes[i,j],code);
Delete(str,1,k);
end;
Val(str,boxes[i,dimension],code);
end;


for i:=1 to box_count do dimension_bublesort(i);

for i:=1 to box_count do
for j:=1 to box_count do graph[i,j]:=0;
for i:=1 to box_count do
for j:=1 to box_count do
if(nest_box(i,j) = true) then graph[i,j]:=1
else graph[i,j]:=0;

max_chain_length:=0;
for i:=1 to box_count do begin
max_chain:=0;
current_chain:=0;
end;

for i:=1 to box_count do begin
current_chain_length:=0;
find_chain(i);
end;

WriteLn(max_chain_length);
for i:=1 to max_chain_length do begin
if(i <> max_chain_length) then Write(max_chain,' ')
else WriteLn(max_chain);
end;

end;
end.

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon »

this is a huge code .
it is better to post your procedure than code for better undestanding
for the reader.
and you also may get the reply from all the programmers of different
languages .

cyph1e
New poster
Posts: 2
Joined: Sun Jan 08, 2006 12:30 pm

103 CE

Post by cyph1e »

Hi, I get "Compiler Error" on this piece of code for problem 103. How do I track down these kinds of errors? I'm using the latest version of Dev-C++.

Code: Select all

removed
edit: Thank you Krzysztof Duleba
Last edited by cyph1e on Sun Jan 08, 2006 1:08 pm, edited 1 time in total.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

std::sort comes from <algorithm> and you don't include it.

jan-jun-john
New poster
Posts: 6
Joined: Tue Feb 07, 2006 6:26 pm
Location: Japan

103 Why CE ?

Post by jan-jun-john »

I suppose it gives right answer...
But, I got Compile Error.
Where should be corrected?
I need your help!

Code: Select all

Sorry, it was removed.
Last edited by jan-jun-john on Thu Feb 09, 2006 4:56 pm, edited 2 times in total.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Have you tried to compile it at all with gcc? This code just can't work - i is undeclared in line 79th.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

jan-jun-john
New poster
Posts: 6
Joined: Tue Feb 07, 2006 6:26 pm
Location: Japan

Ploblem is solved!

Post by jan-jun-john »

I use "VC++.net" as development environment .
Using this compiler, that code doesn't suggest "CompileError".
Has it been optimized underground?
I have no idea...

Anyway, I owe you a lot!
Changed like this...

Code: Select all

Sorry, it was removed.
Then, I got AC!

////////////////////////////////////////////////////////////////////////////////
I'm Japanese, and I started studying "C++" a week ago.
So, it is hard for me to read and to solve problems.
Thank you, nice programer Krzysztof Duleba!
Last edited by jan-jun-john on Thu Feb 09, 2006 4:55 pm, edited 1 time in total.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

You're welcome.

VC++ .NET is a pretty good compiler, but as you say, during optimization phase strange things do happen. You can try setting all the warnings on and using Debug instead of Release, but I don't know if it will change a thing.

Since you have AC now, please remove your code from the board.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

jan-jun-john
New poster
Posts: 6
Joined: Tue Feb 07, 2006 6:26 pm
Location: Japan

Post by jan-jun-john »

I removed my code from the board.
I greatly appreciate your kindness! :D

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

Post by sds1100 »

구루. good

alltoucher
New poster
Posts: 2
Joined: Sat Mar 11, 2006 8:39 pm
Contact:

Why my code get Compilation Error in 103 problem ???

Post by alltoucher »

This is my code:

Code: Select all

Code was deleted!!!
Last edited by alltoucher on Sun Mar 12, 2006 11:51 am, edited 2 times in total.

Post Reply

Return to “Volume 1 (100-199)”