Jewels

[Adrian_Kosowski]

In reply to zhuzeyuan's email:

I'm now trying to solve Jewelry and Fashion(contest set2). I don't know whether the standard program runs in O(N^2) for each testcase. [...] May I know the time spent by the standard program?

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 .

I think the time limit should be at least twice of it...

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 .

[Pascal_sof]

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 .

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]

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.

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

But perhaps it is better not to touch anything .

[Pascal_sof]

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]

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 ?

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

[Adrian_Kuegel]

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]

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.

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

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.