What is a right algorithm to that problem?

Tell me please!

Is it greedy???

Yes (-)

Posted by

Ivan 26 Oct 2008 12:14

Re: What is a right algorithm to that problem?

Posted by

svr 26 Oct 2008 19:56

Greedy only? I think.

I don't solve else but think that next algo is right:

1. maximal production =d in all n periods;

2. Greedy approach :satisfy first demand as fully as possible;

3. If we have residue in last period equal to k

diminish by k residues in previous periods until it is possible

4. Sum final residues along all periods.

*Edited by author 26.10.2008 20:52*

Re: What is a right algorithm to that problem?

My algo is the same as your! (but still wa 15) :-(

Re: What is a right algorithm to that problem?

Use DP

Re: What is a right algorithm to that problem?

Posted by

svr 26 Oct 2008 21:43

You definitely need reading math eco theory

optimal store managing(Taha a.s.o.)

P.S.I also have WA14. First number of output I guarantee but

the second need more delicate algo.

Re: What is a right algorithm to that problem?

may be your problem with the type of the second number(it should be __int64)???

*

I have WA49 with greedy and restroring.

Re: *

Posted by

double 27 Oct 2008 06:17

use int64(long long) ,then you'll get AC.

Re: What is a right algorithm to that problem?

Posted by

svr 27 Oct 2008 09:21

Yuare right!

With __int 64 AC.

I didn'r recognized masked danger:100000*100000=10*1-e9.

All data seemed fitted in int type.

*Edited by author 27.10.2008 09:21*

Re: What is a right algorithm to that problem?

Are you got AC with your algo or you had chaged it???

Re: What is a right algorithm to that problem?

*Edited by author 28.10.2008 14:51*

Re: What is a right algorithm to that problem?

Posted by

svr 27 Oct 2008 18:54

I considered stored values backward more attentievely

according with alg:

store[i-1]=max(store[i]+sell[i-1]-d,0)

store[n]:=0;

i=n..1

where sell[i-1] array of greedy selling on the first stage.

Re: What is a right algorithm to that problem?

Accepted!!!!!!

this test help me find my bug...

in:

5 5

3 1 20 3 10

out: 25 10

and now,after accepted, could somebody, who solved this problem with DP, sent to me your solution?

my mail: asyamov@mail.ru

*Edited by author 28.10.2008 16:18*

Re: What is a right algorithm to that problem?

I think greedy can work well.

Re: What is a right algorithm to that problem?

I don'n understand, how to solve this problem whith DP or greedy. I solve with RMQ.