DIGFORST : Even setter's solution got TLE in practice?

I am struggled with this problem…
I read the editorial and seems like my submissions in contest matched what the editorial said.
I implemented Dijkstra and SPFA (that was the “Bellman-Ford + Queue” in the editorial) and submitted in practice session but getting TLE. I even submitted setter’s solution with no luck.

Why is the issue? Is it possible that setter’s solution is not guaranteed to finish the test cases within time limit?

2 Likes

Hi, it’s not strange at all :slight_smile: setter’s solution is a clear version so everyone could get the idea to solve. You might see a very nice solution of the tester with lots of useful improvements. Let it challenge you :slight_smile:

1 Like

Hm, I thought that programming contests are about algorithms and not performance tunning. Finally I found “useful improvements”.

1.) multidimensional array -> one dimensional

I always thought that when I have multidimensional array (in following example 3D):

int a[A][B][C];

and I want to get value for

int v = a[i][j][k];

C/C++ calculates memory position like

int v = a + i * B * C * sizeof(int) + j * C * sizeof(int) + k;

In this problem I found, that when you perform such calculation in code, performance is 4-times better on my computer (shame on you C/C++).

2.) Loop unwinding (wikipedia)

Applying first improvement was not enought, still getting TLE. When I changed state update from

for ( int j = 0; j < MODSL; ++j )
	s->mods[j] = (act->mods[j] * 10 + v) % MODS[j];
s->mods[2] = s->mods[2] == 0 ? 0 : 1;

to

s->mods[0] = (10 * act->mods[0] + v) % 3;
s->mods[1] = (10 * act->mods[1] + v) % 4;
s->mods[2] = v == 5 ? 0 : 1;
s->mods[3] = (10 * act->mods[3] + v) % 7;

performance improved slightly, but it was finally enough to pass time limit.

1 Like

I could understand if the author’s solution is NOT an intended solution. Judging from the sketch of author’s solution idea I think this is exactly what we want, without any optimization mentioned.

I don’t think challenge includes optimizing certain constant time operations so as to pass the time limit. Moreover in other contests it is known that the time limit is certain multiple of how fast the slowest intended solution could pass the test data (I even heard that the factor was 10 in ACM ICPC World Final).

It would be discouraging to spent over days to get a suggested solution worked due to tight time limit.

2 Likes

I had same idea and also got TLE :-/ http://www.codechef.com/viewsolution/1035064