OJ Board

Input:

5 5
..AAA
E.BBB
..AA.
CC.DD
CC.D.
25 33
.................................
.................................
.................................
.................................
.................................
.................................
....AAAAA.....AAAA.........AAAAA ...

yayas wrote:

Code: Select all

printf("Tower : #%d\n",tm);

That is OK with the Output part of the problem, but their test output simply writes: I have got AC after removing colon and space.

Straight forward technique has already been shown:

#define ROWS 10
#define COLS 5

int **ppnMatrix = (int**)calloc(ROWS, sizeof(int));
for (int i = 0; i < ROWS; i++)
ppnMatrix[i] = (int*)calloc(COLS, sizeof(int));

// now destroy it:
for (i = 0; i < ROWS; i++)
free((void*)ppnMatrix[i]);
free ...

Sorry if I sounded rude, Adrian, I meant it's fishy that 95% of people didn't find out that both LIS and simple greedy are fundamentally incorrect. :wink:

Well, it seems like I have got AC again, by modifying the greedy algorithm. It now uses construction approach:
1. start with an empty stack
2 ...

I've first got AC on greedy algorithm, and now it's not AC anymore (I haven't received email stating the new judgement yet). However, acceptance rate is now less than 5%... Something's fishy here.

This is not in fact a LIS problem, but rather one that is solved with greedy algorithm. Before using LIS, I suppose that you are sorting the input, boiling down to a greedy algorithm where sorting criterion is the cost function.

I've got AC on greedy algo by maximizing "remaining strength" which is ...

Well, I finally got it AC in only 0.002 sec, without use of big number division.

To solve the problem, you got to transform the expression to the form:
D(t, a, b) = sum(i=0, a/b - 1) (t^b)^i, where a%b=0

This sum can be further solved recursively:
D(t, a, b) = f(t^b, a/b)
f(x, 1) = 1
f(x, 2k) = (1 ...

I've got TLE as well, and here's what I did:

1. checked for special cases (b < a, b = 0, a = 0 -- although problem text says POSITIVE integers --, t = 1) - in each of these cases, result is either integer 0, or is not an integer
2. checked whether (a - b) * log10(t) > 99 - in this case result is ...