# Warning:

# This post is a full spoiler, including my tutorial and a link to my solution in Python.

# I haven't hidden any hint, so clicking *"Read more…" *will reveal the entire post.

Active In

Competitive Programming

Algorithms and Data Structures

Featured Contributions

comment in this discussion

Read more… (253 words)

comment in this discussion

Too bad the website only accepts C, C++, and PASCAL (!!??) submissions. The solution in Python is, as always, compact and elegant:

# https://szkopul.edu.pl/problemset/problem/4CirgBfxbj9tIAS2C7DWCCd7/site/?key=statementimport sys, heapqn = int(sys.stdin.readline().strip())a = [int(sys.stdin.readline().strip()) for i in xrange(n)]smallest = [float('inf')] * a[0]smallest[0] = 0queue = [(0, 0)]while queue:total, modulo = heapq.heappop(queue)for i in xrange(1, n):x1, x2 = smallest[modulo] + a[i], (modulo + a[i]) % a[0]if x1 < smallest[x2]:smallest[x2] = x1heapq.heappush(queue, (x1, x2))k = int(sys.stdin.readline().strip())b = [int(sys.stdin.readline().strip()) for i in xrange(k)]

Read more… (62 words)

comment in this discussion

My solution in Python 2, accepted by SPOJ (with 2.76 seconds or about half the time limit)

Algorithm:

Code:

from sys import stdin, stdoutfrom heapq import heappush, heappopdef dijkstra(city1, cities2, graph):# city1 = source# cities2 = set of all destinationsvisited = set()queue = [(0, city1)]output = []while queue:

Read more… (56 words)

comment in this discussion

Take the example A = [1, 6, 2, 3, 4, 7, 5]

Going to the right, you have 2 possible LIS for A:

LIS1 = [1, 2, 3, 4, 5] → A minus LIS1 = [6, 7]

LIS2 = [1, 2, 3, 4, 7] → A minus LIS2 = [6, 5]

Going to the left:

on A minus LIS1: LIS = [7] or [6]

on A minus LIS2: LIS = [6, 5]

For your solution to be eventually correct, you would need to examine all LIS going to the right, as there could be multiple of them (and it will not be completely trivial to list them all).

Read more… (108 words)

comment in this discussion

This problem is an excellent challenge!

My solution in Python 2 (time 0.88 in CodeChef, the fastest Python execution time!):

# Python 2def maxsumright(array):# compute the array of maximum sum possible going right# starting at array[0] and jumping 1 or 2 at each move# output:# array A, where A[i] = maximum sum possible going from 0 to ilength = len(array)A = [0] * lengthif length > 1:A[1] = array[1]for i in xrange(2, length):A[i] = max(A[i - 1] + array[i], A[i - 2] + array[i])return Adef maxsumleft(array):# compute the array of maximum sum possible going left# finishing at array[0] and jumping 1 or 2 at each move

Read more… (20 words)

comment in this discussion

My solution to the problem (no 2 consecutive Knights don't have no dessert):

# Python 2n = int(raw_input().strip())cost = map(int, raw_input().strip().split())# C[i] = minimum cost from [0, i], with knight(i) having his dessert.# if knight(i) has dessert, knight(i-1) or knight(i-2) must have dessert# as well so no consecutive knights don't have dessert. Therefore:# C[i] = cost[i] + min(C[i-1], C[i-2])def minimum(cost):C = [0] * nC[0] = cost[0]C[1] = 0 + cost[1]C[2] = min(cost[0], cost[1]) + cost[2]for i in xrange(3, n):

Read more… (13 words)

comment in this discussion

The problem states:

"A strange feature of the Knights is that they will not complain about not getting dessert unless they get support from both their neighbors. So, you decide to pick the cheapest desserts to make, such that for every pair of adjacent Knights, at least one gets his dessert."

Deciding that that "for every pair of adjacent Knights, at least one gets his dessert" is __sub-optimal__. To make sure that there will be no complaints, it is enough to solve the problem: **for every triplet of adjacent Knights, at least one gets his desert.**

For example: 5 Knights, costs = 10, 1, 1, 1, 10

All the algorithms in this discussion give the answer 12, but the answer should be 2. Selecting Knights 2 and 4 guarantees that no Knight gets support from both his neighbors.

Read more… (139 words)