103 - Stacking Boxes

[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]

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]

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

[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]

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]

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]

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

[Krzysztof Duleba]

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

[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.

[Krzysztof Duleba]

Have you tried to compile it at all with gcc? This code just can't work - i is undeclared in line 79th.

[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!

[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.

[jan-jun-john]

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

[sds1100]

구루. good

[alltoucher]

This is my code:

Code: Select all

Code was deleted!!!