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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10604 - Chemical Reaction

Post by little joey » Wed May 12, 2004 3:56 pm

Having a degree in chemistry, I feel strongly obliged to protest against the reality value of this problem.

When solving problems on this site, one slowly gets used to necklaces with thousands of beads, cities with millions of bus lines and paper that can be folded hundreds of times. Not to speak of mushroom fields the size of the universe. But this realy goes too far.

Apart from being thermodynamicaly insane, this problem let's us believe that the mixing order (?!?) of two chemicals can lead to different products: mixing A with B can give a different product than mixing B with A. In my opinion the problemsetter should have warned us for this counterintuitive anomality. Would have saved me some hours in frustration...

Please, dear problemsetters, I know it's appealing to translate an abstract concept into a real life example. But try to stay a little closer to reality, and please warn us when the deviations take on these magnitudes.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed May 12, 2004 6:16 pm

Isn't there also something like this in reality?
What about putting water into acid, or acid into water?
If I recall it right, I learned in school, you should never put water into acid, only acid into water.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

more of reality

Post by abishek » Wed May 12, 2004 6:33 pm

I feel that the skill of an author lies in the fact that he is able to construct a nice realistic situation where the algorithm used is really applicable. Mere linking a story to it is not nice and serves no pupose.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed May 12, 2004 8:57 pm

Adrian Kuegel wrote:Isn't there also something like this in reality?
What about putting water into acid, or acid into water?
If I recall it right, I learned in school, you should never put water into acid, only acid into water.
No.
The heat production and the end product are the same in both cases. What you mention is more of a practical matter: pouring water into concentrated sulfuric acid produces the heat much quicker than the other way around, so the thing might explode in your face. But in the end the heat produced is the same (and equal to the heat required to extract the water from the diluted sulfuric acid again) and the end product too (diluted acid with the same concentration).

The world would be a strange place if the laws of thermodynamics wouldn't apply...

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

10604 Chemical Reaction

Post by cytmike » Tue Jun 15, 2004 10:41 am

I got TLE again and again.
Can anybody tell me what is the correct algo?
I used DFS. :cry:

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Tue Jun 15, 2004 1:33 pm

Use memoization on that fact that you only have 10 possible tubes.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Tue Jun 15, 2004 1:47 pm

UFP2161 wrote:Use memoization on that fact that you only have 10 possible tubes.
I used a hash table to store the values of remaining tubes and heat evolved.
If they are occured before, I just quit. But still, I got TLE.

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by subbu » Wed Jun 16, 2004 11:17 am

What was your state encoding?
If i remember right, I used a single integer for the state for
memoization.
The first time,i used a vector<int> for the state and got TLE.
Thx,
Subra.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Wed Jun 16, 2004 11:25 am

I used a hash_map <int,int> and got WA on 4s.
Can anybody give me some inputs or kindly look at my code?

[cpp]
#include <iostream>
#include <string>
#include <algorithm>
#include <hash_map.h>


using namespace std;

int r[7][7];
int h[7][7];
int k;
int sky=99999999;

hash_map <int,int> hs;

int x(string p)
{
int h=0;
for (int y=0;y<p.length();y++)
{
h*=8;
h+=p[y]-'0';
}
return h;
}

void hpsky(string p,int i)
{
int m=x(p);
if (hs.count(m))
if (hs[m]<=i)
return;
hs[m]=i;

if (p.length()==2)
{
i+=h[p[0]-'0'][p[1]-'0'];
if (i<sky)
sky=i;
return ;
}

int hp[k];
for (int y=0;y<p.length();y++)
hp[y]=p[y]-'0';
sort (hp,hp+p.length());
int w=p.length();
p="";
for (int y=0;y<w;y++)
p+=(char)(hp[y]+48);

for (int y=1;y<w;y++)
for (int l=0;l<w;l++)
if (y>l)
if ((l==0)||(p[l]!=p[l-1]))

{

string pt=p;
int it=i;
it+=h[p[y]-'0'][p[l]-'0'];
int s=r[p[y]-'0'][p[l]-'0'];
pt.erase(y,1);
pt.erase(l,1);
pt+=(char)(s+48);
hpsky(pt,it);
}
}

int main()
{
int p;
cin>>p;
for (int php=0;php<p;php++)
{
int m;
cin>>m;
hs.clear();
sky=999999999;
for (int y=1;y<=m;y++)
for (int l=1;l<=m;l++)
cin>>r[y][l]>>h[y][l];

cin>>k;
int hp[k];
for (int y=0;y<k;y++)
cin>>hp[y];

char s;
cin>>s;
string temp="";
for (int y=0;y<k;y++)
temp+=(char)(hp[y]+48);

hpsky(temp,0);

cout<<sky<<endl;
}
return 0;
}[/cpp]

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by subbu » Wed Jun 16, 2004 11:48 am

I think this will timeout always no matter what encoding is used.
If you look at it,in essence, you are
trying to find the shortest path by DFS.
The problem is that you are memoizing heats evolved in getting to
a particular state from the start state, and redoing the calculation
from this state to the target state.

suppose A is the start state and F is final state.

suppose A------B--C--D--F takes 10+15+10+10 your hashmap
contains h[a] = 10,h=25,h[c]=35,h[d]=45.

Suppose A--E--B--C--D--F takes 2+3+15+10+10,you redo your recursive calculations to update all the "h" values.

You should rather store the heats from this state to the Target state.
(saying "the" Target state is not valid,but guess it makes sense)
Or did i misunderstand your code?
Thx,
Subra.[/list]

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Jun 16, 2004 12:04 pm

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, but I don't think I've time to do so :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by subbu » Wed Jun 16, 2004 12:13 pm

Ohh wait was that WA in 4 sec.
The limit is 10 tubes right?
I made such mistake once with a limit of 50,and it timed out.

I forgot, mixing A with B need not be same as mixing B with A.

for (int y=1;y<w;y++)
for (int l=0;l<w;l++)
if (y>l)
if ((l==0)||(p[l]!=p[l-1]))

this could be changed to reflect that.
Subra.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Wed Jun 16, 2004 1:27 pm

subbu wrote:Ohh wait was that WA in 4 sec.
The limit is 10 tubes right?
I made such mistake once with a limit of 50,and it timed out.

I forgot, mixing A with B need not be same as mixing B with A.

for (int y=1;y<w;y++)
for (int l=0;l<w;l++)
if (y>l)
if ((l==0)||(p[l]!=p[l-1]))

this could be changed to reflect that.
Subra.
can be changed???
even if I delete the last line, still it is WA...
if i delete if (y>l) it's TLE

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Wed Jun 16, 2004 1:43 pm

for (int y=0;y<w;y++)
for (int l=0;l<w;l++)
if (y!=l)
if ((l==0)||(p[l]!=p[l-1]))
if ((y==0)||(p[y]!=p[y-1]))


if i use this, it's WA???

:cry:

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu » Wed Jun 16, 2004 6:49 pm

When I used DFS, without memorization I got TLE, with memorization I got MLE.
Then I changed to BFS, and got AC with pretty good time and mem.
At each loop, I record only the possible configurations for the current and next step and its minimum heat values.

Take the first sample input for example.

Originally we have numTubes=4, possible configurations are
1,2,1 -> 0 heat

At next step, numTubes=3, possible configurations are
0,1,2 -> -10 heat
0,2,1 -> 3000 heat
1,1,1 -> 0 heat
2,1,0 -> -500 heat

At next step, numTubes=2, possible configurations are
1,0,1 -> -510 heat
0,1,1 -> -10 heat
1,1,0 -> -500 heat
0,0,2 -> -10 heat
2,0,0 -> -500 heat

and finally, numTubes=1, possible configurations are
0,0,1 -> -510 heat
1,0,0 -> -510 heat

Post Reply

Return to “Volume 106 (10600-10699)”