10604 - Chemical Reaction

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

[ulin]

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

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!

[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

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

[ziliang]

this is ridiculous.

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


[asmaamagdi]

Can any1 plz provide some input & output. I got WA
Thnx in advance

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

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

Thanks.

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