Sort by

recency

|

5 Discussions

|

  • + 0 comments

    Wonderful blogpost. Find out more about apk legends fr

  • + 0 comments

    great post, also check SSS Contribution

  • + 0 comments

    Really don't know, why this problem is listed under 'Number Theory'.
    To me it is plain linear algebra (e.g. Gauss elimination), in the boolean Field aka , $\mathbb{Z}_2 , wtf ...

    from itertools import chain
    from operator import xor
    
    def main():
        n, d = map(int, input().split())
        flatn = n*n
        inrange = lambda p1, p2: d >= sum(abs(a-b) 
    		            for a,b in zip(p1,p2) )
        to2d = lambda i: divmod(i, n) 
        board = [list(map(int,input().split())) for _ in range(n)]
        oparray = [ [inrange(base, pnt) 
                        for base in map(to2d, range(flatn))]
                    for pnt in map(to2d, range(flatn))]
        flatboard = list(chain(*(map(bool, row) for row in board)))
        result = gauss(oparray, flatboard)
        if result is None or len(result) == n:
            print('Impossible')
        else:
            print('Possible')
            print(len(result))
            for r in result: print(*to2d(r))
    
    def gauss(m, v):
        n = len(m)
        row = col = 0
        rank = []
        while row < n and col < n:
            for pivr in range(row, n):
                if m[pivr][col]:
                    break
            else:
                col += 1
                continue
            rank.append(col)
            if row != pivr: 
                m[row], m[pivr] = m[pivr], m[row]
                v[row], v[pivr] = v[pivr], v[row]
            for r in range(n):
                if r != row and m[r][col]:
                    m[r][col:] = map(xor, m[r][col:], m[row][col:])
                    v[r] ^= v[row]
            row += 1
            col += 1
        if sum(v[len(rank):]): return None
        return [r for r,vv in zip(rank, v) if vv]
             
    if __name__ == '__main__': 
        main()       
    
  • + 0 comments

    Python 3 solution

    # Enter your code here. Read input from STDIN. Print output to STDOUT
    
    read_ints = lambda: list(map(int, input().split()))
    
    def solve(rect, mat_len):
        l = len(rect)
        ret = [0 for i in range(l)]
        pos = 0
        for i in range(l):
            while True:
                find = False
                for j in range(i, l):
                    if rect[j][pos] == 1:
                        rect[i], rect[j] = rect[j], rect[i]
                        find = True
                        break
                if find:
                    break
                else:
                    pos += 1
                    if pos == l:
                        break
            if pos == l:
                break
            for j in range(i + 1, l):
                if rect[j][pos]:
                    for k in range(pos, l + 1):
                        rect[j][k] ^= rect[i][k]
            pos += 1
            if pos == l:
                break
        rect.reverse()
        for i in range(l):
            pos = -1
            for j in range(l + 1):
                if rect[i][j]:
                    pos = j
                    break
            if pos == l:
                print('Impossible')
                return
            if pos == -1:
                continue
            ret[pos] = rect[i][l]
            for j in range(i + 1, l):
                if rect[j][pos]:
                    for k in range(pos, l + 1):
                        rect[j][k] ^= rect[i][k]
        print('Possible')
        print(sum(ret))
        k = 0
        for i in range(mat_len):
            for j in range(mat_len):
                if (ret[k]):
                    print(i, j)
                k += 1
    
    if __name__ == "__main__":
        [r, d] = read_ints()
        mat = []
        for i in range(r):
            mat.append(read_ints())
        rect = []
        k = 0
        for i in range(r):
            for j in range(r):
                rect.append([])
                for iter_i in range(r):
                    for iter_j in range(r):
                        if abs(i - iter_i) + abs(j - iter_j) <= d:
                            rect[k].append(1)
                        else:
                            rect[k].append(0)
                if mat[i][j]:
                    rect[k].append(1)
                else:
                    rect[k].append(0)
                k += 1
        solve(rect, r)
    
  • + 2 comments

    For testcase #3, my submission was marked as giving the wrong answer. I downloaded the input and output for that testcase, and it said the output should be "impossible", but I worked out my program's solution for that testcase by hand and it seems to work. Also, I have a friend who also worked on this problem and his solution was marked correct on that testcase, but his program verified that that testcase should output "possible", and that my solution works. What's happening?

No more comments