10604 - Chemical Reaction

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

Moderator: Board moderators

Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn »

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.

New poster
Posts: 15
Joined: Wed Jun 30, 2004 11:24 am
Location: POLAND (Plock)

Post by ulin »

Observer wrote:I use some kind of dynamic programming (with many loops :P ) 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 also use DP, but it much less efficienly than your algorithm. My program runs in 8.980 :(
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!

New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm

Post by Pavl0 »

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

Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac »

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!

New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm


Post by ziliang »

this is ridiculous.

A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

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?

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

Post by asmaamagdi »

Can any1 plz provide some input & output. I got WA :(
Thnx in advance
Asmaa Magdi

Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm

Re: 10604 - Chemical Reaction

Post by kbr_iut »

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

Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 10604 - Chemical Reaction

Post by nymo »

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.


[EDIT: ]Initialization part had a flaw. AC now :)

New poster
Posts: 8
Joined: Thu Dec 25, 2014 4:50 pm

Re: 10604 - Chemical Reaction

Post by Tahanima »

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

Post Reply

Return to “Volume 106 (10600-10699)”