IOPC1200: Time Limit for Java less than time limit for C++

Hi,

I have been trying to get AC for this problem - ‘Hardware Upgrade’ for quite some time now. I always get TLE. Since I am new to the site, I thought maybe the algorithm I am using is not fast enough. But after reading up the FAQ section and Variable Time Limits Based on Programming Language, I got to know that the time limit listed at the bottom of the page is for programming languages beginning with C and Java gets twice that time.

However, I fail to understand how the previous two submissions which got AC could take times in excess of 2s and 3s. Is something wrong with my understanding here or are the time limits set wrongly? I am okay with having the same time limit for C++ as for Java, since if I get TLE in that case I should probably start learning C++. Actually, what I am worried about here is that maybe the problem can’t be solved in under 2s (since the previous AC submissions take time in excess of that) and I am wasting my time.

Thanks in advance for your comments :smiley:

Warmest Regards.

P.S. - Any comments on my submission or algorithm or approach or code are also welcome and will be greatly appreciated.

the displayed time limit for a problem is set for each test file given in input. the online judge evaluates your code on several test files, to check if you program is correct or not. at the end, if you pass successfully, it gives you the total time spent by your program over all the test files used.
that’s why you can get AC, but show an execution time greater than the problem time limit. you have to keep in mind there is at least one test file for each problem.

3 Likes

Oh, I see. That does clear things up :slight_smile:

about the very algorithm, here’s how i see it.

it’s the well-known ‘Rooted Tree Isomorphism Counting Problem’. the task is to count the number of possible isomorphism of a classic rooted tree. you can do it by recursion and, for each subgraph, compute a hash value to tell you if this substructure has already been met or not. the trick here, is to notice that the order of children does not matter. then, your hash function has to be commutative. at last, for each node, the number of isomorphisms is given by the product of the factorials of the numbers of common children subgraphs (common children hashes).

moreover, it seems that it is the way fura2 implemented it, and i think there is no easier way to do it.

1 Like

@cyberax -
Hi,

Sorry for the late response.

Yeah, I do know about the problem. The only difficulty seems to be in finding the hash function. How fura2 does is that he calculates the hash of any node by summing the product of the children of any node with random numbers (at least this is what I understood on glancing through the code). This approach, I think, works only because the test data might not be that strong.

I tried two approaches -

  1. http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/HW5+.pdf Look at the algorithm under Rooted Tree Isomorphism. It performs a BFS first to know which nodes are at which level. Then it goes from the bottom most level to the top, assigning labels to the parents of the children. This of course involves costs in sorting the labels of children of each node and sorting the labels themselves at each row. And if this is not clear, it might be easier to understand by looking at the link :stuck_out_tongue: But this still gets me TLE.

  2. DFS and the hash is an array list formed by the ordered labels of children. This approach, I think is getting TLE, because comparing arrays is expensive and it will be great if I can get an integer hash (I have failed to think of a suitable method of getting one). This also gets TLE.

1 Like

This approach, I think, works only
because the test data might not be
that strong.

indeed. i’ll try to find a correct hash function, if i have some time in the following days. :slight_smile:

Thanks for your question I didn’t know about variable time limit.