10604 - Chemical Reaction
Moderator: Board moderators
-
- Learning poster
- Posts: 83
- Joined: Wed Feb 27, 2002 2:00 am
- Location: Taiwan
To little joey:
The random input generator was written by me.
I made a mistake at the first time, that the heat generated by Chemical i + Chmical j was not equal to that of Chemical j + Chemical i.
I corrected that error but I didn't notice(and had no sense) that the final product must be the same. I would never put those cases on purpose.
Sorry if I make you waste your time solving this problem.
The random input generator was written by me.
I made a mistake at the first time, that the heat generated by Chemical i + Chmical j was not equal to that of Chemical j + Chemical i.
I corrected that error but I didn't notice(and had no sense) that the final product must be the same. I would never put those cases on purpose.
Sorry if I make you waste your time solving this problem.
I also use DP, but it much less efficienly than your algorithm. My program runs in 8.980Observer wrote:I use some kind of dynamic programming (with many loops ) and get accepted. It finishes in 1.8s.
I think the runtime can be further reduced if I modify the loops, or take care of tubes with the same chemical, ...
I don't know how to do it faster.
My algo is like that:
I make all possible subsets of tubes (according to number of chemicals) in rising order and then for each state I compute all minimal temps for each kind of chemical it may be made.
It runs slow... Can sb tell me what improve in my algorithm or what is the optimal solution?
Best Regards!
J get AC 0:00.158
after one modification j was geting TLE
J using dymic programing + recurence
all data stored in int tst[11][11][11][11][11][11]; table
and all secret is DO NOT CLEAR TABLE it take too much time
beter is declarate second table tst[11][11][11][11][11][11];
end for valible data who can be use end store number of test
after one modification j was geting TLE
J using dymic programing + recurence
all data stored in int tst[11][11][11][11][11][11]; table
and all secret is DO NOT CLEAR TABLE it take too much time
beter is declarate second table tst[11][11][11][11][11][11];
end for valible data who can be use end store number of test
I got AC in C++ with DFS and memoization. Before each run I clear my memoization table. To my surprise, I saw that using memset for clearing the table instead of a couple of loops decreased my running time from 4.2s to 0.7s!
By the way, this is one of the many problems where Java solutions based on exactly the same method run out of time where C++ solution are accepted. I hate that!
By the way, this is one of the many problems where Java solutions based on exactly the same method run out of time where C++ solution are accepted. I hate that!
Well, so it's all correct now?
Is merging i-th and j-th chemicals produce the same result and the same heat as that of merging j-th and i-th?
Is merging i-th and j-th chemicals produce the same result and the same heat as that of merging j-th and i-th?
Code: Select all
for (x = 0; x < (1 << m); x++)
for (y = 0; y < x; y++)
if (!(x & y))
for (i = 0; i < n; i++)
if (z[x][i] < oo)
for (j = 0; j < n; j++)
if (z[y][j] < oo)
if (z[x|y][c[i][j]] > z[x][i] + z[y][j] + e[i][j])
z[x|y][c[i][j]] = z[x][i] + z[y][j] + e[i][j];
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
-
- New poster
- Posts: 27
- Joined: Tue Dec 20, 2005 9:14 am
- Location: Egypt
-
- Experienced poster
- Posts: 103
- Joined: Tue Mar 25, 2008 11:00 pm
- Location: IUT-OIC, DHAKA, BANGLADESH
- Contact:
Re: 10604 - Chemical Reaction
I tried with 6 dimensional dp (each dimension is of size 10) and unexpectedly I got AC in 0.064 seconds. I thought this would time out because I need some extra 6*6 calculations inside dp recurrence. Later I understood it, noticing the limit of k.
"asmaamagdi" wrote,
no tricky i/o is there, so far I think. If u still get WA u can post ur code.
"asmaamagdi" wrote,
Can any1 plz provide some input & output. I got WA
Thnx in advance
no tricky i/o is there, so far I think. If u still get WA u can post ur code.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
It is more tough to become a good person.
I am trying both...............................
Re: 10604 - Chemical Reaction
I am also using a 6-D DP. I believe my code is okay. But, I am getting WA. Some additional IO is highly appreciated.
Thanks.
[EDIT: ]Initialization part had a flaw. AC now
Thanks.
[EDIT: ]Initialization part had a flaw. AC now
regards,
nymo
nymo
Re: 10604 - Chemical Reaction
My idea is say the tube has 1,2,2,3 so I will try out (1,2), suppose their combination produces 2, now I've two options, taking 2 (which I got from (1,2)) and combine it with either 2 or 3 (from the remaining tubes) or combining remaining tubes (2,3), get their combination and try out with 2. Afterwards, I'll try out another combination from the beginning and this goes on.
Initially, I overlooked the fact that I can try out combinations from tubes remaining despite using one of the reagents from the combination formed from two tubes. So, I coded a solution, of course it is buggy. But now I am facing problems in implementing what I just have explained. Any help is really appreciated.
Buggy solution link: http://ideone.com/h2nMTX
Initially, I overlooked the fact that I can try out combinations from tubes remaining despite using one of the reagents from the combination formed from two tubes. So, I coded a solution, of course it is buggy. But now I am facing problems in implementing what I just have explained. Any help is really appreciated.
Buggy solution link: http://ideone.com/h2nMTX