Week 7 Materials (expanded, click to collapse) Completed LSH Families (21:13) slides for LSH Families (21:13) Subtitles (text) for LSH Families (21:13) Subtitles (srt) for LSH Families (21:13) Video (MP4) for LSH Families (21:13) Completed More About LSH Families (12:57)
...
안에도 설명이 있는데, 화질, 음질이 더 깔끔하다.
하지만, 너무 어렵다 ...
LSI
stanford ng 옛날 강의
text에서 PCA하는 셈. 거의 비슷하다. 그게 끝? LSI설명은 거의 없네.
subspace에 projection하는 것?
PCA, SVD 관계도 조금 알 수 있다. SVD를 이용해서 Xt * X의 eigenvectors (columns of U)를 알아내서 PCA를 계산하는 방법이 있다.
def reverse(n): result = 0 while n: digit = n % 10 n = n / 10 result = result * 10 + digit return result
def solve(N): n = N times = 0 while n: next_n = n-1 next_s = 1 for i in range(len(str(n))-1): substract = n % (pow(10, i+1)) - 1 r = reverse(n - substract) if r + substract + 1 < next_n + next_s and r >= 0: #print " ", n, next_n, r next_n = r next_s = substract + 1 if next_s > 1: print n, next_n, next_s times += next_s n = next_n # if n > r #and (n % 10 != 0) and (n % 10 == 1): # print n, r # n = r # else: # n -= 1 return str(times)
# def bottomup(N): # p = 0 # while p != n: # next_i = p+1 # next_a = 1 # for i in range(len(str(N))-1): # adding = def less(N, n, times): if n <= 0: return times if times > N: return times r = reverse(n) times1 = less(N, n-1, times+1) times2 = less(N, r-1, times+2) return min(times1, times2)
def brute(N):
return str(less(N, N-1, 1))
for i in range(T): N = int(fin.readline()) print N solution = solve(N) # b_solution = brute(N) # if solution != b_solution: # print solution, b_solution answer = "Case #%d: %s\n" % (i + 1, solution) print answer fout.write(answer)
def solve(N, ss): f = 0 c = 0 for i, s in enumerate(ss): if c < i: f += i - c c += i - c
c += s
return f, c
for i in range(T): N, S = fin.readline().split() ss = [] for j in range(int(N)+1): ss.append(int(S[j])) solution = solve(int(N), ss) answer = "Case #%d: %s\n" % (i+1, solution[0]) print answer fout.write(answer)
def mult(qs): r = q('1') for vq in qs: r = r * vq return r
def mult_table(table, vs, a, b, indices): key = str(a) + ',' + str(b) if table.has_key(key): return table[key] else: cs = [x for x in indices if a < x < b] if not cs: value = mult(vs[a:b]) else: c = cs[len(cs)/2] value = mult_table(table, vs, a, c, indices) * mult_table(table, vs, c, b, indices) #print key, value, a, c, b table[key] = value return value
#print q('i') * q('j'), q('j') * q('k'), q('i') * q('j') * q('k') def solve(L, X, ijk): fqs = [] for i in ijk: if i == 'i' or i == 'j' or i == 'k': fqs.append(q(i)) qs = [] X = X % 16 extend = min(X, 4) for i in range(extend): qs.extend(fqs)
print qs lq = q('1') left_plus = [] left_minus = [] for i_l, l in enumerate(qs): # print lq, l lq = nx = lq * l if nx == q('i'): left_plus = [i_l+1, nx, l] if nx == -q('i'): left_minus = [i_l+1, nx, l] if left_plus and left_minus: break right_plus = [] right_minus = [] rq = q('1') for i_r, r in enumerate(reversed(qs)): rq = nx = r * rq if nx == q('k'): right_plus = [i_r+1, nx, r] elif nx == -q('k'): right_minus = [i_r+1, nx, r] if right_plus and right_minus: break if (not left_plus) and not left_minus: return "NO" if not right_plus and not right_minus: return "NO" dqs = [] for idqs in range(X):#range(min(X, 8)): dqs.extend(fqs)
lefts = [] rights = []
mc = {} mfqs = mult(fqs) indices = [] if left_plus: indices.append(left_plus[0]) lefts.append(left_plus) if left_minus: indices.append(left_minus[0]) lefts.append(left_minus) if right_plus: indices.append(len(dqs) - right_plus[0]) rights.append(right_plus) if right_minus: indices.append(len(dqs) - right_minus[0]) rights.append(right_minus) for ie in range(8): index = ie * len(fqs) indices.append(index) mc[str(index) + ',' + str(index + len(fqs))] = mfqs sorted_indices = sorted(set(indices))
# prev = -1 # mc = mult_table(qs, sorted_indices) # for ii in sorted_indices: # for ij in sorted_indices[]: # if # if prev > 0 # mc[[prev, index]] = mult(qs[prev:index+1]) # prev = index print mfqs, mc, sorted_indices for j_l in lefts: for j_r in rights: if j_l[0] + j_r[0] < len(dqs) + 2: #isj = mult_table(mc, dqs, j_l[0], len(dqs)-j_r[0], sorted_indices) isj = mult(dqs[j_l[0] : len(dqs) - j_r[0] ]) #print j_l[1], isj, j_r[1], j_l[1] * isj * j_r[1] if j_l[1] * isj * j_r[1] == -q('1'): return "YES" # else: # j_left = mult(dqs[j_l[0] : -1]) # j_right = mult(dqs[0 : len(dqs) - j_r[0]]) # j_middle = q('1') # for k_d in range(min(X - 8, 4)): # j_middle = j_middle * mfqs # if j_l[1] * j_left * j_middle * j_right * j_r[1] == -q('1'): # return "YES" return "NO" for i in range(T): L, X = map(int, fin.readline().split()) ijk = fin.readline() solution = solve(L, X, ijk) # if solution > candidate: # print 'ERROR', i + 1, solution, candidate # if solution != solution1: # print 'ERROR', i + 1, solution, solution1, candidate answer = "Case #%d: %s\n" % (i + 1, solution) print answer fout.write(answer)
Gabriel = "GABRIEL" Richard = "RICHARD" def solve(X, R, C): if (R * C) % X != 0: print "%" return Richard if R < X and C < X: print "<" return Richard if X > 6: print "6" return Richard min_l = 1 + (X - 1) / 2 if X > 2 and (R < min_l or C < min_l): print "sqrt" return Richard snake = 2 + (X - 2) / 3 if X > 3 and (R <= snake or C <= snake): print "snake" if X == 4: return Richard elif X == 5 and (R < 5 and C < 5): return Richard elif X == 6 and (R < 7 and C < 7): return Richard
return Gabriel
for i in range(T): X, R, C = map(int, fin.readline().split()) print i+1, X, R, C
solution = solve(X, R, C) # if solution > candidate: # print 'ERROR', i + 1, solution, candidate # if solution != solution1: # print 'ERROR', i + 1, solution, solution1, candidate answer = "Case #%d: %s\n" % (i + 1, solution) print answer fout.write(answer)
def solve(outlets, plugs, N, L): #print outlets, plugs plugs.sort()
shuffle = [] switch = [] unknown = [] for i in range(L): ips = [(p >> i) % 2 for p in plugs] ios = [(o >> i) % 2 for o in outlets] print i, ips, ios if ips.count(1) == ios.count(1): if ips.count(1) == ips.count(0): unknown.append(i) elif ips.count(0) == ios.count(1): if ips.count(1) == ips.count(0): unknown.append(i) else: shuffle.append(i) else: return "NOT POSSIBLE" shuffled_outlets = outlets[:] for s in shuffle: shuffled_outlets = [o ^ pow(2, s) for o in shuffled_outlets]
result = len(shuffle) print plugs print shuffled_outlets
if plugs == shuffled_outlets: return str(result)
for i in range(len(unknown)): for j in itertools.combinations(unknown, i+1): shuffled_outlets2 = shuffled_outlets[:] for k in j: shuffled_outlets2 = [o ^ pow(2, k) for o in shuffled_outlets2] shuffled_outlets2.sort() #print shuffled_outlets if plugs == shuffled_outlets2: return str(result + i + 1)
return "NOT POSSIBLE" for i in range(T): N, L = map(int, fin.readline().split()) outlets = [int(n, 2) for n in (fin.readline().split())] plugs = [int(n, 2) for n in (fin.readline().split())] print 'o', outlets print 'p', plugs solution = solve(outlets, plugs, N, L) if N == 1 and solution == "NOT POSSIBLE": print "ERROR1" if solution != "NOT POSSIBLE" and N < int(solution): print "ERROR2" answer = "Case #%d: %s\n" % (i+1, solution) print answer fout.write(answer)
#sorted_star2_indices = [v[0] for v in sorted(enumerate(star2s), key=lambda x:x[1])] sorted_star2_indices = [v[0] for v in sorted(enumerate(star2s), cmp=greater)] sorted_star2_values = [v[1] for v in sorted(enumerate(star2s), cmp=greater)]
for i in range(T): N = int(fin.readline()) stars = [] completed = [] for j in range(N): stars.append(map(int, fin.readline().split())) completed.append(False)
RECENT COMMENT