dirkneuhaeuser/exercise-problems

Solutions for problems on kattis and UVa.

Problems-List

This folder contains my solutions for problems on Online-Judge(UVa) and kattis. They are mainly categorised according to their classification by Competetive-Programming 4. This list is still uncomplete. I try to add all solved problems
within this repository as soon as possible.

Problem	Category	Solution	idea
UVa00369 - Combinations	Binomial coefficient	c++	Pascals formula for binomial coeficients
UVa10541 - stripe	Binomial coefficient	c++	First of all subtract from the possible white balls all the balls you already know where they will be (1 in between each black at least). For the rest, you can distribute them freely. Formula to put r elements in k bins:
UVa11955 - Binomial Theorem	Binomial coefficient	c++	String processing + Pascals formula for binomial coeficients
UVa12712 - Pattern Locker	Binomial coefficient	c++	, but keep track of permutation: , Also derivable via first one has second one
kattis - Election	Binomial coefficient	c++	Pascals formula for binomial coeficients
kattis - Tree Insertion	Binomial coefficient	c++	BST, Post-Order + Pascals formula for binomial coeficients but using bigint as n>66
kattis - Locked Treasure	Binomial coefficient	c++	For each (m-1)-group, create key and give it to the rest
kattis - Odd Binomial Coefficients	Binomial coefficient	c++	Print Pascals triangle mod 2 and find pattern. Eventually, you need to count all 1 in the upper triangel, up to row n
kattis - Perica	Binomial coefficient	c++	Calculate the binomial Coefficient with Modulo: Precalculate the factorials and use mod-inverse
UVa00991 - Safe Salutations	Catalan Numbers	c++	Hidden catalan numbers.
UVa10007 - Count the Trees	Catalan Numbers	c++	Different trees: catalan numbers, Different order: n!. Use bigint, as n might be big.
UVa10223 How Many Nodes?	Catalan Numbers	c++	Hidden catalan numbers.
UVa10312 - Expression Bracketing	Catalan Numbers	c++	Super catalan numbers count the number of trees with n leaves and each inner node has >=2 children; there is a bijection from that tree to all possible bracketings (binary and non binary). Note, binary bracketing means ops(x1, x2) = ( x1, x2 ) - so two elemnts get transformed. Catalan numbers, on the other hand, count the binary bracketings, for example: (x(x(xx))). As both grow fast, use Bigint.
kattis - Catalan Numbers	Catalan Numbers	c++	Catalan numbers for big n, use bigint. Note thate the groth of catalan numbers is approx , thus long long will overflow for n>32
kattis - Catalan Square	Catalan Numbers	c++	Catalan numbers for big n, use bigint. Note thate the groth of catalan numbers is approx , thus long long will overflow for n>32
kattis - fiat	Catalan Numbers	c++	Hidden catalan numbers.
UVa00495 - Fibonacci Freeze	Fibonacci Numbers	c++	Growth of Fibonacci approx. . Therefore, if n>64, we need bigint.
UVa00763 - Fibinary Numbers	Fibonacci Numbers	c++	Adding both numbers via Top-Down String processing method: Implement a method which can add a 1 at a specific index.
UVa10334 - Ray Through Glasses	Fibonacci Numbers	c++	Growth of Fibonacci approx. . Therefore, if n>64, we need bigint.
UVa10689 Yet Another Number Sequence	Fibonacci Numbers	c++	Fibonacci Numbers with Modulo, make use of Pisano-Period to reduce computation.
kattis - Batmanacci	Fibonacci Numbers	c++	The string size is still fibonacci long, so you can just simulate, where it will be after all.
kattis - Interesting Integers	Fibonacci Numbers	c++	Let x and y be the and , then the sequence woulde be: and hence the coefficients are again fibonacci. Therfore, for two consecutve fibonacci, find the coefficients s and t, s.t. . This again is a linear diophantine equation.
kattis - Ocean's Anti-11	Fibonacci Numbers	c++	Fibonacci with Modulo.
kattis - Riječi	Fibonacci Numbers	c++	Basic Fibonacci Problem
UVa01224 - Tile Code	Harder Combinatorics	c++	Count all possible and subtract all palindromes, then divide answer by two and add palindromes
UVa10784_- Diagonal	Harder Combinatorics	c++	Precalculate for each ngon for all possible n the number of diagonals. This is easy, as there are only two basic cases; n is even or odd
UVa11069 - A Graph Problem	Harder Combinatorics	c++	Basic DP
UVa11538 - Chess Queen	Harder Combinatorics	c++	Count all possibilties.
kattis - Anagram Counting	Harder Combinatorics	c++	Multinomial Coefficent and Bigint
kattis - Incognito	Harder Combinatorics	c++	Basic combinatorics
kattis - Kitchen Combinatorics	Harder Combinatorics	c++	Text and number of plates and ingridients hight, but eventually it is just basic combinatorics
kattis - Tri Tiling	Harder Combinatorics	c++	DP problem: dp[i][j] := how many ways you can end up in column i and use j to encode the missing pieces in the column i.
UVa11310_- Delivery Debacle	Simple Combinatorics	c++	New forms can be created by using last 4 (dp[i-2]) to create L shapes, you can use last 2 (dp[i-1]) to add two dots, you can use last 6 (dp[i-3]) to use two combined L shapes.
UVa11401 - Triange_Couting	Simple Combinatorics	c++	By taking two rods, check the condition for the 3rd rod.
UVa12463 - Little Nephew	Simple Combinatorics	c++	Basic combinatorics
Uva11597 - Spanning Subtree	Simple Combinatorics	c++	Basic combinatorics
kattis - Character	Simple Combinatorics	c++	Calculate binomical Coefficients with pascals' formula.
kattis - honey	Simple Combinatorics	c++	DP Problem; The difficulty is to get from the Honeycomb to a matrix
kattis - Integer Division	Simple Combinatorics	c++	Basic Combinatorics
UVa00350 - Pseudo Random Numbers	Cycle-Finding	c++	Floyd's Cycle-Finding
UVa11036 - Eventually Periodic Sequence	Cycle-Finding	c++	String processing + Floyd's Cycle-Finding
UVa11053 - Flavius Josephus Reload	Cycle-Finding	c++	Floyd's Cycle-Finding
UVa11511 - Freeze Patterns	Cycle-Finding	c++	freeze pattern will repeat very quickly -> do floyd's cycle detection on vectors
kattis - Fibonacci Cycles	Cycle-Finding	c++	Floyd's Cycle Finding on the fibonacci numbers with mod; Or simply use Pisano-Period
kattis - Happy Primes	Cycle-Finding	c++	Floyd's Cycle-Finding
kattis - Party Game	Cycle-Finding	c++	simulate problem
kattis - Rats	Cycle-Finding	c++	string processing
LA6808 - Best Position	Convolution	c++	String Matching with Wildcards. Flatten the 2D array and then and add wildcards to the query, such that it has the same length as a row.
atcoder - abc196F	Convolution	c++	Bitstring Matching. Match (1 and 1) and (0 and 0). 1 and 1 is easily matched by just the actual number 1. The multiplication then just add up to 1. For 0:0 we have to flip it and do it again.
kattis - aplusb	Convolution	c++	Calculate frequencies convolution (all possible sums). Here numbers can be negative, thus shift all of them to the right. Also take into account the number of times a number gets projected onto itself by 0 (a_i + 0 = a_i or 0 + a_i = a_i, which is not allowed as not distinct.
kattis - figurinefigures	Convolution	c++	With we get the freqs of all possible 4-pack weights. As it is only important to us whether this weight is possible ( frequency >=1 ) or not (frq ==0 ) and as numbers a quite big, we compute first and recude all values greate than 1 to 1.
kattis - golfbot	Convolution	c++	Basic convolution problem.
kattis - moretriangles	Convolution	c++	Complicated frequency convolution. For all a < n, calculate a^2(mod n) and add this to the frequency array. Afther this, do FFT-convultion 1 time and check if result itself is square (if it is in origin freq-array). Also, you need to take a<=b inta account: handle a==b separately and for the rest just divide by 2.
kattis - polymul2	Convolution	c++	Basic polynomial multiplication.
kattis - tiles	Convolution	c++	Complicated geometry + number-theory + convolution problem. The area A of a parallogram, which endpoints are all laying on the edges of a reactangle, can be coumputed by A=ac+bd. This can be seen as A = k + (A-k). Now for all k=1,...A-1 we have num_divs(k)*num_divs(A-k) possibilities. This is a normal convoltion formula, thus precalculate it once for all test-cases and then go through array to check for the answer.
UVa10111 - Find The Winning Move	Game Theory	c++	XXX
UVa10536 - Game Of Euler	Game Theory	c++	XXX
UVa11489 - Integer Game	Game Theory	c++	XXX
kattis - Bachets Game	Game Theory	c++	XXX
kattis - Block Game	Game Theory	c++	XXX
kattis - Cutting Brownies	Game Theory	c++	XXX
kattis - Euclids Game	Game Theory	c++	XXX
kattis - Irrational Divison	Game Theory	c++	XXX
kattis - Ivana	Game Theory	c++	XXX
kattis - Joyless Game	Game Theory	c++	XXX
kattis - Linije	Game Theory	c++	XXX
kattis - Multiplication Game	Game Theory	c++	XXX
kattis - PEG Game For Two	Game Theory	c++	XXX
UVa00820 - Internet Bandwith	Maxflow - standard	c++	Standard max flow, sink and target already given. Just compute max flow.
UVa11167 - Monkeys in the Emei Mountain	Maxflow - standard	c++	Assignment Problem: If allocation possible, if so, generate possible allocation.
UVa11418 - Clever Naming Patterns	Maxflow - standard	c++	Bipartite unweighted matching (MCBM): Numbers (A, B,...) to Problems. Titles are edges.
UVa12873- The Programmers	Maxflow - standard	c++	Normal max flow/assignment problem (people to sites).
kattis - Councilling	Maxflow - standard	c++	Assignment problem. Structure of network: source, clubs, persons, vertex restrictions(again persons), parties, sink.
kattis Jupiter Orbiter	Maxflow - standard	c++	Complex maxflow with back-coupling (to next time periods). Maxflow structure: source, sensortimes, queuestime (sum up previous and current), queues*time(vertex restriction: sum < cap), times (window restriction).
kattis - Maximum Flow	Maxflow - standard	c++	Normal Maxflow with edge extraction.
kattis - Maze Movement	Maxflow - standard	c++	Normal maxflow. Use GCD for checking the flow capacity.
kattis - Minimum Cut	Maxflow - standard	c++	Get left-partition of the Min-Cut: Dfs from source within resiudal-graph (over all non saturated edges).
kattis - Piano	Maxflow - standard	c++	Either use heap or Maxflow as it is an assignment problem (pianos to days). Important: MaxFlow problem become NP-hard if you need to add condition on edge to either use it to full capacity or not at all. E.g. piano needs to be delivered by two workers. However, these workes are not allowed to work on different days. If this is the case: try to model the problem differently. Here, we just use a weight of 1 instead of 2 and therfore the capacities of a single day by 2.
kattis - RA-Duty-Scheduler	Maxflow - standard	c++	Maxflow assignment problem. Note the description is not correct: The input days are not unique.
kattis - Tomography	Maxflow - standard	c++	Match rows with columns, from source to row capacity row_sum, from col to sink with capacit col_sum and in between add edges between specific col and row for each cell they share. Note: This Problem gets now TLE with Maxflow, use greedy heap instead.
kattis - Waif	Maxflow - standard	c++	Basic maxflow assignment problem.
kattis - Water	Maxflow - standard	c++	Normal maxflow, but with dynamic edges: either reset all graph and change capacity OR just add new edge to used graph and the result is the gained difference.
UVa00563 - Crimewave	Maxflow - Variants	c++	As nodes can only be used once, we are looking for independent paths: Each vertex has a capacity of 1. We connect all banks to be robbed to the source, and all frame-out of city nodes to the sink. Note, Vertex capacity of 1 also implise edge capacity of 1, so we can actually mess with their capacity, I set it to INF, but 1 would also be ok.
UVa11380 - Down Went The Titanic	Maxflow - Variants	c++	A pure maxflow modelling problem. Note we don't need to bother that maximal 1 person can be on the iceberg at the same time, as people can just stay at their previsous place as long as possible. Also note that each node has a vertex capacity, flaoting ice and persons have 1, wood and icebergs have INF
UVa11757 - Winger Trial	Maxflow - Variants	c++	Very creative geometric problem, given a field y_field x x_field, go from left to right with as few attackers possible. Therefore, let the bottom be the source, and the top be the sink. Build up the graph via the robotor nodes: Whenever two nodes intersect, then connect these in the mincut graph. Also all nodes which are at the bottom (y<=d) gets connected to source and all at the top (y>=y_field-d) get conected to sink. Note, you have to apply vertex capacity, as each robotor can only be used once: Now whenever you can can, connect source and sink, it is not possible to omit MinCut obstacles.
UVa11765 Component Placement	Maxflow - Variants	c++	Complicated min cut problem. Idea: Place bottlenecks of bottom and top components on opposite sides: Bottom elements have bottleneck towards the sorce and have INF capacity towards the sink. For Top elements vice versa. This set up alone will give us the cost for placing the elements when not considering the interconnection cost. Now an interconnection cost r can increase the min-cut(overall cost), iff connected with top and bottom elements: This way, we can use the INF part of either parts and thus increase by r. However, when the interconnection cost is in-between two components of the same side, then, the bottleneck will prevent an increase.
kattis - avoidingtheapocalypse	Maxflow - Variants	c++	Max flow with time. In order to also reflect the time constraint, create (s+1) nodes for each location at each given time stamp (Blow up each vertex). When passing a road, then we pass to the specific target node in the future.
kattis - Budget	Maxflow - Variants	c++	Create flows from row sums to col sums via cells. In order to properly model '>', '<' and '=' you need to construct 2 graphs. The first will take care of all mandatory flows ('=' and if > x, then you also need at least a flow of x+1). The remaining row-sums can be allocated/flowed via another graph. Note you can't take the same graph, as then the algorithm might revoke some must flows.
kattis - Chess Competition	Maxflow - Variants	c++	For each team, let it win all opcoming matches and for the remaining matches do a max-flow: source, teams, matches, sink. Where the edge from source to the other teams has the capacity of the difference towards your highscore (they can not make more points than you in total). Then each team is connected to its opcoming matches (with capacity 2). If the maxflow can assign all points from all remaining matches, then you can win still
kattis - Congest	Maxflow - Variants	c++	Firstly get rid of all edges which are not otpmial, which means, they would lead to a detour (use SSSP-algorithm). Then create a max flow problem. Each each has a capacity of 1. To deal with the fact, that a road could be used more than once at different times, we repeat the maxflow for each possible dinstance towards the downtown.
kattis - conveyorbelts	Maxflow - Variants	c++	Maxflow problem with time and modulo. Blow up each vertix k times (because we are interested in an always moving window of k; if a solution includes that product gets delivered at k+1, then it might be crashing with another product). Thus at each edge, deliver a product from t to (t+1) %k.
kattis - Cops And Robbers	Maxflow - Variants	c++	Basic min-cut problem, add a frame (outter world) and add vertex capacity to each node.
kattis - darkness	Maxflow - Variants	c++	Very interesting Mincut (not vertex but the edge version). A fence between two cells is an bidrectional edge between them. Then from each dark cell you need to find the mincut to the frame. Greedily circle around all dark cells doesn't work here, as you might have some bright cells inside the dark territory which you better not fence up (like en enclave). Make the frame the sink and connect each dark field to the source with capacity INF.
kattis - fakescoreboard	Maxflow - Variants	c++	Repeated maxflow: Frist route the row-sums to col-sums accordingly. Now in order to get the lowest lexicographical order, we want to set N as early as possible. Therefore, we go through the grid and see if the edge between rowsum i and colsum j has been activated. If so, we reset it 0 (here is the actual problem of this problem, we can't brueforce all n*m - times the max flow. We are only allowed to reset a specific edges in order to keep us from TLE). So find the right index of all contributing edges (so from source to row i, from row i to col j and from col j to sink) and subtract 1 from forward flow and add 1 to backward flow. Now try dinic again. If the result is 1, then the network found an alternative way activating any cell after the current cell (as all the others have already been fixed).
kattis - floodingfields	Maxflow - Variants	c++	The cows need to survive at each time stamp. Blow each gridcell up with time. Connect each cell at t with itself at t+1 and its neighbours at t+1 only if the target cell is not floated. Also add vertix capacity in order to secure, that only 1 cow can be there at a given time.
kattis - landscaping	Maxflow - Variants	c++	The most difficult max flow problem for me. Connect all down-fields with source and all up fields with sink, both with capacity B. Now connect each neighboud element with capacity A. Each cell can then cause only B trouble and has the task to give the reamining flow to its neighbours. Two cases for higher fields (WLOG also for lower): 1. Case: A higher field has less input flow than B, then transfer all of it to the sink (no changes) 2. Case: A higher field has more input flow than B, then the field takes B and allocates the remaining toward its neighbours. Lets assume we only have one high neighbour. case 2.1 Remaining to this high neighbour is more than A: Send only A. The equivalent is, that the current high field will be changed to low field. case 2.2 Remining to this neighbour is less than A: Send less than A. The equivalent is, that the current high field stays high field (Its not worth it, as changing to a lower field will not get rid of the border between the now low and the still high neighbour field.
kattis - marchofpenguins	Maxflow - Variants	c++	Repeated Maxflow problem
kattis - neutralground	Maxflow - Variants	c++	Basic min-cut with vertex capacity. A is connected to source and B to sink.
kattis - openpitmining	Maxflow - Variants	c++	Add up the weights of all positve blocks. Then subtract the costs of using these positive blocks. That is caclulated via maxflow: Each block with pos. weight w, can only caus costs <= w. So connect all positive blocks to the source with weight w. Then add edges towards the obstacles with INF. Finally, connect all neg blocks with weight z to the sink with capcaity -z. The maxflow will give you then the total cost of adding all positve blocks, limited be not negative for each block (or rather synergy of blocks).
kattis - thekingofthenorth	Maxflow - Variants	c++	Basic min-cut problem. Here each location comes with a vertex capacity, given by the amount of people needed to defend that place. Connection all neighbours up to the frame, will lead to a correct min-cut result. Note, when having vertex-capacities, you actually need to connect each vertex with all 4 neighbours. It is not sufficient to connect from top to bottom and left to right.
kattis - transportation	Maxflow - Variants	c++	Very basic assignment problem. Assign transport companies to delivery routes. As they can only deliver from at most one state to another, use vertex capcacity.
kattis - unfairplay	Maxflow - Variants	c++	MaxFlow problem, assign each team its max. points in order to still lose and check if flow equals the total match points. Then, a simple inside view into the used edges (get_used_backward_edges) of each match will tell us, the winner or loser (assignment problem).
UVa00481 - What Goes Up	DP - LIS	c++	Basic LIS with reconstruction.
UVa10534 - Wavio Sequence	DP - LIS	c++	Construct greedy LIS from left to right and from right to left (this equals LDS). Also, save for each number the current max increasing subsequence in a new vector. Then, greedily combine both and check where is the max.
UVa11790 - Muricia's Skyline	DP - LIS	c++	The normal greedy LIS in O(n*log(k)) here not possible as you can't override a previous higher building when it is wider. Therfore, just use the DP O(n^2) wher dpLIS[i] saves the comulated with if the sequence would end with the ith element
UVa_01196 - Tiling Up Blocks	DP - LIS	c++	Sort the PIIs in the first dimension (and also second dimension after that - also ascending, as not stricly increasing) and do LIS in the second. Then any subsequence is alwyas increasing (not strictly here) in first dimension. And by appliying LIS with the numbers of second dimension we find that subsequence which is increasing in both. As not strictly increasing, use upper_bound.
kattis - alphabet	DP - LIS	c++	Basis LIS problem.
kattis - increasingsubsequence	DP - LIS	c++	LIS lexicographic order. To find lexicographically smalles, adjust end if possible to further behind, bc then you have more chances to have chosen smaller in general (more selection, and the greedy algo always take the smallest, overwriting of bigger ones)
kattis - longincsubseq	DP - LIS	c++	Basic LIS with reconstruction (parent -vector)
kattis - manhattanmornings	DP - LIS	c++	2D LIS. Sort in both dimension (fst dimension then snd dimension). Here not strictly increasing in both dimension, therefore ASC in both (othewise snd dimension DSC). Apply LIS on second dimension, as first dimension is already save increasing (its sorted). As not strictly increasing: user upper_bound not lower_bound
kattis - nesteddolls	DP - LIS	c++	Complicated 2D LIS with multiset. Problem, we don't want to know the LIS, but the max. number of threads (or dolls, when as many smaller ones are in bigger ones). Consider each element in the multiset as a new thread. You can delete small doll-thread if you have a current bigger doll, as you can fit the smaller in the bigger one. However, you still insert a new thread (for the bigger one). Dolls need to be strictly bigger in both dimensions, thefore, sort ascending in first and descending in second.
kattis - studentsko	DP - LIS	c++	Find LIS, the elements which are not part of LIS need to be arranged. Issue: The order of within each team doesn't matter, so reset the talent of each student to its team-number, and then find LIS.
kattis - trainsorting	DP - LIS	c++	You can put the car on the front -> increasing subsequence order (LIS), or you can put it to the back -> decreasing subsequence order (LDS). Restriciton: All elements from LDS need to be lower than all elements in LIS. Solution: Let w* be the frontier-weight to put cars either to left or right, simply try all w* out and for each calculate LIS and LDS accordingly
UVa00787 - Maximum Subsequence Product	DP - Kadane	c++	Kadanes algorithm but keep track of two numbers, current-negative and current positive. If the overall result is 1, which is neutral element of multiplicaiton, then there are no positive elemnts >1 in array -> linear scan and find best single element. If elment is 0, restart from 1
UVa01105 - Coffee Central	DP - Kadane	c++	Complicated diagonal 2D-prefixsum. To test each field would timeout, as naive comes with , Note the window in WC is bigger than dx or dy. Better Idea: For each cell, we need to test a certain cube. These cubes are very much overlapping. However, the diagonal nature of these cubes make it difficult to precalculate sums. Therefore, rotate each cell by 45 degees, such that you have normal rectangles. Now you can calculate a 2D Prefixsum, which is NOT kadane. In kadane we would only prefixsum over each row and then 'kadende' over all possible l and r column combination. Here, however, we do not need to look at windows of variable size. The window-size is fixed, so each cell we get in with 2D Prefixsum, leading to overall
UVa10684 - The Jackpot	DP - Kadane	c++	Basic Kadane: Max range sum.
UVa10755 - Garbage Heap	DP - Kadane	c++	Prefixsum over the AB Planes for all C in , and then kadane over C for each rectangle size for in total in . Note: The result can't be empty: In Worst-Case, take the 'smallest' (from magnitude perspective) negative element.
kattis - alicedigital	DP - Kadane	c++	1D Kadane with two numbers: no_m and one_m. In no_m we count while not having encountered a single m, and in one_m we count only when we already have a m found. We reset when we find a number smaller than m (m needs to be minimum)
kattis - commercials	DP - Kadane	c++	Basic Kadane.
kattis - foldedmap	DP - Kadane	c++	There are only in total many possibilites to start with the first tile. These tiles == fixed window => 2D Prefixsum over the map and try all in
kattis - prozor	DP - Kadane	c++	Here the size of the rack is given, so: 2D prefix sum and then you can check each of the O(a*b) potential racket fields in O(1).
kattis - purplerain	DP - Kadane	c++	Kadane over two separate variables: The amount of R's and the amount of B's
kattis - sellingspatulas	DP - Kadane	c++	Very basic kadane. take care that the precision of the cout when printint the profit is correct.
kattis - shortsell	DP - Kadane	c++	Kadane over the Buying price, which must be as high as possible. Here, you also need to subtract the interest constantly.
UVa01213 - Sum of Different Primes	DP - Knapsack	c++	Knap sack with prime numbers as weight. As we can only have k items (and not as many as the weight allow), we need an additonal state.
UVa10130 - superSale	DP - Knapsack	c++	knapsack problem: dp[j] denotes the max value you can get having a weight of max j. Normally: dp[i][j] denotes the max value you can get having a weight of max j considering the first i objects, but this dimension is not really needed
UVa11566 - Lets Yum Cha	DP - Knapsack	c++	Knapsack with restrictions (only 2*n dishes) -> new state, also each dish can be used 2 times
UVa11832 - Account Book	DP - Knapsack	c++	Knapsack with offset and printing the solution. As the dp array is big in not all states are needed all the time, top-down would be better here.
kattis - knapsack	DP - Knapsack	c++	Basic Knapsack with solution retrieval
kattis - muzicari	DP - Knapsack	c++	It seems greedy, but in fact, it is a job-shop scheduling problem (np-hard), in which you want to minimise the makespan, s.t. it smaller/equal than T (duration of concert). If you take greedily, you might end up with 2 minutes left for both slots, but the last guy needs 4 miniutes of rest, which you can't split. Here: We do not need to minimise the make-span, only it hast to be lower than T. As there are only two pause-slots, the idea would be to utilize the first on as much as possible, s.t. the allocated pauses are in total <= T. We do this by knapsack-dp. Then we recover the solution, and all other dudes, will be assigned to the second slot.
kattis - ninepacks	DP - Knapsack	c++	Double Knapsack problem. Then, go trough all possible comulated weights in both dp (in last row), and minimise the sum over both
kattis - orders	DP - Knapsack	c++	Knapsack for reconstruction (without dimension reduction).
kattis - presidentialelections	DP - Knapsack	c++	Classical knapsack: items: states, weight: delegates, value to min.: votes
UVa00674 - Coin Change	DP - Coin Change	c++	Basic coin-change. It is very similar to knapsack, but we are not min./max. sth but, counting the possibilities. You need a dimension for the types (items in knapsack) and a state for current value (weight in knapsack)
UVa11259 - Coin Change Again	DP - Coin Change	c++	Very complex infinite coin-change with inclusion-exclusion. Instead of prohibitive finite-coin change (which would be if d1 = 10^5 and v = 10^5 -> 10^10). Instead: Infinite coin change and make use of inclusion/exlusion princible to account for overcounting. For example the possibility to have d1+1 times the c1 coin needs to be subtracted. The same for d2 + 1times the c2 coin. However, then you need to add again when you have both (d1+1) times c1 and (d2+1) times c2.
kattis - Bagoftiles	DP - Coin Change	c++	Basic coin-change dp + binomial coefficients
kattis - Canonical	DP - Coin Change	c++	Basic coin-change dp + check if greedy works
kattis - Exactchange2	DP - Coin Change	c++	Basic coin-change dp
UVa11795 - Mega Man's Mission	DP - TSP, Hamiltonian Paths	c++	Count all Hamiltonian Paths. Bitmask dp. dp[mask] := ways to kill the remaining robots in mask. Also here we are using 1 in the mask for 'has not been killed' because of LSOne();
UVa12841 - In Puzzleland	DP - TSP, Hamiltonian Paths	c++	Hemiltonian Path Problem. Find the lexicographically smallest solution, therefore, sort the bitmask, such that first bit(from right) stands for the smalles lexicographically value and when passing through the mask int the top-down held-karp algorithm we get the first set bit with LSOne, which automatically is the smallest possible lexicographically value for the current mask. Then just check if it is indead possible to go that way or abort. Also retrieve the solution afterwards.
kattis - beepers	DP - TSP, Hamiltonian Paths	c++	Travelling Salesman Problem: Mask only encodes the beepers (saving one bit), not the initial-position. Last encodes ALL positions, including the initial-position
kattis - bustour	DP - TSP, Hamiltonian Paths	c++	More suffisicated TSP. The first half of the hotels need to be also in the first half on way back. Try all combinations for n/2 hotels in the first half (on the way towards the destination); 18 choose 9 = 48K differnt masks. Now we need to split the round into 4 different paths: 1. First n/2 hotls on the way towards destination, 2. Second n/2 hotls on the way towards destination, 3. First n/2 hotls on return, 4. Second n/2 hotls on return. NOTE: In order to use memo, the destination of the current path always needs to be same. Here the roads are bidrectional, so we structure the four paths in that way, that the destination is alywas either the start 0, or the destination n-1. NOTE: A good way to get permutations: use permutations of an 0-1 vector.
kattis - cycleseasy	DP - TSP, Hamiltonian Paths	c++	Basic TSP Problem
kattis - errands	DP - TSP, Hamiltonian Paths	c++	Basic hamiltonian path.
kattis - maximizingyourpay	DP - TSP, Hamiltonian Paths	c++	Find greatest hamiltionian cycle. Try all possible masks and check if there is a hamiltionian cycle. Note, we don't need to minimise anything, just possible or not possible to visit all.
kattis - pokemongogo	DP - TSP, Hamiltonian Paths	c++	TSP Problem: Catch all unique pokemons and return to initial place. Problem: A pokemon can appear more then once. Try all masks and continue if the mask contains a pkm more than once or 0 times.
kattis - race	DP - TSP, Hamiltonian Paths	c++	Hamiltionian Path Problem with deadline-restrictions on each node: Try all potential mask: If it is possible to have hamiltoninan path, save its value and go to next mask
UVa10003 - Cutting Sticks	DP - Level 1	c++	Classical log cutting dp.
UVa10912 - Simple Minded Hash	DP - Level 1	c++	Basic dp with three states. dp[i][j][k] possibilities, after ith letter, after j letters in total used and got a hash of k
UVa11420 - Chest Of Drawers	DP - Level 1	c++	dp[i][j][k] := possibilities after the ith drawer(from above), which is unlocked(k=0)/locked(k=1) and after already having j secure drahers
UVa13141 Growing Trees	DP - Level 1	c++	Fibonacci like dp
kattis - keyboardconcert	DP - Level 1	c++	Basic dp
kattis - nikola	DP - Level 1	c++	dp[i][j] the min entry fee, to get to square i, whereas the last jump has been of size j
kattis - permutationdescent	DP - Level 1	c++	Difficult dp + permutation. States: Order of the current permutation and the Descents already incorprated. Now, when increasing the order of the permuation, you have the biggest number of the hole sequence at your disposasl: 1. Not inceasing the number of descents. Therefore add the new number at the end or in an already existing descent. 2. Incease the number of descents and add number at the beginning or not in an already existing descent
kattis - spiderman	DP - Level 1	c++	dp with reconsruction of solution. dp[i][j] := min building size after processing the ith training part and are at pos j;
kattis - ticketpricing	DP - Level 1	c++	dp[i][j][0] := max price after the ith week for j seats.
kattis - weightofwords	DP - Level 1	c++	Coin change, possibility check. Restriction: n the number restriction (additional dimension). Note the same letter can be used multiple times -> infinite coin-change
kattis - wordclouds	DP - Level 1	c++	This dp requires top-down, only few states are actully computed. Even coming up with a complete memo array of 5000x1000x150 would be too large. Take a map as memo instead and use vector as state.
UVa12324 - Philip J Fry Problem	DP - Level 2	c++	Basic Top-Down
UVa12862 - Intrepid Climber	DP - Level 2	c++	DFS problem. Before we go to a certain child and add the cost towards it, wee need to know wether there is indead a friend in this subtree. As the hasSubtreeFriend function is maybe called often, we will memo it.
UVa12955 - Factorial	DP - Level 2	c++	As each factorial is a multiple of the smaller factorials, it is ok to greedily take the biggest factorial which fits into the current number. There is no advantage of skipping one factorial just to see if the next one yield an overall better result. As there are many test-cases: Use memo.
kattis - debugging	DP - Level 2	c++	Top-Down DP. dp[n] The worst case time, when having n lines. At each state we try all possible printfs. Note when putting printf, you want them evenly distributed to minmise worst case. Take ceil(n/(printfs+1)) for the next state.
kattis - drivinglanes	DP - Level 2	c++	Classic dp problem.
kattis - kutevi	DP - Level 2	c++	Just complete all possible values with a dfs and save values in a memo, such that query is fast.
kattis - tight	DP - Level 2	c++	Simple dp. Similar to digit dp. Chose double as the solution might be very big.
kattis - walrusweights	DP - Level 2	c++	Basic subset-sum
kattis - watersheds	DP - Level 2	c++	Rather a dfs than a dp excersie.
UVa10090 Marbles	Extended Euclidean	c++	Basic Linear Diophantine Equation.
UVa10104 - Euclid Problem	Extended Euclidean	c++	Compute Bézout's coefficients.
UVa10633 - Rare Easy Problem	Extended Euclidean	c++	Hidden Linear Diophantine Equation Problem: We can write . If we denote c = n-m, then our equation is .
UVa10673 - Play with Floor and Ceil	Extended Euclidean	c++	Basic Linear Diophantine Equation.
kattis - candydistribution	Extended Euclidean	c++	Compute Inverse with Extended Euclidean with complicated edge cases. There are k kids and c candys per bag. Buy as many bags, s.t. you can distribute the candies fairly and have one over. Thus . Therefore, goal find: . Also possible: Linear Diophantine Equation.
kattis - jughard	Extended Euclidean	c++	Hidden Linear Diophantine Equation. Let jug one have a capacity of a and jug tow a capacity of b. You need to arrive at a level of c in one of the jugs. Thus by adding or subracting the levels we have the equation . Now, if c is divisiable by the GCD of a and b, then this linear diophantine equation has a solution (infinite).
kattis - modulararithmetic	Extended Euclidean	c++	Basic Modular Arithmetic. Use euclidean algorithm to compute the inverse.
kattis - soyoulikeyourfoodhot	Extended Euclidean	c++	Linear Diophantine Equation. Make doubles to integers by upgrading them to bigger numbers.
kattis - wipeyourwhiteboards	Extended Euclidean	c++	Linear Diophantine Equation.
UVa11228 - Transportation System	Graph - MST	c++	basic MST problem.
UVa11631 - Dark Roads	Graph - MST	c++	basic MST problem.
UVa11747 - Heavy Cycle Edges	Graph - MST	c++	basic MST problem.
kattis - cats	Graph - MST	c++	basic MST problem.
kattis - communicationssatellite	Graph - MST	c++	Hidden MST problem, note that the no crossing beams criteria is won't be avoided by the MST anyway (because then another satellite would be closer).
kattis - drivingrange	Graph - MST	c++	MST MiniMax problem with checking if exist a MST ( single forrest == only one union set left ).
kattis - reckles	Graph - MST	c++	Basic MST problem.
kattis - islandhopping	Graph - MST	c++	Basic MST problem.
kattis - jurassicjigsaw	Graph - MST	c++	Basic MST problem.
kattis - lostmap	Graph - MST	c++	Basic MST problem.
kattis - minspantree	Graph - MST	c++	basic MST problem with checking if exist a MST (single forrest == only one union set left).
UVa01013 - Island Hopping	Graph - MST (Variants)	c++	MST MiniMax problem. Crate the MST MiniMax Graph and then dfs through it to calculate the average connecting time
UVa01265 - Tour Belt	Graph - MST (Variants)	c++	Advanced variant of maximum spanntree. Sort edges in decreasing order. In DJU save minimum inside-edge weight over all edges already connected to same tree at parents side.
UVa10048 - Audiophobia	Graph - MST (Variants)	c++	MST MiniMax problem. As there are many queries, prepocess APSP with Floyed-Warshall
UVa10457 - Magic Car	Graph - MST (Variants)	c++	MST variant. The answer is the the maxWeight minus the minWeight of all edges used to get from start to end. Use each edge as the starting point of a MST O(E^2)
kattis - arcticnetwork	Graph - MST (Variants)	c++	Minimum Spanning Forrest Problem. When there are as S satalite stations, leave S forrests in the kurstal datastructure. The first one will send, for each other, you can have another Forrest.
kattis - firetrucksarered	Graph - MST (Variants)	c++	Basic Disjoint Union Datastructure
kattis - inventing	Graph - MST (Variants)	c++	Mimicing MST via Kruskal. For each added edge with Weight c, add l edges of weight c+1, where l is the (size of component 1 multiplied with size of component 2). Also subtract one, as for the actual edge, which is part of MST.
kattis - landline	Graph - MST (Variants)	c++	MST with some restrictions. First process all secure edges afterwards all edges, which have exactly one insecure endpoint
kattis - naturereserve	Graph - MST (Variants)	c++	MST Prim algorithm. When starting from several starting points, prim algorithm might be beneficial
kattis - redbluetree	Graph - MST (Variants)	c++	Compute two MST. One with the fewest blue edges and one with the largest amount. If k leys in between them, we are ok.
kattis - spider	Graph - MST (Variants)	c++	1. Create MST O(E log E), 2. DFS over MST to get the max distane between any two nodes O(V^2), 3. Go trough all edges again and see subtract the current edge and add the maxEdge insde mst between them O(E)
kattis - treehouses	Graph - MST (Variants)	c++	Basic MST problem with already connected components (Minimum Spanning Subgraph). Here already connected via open land or cables.
UVa00200 - Rare Order	Graph - Topological Sort	c++	More advanced topological sort problem. Convert the given list of words into a adjacency list and then use topological sort to find the order of the alphabet
UVa00872 - Ordering	Graph - Topological Sort	c++	Backtracking. All possible alphabet orders given the contraints with backtracking. The topological order was controlled by indegree here, as it is more flexible
UVa11060 - Beverages	Graph - Topological Sort	c++	Basic Topological Sort.
kattis - brexit	Graph - Topological Sort	c++	Similar to topological sort: Modified kahn algorithm. Use indegree for to count the current remaining partnerships.
kattis - brexitnegotiations	Graph - Topological Sort	c++	Advanced Topological Sort: To minimise the maximum meeting time, do the topological sorting from behind and always add the current smallest available meeting. The still big offset will therefore be added to the smallest possible values.
kattis - builddeps	Graph - Topological Sort	c++	Topological sort. Convert strings to indicies. Also here we need to take a look at the reversed dependency graph ('comes before / is part of' rather than 'depends on')
kattis - collapse	Graph - Topological Sort	c++	Bacic topological sort. Here: We don't care about the in-degree, but about whether island collapsed (has enough income)
kattis - conervation	Graph - Topological Sort	c++	Topological order with kahn-algorithm to give priority to the same lab and not transport. Not that, we have to run the algorithm two times. Once, for the first lab to begin, and once for the second lab to begin.
kattis - digicomp2	Graph - Topological Sort	c++	Actually just a dfs problem, but in order to decrease computation, we only want to compute a vertex when its indegree==0. Therefore we use the topological order within the Kahns algorithm.
kattis - easyascab	Graph - Topological Sort	c++	Topologic Sorting with some pitfalls
kattis - grapevine	Graph - Topological Sort	c++	Topological sort, but instead of in-degree, use the Skepticism.
kattis - managingpackaging	Graph - Topological Sort	c++	Topological Sort with cycle check. Use Kahn algorithm to prefere lexicographically smaller strings
kattis - pickupsticks	Graph - Topological Sort	c++	Basic Topologial Sort
UVa10004 - Bicoloring	Graph - Bicoloring/Cycle-Check	c++	Basic bipartite graph check. Use dfs and check if adjacent color is ok if exist.
UVa10116 - Robot Motion	Graph - Bicoloring/Cycle-Check	c++	Easy cycle check. In the implicit graph there is always only one way (forward edges are not possible. Hence it is sufficient to check if the next grid element has been already visited to find a cycle;
UVa10505 - Montesco vs Capuleto	Graph - Bicoloring/Cycle-Check	c++	For each connected compontents, check if it is bipartite and then get the max partition of it (left or right) and add it to the result.
kattis - amanda	Graph - Bicoloring/Cycle-Check	c++	Bi-coloring problem: First do all certain vertexes (no airport at either edge or both has to be airports). For the remaining connected components: normalal bicoloring
kattis - ballsandneedles	Graph - Bicoloring/Cycle-Check	c++	3D cycle detetcion and 2D cycle detection. Note that due to the loss of a dimension, some cycles (in height) are not longer cycles, and some none-cycles (because of differences in height) might have become cycles.
kattis - breakingbad	Graph - Bicoloring/Cycle-Check	c++	Basic bicoloring problem.
kattis - hoppers	Graph - Bicoloring/Cycle-Check	c++	bipartite + connected components. Of all components you need at least one non-bipartite network, which can be used to reach all left and right sides of all the other networks (if you add a single edge for each of the other networks).
kattis - molekule	Graph - Bicoloring/Cycle-Check	c++	First Observation: N molecuels, all connected with N-1 edges -> tree. Then we can reduce the longest path within the tree always to 1 by creting a level graph (or bi-coloring) and always direct the edge towars the color 0 (or 1, if you like)
kattis - pubs	Graph - Bicoloring/Cycle-Check	c++	Weak bicoloring (do not check if neihbours have same color). Not possible iff a connected component consists of only one node
kattis - runningmom	Graph - Bicoloring/Cycle-Check	c++	Basic cycle check. Let the dfs return true if you find a backward edge.
kattis - torn2pieces	Graph - Bicoloring/Cycle-Check	c++	Basic bfs with retrieving solution (parents array)
UVa00315 - Network	Graph - Articulation Points/Bridges	c++	Basic Articulation Points.
UVa10765 - Doves and Bombs	Graph - Articulation Points/Bridges	c++	Articulation points problem with counting at each articulation points the number of different connected components if the current vertex would be removed
UVa12363 - Hedge Mazes	Graph - Articulation Points/Bridges	c++	Articulation Bridge Problem. Task here: Check if there exist exactly ONE simple path (All vertexes used at max one time). We can reduce this problem to a graph of only articulation bridges. If at some point we would take a non-articulation bridge, that means, that there is also an other corridor. Hence: The simple path is not unique.
UVa12783 - Weak Links	Graph - Articulation Points/Bridges	c++	Finding all articulation bridges.
kattis - birthday	Graph - Articulation Points/Bridges	c++	Basic finding atriculation bridges
kattis - caveexploration	Graph - Articulation Points/Bridges	c++	For each articulation bridge get the number of nodes connected to it
kattis - intercept	Graph - Articulation Points/Bridges	c++	Find articultion point on the SSSP DAG (apply dijstra two times from start and from end, then use once more dijstra and go from start to all points where dist[end] == dist[x] + distReversed[x]. In final dijkstra, a node is an articulation point, if after poping it from the queue, there is no other node in the queue
kattis - kingpinescape	Graph - Articulation Points/Bridges	c++	Complicated matching of leaves. One has to think a lot on how to connect the leaves in order to minimise the tunnels. Here it turns out to get the leaves within an inorder traversa and then connect them with an offset (half)
UVa00247 - Calling Circles	Graph - Strongly Connected Components	c++	Strongly connected components. Here with retrievel of solution.
UVa11709 - Trust Groups	Graph - Strongly Connected Components	c++	basic count of different SCC
UVa11770 Lighting Away	Graph - Strongly Connected Components	c++	SCC problem. Reduce the ssc to one node and then count all nodes with indegree==0
UVa11838 - Come and Go	Graph - Strongly Connected Components	c++	Count Strongly Connected Components.
kattis - cantinaofbabel	Graph - Strongly Connected Components	c++	Get the biggest SCC and dismiss the rest
kattis - dominos	Graph - Strongly Connected Components	c++	Reduce all strongly connected components to one node each. In this reduced graph find all nodes with inDegree == 0
kattis - equivalences	Graph - Strongly Connected Components	c++	Make directed Graph strongly Connected: 1. Reduce Graph by all its SSC (merge to one node, 2. Count nodes for which inDegree==0 and analogously for outDegrees, 3. The answer is the max of both
kattis - loopycabdrivers	Graph - Strongly Connected Components	c++	Reporting all SCC in a formatted way
kattis - reversingroads	Graph - Strongly Connected Components	c++	Check if graph is SCC. If not, brute-force all edges and flip them and for each check again, if graph is SCC. It might be easier with an AM instead of an AL.
kattis - test2	Graph - Strongly Connected Components	c++	Find all SCC and format the answer.
UVa00336 - A Node Too Far	Graph - Unweighted Shortest Path	c++	Unweigted SSSP: basic level bfs
UVa10653 - Bombs No They Are Mines	Graph - Unweighted Shortest Path	c++	Unweigted SSSDSP: basic 2D level bfs
UVa11352 - Crazy King	Graph - Unweighted Shortest Path	c++	Unweigted SSSDSP: basic 2D level bfs.
UVa11792 - Krochanska Is Here	Graph - Unweighted Shortest Path	c++	Unweigted SSMDSP: For all important station do a level bfs, and get the one with lowest average
UVa12160 - Unlock The Lock	Graph - Unweighted Shortest Path	c++	Unweigted SSSDSP: basic level bfs
UVa12826 - Incomplete Chessboard	Graph - Unweighted Shortest Path	c++	Basic unweighted SSSP: Level bfs
kattis - beehives2	Graph - Unweighted Shortest Path	c++	Task translated: Find the smallest non-trival cycle. BFS from each node and once you find a node, which you have already seen: add up the distances.
kattis - buttonbashing	Graph - Unweighted Shortest Path	c++	Basic bfs problem. Note: DP not possible as you jump forward and backward (-> bfs indicator)
kattis - conquestcampaign	Graph - Unweighted Shortest Path	c++	Unweigted MSSP: basic level 2d bfs
kattis - dungeon	Graph - Unweighted Shortest Path	c++	Basic unweighted SSSP.
kattis - elevatortrouble	Graph - Unweighted Shortest Path	c++	Unweigted SSSDSP: basic level bfs
kattis - erdosnumbers	Graph - Unweighted Shortest Path	c++	Basic sssp, here I choose again with queue and dis array.
kattis - erraticants	Graph - Unweighted Shortest Path	c++	Unweigted SSSDSP: 2D level bfs. Here the paths of the ants needs to be modelled into a graph (assume a 201x201 grid as there max 100 directions and reconstruct AL)
kattis - fire2	Graph - Unweighted Shortest Path	c++	SSMDSP Problem, here with two types: Fire type 1 and you type 0. Type 1 will always be the first to propagate and then only type 2 can go ahead. If you meet a border: Stop
kattis - fire3	Graph - Unweighted Shortest Path	c++	Same as fire2
kattis - grasshopper	Graph - Unweighted Shortest Path	c++	Basic unweighted SSSP.
kattis - grid	Graph - Unweighted Shortest Path	c++	Basic 2d level bfs (SSSDSP)
kattis - hidingplaces	Graph - Unweighted Shortest Path	c++	Basic unweighted SSMDSP
kattis - horror	Graph - Unweighted Shortest Path	c++	Unweigted MSSP: basic level bfs
kattis - knightjump	Graph - Unweighted Shortest Path	c++	Basic unweighted SSMDSP
kattis - landlocked	Graph - Unweighted Shortest Path	c++	SSSP with 0/1 weights. With deque and also with distance vector instead of level bfs. Push free-element to front else to back. Note: It works exactyly like Dijkstra, but faster.
kattis - lava	Graph - Unweighted Shortest Path	c++	Basic SSSDSP, but there are O(n^2) adjacent fields, but only 1000 potential fields -> Don't check all adjacent fields but all potential fields
kattis - lost	Graph - Unweighted Shortest Path	c++	Unweigted SSSP: basic level bfs. However, here at each level we need to prefer the lower cost variant. Or other way: Of all possible bfs spanning trees, take the minimum cost version
kattis - mallmania	Graph - Unweighted Shortest Path	c++	Basic MSSP.
kattis - oceancurrents	Graph - Unweighted Shortest Path	c++	SSSP with 0/1 weights with Deque
kattis - onaveragetheyrepurple	Graph - Unweighted Shortest Path	c++	Unweigted SSSDSP: basic level bfs. Here the solution of the max color changes is shortestPath - 1
kattis - showroom	Graph - Unweighted Shortest Path	c++	SSSP with 0/1 weights. With deque and also with distance vector instead of level bfs. Push door-element to front else to back.
kattis - sixdegrees	Graph - Unweighted Shortest Path	c++	Muliple SSMDSP Problem: Brute Force Try all IPs and check if they can reach all otheres in 6 steps
kattis - slikar	Graph - Unweighted Shortest Path	c++	Same as fire2 and fire3
kattis - spiral	Graph - Unweighted Shortest Path	c++	Unweigted SSSDSP: Level bfs. Major Problem: The bfs works on the 1D number, but to know which other number is adjacent to it, we need to recunstruct the Prime Spiral and alongside a mapping from number to coordinates and coordintes to number.
katt - wettiless	Graph - Unweighted Shortest Path	c++	BFS Problem.
kattis - zoning	Graph - Unweighted Shortest Path	c++	MSMDSP Problem: Put all commercial zones into the queue with distance 0. Then for all Residential zones check the distances
UVa00589 - Pushing Boxes	Graph - Weighted Shortest Path	c++	Advanced unweighted SSSP Problem with simultanoues states (you and box). Here however we need to use a priority_queue (like in weighted shortest paths problems) to prefer pathes with fewer pushes/smaller path length. If we have seen a state (my position + box postion) we don't need to recompute it, as we were there already with smaller pushes or smaller path length.
UVa01112 - Mice And Maze	Graph - Weighted Shortest Path	c++	SSSP idea: Always take the next node with minimial distance.
UVa10986 Sending Email	Graph - Weighted Shortest Path	c++	Basic weighted SSSP.
UVa12047 - Highest Paid Toll	Graph - Weighted Shortest Path	c++	Weighted SSSP. To see if an edge is part of a path which cost in total no more than p, we can perform dijkstra from left and from right. For each edge a->b we have now the lowest cost to go to s->a dist[s][a] and b->t dist[b][t]. Now simply check if this added up plus the weight is still smaller than p.
UVa12950 - Even Obsession	Graph - Weighted Shortest Path	c++	Basic weigted SSSP + add even/odd state.
kattis - backpackbuddies	Graph - Weighted Shortest Path	c++	For both Mr. Day and Mr. Knight do a weighted SSSP (Dijkstra). Within the Dijkstra add the restrictions.
kattis - blockcrusher	Graph - Weighted Shortest Path	c++	Weigted MSMDSP + parent reconstruction. Note: Graph is no DAG, (you can also go up/left/rigth..) so no DP possible. But weighted MSMDSP problem -> Dijkstra
kattis - detour	Graph - Weighted Shortest Path	c++	Weighted SSSP: From the end node apply dijkstra and record all paths taken. These are fordbidden to use in a normal dfs from start to end.
kattis - emptyingbaltic	Graph - Weighted Shortest Path	c++	Weighted SSSP. Go from drainer and spread the negative attitude. Only works with faster_dijkstra
kattis - firestation	Graph - Weighted Shortest Path	c++	Weighted MSSP Problem. As the number of nodes and edges are quite low, we can run dijkstra for each node (and also include all the existing stations) and see which node comes with the minimal max. distance
kattis - flowerytrails	Graph - Weighted Shortest Path	c++	Weighted SSSDSP. To know whether a node is part of the the shortest path: Run dijstra twice from end and start, then the destFromStart + destFromEnd == destTowardsDest. To check if en edge is part of the graph: Check if both nodes are part of the shortest path + check if the weight difference is matching
kattis - forestfruits	Graph - Weighted Shortest Path	c++	Weighted SSSP. Sort the dist-array and only inlcude the clearings.
kattis - fulltank	Graph - Weighted Shortest Path	c++	Weighted SSSDSP Problem. Main Issue: Model the graph that dijkstra can minimize the cost for the fuel. Blow the distance graph to a state-space graph which also includes the fuel capacity at the current node. Most important takeaway: Once you reach your destination, break in order to keep the timelimit
kattis - george	Graph - Weighted Shortest Path	c++	Basic weighted SSSDSP. Dijsktra + extra waiting time restriction at each node
kattis - getshorty	Graph - Weighted Shortest Path	c++	Basic weighted SSSP
kattis - gruesomecave	Graph - Weighted Shortest Path	c++	Weighted SSSDSP. Main Problem is to get the probability for each field: It is sufficient to add +1 to each vacant adj field if you are at a vacant field already. Meaning there is one way to go to this field. Then just dividing by all the sums and you have the probability of being in a certein vacant field
kattis - hopscotch50	Graph - Weighted Shortest Path	c++	DP: O(n^4) = O(2.5KK) for each level check the prior level. Smart traversal though. Alternative: Create level graph and do Disjkstra. O(E) = O(n^4) -> Dijkstra O(E * log(V))
kattis - invasion	Graph - Weighted Shortest Path	c++	Weighted MSSP Problem. For each added Alien station, just apply Dijkstra(with multiple sources) once more and also keep the dist-array globally
kattis - passingsecrets	Graph - Weighted Shortest Path	c++	Weighted SSSDSP. Major issue is converting the names. With Reconstruction.
kattis - shoppingmalls	Graph - Weighted Shortest Path	c++	Basic weighted SSSP with Reconstruction of a single shortest path.
kattis - shortestpath1	Graph - Weighted Shortest Path	c++	Basic SSSP
kattis - shortestpath2	Graph - Weighted Shortest Path	c++	Basic weighted SSMDSP. Dijsktra + extra waiting time restriciton at each node
kattis - subway2	Graph - Weighted Shortest Path	c++	Weighted SSSDSP: Basic Dijkstra, with some tedious distances.
kattis - texassummers	Graph - Weighted Shortest Path	c++	Weighted SSSP with Reconstruction (use parent array). Use fast Dijkstra
kattis - tide	Graph - Weighted Shortest Path	c++	Weighted MSSDSP Problem. Major Problem are the many restrictions.
kattis - visualgo	Graph - Weighted Shortest Path	c++	A modifed dijsktra to get the total number of shortest paths
kattis - wine	Graph - Weighted Shortest Path	c++	Very advanced Subset-Sum/Knapsack with reducing the search-space. Alternative: PQ/Dijkstra with reducing the search-space (I dont feel it is fitting here, but in CP4 its recommended as weighted shortest path. However, I think it is faster, as we just compute selected/needed elements and do not go over all elements like in knapsack)
UVa00558 - Wormholes	Graph - Shortest Path with neg. Cycle	c++	Here only n loops are neccesary until bellman ford terminates, IF there are no negative cycles. We do one more to check if we can still improve (what means that there is a cycle)
UVa10449 - Traffic	Graph - Shortest Path with neg. Cycle	c++	Negative Cycle Detection
UVa12768 - Inspired Procrastination	Graph - Shortest Path with neg. Cycle	c++	Change Signs of Weights. If we take the weights as negative weights, then we want to minimize the distance from node 0 -> this is a normal SSSP problem. However, there could be negative cycles. Therefore, instead of dijkstra, take bellmann_ford, to detect them.
kattis - crosscountry	Graph - Shortest Path with neg. Cycle	c++	Weighted SSSP. Normal Dijkstra, but Bellmann_ford would also work.
kattis - hauntedgraveyard	Graph - Shortest Path with neg. Cycle	c++	Weighted SSSP Problem with negative cycles. Here I use Bellmann-Ford to detect negative cyles. Within Bellmann-Ford, when you are at the end field, you continue (some restrictions), and you do not go the adjacent fields. + Prunning
kattis - shortestpath3	Graph - Shortest Path with neg. Cycle	c++	Negative Cycle Detection
kattis - xyzzy	Graph - Shortest Path with neg. Cycle	c++	Bellmann Ford SSSP with negative cycles with restrictions + sign change of weights
UVa00821 - Page Hopping	Graph - APSP	c++	Basic All-Pairs-Shortest-Path, Floyed Marshall.
UVa00869 - Airline Comparison	Graph - APSP	c++	Basic ASAP - transitive closure problem. For both graphs run boolean floyed-warshall to see if it is possible to go from i to j and compare both for differences.
UVa01056 - Degrees Of Separation	Graph - APSP	c++	Basic ASAP problem to get the diameter (max shortest path between any pair) of a graph.
UVa01247 - Interstar Transport	Graph - APSP	c++	Weighted APSP (Floyd-Warshall) + Retrieval of solution.
UVa10342 - Always Late	Graph - APSP	c++	Second Shortest Path between a lot of pairs: APSP Problem. Precalculat the shortest path between all pairs and then, for each query go through each node and try to make a little error and save the best not best resuls. Note, optimal subpaths AM[a][i] + AM[i][b] can often be used when the problem involves shortest paths with some restrictions
UVa10987 - Antifloyd	Graph - APSP	c++	APSP Problem: Check if the distances between two nodes can be improved -> wrong messaurements. Else run another Floyd-Warshall and see if you can make a detour without increasing the distance. If so, delete this edge.
UVa11463 - Commandos	Graph - APSP	c++	APSP problem: As n is low (<=100), we can compute APAS with Floyd-Warshall and just get the shortest path from start to each other node and then further from that specific node to the end node
kattis - allpairspath	Graph - APSP	c++	Basic APSP + neg. cycle detection: If there is one k such that there is a path from i to k and from k to j and also AM[k][k] < 0, then we can make the way from i to j infinietely small.
kattis - arbitrage	Graph - APSP	c++	APSP Problem. If you can find a path from one currency to itself such that that you have to pay less than 1 to get 1 unit of it, you have arbitrage. Note, here we work with multiplication instead of addition.
kattis - assembly	Graph - APSP	c++	Transitive Closure connectivity check (Floyd-Warshall). If we can reach the same connector label we are unbound.
kattis - hotels	Graph - APSP	c++	Advanced APSP Problem. Here the ASAP are between elevators. Therefore we get all possible reachable levels together with the specific elevaor reaching this level. Instead going over all possible pairs of reachable levels, we can make use of the transitive nature of Floyed-Warshall: Sorting the reachable levels vector and going over within a linear scan to check if for two adj entries, the elevators connection within the AM can be improved (TRANSITIVE NATURE) This however, is just the initial distance. We now need to run Floyed-Warshall on this to get the APSP. Learned: In floyed-warshall the inital AM do not need all start-values as long these can be build by the principe of transitivity
kattis - importspaghetti	Graph - APSP	c++	Finding shortest cycles with Floyd-Warshall by checking all AM[i][i]. + Reconstruction of solution
kattis - isahasa	Graph - APSP	c++	Advanced transitive closure problem (Floyd-Warshall). For is-A relation it is a basic transitive closure. For the has-A relation on the other hand, we carefully need to construct the inital AM matrix, such that Floyed-Warshall can reconstruct the whole transitive relation. Therefore: we set all normal hasA, all detours over isA (isA->hasA), and also all hasA of these (isA -> hasA -> hasA) in the initial matrix.
kattis - kastenlauf	Graph - APSP	c++	Basic transitive closure problem.
kattis - secretchamber	Graph - APSP	c++	Frequent check if a path from char a to char b exist -> Warshall's transitive closure.
kattis - slowleak	Graph - APSP	c++	Hidden ASAP Problem. Model a new graph where you can only go from repair to repair stop (or home/school) by using Floyd-Warshall
kattis - transportationplanning	Graph - APSP	c++	APSP Problem. To get the commute time, we need the shortest path between all intersections and then smartly use these optimal sub-paths AM[i][b] + AM[a][j] + roadLength.