USACO - Silver-Ants

Ovo je samo za one koji su radili ili rade Usaco.
Radio sam Silver diviziju i imam mali problem oko zadatka ants. Naime, ideja mi je dobra (znam jer se poklapa sa njihovom zvanicnom), ali nikako ne mogu da nadjem gresku zasto mi ne prolazi za sve test primere. Ostala dva su mi u potpunosti tacna i ovo mi je sansa da predjem u Gold diviziju, zato i trazim pomoc. Saljem kod, pa ako neko ima zivaca da mi kaze gde sam pogresio, hvala unapred. Znam da je naporno gledati tudj kod, ali mozda neko nadje vremena. Ok je i ako neko posalje neki mali test primer (do 10 mrava) na kom mi puca program. Hvala jos jednom.
{
PROG: ants
LANG: PASCAL
}

program Ants;
const
MaxN=110;
MaxM=1010;
type
Matrix=array[0..MaxM,0..MaxN] of longint;
Niz=array[1..MaxN] of longint;
var
T,A,S,B:longint;
Family:Niz;
D:Matrix;

procedure Init;
var
f:text;
i,j:longint;
begin
assign(f,'ants.in');
reset(f);
readln(f,T,A,S,B);
for i:=1 to T do
Family[i]:=0;
for i:=1 to A do
begin
readln(f,j);
inc(Family[j])
end;
close(f)
end;

procedure Solve;
var
i,j,k:longint;
f:text;
Res,Sum:longint;
begin
Sum:=0;
for i:=0 to MaxN do
for j:=0 to MaxM do
D[i,j]:=0;
for i:=1 to T do
begin
j:=1;
Sum:=Sum+Family[i];
while Sum>=j do
begin
k:=0;
while (j-k>=0) and (k<=Family[i]) do
begin
if (j-k)=0 then
inc(D[i,j])
else
D[i,j]:=(D[i,j]+D[i-1,j-k]) mod 1000000;
inc(k)
end;
inc(j)
end;
end;
assign(f,'ants.out');
rewrite(f);
Res:=0;
for i:=S to B do
Res:=(Res+D[T,i]) mod 1000000;
writeln(f,Res);
close(f)
end;

begin
Init;
Solve
end.

Ne znam zasto, ali nije hteo da mi nazubi program, pa pokusavam opet da posaljem sve isto.
{
PROG: ants
LANG: PASCAL
}

program Ants;
const
MaxN=110;
MaxM=1010;
type
Matrix=array[0..MaxM,0..MaxN] of longint;
Niz=array[1..MaxN] of longint;
var
T,A,S,B:longint;
Family:Niz;
D:Matrix;

procedure Init;
var
f:text;
i,j:longint;
begin
assign(f,'ants.in');
reset(f);
readln(f,T,A,S,B);
for i:=1 to T do
Family[i]:=0;
for i:=1 to A do
begin
readln(f,j);
inc(Family[j])
end;
close(f)
end;

procedure Solve;
var
i,j,k:longint;
f:text;
Res,Sum:longint;
begin
Sum:=0;
for i:=0 to MaxN do
for j:=0 to MaxM do
D[i,j]:=0;
for i:=1 to T do
begin
j:=1;
Sum:=Sum+Family[i];
while Sum>=j do
begin
k:=0;
while (j-k>=0) and (k<=Family[i]) do
begin
if (j-k)=0 then
inc(D[i,j])
else
D[i,j]:=(D[i,j]+D[i-1,j-k]) mod 1000000;
inc(k)
end;
inc(j)
end;
end;
assign(f,'ants.out');
rewrite(f);
Res:=0;
for i:=S to B do
Res:=(Res+D[T,i]) mod 1000000;
writeln(f,Res);
close(f)
end;

begin
Init;
Solve
end.

A da bolje napishesh koja ti je ideja za reshavanje zadatka ...

Rajko ti moju ideju znas jer sam ti pricao o tome u skoli. Sto se tice ostalih, ideja mi je dinamicko kao i na sajtu i nije u tome frka. IDeja je dokazana i prolazi mi za prva 3 test primera i treci nije ni malo naivan, pa se pitam ako mi za 3 prolazi koji je zahtevan, zasto ne prolazi za ostatak. Najverovatnije su neke glupe greske. Ako neko drugi moze da pomogne i misli da ima potrebe da objasnim ideju, objasnicu, ali ako neko zna njihovu zvanicu, onda ce i moj kod lako shvatiti.
Da, posto html "ubija" tabove i "visak" space-ova, kod ne moze da bude nazubljen, sem ako ne koristim tag code, koji ne znam kako ovde da iskoristim!

Koja je ta zvanichna ideja?

Otidi na http://ace.delos.com/NOV05.htm, pa procitaj, a moj kod sam poslao!

Jeste da ne radim USACO - necu da pamtim nebulozni (za mene) user name, pa zato i ne znam tekst zadatka. Posalji tekst pa cu da malo pogledam resenje, mada ovako na prvi pogled nesto malo razumem.

Zasto umesto
for i:=0 to MaxN do
for j:=0 to MaxM do
D[i,j]:=0;

ne stavis
FillChar(D,SizeOf(D),0);

radice brze.

Ne znam da je to moguce :(
Zadatak
Problem 8: Ant Counting [Jacob Steinhardt, 2005]

Bessie was poking around the ant hill one day watching the ants
march to and fro while gathering food. She realized that many of
the ants were siblings, indistinguishable from one another. She
also realized the sometimes only one ant would go for food, sometimes
a few, and sometimes all of them. This made for a large number of
different sets of ants!

Being a bit mathematical, Bessie started wondering. Bessie noted
that the hive has T (1 <= T <= 1,000) families of ants which she
labeled 1..T (A ants altogether). Each family had some number Ni
(1 <= Ni <= 100) of ants.

How many groups of sizes S, S+1, ..., B (1 <= S <= B <= A) can be
formed?

While observing one group, the set of three ant families was seen
as {1, 1, 2, 2, 3}, though rarely in that order. The possible sets
of marching ants were:

3 sets with 1 ant: {1} {2} {3}
5 sets with 2 ants: {1,1} {1,2} {1,3} {2,2} {2,3}
5 sets with 3 ants: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
3 sets with 4 ants: {1,2,2,3} {1,1,2,2} {1,1,2,3}
1 set with 5 ants: {1,1,2,2,3}

Your job is to count the number of possible sets of ants given the
data above.

PROBLEM NAME: ants

INPUT FORMAT:

* Line 1: 4 space-separated integers: T, A, S, and B

* Lines 2..A+1: Each line contains a single integer that is an ant
type present in the hive

SAMPLE INPUT (file ants.in):

3 5 2 3
1
2
2
1
3

INPUT DETAILS:

Three types of ants (1..3); 5 ants altogether. How many sets of size 2 or
size 3 can be made?

OUTPUT FORMAT:

* Line 1: The number of sets of size S..B (inclusive) that can be
created. A set like {1,2} is the same as the set {2,1} and
should not be double-counted. Print only the LAST SIX DIGITS
of this number, with no leading zeroes or spaces.

SAMPLE OUTPUT (file ants.out):

10

OUTPUT DETAILS:

5 sets of ants with two members; 5 more sets of ants with three members


Njihova zvanicna ideja

November 2005 Problem 'ants' Analysis
by Bruce Merry

The actual number of possible arrangements can be enormous - hence the requirement that one prints the last six digits only. Clearly, trying to enumerate all the possibilities one at a time will be too slow. Instead, we must turn to dynamic programming to help us.

Suppose we already know how many possibilities there are for the first T - 1 families of ants, for each possible count up to B (note: we also know it for counts less than S). Let o[j] be the number of ways of making j ants. If we want to find the number of ways of making i ants including family T (call this array n[i]), we have to consider how many ants to take from family T. Say family T has 3 ants; then we can take 0, 1, 2 or 3 from family T, and the rest from the other families. So

n[i] = s[i] + s[i - 1] + s[i - 2] + s[i - 3].

Repeating this process starting from 0 families and building up to T families, we will have the all the counts for the complete set of ants. There are a few subtleties that remain:

Firstly, this will be too slow in the worst case (1000 families of 100 ants), because have to add 1000 families in this way, doing a summation of 100 elements for close to 100000 different counts - about 10 billion operations. However, the summations are all quite similar to each other: for example, to get from

s[0] + s[1] + s[2] + s[3]
to

s[1] + s[2] + s[3] + s[4]
we have only to subtract s[0] and add s[4], rather without having to resum the middle elements. This reduces the number of operations by two orders of magnitude, and makes it possible to run in time.

The other subtlety is the requirement to print only the last six digits. Basically this just requires careful placement of "mod 1000000" operations - too few and integer overflow becomes a danger. However, another consideration is that the "subtract and add" method of computing the sums may lead to negative intermediate results, and thus possibly a negative final result (because the % operator gives a negative answer if the left operand is negative). All that needs to be done is to ensure that the 1000000 is added to the final answer if necessary.

Here is coach Mathijs Vogelzang's solution, which might be simpler than the analysis above:

#include <stdio.h>
#include <string.h>

int count[1010];
int currentposs[100010];

int main() {
FILE * fin = fopen("ants.in", "r");

int Ntype, total, begin, end;
fscanf(fin, "%d %d %d %d", &Ntype, &total, &begin, &end);
memset(count, 0, sizeof(count));
for (int i = 0;i<total;i++) {
int t;
fscanf(fin, "%d", &t);
count[t-1] ++;
}
fclose (fin);

int answer = 0;

int max = 1;
currentposs[0]= 1;
for(int i=0;i<Ntype;i++) {
for(int b=max+count[i]-1;b>=0;b--)
for(int add=count[i] <? b;add>0;add--)
currentposs[b]= (currentposs[b]+currentposs[b-add]) % 1000000;
max += count[i];
}

for(int i = begin;i<=end;i++)
answer = (answer + currentposs[i]) % 1000000;

FILE *fout = fopen("ants.out","w");

fprintf(fout, "%d\n", answer);
fclose(fout);
return 0;
}

Sta si mislio sa: "Ne znam da je to moguce"
Ako si mislio da nema ta procedura (FillChar) grdno se varas.

Verujem ti da ima, ali nisam znao da postoji. Na to sam mislio. Hvala u svakom slucaju na pomoci!

Evo, u zadatku z-picerije sam koristio to i super radi. Hvala ti na savetu!

Evo, u zadatku z-picerije sam koristio to i super radi. Hvala ti na savetu!

Nema na cemu, jos samo da nadjem malo vremena pa da procitam zadatak pa cu da javim svoje misljenje.
FillChar(a,SizeOf(a),0); radi potpuno isto ka for i=1 to max_n do a[i]:=0; ali kad se prevede u masinski kod ima jednu operaciju manje jer ne pamti rezultat za i - tu je usteda u vremenu.

Vratio sam se opet na ovaj zadatak i pogodite sta sam otkrio. Nisam stavio dobra ogranicenja. Promenio sam malo ogranicenja i sa ISTOM idejom radi sve u vremenu :) Glupa greska, da sam to uradio sad bih bio u GOLD-u :(