10604 - Chemical Reaction

[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]

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]

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]

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]

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

[UFP2161]

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

[cytmike]

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]

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]

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]

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]

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, but I don't think I've time to do so

[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]

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]

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

[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