Submission #1286581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286581		_rain_	K-th path (IZhO11_kthpath)	Pypy 3	0 / 100	719 ms	327680 KiB

kthpath

#!/usr/bin/env python3
import sys

# Constants similar to the original C++
DX = (0, 1)
DY = (1, 0)

def compute_binomials(max_i, max_j):
    """Compute binomial coefficients C[i][j] for 0 <= i <= max_i, 0 <= j <= max_j."""
    C = [[0] * (max_j + 1) for _ in range(max_i + 1)]
    for i in range(max_i + 1):
        C[i][0] = 1
    for i in range(1, max_i + 1):
        for j in range(1, min(i, max_j) + 1):
            C[i][j] = C[i-1][j-1] + C[i-1][j]
    return C

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    numrow = int(next(it))
    numcol = int(next(it))

    # grid with 1-based indexing (pad with dummy at index 0)
    a = [[''] * (numcol + 1) for _ in range(numrow + 1)]
    for i in range(1, numrow + 1):
        s = next(it)
        # s length should be numcol
        for j in range(1, numcol + 1):
            a[i][j] = s[j-1]

    need_k = int(next(it))

    # Precompute binomial coefficients up to (numrow+numcol-1) choose up to max(numrow,numcol)
    max_i = numrow + numcol - 1
    max_j = max(numrow, numcol)
    C = compute_binomials(max_i, max_j)

    def ways(start_x, start_y):
        """Number of monotone paths from (start_x, start_y) to (numrow, numcol) moving only right/down."""
        t1 = numrow - start_x + 1
        t2 = numcol - start_y + 1
        # number of moves = t1 + t2 - 2, choose where the right moves (t2-1) go
        return C[t1 + t2 - 2][t2 - 1]

    # pos lists for letters 'a'..'z'
    pos = [[] for _ in range(26)]

    def reset_pos():
        for i in range(26):
            pos[i].clear()

    # initial current positions: start at (1,1)
    cur_pos = [(1, 1)]
    result_chars = []

    # total length of path = numrow + numcol - 1
    for _ in range(1, numrow + numcol):
        # sanity checks similar to the C++ assert
        assert need_k > 0 and len(cur_pos) > 0

        # print the character for the first position in cur_pos
        x0, y0 = cur_pos[0]
        result_chars.append(a[x0][y0])

        reset_pos()

        # gather next-layer positions grouped by character
        for (ux, uy) in cur_pos:
            for t in range(2):
                nxt_u = ux + DX[t]
                nxt_v = uy + DY[t]
                if nxt_u <= numrow and nxt_v <= numcol:
                    ch = a[nxt_u][nxt_v]
                    idx = ord(ch) - ord('a')
                    pos[idx].append((nxt_u, nxt_v))

        # choose the letter whose accumulated paths cover the k-th path
        for ii in range(26):
            t = need_k
            for (ux, uy) in pos[ii]:
                t -= ways(ux, uy)
            if t <= 0:
                # choose this letter
                cur_pos = pos[ii][:]
                break
            # skip all paths that start with this letter and continue searching
            need_k = t

    # The loop above appends exactly (numrow + numcol - 1) characters;
    # join and output
    sys.stdout.write(''.join(result_chars))

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'kthpath.py'...

=======
  adding: __main__.pyc (deflated 45%)

=======

• Subtask 1: 0 / 100