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

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

10604 - Chemical Reaction

Post by little joey »

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 »

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.

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

more of reality

Post by abishek »

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.

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

Post by little joey »

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

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 »

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

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

Post by UFP2161 »

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

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

Post by cytmike »

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 »

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.

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

Post by cytmike »

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 »

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 »

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 »

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.

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

Post by cytmike »

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

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

Post by cytmike »

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 »

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)”