10604 - Chemical Reaction
Moderator: Board moderators
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
10604 - Chemical Reaction
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.
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.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
more of reality
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.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
No.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.
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...
-
- Learning poster
- Posts: 95
- Joined: Mon Apr 26, 2004 1:23 pm
- Location: Hong Kong and United States
- Contact:
10604 Chemical Reaction
I got TLE again and again.
Can anybody tell me what is the correct algo?
I used DFS.![:cry:](./images/smilies/icon_cry.gif)
Can anybody tell me what is the correct algo?
I used DFS.
![:cry:](./images/smilies/icon_cry.gif)
-
- Learning poster
- Posts: 95
- Joined: Mon Apr 26, 2004 1:23 pm
- Location: Hong Kong and United States
- Contact:
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]
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]
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]
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]
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![:wink:](./images/smilies/icon_wink.gif)
![:P](./images/smilies/icon_razz.gif)
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:](./images/smilies/icon_wink.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
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.
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.
-
- Learning poster
- Posts: 95
- Joined: Mon Apr 26, 2004 1:23 pm
- Location: Hong Kong and United States
- Contact:
can be changed???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.
even if I delete the last line, still it is WA...
if i delete if (y>l) it's TLE
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
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