OJ Board

mf, you said you can find out what characters need to be merged in O(n^3) dp at every step. Can you please explain how to do that? If you use dp similar to CYK algorithm, then it need not be correct for finding out the characters to merge. because if you use dp[i,j] = function(dp[i,k],dp[k+1,j]), we ...

This is my output.


6 guess(es) required.
7 guess(es) required.
7 guess(es) required.
7 guess(es) required.
8 guess(es) required.
8 guess(es) required.
10 guess(es) required.
10 guess(es) required.
10 guess(es) required.
10 guess(es) required.
10 guess(es) required.
10 guess(es) required.
13 guess ...

can you tell me the order of your algorithm?

Sumankar,
I didnt exactly understand your solution. The polygon might have some area that is not in any triangle too.

So you would have to be very careful in finding the various polygons first, something like finding the components in a graph where the nodes are represented by the traingles and ...

my j loop runs from i+1 to n. So no conflicts.

Also i just find out whether my mat[k]>mat[j][k]
or otherwise when i check for inequality.

Also, I didnt not sort the strings anywhere in my code.
That was the mistake.

Thanks to Christian for finding it out.

Thanks anyway.
ranjit

687 is a very interesting problem. Though i am not able to either reduce the search space
or even find out all the possible configurations for the sample input.

Can anyone who is interested in this problem help ?

Thanks.

I keep getting WA in 5sec with the foll. algorithm
Can somebody point out the mistake.

1.mat[i][j] stores the number of occurrences of "j+'a' " character in string i.
2.loop overall i
2a. if i not marked dominated
3. loop overall j
3a. if j not marked
if mat[i][k]!=mat[j][k]
if i dominates j ...

is there any greedy solution to the problem. I see some zero memory and time solutions

hi abishek,
from your description of the solution,it is not clear whether you ensure that at the destination
the truck has fuel > 100 litres.

Also, print Impossible not -1.

I have got WA many times in this problem. I think there are many ambiguties.
For eg. the problem says the persons are transferred every new month. Does that mean

they shift over on the 1st of the new month or exactly one month later. Ofcourse the latter
assumption is instantly proved inconsistent ...

My ac code gives the o/p for both the cases.

Hope it helps

Can anyone verify these i/o and tell if there are any mistakes. I have been getting WA for tihis problem

Thanks in advance.

Input


23 23
? ? ? 1 17 16 ? 6 17 9 17 ? 15 10 ? 8 12 16 11 2 3 1 16
41 28
38 18 9 13 3 ? ? 22 33 25 1 40 10 15 30 1 ? 31 ? ? ? 26 ? 29 ? 11 7 ? ? 27 ? 7 ? 36 16 29 ...

Thanks. Even i didnt initialize properly !!

it need not be critical i/o always. just tens of i/o can explain to the programmer atleast whether he is on the right track. If probably he finds that he is on the right track he atleast can look at the prospect of his pgms working/not working for the critical i/p.

This is mainly in regard to ...

Can it be made possible that more number of input-output are provided for the problems.
Note that these may be separate from the test cases used to judge the program.
This would possibly eliminate many wrong submissions resulting from trivial doubts (like whether to add a new line at the end ...