Nov 2004
1 / 7
Nov 2004
Nov 2004
Adrian_Kosowski
Nov '04

In reply to zhuzeyuan's email:

The time used by the standard program is about 25s. The model solution is quite well optimised, but still requires O(n^2) time. However, it seems to be possible to solve the problem in a much faster way using a more optimal algorithm. Therefore solutions not faster than the model solution should really be treated with suspicion wink.

If the problem "survives" until the next problemset without a single correct solution, the test data will be slightly modified and the time limit will be increased. But I wouldn't really count on this happening smile.

Pascal_sof
Nov '04

Please don't do that ! If you have a valid solution, I think you should keep the problem and test data as they are, until someone finds the trick, instead of making the problem simpler.

Adrian_Kosowski
Nov '04

You misunderstood me... I want to add a few test cases to make sure no O(n^3) heuristic could pass smiling_imp.

But perhaps it is better not to touch anything smile.

Pascal_sof
Nov '04

What about the limit of 100 submissions per person for this problem ? Is it 100 for problem set 2 and 100 for problem set 3, or 100 for both ?

Adrian_Kosowski
Nov '04

One hundred for each. You can treat JEWELS(set2) and JEWELS(set3) as separate problems.

Adrian_Kuegel
Nov '04

For problem Jewels:
What should be the cut, if the best length is zero?
I know that is not the reason why I got WA, because I tried both, a cut of 0 and a cut of 1. But it would help if I wouldn't have to try for each change in my program both possibilities.

Adrian_Kosowski
Nov '04

The frank answer would be: I don't know really, there is no such test case. smile

But thanks for bringing my attention to this. For the sake of precision, I've modified the problem description to make it equal to 1.