00100 |
Fetching from uHunt |
5.2b, Math Simulation, Easier |
simply do as asked; the only trap is that j can be < i |
00101 |
Fetching from uHunt |
non-starred |
stack-like simulation; but we need to access the content of each stack too; so it is better to use 2D array |
00102 |
Fetching from uHunt |
3.2a, Iterative (One Loop) |
try all 6 combinations |
00103 |
Fetching from uHunt |
non-starred |
longest paths on DAG; backtracking OK |
00104 |
Fetching from uHunt |
non-starred |
small arbitrage problem solvable with Floyd Warshall's |
00105 |
Fetching from uHunt |
non-starred |
height map; sweep left-right |
00106 |
Fetching from uHunt |
non-starred |
brute force; use GCD to get relatively prime triples |
00107 |
Fetching from uHunt |
non-starred |
use logarithm; power |
00108 |
Fetching from uHunt |
3.5b, Max 2D Range Sum |
max 2D range sum |
00109 |
Fetching from uHunt |
non-starred |
find CH; test if point inPolygon; compute area of polygon |
00110 |
Fetching from uHunt |
non-starred |
actually an ad hoc sorting problem |
00111 |
Fetching from uHunt |
non-starred |
be careful of the ranking system |
00112 |
Fetching from uHunt |
non-starred |
backtracking |
00113 |
Fetching from uHunt |
non-starred |
use exp(ln(x)*y) |
00114 |
Fetching from uHunt |
non-starred |
simulation of pinball machine |
00115 |
Fetching from uHunt |
non-starred |
tree traversal to determine relationships between vertices |
00116 |
Fetching from uHunt |
non-starred |
similar to UVa 10337 |
00117 |
Fetching from uHunt |
non-starred |
Euler tour; get cost of tour |
00118 |
Fetching from uHunt |
non-starred |
traversal on implicit graph |
00119 |
Fetching from uHunt |
non-starred |
simulate the give and receive process |
00120 |
Fetching from uHunt |
non-starred |
pancake sorting; greedy version |
00121 |
Fetching from uHunt |
non-starred |
use Pythagorean theorem; grid |
00122 |
Fetching from uHunt |
non-starred |
tree traversal |
00123 |
Fetching from uHunt |
non-starred |
modified comparison function; use sort |
00124 |
Fetching from uHunt |
non-starred |
use backtracking to generate valid toposorts |
00125 |
Fetching from uHunt |
non-starred |
modified Floyd Warshall's |
00126 |
Fetching from uHunt |
non-starred |
polynomial multiplication and tedious output formatting |
00127 |
Fetching from uHunt |
non-starred |
shuffling stack |
00128 |
Fetching from uHunt |
non-starred |
(a * b) % s = ((a % s) * (b % s)) % s |
00129 |
Fetching from uHunt |
non-starred |
backtracking; string processing check; a bit of output formatting |
00130 |
Fetching from uHunt |
non-starred |
the original Josephus problem |
00131 |
Fetching from uHunt |
non-starred |
backtracking with 2^5 bitmask to help deciding which card is retained in hand/exchanged with the top of deck; use 5! permutation to shuffle the 5 cards in hand and get the best value |
00132 |
Fetching from uHunt |
non-starred |
brute force as instructed in problem description; use polygon routines |
00133 |
Fetching from uHunt |
non-starred |
brute force; similar to UVa 130 |
00134 |
Fetching from uHunt |
non-starred |
recursive grammar check; tedious |
00136 |
Fetching from uHunt |
non-starred |
use similar technique as UVa 443 |
00137 |
Fetching from uHunt |
non-starred |
convex polygon intersection; line segment intersection; inPolygon; CH; area; inclusion-exclusion principle |
00138 |
Fetching from uHunt |
non-starred |
arithmetic progression formula; precalculation |
00139 |
Fetching from uHunt |
non-starred |
calculate phone bill; string manipulation |
00140 |
Fetching from uHunt |
non-starred |
max n is just 8; use next_permutation; the algorithm inside next_permutation is iterative |
00141 |
Fetching from uHunt |
non-starred |
solvable with one linear scan |
00142 |
Fetching from uHunt |
non-starred |
brute force; point-in-rectangle; dist |
00143 |
Fetching from uHunt |
non-starred |
count integer points in triangle; beware of precision issue |
00144 |
Fetching from uHunt |
non-starred |
simulation |
00145 |
Fetching from uHunt |
non-starred |
similar to UVa 139 |
00146 |
Fetching from uHunt |
2.2c, algorithm/Collections |
use next_permutation |
00147 |
Fetching from uHunt |
non-starred |
similar to UVa 357 and 674 |
00148 |
Fetching from uHunt |
non-starred |
uses backtracking |
00150 |
Fetching from uHunt |
non-starred |
convert between Julian and Gregorian dates |
00151 |
Fetching from uHunt |
non-starred |
the original Josephus problem |
00152 |
Fetching from uHunt |
non-starred |
sort the 3D points first |
00153 |
Fetching from uHunt |
non-starred |
find formula for this; similar with UVa 941 |
00154 |
Fetching from uHunt |
non-starred |
3 nested loops |
00155 |
Fetching from uHunt |
non-starred |
recursive counting |
00156 |
Fetching from uHunt |
9.3, Anagram |
easier with algorithm::sort |
00157 |
Fetching from uHunt |
non-starred |
tedious input parsing; SSSP on graph with 2-valued weighted graph (1 or 3 units of time); be careful of station with multiple names; changing between them should be just 3 units of time; print the shortest path |
00158 |
Fetching from uHunt |
non-starred |
a simulation of calendar manager; it requires sorting and a bit of string processing |
00159 |
Fetching from uHunt |
non-starred |
tedious output formatting problem |
00160 |
Fetching from uHunt |
non-starred |
precalculate small primes as prime factors of 100! is < 100$ |
00161 |
Fetching from uHunt |
1.4e, Real Life, Easier |
this is a typical situation on the road |
00162 |
Fetching from uHunt |
non-starred |
card game simulation; straightforward |
00164 |
Fetching from uHunt |
non-starred |
String Alignment/Edit Distance |
00165 |
Fetching from uHunt |
3.2j, Pre-calculate-able |
requires some DP too; can be pre-calculated |
00166 |
Fetching from uHunt |
non-starred |
two coin change variants in one problem |
00167 |
Fetching from uHunt |
non-starred |
8-queens chess problem |
00168 |
Fetching from uHunt |
non-starred |
Adjacency Matrix; parsing; traversal |
00170 |
Fetching from uHunt |
non-starred |
simulation; time |
00171 |
Fetching from uHunt |
non-starred |
recursive grammar check; tedious |
00172 |
Fetching from uHunt |
non-starred |
another recursive parser; tedious |
00173 |
Fetching from uHunt |
non-starred |
non classic graph traversal variant; use bitmask to record vertices visited by Paskill and Lisper as they move through the graph; look at problem description closely for various small details |
00179 |
Fetching from uHunt |
non-starred |
use brute force |
00183 |
Fetching from uHunt |
3.3c, Other DnC Problems |
simple exercise of Divide and Conquer |
00184 |
Fetching from uHunt |
non-starred |
brute force; collinear test |
00185 |
Fetching from uHunt |
non-starred |
also involving backtracking |
00186 |
Fetching from uHunt |
non-starred |
graph is small; print path |
00187 |
Fetching from uHunt |
non-starred |
an accounting problem |
00188 |
Fetching from uHunt |
non-starred |
3 nested loops; until the answer is found |
00190 |
Fetching from uHunt |
non-starred |
triangle's circumcircle |
00191 |
Fetching from uHunt |
non-starred |
line segment intersection |
00193 |
Fetching from uHunt |
non-starred |
optimization version of Max Independent Set problem on general graph which is NP-Hard with small input |
00195 |
Fetching from uHunt |
9.3, Anagram |
use algorithm::next_permutation |
00196 |
Fetching from uHunt |
non-starred |
notice that the dependencies of cells are acyclic; we can therefore memoize the direct (or indirect) value of each cell |
00200 |
Fetching from uHunt |
non-starred |
toposort |
00201 |
Fetching from uHunt |
non-starred |
counting square of various sizes; try all |
00202 |
Fetching from uHunt |
non-starred |
do expansion digit by digit until it cycles |
00208 |
Fetching from uHunt |
3.2h, Backtracking (Harder) |
LA 5147 - WorldFinals SanAntonio91; backtracking with some pruning |
00209 |
Fetching from uHunt |
7.2f, Quadrilaterals |
LA 5148 - WorldFinals SanAntonio91; put the triangular vertices on 2D plane; then use brute force checks to determine if the given points form a triangle; a parallelogram (which is a quadrilateral); or a hexagon |
00211 |
Fetching from uHunt |
non-starred |
map the complex bone IDs to pips using 2D array; use backtracking to try the placement of various domino bones |
00213 |
Fetching from uHunt |
6.3b, Cipher, Harder |
LA 5152 - WorldFinals SanAntonio91; decrypt the message |
00214 |
Fetching from uHunt |
non-starred |
just simulate the process; be careful with subtract (-); divide (/); and negate (@); tedious |
00215 |
Fetching from uHunt |
non-starred |
a bit of string parsing; this problem is similar to UVa 196; however; we have to check if there is a circular reference this time |
00216 |
Fetching from uHunt |
non-starred |
LA 5155 - WorldFinals KansasCity92; DP TSP problem; but still solvable with backtracking |
00218 |
Fetching from uHunt |
non-starred |
LA 5157 - WorldFinals KansasCity92; find CH; perimeter of polygon |
00220 |
Fetching from uHunt |
non-starred |
follow the game rules; a bit tedious |
00222 |
Fetching from uHunt |
3.2h, Backtracking (Harder) |
LA 5161 - WorldFinals Indianapolis93; looks like a DP problem but the state cannot be memoized as 'tank' is floating-point; fortunately; the input is not large |
00227 |
Fetching from uHunt |
non-starred |
parse the input; array manipulation |
00230 |
Fetching from uHunt |
non-starred |
string parsing; maintain sorted books by author names then by title; the input size is small; we do not need balanced BST |
00231 |
Fetching from uHunt |
non-starred |
straightforward |
00232 |
Fetching from uHunt |
non-starred |
complex array manipulation problem |
00234 |
Fetching from uHunt |
3.2e, Iterative (Fancy Techniques) |
LA 5173 - WorldFinals Phoenix94; use next_permutation; simulation |
00242 |
Fetching from uHunt |
3.5e, Coin-Change |
LA 5181 - WorldFinals Nashville95; for each set of stamp denominations; iterate through all possible values; use DP CC to find the min number of coins (stamps) to get each value; stop as soon as it requires more than S; keep the best set of stamp den |
00245 |
Fetching from uHunt |
non-starred |
LA 5184 - WorldFinals Nashville95; use the given algorithm |
00247 |
Fetching from uHunt |
4.2g, SCCs |
SCC + printing solution |
00253 |
Fetching from uHunt |
non-starred |
try all; similar problem in UVa 11959 |
00254 |
Fetching from uHunt |
non-starred |
define a recursive formula |
00255 |
Fetching from uHunt |
1.4b, Game (Chess) |
check the validity of chess moves |
00256 |
Fetching from uHunt |
non-starred |
brute force; math; pre-calculate-able |
00257 |
Fetching from uHunt |
non-starred |
palindrome check (DP-able) plus brute force checks for non embedding criteria |
00259 |
Fetching from uHunt |
non-starred |
assignment problem; matching with capacity; similar to UVa 10092; 11045; and 12873; but actually the input constraint is actually small enough for recursive backtracking |
00260 |
Fetching from uHunt |
non-starred |
6 neighbors per cell |
00261 |
Fetching from uHunt |
non-starred |
sliding window variant |
00263 |
Fetching from uHunt |
non-starred |
sort digits; convert to integers; check cycle |
00264 |
Fetching from uHunt |
5.2f, Grid |
grid; pattern |
00270 |
Fetching from uHunt |
non-starred |
gradient sorting; complete search |
00271 |
Fetching from uHunt |
non-starred |
grammar check; linear scan |
00272 |
Fetching from uHunt |
non-starred |
replace all double quotes to TeX style quotes |
00273 |
Fetching from uHunt |
non-starred |
line segment intersection and Warshall's transitive closure algorithm |
00274 |
Fetching from uHunt |
non-starred |
variant of transitive closure problem |
00275 |
Fetching from uHunt |
non-starred |
similar to UVa 202 except the output format |
00276 |
Fetching from uHunt |
non-starred |
multiplication of Egyptian hieroglyphs |
00278 |
Fetching from uHunt |
1.4b, Game (Chess) |
basic chess knowledge is needed; derive the closed form formulas |
00280 |
Fetching from uHunt |
4.2a, Just Graph Traversal |
simple reachability test; traverse the graph |
00290 |
Fetching from uHunt |
non-starred |
also involving palindrome |
00291 |
Fetching from uHunt |
4.7e, Eulerian Graph |
Euler tour on a small graph; backtracking is sufficient |
00294 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
numDiv(N) |
00295 |
Fetching from uHunt |
8.5h, Three Components |
binary search the answer x for this question: if the person is of diameter x; can he go from left to right? model the graph and test connectivity; similar with UVa 10876 |
00296 |
Fetching from uHunt |
non-starred |
try all 10000 possible codes; 4 nested loops; use similar solution as Master-Mind game |
00297 |
Fetching from uHunt |
non-starred |
simple quadtree problem |
00298 |
Fetching from uHunt |
non-starred |
s: (row; col; 49 possible speeds) |
00299 |
Fetching from uHunt |
non-starred |
solvable with O(n^2) bubble sort |
00300 |
Fetching from uHunt |
non-starred |
ad hoc; time |
00301 |
Fetching from uHunt |
non-starred |
2^22 with pruning is possible |
00302 |
Fetching from uHunt |
non-starred |
Euler tour; print the tour |
00305 |
Fetching from uHunt |
non-starred |
the answer can be precalculated |
00306 |
Fetching from uHunt |
non-starred |
can be made faster by avoiding cycle |
00307 |
Fetching from uHunt |
3.2h, Backtracking (Harder) |
sort the sticks in descending length; group similar lengths; brute force the number of sticks; backtracking to check feasibility |
00311 |
Fetching from uHunt |
non-starred |
greedy |
00313 |
Fetching from uHunt |
non-starred |
use trigonometry to project the light to the ground through the pipes; sort the intervals; merge overlapping intervals; if any |
00314 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
pre-process the input graph first; then run BFS with states/vertices: (row; column; direction) and 5 transitions/edges: turn left/right or move 1/2/3 steps |
00315 |
Fetching from uHunt |
4.2f, Articulation Points/Bridges |
finding articulation points |
00318 |
Fetching from uHunt |
non-starred |
graph traversal; be careful of corner cases |
00320 |
Fetching from uHunt |
non-starred |
requires flood fill technique |
00321 |
Fetching from uHunt |
non-starred |
s: (position; bitmask 2^10); print the path |
00324 |
Fetching from uHunt |
non-starred |
count digits of n! up to 366! |
00325 |
Fetching from uHunt |
6.3f, Regular Expression |
trivial with Java RegEx |
00326 |
Fetching from uHunt |
non-starred |
difference table |
00327 |
Fetching from uHunt |
non-starred |
implementation can be tricky |
00330 |
Fetching from uHunt |
non-starred |
use map to help |
00331 |
Fetching from uHunt |
non-starred |
n <= 5... |
00332 |
Fetching from uHunt |
non-starred |
use GCD to simplify fraction |
00333 |
Fetching from uHunt |
non-starred |
this problem has buggy test data with blank lines that potentially cause lots of Presentation Errors |
00334 |
Fetching from uHunt |
non-starred |
transitive closure |
00335 |
Fetching from uHunt |
non-starred |
simulation |
00336 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
simple SSSP solvable with BFS |
00337 |
Fetching from uHunt |
non-starred |
simulation; output related |
00338 |
Fetching from uHunt |
non-starred |
tedious |
00339 |
Fetching from uHunt |
non-starred |
follow problem description |
00340 |
Fetching from uHunt |
non-starred |
determine strong and weak matches |
00341 |
Fetching from uHunt |
non-starred |
the graph is small |
00343 |
Fetching from uHunt |
5.3b, Bonus: Base Number |
try all possible pair of bases |
00344 |
Fetching from uHunt |
non-starred |
count how many Roman characters are used to make all numbers from 1 to N |
00346 |
Fetching from uHunt |
non-starred |
musical chord; major/minor |
00347 |
Fetching from uHunt |
non-starred |
simulate the process |
00348 |
Fetching from uHunt |
non-starred |
DP; s(i; j); output the optimal solution too; note that the optimal matrix multiplication sequence is not unique; e.g. imagine if all matrices are square matrices |
00349 |
Fetching from uHunt |
non-starred |
simulation |
00350 |
Fetching from uHunt |
5.7a, Cycle Finding |
very basic cycle-finding problem; simply run Floyd's cycle-finding algorithm |
00352 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
count number of CCs; see UVa 572 |
00353 |
Fetching from uHunt |
non-starred |
brute force all substrings; count how many substrings are palindrome |
00355 |
Fetching from uHunt |
non-starred |
basic base number conversion |
00356 |
Fetching from uHunt |
non-starred |
Euclidean distance; brute force |
00357 |
Fetching from uHunt |
non-starred |
similar to UVa 147 and 674 |
00361 |
Fetching from uHunt |
non-starred |
check if a point is inside CH of Cop/Robber; if a point pt is inside a convex hull; then there is definitely a triangle formed using three vertices of the convex hull that contains pt |
00362 |
Fetching from uHunt |
non-starred |
typical file download situation |
00369 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
be careful with overflow issue |
00371 |
Fetching from uHunt |
non-starred |
similar to UVa 100 |
00373 |
Fetching from uHunt |
non-starred |
check 'g' versus 'p'; ad hoc |
00374 |
Fetching from uHunt |
non-starred |
solvable with Java BigInteger modPow; or write your own code |
00375 |
Fetching from uHunt |
non-starred |
triangle'sincircles |
00377 |
Fetching from uHunt |
5.2j, Base Number Variants |
base 4 operations |
00378 |
Fetching from uHunt |
7.2b, Lines |
library routines: areParallel; areSame; areIntersect |
00379 |
Fetching from uHunt |
non-starred |
follow problem description |
00380 |
Fetching from uHunt |
non-starred |
simple backtracking; but we have to work with strings |
00381 |
Fetching from uHunt |
non-starred |
simulation |
00382 |
Fetching from uHunt |
5.2b, Math Simulation, Easier |
do trial division |
00383 |
Fetching from uHunt |
non-starred |
simple SSSP solvable with BFS; use mapper |
00384 |
Fetching from uHunt |
non-starred |
recursive grammar check |
00385 |
Fetching from uHunt |
non-starred |
a kind of decryption problem; tedious |
00386 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
4 nested loops with pruning |
00387 |
Fetching from uHunt |
non-starred |
use backtracking to try placement of various puzzle pieces |
00388 |
Fetching from uHunt |
non-starred |
key idea: we want to minimize planet movements because every edge used decreases value by 5% |
00389 |
Fetching from uHunt |
5.3b, Bonus: Base Number |
use Java Integer class |
00391 |
Fetching from uHunt |
non-starred |
use flags; tedious parsing |
00392 |
Fetching from uHunt |
non-starred |
follow the orders; output formatting |
00393 |
Fetching from uHunt |
8.5d, Graph and Other |
build the small visibility graph with line segment intersection checks; run Floyd Warshall's routine to get the answer |
00394 |
Fetching from uHunt |
non-starred |
any n-dimensional array is stored in computer memory as a single dimensional array; follow the problem description |
00397 |
Fetching from uHunt |
6.3d, Iterative Parsing |
iteratively perform the next operation |
00400 |
Fetching from uHunt |
non-starred |
this command is very frequently used in UNIX |
00401 |
Fetching from uHunt |
non-starred |
simple palindrome check |
00402 |
Fetching from uHunt |
non-starred |
modified Josephus; simulation |
00403 |
Fetching from uHunt |
non-starred |
emulation of printer driver; tedious |
00405 |
Fetching from uHunt |
non-starred |
simulation |
00406 |
Fetching from uHunt |
non-starred |
sieve; take the middle ones |
00408 |
Fetching from uHunt |
non-starred |
cycle finding problem with easier solution: it is a good choice if step < mod and GCD(step; mod) == 1 |
00409 |
Fetching from uHunt |
non-starred |
tokenize and compare with list of excuses |
00410 |
Fetching from uHunt |
non-starred |
load balancing |
00412 |
Fetching from uHunt |
non-starred |
brute force; GCD to find elements with no common factor |
00413 |
Fetching from uHunt |
non-starred |
simulate; array manipulation |
00414 |
Fetching from uHunt |
non-starred |
get the longest stretch of Bs |
00416 |
Fetching from uHunt |
non-starred |
backtrack; try all |
00417 |
Fetching from uHunt |
2.3c, unordered_map/HashMap |
generate all words; add to map for auto sorting |
00418 |
Fetching from uHunt |
non-starred |
use next_permutation to permute the 4 molecule locations and then use 12^6 six-nested-loops to check the area of the super molecule; if any |
00422 |
Fetching from uHunt |
6.4b, String Matching, 2D Grid |
2D grid; backtracking |
00423 |
Fetching from uHunt |
non-starred |
the graph is small |
00424 |
Fetching from uHunt |
non-starred |
BigInteger addition |
00426 |
Fetching from uHunt |
non-starred |
tokenize; sort; reformat output |
00427 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
for each two consecutive corridors; try rotating the piano by a small angle alpha in [0.1..89.9] degrees; use trigonometry to determine if the piano rotated by angle alpha can pass |
00429 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
each word is a vertex; connect 2 words with an edge if differ by 1 letter |
00431 |
Fetching from uHunt |
non-starred |
classic 0-1 Knapsack Problem; output any optimal solution as there is a special checker for this problem |
00433 |
Fetching from uHunt |
non-starred |
similar to UVa 416 |
00434 |
Fetching from uHunt |
non-starred |
a kind of visibility problem in geometry; solvable with using 2D array manipulation |
00435 |
Fetching from uHunt |
non-starred |
only 2^20 possible coalition combinations |
00436 |
Fetching from uHunt |
non-starred |
another arbitrage problem |
00437 |
Fetching from uHunt |
non-starred |
can be modeled as LIS |
00438 |
Fetching from uHunt |
7.2e, Triangles + Circles |
triangle's circumcircle |
00439 |
Fetching from uHunt |
non-starred |
one BFS per query is enough |
00440 |
Fetching from uHunt |
non-starred |
brute force; similar to UVa 151 |
00441 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
6 nested loops; easy |
00442 |
Fetching from uHunt |
non-starred |
properties of matrix chain multiplication |
00443 |
Fetching from uHunt |
5.2g, Number Systems/Sequences |
try all 2^i * 3^j * 5^k * 7^l; sort |
00444 |
Fetching from uHunt |
non-starred |
each char is mapped to 2 or 3 digits |
00445 |
Fetching from uHunt |
non-starred |
simulation; output formatting |
00446 |
Fetching from uHunt |
non-starred |
base number conversion |
00447 |
Fetching from uHunt |
non-starred |
life simulation model |
00448 |
Fetching from uHunt |
non-starred |
tedious hexadecimal to assembly language conversion |
00449 |
Fetching from uHunt |
non-starred |
easier if you have a musical background |
00450 |
Fetching from uHunt |
non-starred |
tedious sorting problem |
00452 |
Fetching from uHunt |
4.7a, S/L Paths on DAG |
PERT; longest paths on DAG |
00454 |
Fetching from uHunt |
non-starred |
anagram |
00455 |
Fetching from uHunt |
non-starred |
find s in concatenate(s; s); similar with UVa 10298 |
00457 |
Fetching from uHunt |
non-starred |
simplified game of life simulation; similar idea with UVa 447; explore the Internet for that term |
00458 |
Fetching from uHunt |
non-starred |
shift ASCII values by -7 |
00459 |
Fetching from uHunt |
non-starred |
also solvable with UFDS |
00460 |
Fetching from uHunt |
non-starred |
rectangle-rectangle intersection |
00462 |
Fetching from uHunt |
non-starred |
simulation; card |
00464 |
Fetching from uHunt |
non-starred |
generate output based on the given BNF grammar |
00465 |
Fetching from uHunt |
non-starred |
BigInteger add/multiply; compare with 2^31-1$ |
00466 |
Fetching from uHunt |
non-starred |
core functions: rotate and reflect |
00467 |
Fetching from uHunt |
non-starred |
linear scan; 1D boolean flag |
00468 |
Fetching from uHunt |
non-starred |
letter frequency mapping |
00469 |
Fetching from uHunt |
non-starred |
count size of a CC |
00471 |
Fetching from uHunt |
non-starred |
somewhat similar to UVa 725 |
00473 |
Fetching from uHunt |
non-starred |
the input constraint is not clear; therefore use resizeable vector and compact states |
00474 |
Fetching from uHunt |
non-starred |
this is just a log and pow exercise |
00476 |
Fetching from uHunt |
7.2f, Quadrilaterals |
basic problem; also see related problems: UVa 477 and 478 |
00477 |
Fetching from uHunt |
non-starred |
similar with UVa 476 and 478 |
00478 |
Fetching from uHunt |
non-starred |
inPolygon/Triangle/Circle/Rectangle |
00481 |
Fetching from uHunt |
3.5c, LIS |
O(n log k) LIS; print solution |
00482 |
Fetching from uHunt |
non-starred |
you may need to use a string tokenizer as the size of the array is not specified |
00483 |
Fetching from uHunt |
non-starred |
read char by char from left to right |
00484 |
Fetching from uHunt |
2.3c, unordered_map/HashMap |
maintain frequency with map |
00485 |
Fetching from uHunt |
non-starred |
binomial coefficients BigInteger |
00486 |
Fetching from uHunt |
non-starred |
parsing |
00487 |
Fetching from uHunt |
non-starred |
use map to store the generated words |
00488 |
Fetching from uHunt |
6.3g, Output Formatting, Easier |
use several loops |
00489 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
just do as asked |
00490 |
Fetching from uHunt |
non-starred |
2d array manipulation; output formatting |
00492 |
Fetching from uHunt |
non-starred |
ad hoc; similar to UVa 483 |
00493 |
Fetching from uHunt |
non-starred |
simulate the spiral process |
00494 |
Fetching from uHunt |
6.3f, Regular Expression |
trivial with Java RegEx |
00495 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
use O(n) DP; Java BigInteger |
00496 |
Fetching from uHunt |
5.2k, Just Ad Hoc |
set manipulation |
00497 |
Fetching from uHunt |
non-starred |
solution must be printed |
00498 |
Fetching from uHunt |
non-starred |
polynomial evaluation |
00499 |
Fetching from uHunt |
non-starred |
use 1D array for frequency counting |
00501 |
Fetching from uHunt |
non-starred |
use multiset with efficient iterator manipulation |
00507 |
Fetching from uHunt |
non-starred |
standard problem |
00512 |
Fetching from uHunt |
non-starred |
apply all rows/columns modifications in descending order; for each query; report the new position of the cell or report GONE |
00514 |
Fetching from uHunt |
2.2e, Stack |
use stack to simulate the process |
00516 |
Fetching from uHunt |
non-starred |
problem involving prime-power factorization |
00517 |
Fetching from uHunt |
non-starred |
convert (a; b) to (0; 1) first so that we only work with integers; major observation: there can only be 2^16 possibilities although s can be gigantic; stop upon encountering a cycle |
00521 |
Fetching from uHunt |
non-starred |
build a graph; the vertices are drivers; give an edge between two drivers if they can meet; this is determined with mathematical rule (gcd); if the graph is connected; then the answer is 'yes' |
00523 |
Fetching from uHunt |
non-starred |
this is actually an SSSP problem on weighted graph solvable with Dijkstra's; use the vertex splitting technique to handle vertex weight |
00524 |
Fetching from uHunt |
3.2g, Backtracking (Medium) |
involving prime number |
00526 |
Fetching from uHunt |
non-starred |
String Alignment/Edit Distance |
00529 |
Fetching from uHunt |
non-starred |
use backtracking to get the solution |
00530 |
Fetching from uHunt |
non-starred |
work with doubles; optimize computation |
00531 |
Fetching from uHunt |
non-starred |
Longest Common Subsequence; print the solution |
00532 |
Fetching from uHunt |
non-starred |
3D BFS |
00533 |
Fetching from uHunt |
non-starred |
recursive grammar check |
00534 |
Fetching from uHunt |
non-starred |
minimax; also solvable with Floyd Warshall's |
00535 |
Fetching from uHunt |
non-starred |
gcDistance |
00536 |
Fetching from uHunt |
4.7d, Tree |
reconstructing binary tree from preorder and inorder binary tree traversal |
00537 |
Fetching from uHunt |
non-starred |
simple formula; parsing is difficult |
00538 |
Fetching from uHunt |
non-starred |
the problem's premise is quite true |
00539 |
Fetching from uHunt |
8.4a, NP-hard/complete, small |
longest simple path in a emph{small} general graph |
00540 |
Fetching from uHunt |
non-starred |
modified queue |
00541 |
Fetching from uHunt |
2.2b, 2D Array Manipulation |
count the number of 1s for each row/col; which must be even; if there is an error; see if the odd number of 1s appear on the same row and col |
00542 |
Fetching from uHunt |
non-starred |
divide and conquer |
00543 |
Fetching from uHunt |
5.5a, Prime Numbers |
sieve; complete search; Christian Goldbach's conjecture (updated by Leonhard Euler): Every even number >= 4 can be expressed as the sum of two prime numbers; similar to UVa 686; 10311; and 10948 |
00544 |
Fetching from uHunt |
non-starred |
maximin; also solvable with Floyd Warshall's |
00545 |
Fetching from uHunt |
non-starred |
use logarithm; power; similar to UVa 474 |
00547 |
Fetching from uHunt |
non-starred |
a problem about 'eventually constant' sequence; similar flavor as cycle-finding |
00548 |
Fetching from uHunt |
non-starred |
reconstructing tree from in postorder |
00550 |
Fetching from uHunt |
non-starred |
rotamult property; try one by one starting from 1 digit |
00551 |
Fetching from uHunt |
non-starred |
bracket matching; stack |
00554 |
Fetching from uHunt |
6.3b, Cipher, Harder |
try all shifts; output formatting |
00555 |
Fetching from uHunt |
non-starred |
card game |
00556 |
Fetching from uHunt |
non-starred |
simulation |
00557 |
Fetching from uHunt |
non-starred |
one possible solution involves combinatorics which can be computed with DP |
00558 |
Fetching from uHunt |
non-starred |
check if negative cycle exists |
00562 |
Fetching from uHunt |
non-starred |
use a one dimensional table |
00563 |
Fetching from uHunt |
4.6b, Network Flow, Variants |
check whether the maximum number of independent paths on the flow graph---with unit edge and unit vertex capacity---equals to b banks |
00565 |
Fetching from uHunt |
non-starred |
backtracking with lots of pruning |
00567 |
Fetching from uHunt |
non-starred |
simple SSSP solvable with BFS; but the graph is small; so can be solved easier with Floyd Warshall's |
00568 |
Fetching from uHunt |
non-starred |
can use Java BigInteger; slow but AC |
00570 |
Fetching from uHunt |
non-starred |
use map to help |
00571 |
Fetching from uHunt |
non-starred |
solution can be suboptimal; add flag to avoid cycling |
00572 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
count number of CCs |
00573 |
Fetching from uHunt |
1.3c, Medium |
simulation; beware of boundary cases! |
00574 |
Fetching from uHunt |
non-starred |
print all solutions with backtracking |
00575 |
Fetching from uHunt |
5.2j, Base Number Variants |
base modification |
00576 |
Fetching from uHunt |
6.3f, Regular Expression |
solvable with Java regular expression |
00579 |
Fetching from uHunt |
1.4g, Time, Easier |
be careful with corner cases |
00580 |
Fetching from uHunt |
non-starred |
related to Tribonacci series |
00583 |
Fetching from uHunt |
5.5d, Finding Prime Factors |
basic factorization problem |
00584 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
simulation; games; reading comprehension |
00585 |
Fetching from uHunt |
non-starred |
recursive grammar check and output formatting |
00587 |
Fetching from uHunt |
7.2a, Points |
Euclidean dist |
00588 |
Fetching from uHunt |
9.4, Art Gallery |
cutPolygon |
00589 |
Fetching from uHunt |
non-starred |
Sokoban puzzle; double SSSP: weighted SSSP of moving the box from source to target; another unweighted SSSP of moving the player to reach correct position to push the box |
00590 |
Fetching from uHunt |
4.7c, Conversion to DAG |
s: (pos; day_left) |
00591 |
Fetching from uHunt |
non-starred |
sum all items; get the average; sum the total absolute differences of each item from the average divided by two |
00592 |
Fetching from uHunt |
non-starred |
key idea: there are only 3^5*2 possible states: the status of each person and whether it is day or night |
00594 |
Fetching from uHunt |
non-starred |
manipulate bit string with bitset |
00596 |
Fetching from uHunt |
non-starred |
basic CH problem; but output formatting is a bit tedious |
00598 |
Fetching from uHunt |
non-starred |
print all solutions with backtracking |
00599 |
Fetching from uHunt |
2.4a, Graph Data Structures |
V-E = number of CCs; use a bitset of size 26 to count the number of vertices that have some edge |
00601 |
Fetching from uHunt |
non-starred |
floodfill is one of the component |
00602 |
Fetching from uHunt |
non-starred |
Gregorian versus Julian calendar |
00603 |
Fetching from uHunt |
non-starred |
simulation |
00604 |
Fetching from uHunt |
non-starred |
2D grid; backtracking; sort and compare |
00607 |
Fetching from uHunt |
8.3b, DP level 3 |
returns pair of information |
00608 |
Fetching from uHunt |
3.3c, Other DnC Problems |
classical problem; after each weighing; we can halve the search space |
00610 |
Fetching from uHunt |
non-starred |
finding bridges |
00612 |
Fetching from uHunt |
non-starred |
needs O(n^2) stable_sort |
00613 |
Fetching from uHunt |
non-starred |
analyze the number; determine the type; similar spirit with the cycle finding problem |
00614 |
Fetching from uHunt |
non-starred |
traversal on implicit graph |
00615 |
Fetching from uHunt |
non-starred |
graph property check |
00616 |
Fetching from uHunt |
5.2c, Math Simulation, Harder |
brute force up to sqrt(n); get pattern |
00617 |
Fetching from uHunt |
non-starred |
try all integer speeds from 30 to 60 mph |
00618 |
Fetching from uHunt |
non-starred |
tedious |
00619 |
Fetching from uHunt |
non-starred |
BigInteger |
00620 |
Fetching from uHunt |
6.3e, Recursive Parsing |
recursive grammar check |
00621 |
Fetching from uHunt |
non-starred |
case analysis for only 4 possible outputs |
00622 |
Fetching from uHunt |
non-starred |
recursive grammar check/evaluation |
00623 |
Fetching from uHunt |
5.5c, Factorial |
easy with Java BigInteger |
00624 |
Fetching from uHunt |
non-starred |
input size is small; backtracking is enough |
00626 |
Fetching from uHunt |
non-starred |
3 nested loops |
00627 |
Fetching from uHunt |
non-starred |
also print the path |
00628 |
Fetching from uHunt |
non-starred |
backtracking; follow the rules in description |
00630 |
Fetching from uHunt |
non-starred |
ad hoc; string |
00632 |
Fetching from uHunt |
non-starred |
simulate the process; use sorting |
00633 |
Fetching from uHunt |
non-starred |
a modified Knight Moves problem with alternating Knight Moves and Bishop Moves (limited to distance 2)); solvable with just one BFS per query |
00634 |
Fetching from uHunt |
7.3a, Polygon, Easier |
basic inPolygon routine; notice that the input polygon can be convex or concave |
00636 |
Fetching from uHunt |
non-starred |
base number conversion up to base 99; Java BigInteger cannot be used as it is MAX_RADIX is limited to 36 |
00637 |
Fetching from uHunt |
1.4e, Real Life, Easier |
application in printer driver software |
00638 |
Fetching from uHunt |
non-starred |
brute force 4 corner points |
00639 |
Fetching from uHunt |
3.2e, Iterative (Fancy Techniques) |
generate 2^(4x4) = 2^16 combinations and prune |
00640 |
Fetching from uHunt |
non-starred |
DP bottom up; generate the numbers; flag once |
00641 |
Fetching from uHunt |
non-starred |
reverse the given formula and simulate |
00642 |
Fetching from uHunt |
non-starred |
go through the given small dictionary for the list of possible anagrams |
00644 |
Fetching from uHunt |
6.3i, String Comparison |
use brute force |
00645 |
Fetching from uHunt |
non-starred |
use recursion to simulate directory structure as it helps the output formatting |
00647 |
Fetching from uHunt |
non-starred |
childhood board game; also see UVa 11459 |
00651 |
Fetching from uHunt |
non-starred |
use the given sample I/O to derive the simple formula |
00652 |
Fetching from uHunt |
9.2, A* or IDA* |
classic sliding block 8-puzzle; IDA* |
00654 |
Fetching from uHunt |
non-starred |
just use brute force |
00656 |
Fetching from uHunt |
9.2, A* or IDA* |
we can use IDDFS with pruning |
00657 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
there are three colors here; non-standard but still relatively easy floodfill problem |
00658 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
s: (bitmask---whether a bug is present or not); the state-space graph is weighted |
00661 |
Fetching from uHunt |
non-starred |
simulation |
00662 |
Fetching from uHunt |
8.3a, DP level 2 |
s: (L; R; k); that denotes the minimum distance sum to cover restaurants at index [L..R] with k depots left |
00663 |
Fetching from uHunt |
non-starred |
try disallowing an edge to see if MCBM changes; which implies that the edge has to be used |
00665 |
Fetching from uHunt |
non-starred |
use 1D boolean flags; each =; <; or > tells us an information; check if there is only one candidate false coin left at the end |
00668 |
Fetching from uHunt |
non-starred |
greedy |
00670 |
Fetching from uHunt |
non-starred |
MCBM |
00671 |
Fetching from uHunt |
non-starred |
string comparison |
00672 |
Fetching from uHunt |
8.3b, DP level 3 |
DP with compact state: (gangster_id; openness_level); we do not use current_time as part of the state as changing openness\_level by 1/0/-1 at every time unit is too slow |
00673 |
Fetching from uHunt |
non-starred |
similar to UVa 551; classic |
00674 |
Fetching from uHunt |
3.5e, Coin-Change |
basic coin change problem |
00677 |
Fetching from uHunt |
non-starred |
print all solutions with backtracking |
00679 |
Fetching from uHunt |
non-starred |
binary search; bit manipulation solutions exist |
00681 |
Fetching from uHunt |
non-starred |
CH; with output formatting |
00684 |
Fetching from uHunt |
non-starred |
modified Gaussian elimination to find (integral) determinant of a square matrix |
00686 |
Fetching from uHunt |
non-starred |
similar to UVa 543; 10311; and 10948 |
00688 |
Fetching from uHunt |
non-starred |
brute force; chop the region into small rectangles and decide if a small rectangle is covered by an antenna or not; if it is; add the area of that small rectangle to the answer |
00694 |
Fetching from uHunt |
non-starred |
similar to UVa 100 |
00696 |
Fetching from uHunt |
1.4b, Game (Chess) |
ad hoc; chess |
00697 |
Fetching from uHunt |
non-starred |
output formatting and basic Physics |
00699 |
Fetching from uHunt |
non-starred |
preorder traversal |
00700 |
Fetching from uHunt |
non-starred |
can be solved with bitset |
00701 |
Fetching from uHunt |
5.2h, Log, Exp, Pow |
use log to count number of digits |
00702 |
Fetching from uHunt |
non-starred |
counting paths in implicit DAG; the implicit DAG is not trivial; 3 parameters |
00703 |
Fetching from uHunt |
non-starred |
3 nested loops |
00704 |
Fetching from uHunt |
non-starred |
state-space search; use meet-in-the-middle to bring down 4^16 to 2*4^8 |
00705 |
Fetching from uHunt |
non-starred |
build the implicit graph first |
00706 |
Fetching from uHunt |
1.4f, Real Life, Harder |
what we see in old digital display |
00707 |
Fetching from uHunt |
non-starred |
this requires 3D array; but as there is no such category; it is classified here |
00710 |
Fetching from uHunt |
non-starred |
backtracking with memoization/pruning |
00711 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
reduce search space; backtracking |
00712 |
Fetching from uHunt |
non-starred |
simple binary tree traversal variant |
00713 |
Fetching from uHunt |
5.3a, BigInteger, Basic |
BigInteger StringBuffer reverse() |
00714 |
Fetching from uHunt |
8.5a, Bsearch-ans and Others |
binary search the answer and greedy |
00719 |
Fetching from uHunt |
non-starred |
min lexicographic rotation; O(n log n) build SA |
00721 |
Fetching from uHunt |
non-starred |
the problem statement is hard to understand; essentially this problem is just about SSSP from vertex 1 to all vertices and SDestinationSP from all vertices to vertex 1 by reversing the edges |
00722 |
Fetching from uHunt |
non-starred |
count the size of CCs |
00725 |
Fetching from uHunt |
non-starred |
try all |
00726 |
Fetching from uHunt |
non-starred |
frequency cypher |
00727 |
Fetching from uHunt |
non-starred |
the classic Infix to Postfix conversion problem |
00729 |
Fetching from uHunt |
3.2f, Backtracking (Easy) |
generate all possible bit strings |
00732 |
Fetching from uHunt |
non-starred |
use stack to simulate the process |
00735 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops; then count |
00736 |
Fetching from uHunt |
6.4b, String Matching, 2D Grid |
2D grid; a bit modified |
00737 |
Fetching from uHunt |
non-starred |
cube and cube intersection |
00739 |
Fetching from uHunt |
non-starred |
straightforward conversion problem |
00740 |
Fetching from uHunt |
6.3b, Cipher, Harder |
just simulate the process |
00741 |
Fetching from uHunt |
non-starred |
simulate the process |
00743 |
Fetching from uHunt |
non-starred |
recursive grammar check |
00748 |
Fetching from uHunt |
non-starred |
BigInteger exponentiation |
00750 |
Fetching from uHunt |
3.2j, Pre-calculate-able |
classic backtracking problem |
00753 |
Fetching from uHunt |
non-starred |
initially a non standard matching problem but this problem can be reduced to a simple MCBM problem |
00755 |
Fetching from uHunt |
non-starred |
Direct Addressing Table; convert the letters except Q and Z to 2-9; keep 0-9 as 0-9; sort the integers; find duplicates if any |
00756 |
Fetching from uHunt |
non-starred |
Chinese Remainder Theorem |
00758 |
Fetching from uHunt |
non-starred |
floodfill |
00759 |
Fetching from uHunt |
non-starred |
Roman number and validity check |
00760 |
Fetching from uHunt |
non-starred |
Longest Common Substring of two strings |
00762 |
Fetching from uHunt |
non-starred |
simple SSSP solvable with BFS; use mapper |
00763 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
Zeckendorf representation; greedy; use Java BigInteger |
00775 |
Fetching from uHunt |
non-starred |
backtracking suffices as the search space is small; it is more likely to have a Hamiltonian cycle in a dense graph; so we can prune early; we do NOT have to find the best one like in TSP |
00776 |
Fetching from uHunt |
non-starred |
label CCs with indices; format output |
00782 |
Fetching from uHunt |
non-starred |
replace spaces with hexes in the grid; similar to UVa 784 and 785 |
00784 |
Fetching from uHunt |
non-starred |
similar to UVa 782 and 785 |
00785 |
Fetching from uHunt |
non-starred |
similar to UVa 782 and 784 |
00787 |
Fetching from uHunt |
3.5a, Max 1D Range Sum |
max 1D range product; be careful with 0; use Java BigInteger |
00790 |
Fetching from uHunt |
2.2c, algorithm/Collections |
multi-fields sorting; use sort; similar to UVa 10258 |
00793 |
Fetching from uHunt |
non-starred |
trivial; application of disjoint sets |
00795 |
Fetching from uHunt |
non-starred |
prepare an 'inverse mapper' |
00796 |
Fetching from uHunt |
non-starred |
finding bridges |
00808 |
Fetching from uHunt |
non-starred |
grid; similar to UVa 10182 |
00811 |
Fetching from uHunt |
non-starred |
LA 5211 - WorldFinals Eindhoven99; get CH and perimeter of polygon; generate all subsets iteratively with bitmask |
00812 |
Fetching from uHunt |
non-starred |
LA 5212 - WorldFinals Eindhoven99; mix between greedy and DP |
00815 |
Fetching from uHunt |
non-starred |
LA 5215 - WorldFinals Eindhoven99; volume; greedy; sort by height; simulation |
00816 |
Fetching from uHunt |
non-starred |
LA 5216 - WorldFinals Orlando00; build the graph; then run BFS with state s: (row; col; dir) |
00820 |
Fetching from uHunt |
4.6a, Network Flow, Standard |
LA 5220 - WorldFinals Orlando00; very basic max flow problem |
00821 |
Fetching from uHunt |
4.5a, APSP, Standard |
LA 5221 - WorldFinals Orlando00; one of the easiest ICPC WorldFinals problem |
00824 |
Fetching from uHunt |
non-starred |
traversal on implicit graph |
00825 |
Fetching from uHunt |
4.7b, Counting Paths, Easier |
counting paths in grid (implicit DAG); DP; similar to UVa 926 and 11067 |
00830 |
Fetching from uHunt |
non-starred |
very hard to get AC; one minor error = WA; not recommended |
00833 |
Fetching from uHunt |
non-starred |
recursive check; use the ccw tests |
00834 |
Fetching from uHunt |
non-starred |
do as asked |
00836 |
Fetching from uHunt |
non-starred |
convert '0' to -INF |
00837 |
Fetching from uHunt |
non-starred |
line segments; sort x-coords first |
00839 |
Fetching from uHunt |
non-starred |
can be viewed as a recursive problem on tree |
00840 |
Fetching from uHunt |
non-starred |
a simple problem to detect cycle in a graph; however the output format is not clearly specified |
00843 |
Fetching from uHunt |
non-starred |
backtracking; try mapping each letter to another letter in alphabet; use Trie data structure to speed up if a certain (partial) word is in the dictionary |
00846 |
Fetching from uHunt |
non-starred |
uses the sum of arithmetic progression formula |
00847 |
Fetching from uHunt |
non-starred |
simulate the perfect play |
00848 |
Fetching from uHunt |
non-starred |
tedious string processing |
00850 |
Fetching from uHunt |
non-starred |
plaintext attack; tricky test cases |
00852 |
Fetching from uHunt |
non-starred |
interesting board game 'Go' |
00855 |
Fetching from uHunt |
non-starred |
sort; median |
00856 |
Fetching from uHunt |
non-starred |
3 nested loops; one for each digit |
00857 |
Fetching from uHunt |
non-starred |
MIDI; application in computer music |
00858 |
Fetching from uHunt |
non-starred |
vertical line and polygon intersection; sort; alternating segments |
00859 |
Fetching from uHunt |
non-starred |
BFS |
00860 |
Fetching from uHunt |
non-starred |
frequency counting |
00861 |
Fetching from uHunt |
non-starred |
backtracking with pruning as in 8-queens recursive backtracking solution; then pre-calculate the results |
00865 |
Fetching from uHunt |
non-starred |
simple character substitution mapping |
00866 |
Fetching from uHunt |
non-starred |
use line segment intersection library; O(n^2) solution can pass |
00868 |
Fetching from uHunt |
3.2g, Backtracking (Medium) |
backtracking from row 1 to N; 4 choices per step; some constraints |
00869 |
Fetching from uHunt |
non-starred |
run Warshall's 2x; compare AdjMatrices |
00871 |
Fetching from uHunt |
non-starred |
find the size of the largest CC |
00872 |
Fetching from uHunt |
4.2d, Topological Sort |
similar to UVa 124; use backtracking |
00880 |
Fetching from uHunt |
non-starred |
grid; similar to UVa 264 |
00882 |
Fetching from uHunt |
non-starred |
s: (lo; hi; mailbox\_left); try all |
00884 |
Fetching from uHunt |
non-starred |
numPF(N); precalculate |
00886 |
Fetching from uHunt |
non-starred |
convert first letter of given name and all the letters of the surname into digits; then do a kind of special string matching where we want the matching to start at the prefix of a string |
00890 |
Fetching from uHunt |
non-starred |
simulation; follow the steps; tedious |
00892 |
Fetching from uHunt |
non-starred |
basic string processing problem |
00893 |
Fetching from uHunt |
non-starred |
use Java GregorianCalendar; similar to UVa 11356 |
00895 |
Fetching from uHunt |
non-starred |
get the letter frequency of each word; compare with puzzle line |
00897 |
Fetching from uHunt |
non-starred |
sieve; just need to check digit rotations |
00900 |
Fetching from uHunt |
non-starred |
combinatorics; the pattern ~ Fibonacci |
00902 |
Fetching from uHunt |
6.3c, Frequency Counting |
read char by char; count word freq |
00906 |
Fetching from uHunt |
non-starred |
compute c from d = 1 until a/b < c/d |
00907 |
Fetching from uHunt |
4.7c, Conversion to DAG |
s: (pos; night_left) |
00908 |
Fetching from uHunt |
4.3a, MST, Standard |
basic MST problem |
00910 |
Fetching from uHunt |
non-starred |
s: (pos; move_left) |
00911 |
Fetching from uHunt |
non-starred |
there is a formula for this: result = n! / (z_1! * z_2! * z_3! * ... * z_k!$) |
00912 |
Fetching from uHunt |
non-starred |
simulation; find and replace |
00913 |
Fetching from uHunt |
non-starred |
derive the short formulas |
00914 |
Fetching from uHunt |
non-starred |
sieve; be careful with L and U < 2 |
00918 |
Fetching from uHunt |
6.3h, Output Formatting, Harder |
tedious; follow the steps |
00920 |
Fetching from uHunt |
non-starred |
Euclidean dist |
00922 |
Fetching from uHunt |
non-starred |
first; compute the area of the polygon; for every pair of points; define a rectangle with those 2 points; use set to see if a third point of the rectangle is on the polygon; keep the current best |
00924 |
Fetching from uHunt |
non-starred |
the spread is like BFS traversal |
00925 |
Fetching from uHunt |
non-starred |
transitive closure |
00926 |
Fetching from uHunt |
non-starred |
counting paths in grid (implicit DAG); DP; similar to UVa 825 and 11067 |
00927 |
Fetching from uHunt |
3.2a, Iterative (One Loop) |
use sum of arithmetic series |
00928 |
Fetching from uHunt |
non-starred |
s: (row; col; direction; step) |
00929 |
Fetching from uHunt |
non-starred |
on a 2D maze/implicit graph |
00930 |
Fetching from uHunt |
5.2i, Polynomial |
Ruffini's rule; roots of quadratic eq |
00939 |
Fetching from uHunt |
non-starred |
map child name to his/her gene and parents' names |
00941 |
Fetching from uHunt |
non-starred |
formula to get the n-th permutation |
00942 |
Fetching from uHunt |
non-starred |
similar to UVa 202 |
00943 |
Fetching from uHunt |
non-starred |
the Portuguese rule is not given; use translation service in the Internet to help you solve this problem |
00944 |
Fetching from uHunt |
non-starred |
similar to UVa 10591 |
00945 |
Fetching from uHunt |
non-starred |
simulate the given cargo loading process |
00946 |
Fetching from uHunt |
non-starred |
just 1D array manipulation; be careful with the special restriction |
00947 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
similar to UVa 340 |
00948 |
Fetching from uHunt |
non-starred |
Zeckendorf representation; greedy |
00949 |
Fetching from uHunt |
non-starred |
interesting graph data structure twist |
00957 |
Fetching from uHunt |
non-starred |
complete search binary search: upper_bound |
00960 |
Fetching from uHunt |
non-starred |
there is a number theory behind this |
00962 |
Fetching from uHunt |
non-starred |
pre-calculate the answer |
00967 |
Fetching from uHunt |
non-starred |
similar to UVa 897; but this time the output part can be speed up using DP 1D range sum |
00974 |
Fetching from uHunt |
non-starred |
there are not that many Kaprekar numbers |
00976 |
Fetching from uHunt |
8.5c, Graph and DP |
use a kind of flood fill to separate north and south banks; use it to compute the cost of installing a bridge at each column; a DP solution should be quite obvious after this preprocessing |
00978 |
Fetching from uHunt |
2.3b, set/TreeSet |
simulation; use multiset |
00983 |
Fetching from uHunt |
non-starred |
max 2D range sum; get submatrix |
00985 |
Fetching from uHunt |
non-starred |
4 rotations is the same as 0 rotations; s: (row; col; rotation = [0..3]); find the shortest path from state [1][1][0] to state [R][C][x] where 0 <= x <= 3 |
00986 |
Fetching from uHunt |
non-starred |
counting paths in DAG; DP; s: (x; y; lastmove; peaksfound); t: try NE/SE |
00988 |
Fetching from uHunt |
non-starred |
counting paths in DAG; DP |
00989 |
Fetching from uHunt |
non-starred |
classic Su Doku puzzle; this problem is NP-Complete but this instance is solvable with backtracking with pruning; use bitmask to speed up the check of available digits |
00990 |
Fetching from uHunt |
non-starred |
print the solution |
00991 |
Fetching from uHunt |
5.4c, Catalan Numbers |
Catalan Numbers |
00993 |
Fetching from uHunt |
non-starred |
find divisors from 9 down to 1; similar to UVa 10527 |
01013 |
Fetching from uHunt |
4.3b, MST, Variants |
LA 2478 - WorldFinals Honolulu02; very interesting MST variant |
01025 |
Fetching from uHunt |
8.3a, DP level 2 |
s: (station, cur_t); t: stay until meeting time (if at station N), or either go to right or go to left using any of the available next train, pick the minimum |
01039 |
Fetching from uHunt |
non-starred |
LA 3270 - WorldFinals Shanghai05; build the graph with simple geometry; then use Floyd Warshall's |
01040 |
Fetching from uHunt |
8.5h, Three Components |
LA 3271 - WorldFinals Shanghai05; iterative complete search: try all subsets of 2^20 cities; form MST with those cities with help of Union-Find DS; complex output formatting |
01045 |
Fetching from uHunt |
non-starred |
LA 3276 - WorldFinals Shanghai05; try all possible final configuration; do a weighted matching; and pick the best configuration; use Kuhn Munkres's algorithm |
01047 |
Fetching from uHunt |
3.2e, Iterative (Fancy Techniques) |
LA 3278 - WorldFinals Shanghai05; notice that n ≤ 20 so that we can try all possible subsets of towers to be taken; then apply inclusion-exclusoin principle to avoid overcounting |
01048 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
LA 3561 - WorldFinals SanAntonio06; tedious state-space search problem; use Dijkstra's |
01052 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
LA 3565 - WorldFinals SanAntonio06; backtracking with some form of bitmask |
01056 |
Fetching from uHunt |
4.5b, APSP, Variants |
LA 3569 - WorldFinals SanAntonio06; finding diameter of a small graph with Floyd Warshall's |
01057 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
LA 3570 - WorldFinals SanAntonio06; use Floyd Warshall's to get APSP information; then model the original problem as another weighted SSSP problem solvable with Dijkstra's |
01060 |
Fetching from uHunt |
non-starred |
LA 4119 - WorldFinals Banff08; not too hard but tedious problem: involving string parsing; basic understanding of divisibility of polynomial; brute force; and modPow |
01061 |
Fetching from uHunt |
1.4f, Real Life, Harder |
LA 3736 - WorldFinals Tokyo07; consanguine = blood; try all eight possible blood Rh types with the information given in the problem description |
01062 |
Fetching from uHunt |
2.2e, Stack |
LA 3752 - WorldFinals Tokyo07; simulation with stack; maximum answer is 26 stacks; O(n) solution exists |
01064 |
Fetching from uHunt |
3.2e, Iterative (Fancy Techniques) |
LA 3808 - WorldFinals Tokyo07; permutation of up to 5 messages; simulation; mind the word 'consecutive' |
01069 |
Fetching from uHunt |
8.5e, Maths and Other |
LA 4119 - WorldFinals Banff08; not too hard but tedious problem: involving string parsing, basic understanding of divisibility of polynomial, brute force, and modPow |
01076 |
Fetching from uHunt |
non-starred |
LA 4126 - WorldFinals Banff08; preprocess the strings; challenging DP bitmask; output up to 42 possible solutions |
01079 |
Fetching from uHunt |
non-starred |
LA 4445 - WorldFinals Stockholm09; iterative complete search (permutation); then binary search the answer and greedy |
01086 |
Fetching from uHunt |
non-starred |
LA 4452 - WorldFinals Stockholm09; can be modeled as a 2-SAT problem |
01091 |
Fetching from uHunt |
1.4f, Real Life, Harder |
LA 4786 - WorldFinals Harbin10; tedious simulation and reading comprehension |
01092 |
Fetching from uHunt |
8.5d, Graph and Other |
LA 4787 - WorldFinals Harbin10; compress the graph first; do graph traversal from exit using only south and west direction; inclusion-exclusion |
01093 |
Fetching from uHunt |
non-starred |
LA 4788 - WorldFinals Harbin10; try all possible roots; DP on tree |
01096 |
Fetching from uHunt |
non-starred |
LA 4791 - WorldFinals Harbin10; Bitonic TSP variant; print the actual path |
01098 |
Fetching from uHunt |
8.4a, NP-hard/complete, small |
LA 4793 - WorldFinals Harbin10; decide if there is a Hamiltonian Tour in the given grid which is NP-Complete; either backtracking with pruning or meet in the middle |
01099 |
Fetching from uHunt |
8.3f, DP in ICPC |
LA 4794 - WorldFinals Harbin10; s: (w; bitmask); recover parameter value h |
01103 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
LA 5130 - WorldFinals Orlando11; major hint: each hieroglyph has unique number of white CCs |
01105 |
Fetching from uHunt |
3.5b, Max 2D Range Sum |
LA 5132 - WorldFinals Orlando11; more advanced 2D Range Sum Queries |
01111 |
Fetching from uHunt |
7.3b, Polygon, Harder |
LA 5138 - WorldFinals Orlando11; CH; distance of each CH side--which is parallel to the side--to each vertex of CH |
01112 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
LA 2425 - SouthwesternEurope01; run Dijkstra's from destination |
01121 |
Fetching from uHunt |
non-starred |
LA 2678 - SouthEasternEurope06; sliding window variant |
01124 |
Fetching from uHunt |
1.3a, Super Easy |
LA 2681 - SouthEasternEurope06; just echo/re-print the input again |
01148 |
Fetching from uHunt |
non-starred |
LA 3502 - SouthWesternEurope05; single source single target shortest path problem but exclude endpoints |
01160 |
Fetching from uHunt |
non-starred |
LA 3644 - SouthWesternEurope06; count the number of edges not taken by Kruskal's |
01172 |
Fetching from uHunt |
8.3e, DP Matching |
LA 3986 - SouthWesternEurope07; non classic DP; a bit of graph matching but with additional left to right and OS type constraints |
01174 |
Fetching from uHunt |
non-starred |
LA 3988 - SouthWesternEurope07; classic MST; just need a mapper to map city names to indices |
01176 |
Fetching from uHunt |
non-starred |
LA 2346 - Dhaka01; special case when k = 2; use Josephus recurrence; simulation |
01180 |
Fetching from uHunt |
5.3c, (Prob) Prime Testing |
LA 2350 - Dhaka01; small prime check |
01184 |
Fetching from uHunt |
non-starred |
LA 2696 - Dhaka02; MPC on DAG ~ MCBM |
01185 |
Fetching from uHunt |
non-starred |
LA 2697 - Dhaka02; number of digits of factorial; use logarithm to solve it; log(n!) = log(n * (n-1) * ... * 1) = log(n) plus log(n-1) plus ... plus log(1) |
01192 |
Fetching from uHunt |
non-starred |
LA 2460 - Singapore01; classic string alignment DP problem with a bit of output formatting |
01193 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
LA 2519 - Beijing02; interval covering |
01194 |
Fetching from uHunt |
4.7f, Bipartite Graph |
LA 2523 - Beijing02; Min Vertex Cover/MVC |
01195 |
Fetching from uHunt |
non-starred |
LA 2565 - Kanazawa02; use sieve to generate the list of primes; brute force each prime p; and use binary search to find the corresponding pair q |
01196 |
Fetching from uHunt |
3.5c, LIS |
LA 2815 - Kaohsiung03; sort all the blocks in increasing L[i]; then we get the classical LIS problem |
01197 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
LA 2817 - Kaohsiung03; Connected Components |
01198 |
Fetching from uHunt |
non-starred |
LA 2818 - Kaohsiung03; transitive closure |
01200 |
Fetching from uHunt |
6.3d, Iterative Parsing |
LA 2972 - Tehran03; the hard part is to parse and tokenize the linear equation |
01201 |
Fetching from uHunt |
non-starred |
LA 3126 - NorthwesternEurope04; MPC on DAG |
01202 |
Fetching from uHunt |
non-starred |
LA 3133 - Beijing04; SSSP; Dijkstra's on a grid: treat each cell as a vertex; the idea is simple but one should be careful with the implementation |
01203 |
Fetching from uHunt |
non-starred |
LA 3135 - Beijing04; use priority_queue |
01206 |
Fetching from uHunt |
non-starred |
LA 3169 - Manila06; CH; input is formatted in complex manner |
01207 |
Fetching from uHunt |
non-starred |
LA 3170 - Manila06; classical String Edit problem |
01208 |
Fetching from uHunt |
non-starred |
LA 3171 - Manila06; MST |
01209 |
Fetching from uHunt |
non-starred |
LA 3173 - Manila06; STL next and prev_permutation |
01210 |
Fetching from uHunt |
5.3c, (Prob) Prime Testing |
LA 3399 - Tokyo05; simple |
01211 |
Fetching from uHunt |
non-starred |
LA 3404 - Tokyo05; precompute array T[L]; the time to run a path of length L; DP with one parameter i; where i is the checkpoint where we change tire; if i = n; we do not change the tire |
01212 |
Fetching from uHunt |
8.4b, NP-hard/complete, special |
LA 3483 - Hangzhou05; MWIS on Bipartite Graph |
01213 |
Fetching from uHunt |
3.5d, 0-1 Knapsack |
LA 3619 - Yokohama06; extension of 0-1 Knapsack; s: (id; remN; remK) instead of s: (id; remN) |
01215 |
Fetching from uHunt |
non-starred |
LA 3669 - Hanoi06 |
01216 |
Fetching from uHunt |
non-starred |
LA 3678 - Kaohsiung06; minimum 'spanning forest' |
01217 |
Fetching from uHunt |
non-starred |
LA 3681 - Kaohsiung06; TSP-like optimization problem; which is NP-Hard; solvable with A*/IDA* |
01219 |
Fetching from uHunt |
non-starred |
LA 3791 - Tehran06 |
01220 |
Fetching from uHunt |
non-starred |
LA 3794 - Tehran06; Maximum Independent Set (MIS) problem on tree; DP; also check if the MIS is unique |
01221 |
Fetching from uHunt |
8.5a, Bsearch-ans and Others |
LA 3795 - Tehran06; binary search the answer and MCBM (perfect matching) |
01222 |
Fetching from uHunt |
non-starred |
LA 3797 - Tehran06; DP on Tree |
01224 |
Fetching from uHunt |
5.4e, Others, Harder |
LA 3904 - Seoul07; derive formula from observing the small instances first |
01225 |
Fetching from uHunt |
5.2b, Math Simulation, Easier |
LA 3996 - Danang07; N is small |
01226 |
Fetching from uHunt |
non-starred |
LA 3997 - Danang07; mod operation |
01229 |
Fetching from uHunt |
non-starred |
LA 4099 - Iran07; identify the SCC of the graph; these vertices and the vertices that have path towards them (e.g. needed to understand these words too) are the answers of the question |
01230 |
Fetching from uHunt |
5.3d, Bonus: Others |
LA 4104 - Singapore07; modPow |
01231 |
Fetching from uHunt |
non-starred |
LA 4106 - Singapore07; DP with dimension reduction |
01232 |
Fetching from uHunt |
non-starred |
LA 4108 - Singapore07; we have to use a Segment Tree; note that this problem is not about RSQ/RMQ |
01233 |
Fetching from uHunt |
non-starred |
LA 4109 - Singapore07; Floyd Warshall's can be used to find the minimum cost cycle in the graph; the maximum input graph size is p <= 500 but still doable in UVa online judge |
01234 |
Fetching from uHunt |
non-starred |
LA 4110 - Singapore07; 'maximum' spanning tree |
01235 |
Fetching from uHunt |
non-starred |
LA 4138 - Jakarta08; the underlying problem is MST |
01237 |
Fetching from uHunt |
3.2a, Iterative (One Loop) |
LA 4142 - Jakarta08; input is small |
01238 |
Fetching from uHunt |
8.3f, DP in ICPC |
LA 4143 - Jakarta08; handle negative parameter with offset technique |
01239 |
Fetching from uHunt |
non-starred |
LA 4144 - Jakarta08; as S <= 1000; brute-force is enough; consider odd and even length palindromes |
01240 |
Fetching from uHunt |
8.3f, DP in ICPC |
LA 4146 - Jakarta08; a medium-level DP problem |
01241 |
Fetching from uHunt |
non-starred |
LA 4147 - Jakarta08; easy |
01242 |
Fetching from uHunt |
non-starred |
LA 4271 - Hefei08; to have a necklace; we need to be able to two edge-disjoint s-t flows |
01243 |
Fetching from uHunt |
non-starred |
LA 4272 - Hefei08; Warshall's transitive closure; SCC; transitive reduction of a directed graph |
01244 |
Fetching from uHunt |
non-starred |
LA 4336 - Amritapuri08; store the best path between i; j; the DP table contains strings |
01246 |
Fetching from uHunt |
non-starred |
LA 4340 - Amrita08; numDiv(N) |
01247 |
Fetching from uHunt |
4.5a, APSP, Standard |
LA 4524 - Hsinchu09; Floyd Warshall's with modification: prefer shortest path with less intermediate vertices |
01249 |
Fetching from uHunt |
non-starred |
LA 4601 - SoutheastUSA09; vector |
01250 |
Fetching from uHunt |
8.5h, Three Components |
LA 4607 - SoutheastUSA09; geometry; SSSP on DAG -> DP; DP 1D range sum |
01251 |
Fetching from uHunt |
non-starred |
LA 4637 - Tokyo09 |
01252 |
Fetching from uHunt |
8.3f, DP in ICPC |
LA 4643 - Tokyo09; DP; s: (bitmask1; bitmask2) where bitmask1 describes the features that we decide to ask and bitmask2 describes the answers of the features that we ask |
01253 |
Fetching from uHunt |
non-starred |
LA 4645 - Tokyo09; tedious state modeling |
01254 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
LA 4657 - Jakarta09; Suffix Array with Segment Tree |
01258 |
Fetching from uHunt |
non-starred |
LA 4721 - Phuket09; Fibonacci variant; Zeckendorf representation; greedy |
01260 |
Fetching from uHunt |
non-starred |
LA 4843 - Daejeon10; check all |
01261 |
Fetching from uHunt |
non-starred |
LA 4844 - Daejeon10; a simple backtracking problem; but we use a setÃ¿to prevent the same state (a substring) from being checked twice |
01262 |
Fetching from uHunt |
3.2h, Backtracking (Harder) |
LA 4845 - Daejeon10; sort the columns in the two 6*5 grids first so that we can process common passwords in lexicographic order; backtracking; important: skip two similar passwords |
01263 |
Fetching from uHunt |
non-starred |
LA 4846 - Daejeon10; geometry; SCC; see two related problems: UVa 11504 and 11770 |
01265 |
Fetching from uHunt |
4.3b, MST, Variants |
LA 4848 - Daejeon10; very interesting non-standard variant of 'maximum' spanning tree |
01266 |
Fetching from uHunt |
non-starred |
LA 3478 - LatinAmerica05; follow the given construction strategy |
01280 |
Fetching from uHunt |
8.5a, Bsearch-ans and Others |
LA 6027 - WorldFinals Warsaw12; binary search the answer and geometric formula |
01281 |
Fetching from uHunt |
3.5f, TSP |
LA 6028 - WorldFinals Warsaw12; a harder version of DP TSP with special constraints on the order of visitation |
01304 |
Fetching from uHunt |
9.4, Art Gallery |
LA 2512 - SouthEasternEurope02; cutPolygon and area of polygon |
01315 |
Fetching from uHunt |
non-starred |
find the pattern; hint: odd indices |
01329 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
LA 3027 - SouthEasternEurope04; interesting variant of UFDS; we need to cleverly modify the union and find routine to suit this problem |
01339 |
Fetching from uHunt |
non-starred |
count character frequencies of both strings; sort and compare |
01347 |
Fetching from uHunt |
8.4b, NP-hard/complete, special |
LA 3305 - SoutheasternEurope05; this is the pure version of Bitonic TSP problem; you may want to start from here |
01368 |
Fetching from uHunt |
non-starred |
the character at column j of the consensus string is the one with highest frequency among all j-th column of all m DNA strings; the error can be computed afterwards |
01388 |
Fetching from uHunt |
7.2c, Circles |
LA 3708 - NortheasternEurope06; divide the circle into n sectors first and then into (n m) sectors |
01449 |
Fetching from uHunt |
non-starred |
LA 4670 - Hefei09; just use strstr; Suffix Array will get TLE as there are too many long strings to be processed |
01513 |
Fetching from uHunt |
2.4c, Tree-related DS |
LA 5902 - NorthWesternEurope11; although the problem describes a stack; this is a just a dynamic range sum query; use Fenwick Tree |
01571 |
Fetching from uHunt |
9.4, Art Gallery |
LA 3617 - Yokohama06; cutPolygon |
01583 |
Fetching from uHunt |
non-starred |
N is small; prepare an array of size 100044; that is the largest possible digit sum for this problem |
01584 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
LA 3225 - Seoul04; min lexicographic rotation; similar with UVa 719; but this problem is solvable without Suffix Array as the input constraint is small; try this problem with larger input |
01585 |
Fetching from uHunt |
1.3a, Super Easy |
LA 3354 - Seoul05; very easy one pass algorithm |
01586 |
Fetching from uHunt |
1.4e, Real Life, Easier |
LA 3900 - Seoul07; basic Chemistry |
01588 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
LA 3712 - NorthEasternEurope06; good iterative brute force problem; beware of corner cases |
01595 |
Fetching from uHunt |
7.2a, Points |
use set to record the positions of all sorted points; check half of the points if the symmetries are in the set too? |
01600 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
LA 3670 - Hanoi06; s: (row; col; k_left); reset k_left to the original k as soon as the robot enters a non obstacle cell |
01605 |
Fetching from uHunt |
6.3g, Output Formatting, Easier |
LA 4044 - NortheasternEurope07; we can answer this problem with just h=2 levels; think of how to make cells from one country intersect at least one other cell from other country |
01610 |
Fetching from uHunt |
2.2c, algorithm/Collections |
LA 6196 - MidAtlanticUSA12; sort; median; be careful of corner cases |
01636 |
Fetching from uHunt |
5.6a, Probability, Easier |
LA 4596 - NorthEasternEurope09; ad hoc probability question; one tricky special case involving all zeroes where the answer should be 'EQUAL' |
01641 |
Fetching from uHunt |
non-starred |
scan row by row; flip the status of inside/outside polygon due to the presence of character slash or backslash |
01644 |
Fetching from uHunt |
5.5a, Prime Numbers |
LA 3883 - Tokyo07; sieve; prime check; upper bound - lower bound |
01645 |
Fetching from uHunt |
non-starred |
LA 6368 - Chengdu12; number of rooted trees with n vertices in which vertices at the same level have the same degree |
01647 |
Fetching from uHunt |
non-starred |
find the simple pattern first using brute force; then precompute the answers using BigInteger |
01709 |
Fetching from uHunt |
1.3b, Easy |
LA 7150 - WorldFinals Marrakech15; linear scan; probably one of the easiest WorldFinals problem |
01714 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
LA 7155 - WorldFinals Marrakech15; Pre-process the adjacent cells with similar characters; s: (row; col; char-typed) |
01721 |
Fetching from uHunt |
1.4i, Time Waster |
LA 7162 - WorldFinals Marrakech15; tedious simulation problem; separates team with a better coder with the rest |
01738 |
Fetching from uHunt |
3.3c, Other DnC Problems |
LA 7578 - WorldFinals Phuket16; a problem about BST insertion+tree equality check; we do not actually use set here; also available at Kattis - ceiling |
01753 |
Fetching from uHunt |
3.3b, Binary Search the Answer |
LA 8043 - WorldFinals RapidCity17; binary search the answer + Physics; also available at Kattis - speed |
01757 |
Fetching from uHunt |
4.5b, APSP, Variants |
LA 8047 - WorldFinals RapidCity17; Warshall's transitive closure; also available at Kattis - secretchamber |
10000 |
Fetching from uHunt |
non-starred |
longest paths on DAG; backtracking OK |
10001 |
Fetching from uHunt |
non-starred |
the upperbound of 2^32 is scary but with efficient pruning; we can pass the time limit as the test case is not extreme |
10002 |
Fetching from uHunt |
non-starred |
centroid; center of CH; area of polygon |
10003 |
Fetching from uHunt |
3.5g, DP level 1 |
s: (l; r) |
10004 |
Fetching from uHunt |
4.2e, Bipartite Graph Check |
bipartite graph check |
10005 |
Fetching from uHunt |
7.2c, Circles |
complete search; use circle2PtsRad |
10006 |
Fetching from uHunt |
non-starred |
non prime which has >= 3 prime factors |
10007 |
Fetching from uHunt |
5.4c, Catalan Numbers |
answer is Cat(n) * n!; BigInteger |
10008 |
Fetching from uHunt |
6.3c, Frequency Counting |
character frequency count |
10009 |
Fetching from uHunt |
non-starred |
simple SSSP solvable with BFS |
10010 |
Fetching from uHunt |
6.4b, String Matching, 2D Grid |
2D grid; backtracking |
10012 |
Fetching from uHunt |
non-starred |
try all 8! permutations; Euclidean dist |
10013 |
Fetching from uHunt |
non-starred |
BigInteger addition |
10014 |
Fetching from uHunt |
non-starred |
derive the required formula |
10015 |
Fetching from uHunt |
non-starred |
modified Josephus; dynamic k; variant of UVa 305 |
10016 |
Fetching from uHunt |
non-starred |
tedious |
10017 |
Fetching from uHunt |
non-starred |
classical problem |
10018 |
Fetching from uHunt |
non-starred |
generating palindrome with specific math simulation; very easy |
10019 |
Fetching from uHunt |
non-starred |
find the pattern |
10020 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
interval covering |
10021 |
Fetching from uHunt |
non-starred |
s: (row; col; cube position; which is a permutation of 6 sides) or up to 10*10*720 = 72000 distinct states |
10022 |
Fetching from uHunt |
5.2f, Grid |
this is not an SSSP problem; find the pattern in this grid (triangle)-like system |
10023 |
Fetching from uHunt |
non-starred |
code Newton's method with BigInteger |
10025 |
Fetching from uHunt |
non-starred |
simplify the formula first; iterative |
10026 |
Fetching from uHunt |
non-starred |
greedy; sorting |
10028 |
Fetching from uHunt |
non-starred |
tedious simulation with several corner cases |
10029 |
Fetching from uHunt |
non-starred |
use map as memo table |
10032 |
Fetching from uHunt |
non-starred |
DP Knapsack with optimization to avoid TLE |
10033 |
Fetching from uHunt |
non-starred |
adhoc; simulation |
10034 |
Fetching from uHunt |
non-starred |
straightforward MST problem |
10035 |
Fetching from uHunt |
non-starred |
count the number of carry operations |
10036 |
Fetching from uHunt |
non-starred |
must use offset technique as value can be negative |
10037 |
Fetching from uHunt |
non-starred |
greedy; sorting |
10038 |
Fetching from uHunt |
2.2a, 1D Array Manipulation |
1D Boolean flags to check [1..n-1] |
10039 |
Fetching from uHunt |
non-starred |
create the graph first; then apply DP; s: (city; curtime); t: try all feasible trains |
10041 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
try all possible locations |
10042 |
Fetching from uHunt |
non-starred |
prime factorization; sum the digits |
10044 |
Fetching from uHunt |
non-starred |
the input parsing part is troublesome |
10045 |
Fetching from uHunt |
non-starred |
brute force string processing |
10047 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
s: (row; col; direction; color) |
10048 |
Fetching from uHunt |
4.3b, MST, Variants |
classic minimax path problem; also solvable with Floyd Warshall's |
10049 |
Fetching from uHunt |
non-starred |
enough to get past > 2G by storing only the first 700K numbers of the Self-describing sequence |
10050 |
Fetching from uHunt |
non-starred |
1D boolean flag |
10051 |
Fetching from uHunt |
non-starred |
longest paths on DAG; DP |
10054 |
Fetching from uHunt |
4.7e, Eulerian Graph |
printing the Euler tour |
10055 |
Fetching from uHunt |
5.2a, The Simpler Ones |
absolute function; the only trap is to use long long |
10056 |
Fetching from uHunt |
5.6b, Probability, Harder |
get the closed form formula |
10057 |
Fetching from uHunt |
non-starred |
involves the median; use STL sort; upper_bound; lower_bound and some checks |
10058 |
Fetching from uHunt |
6.3f, Regular Expression |
solvable with Java regular expression |
10060 |
Fetching from uHunt |
non-starred |
area of polygon; area of circle |
10061 |
Fetching from uHunt |
non-starred |
in Decimal; '10' with 1 zero is due to factor 2*5 |
10062 |
Fetching from uHunt |
non-starred |
ASCII character frequency count |
10063 |
Fetching from uHunt |
non-starred |
do as asked |
10065 |
Fetching from uHunt |
non-starred |
find area of polygon; the CH; then area of CH |
10066 |
Fetching from uHunt |
non-starred |
Longest Common Subsequence problem; but not on 'string' |
10067 |
Fetching from uHunt |
non-starred |
implicit graph in problem statement |
10068 |
Fetching from uHunt |
non-starred |
use BFS from each position to create the APSP data; use backtracking with bitmask and pruning to get the best solution |
10069 |
Fetching from uHunt |
non-starred |
use Java BigInteger |
10070 |
Fetching from uHunt |
non-starred |
more than ordinary leap years |
10071 |
Fetching from uHunt |
non-starred |
super simple: output 2*v*t |
10074 |
Fetching from uHunt |
non-starred |
standard problem |
10075 |
Fetching from uHunt |
non-starred |
Great Circle Distance (gcDistance) with APSP |
10077 |
Fetching from uHunt |
non-starred |
binary search |
10078 |
Fetching from uHunt |
9.4, Art Gallery |
isConvex |
10079 |
Fetching from uHunt |
non-starred |
derive the one liner formula |
10080 |
Fetching from uHunt |
non-starred |
MCBM |
10081 |
Fetching from uHunt |
non-starred |
use doubles |
10082 |
Fetching from uHunt |
1.4e, Real Life, Easier |
this typographical error happens to us sometimes; use 2D mapper array to simplify the problem |
10083 |
Fetching from uHunt |
non-starred |
BigInteger number theory |
10085 |
Fetching from uHunt |
non-starred |
each vertex is the 9 puzzle configuration; BFS from starting configuration to all vertices; print longest shortest path |
10086 |
Fetching from uHunt |
non-starred |
s: (idx; rem1; rem2); which site that we are now; up to 30 sites; remaining rods to be tested at NCPC; and remaining rods to be tested at BCEW; t: for each site; we split the rods; x rods to be tested at NCPC and m[i] - x rods to be tested at BCEW; p |
10088 |
Fetching from uHunt |
non-starred |
Pick's Theorem |
10090 |
Fetching from uHunt |
5.5i, Extended Euclid |
use solution for Linear Diophantine Equation |
10092 |
Fetching from uHunt |
non-starred |
assignment problem; matching with capacity; similar to UVa 259; 11045; and 12873 |
10093 |
Fetching from uHunt |
non-starred |
try all |
10094 |
Fetching from uHunt |
non-starred |
this problem is like the n-queens chess problem; but must find/use the pattern! |
10097 |
Fetching from uHunt |
non-starred |
s: (N1; N2); implicit unweighted graph |
10098 |
Fetching from uHunt |
non-starred |
very similar to UVa 195 |
10099 |
Fetching from uHunt |
non-starred |
maximin; also solvable with Floyd Warshall's |
10100 |
Fetching from uHunt |
non-starred |
Longest Common Subsequence |
10101 |
Fetching from uHunt |
non-starred |
follow the problem description carefully |
10102 |
Fetching from uHunt |
non-starred |
4 nested loops will do; we do not need BFS; get max of minimum Manhattan distance from a 1 to a 3 |
10104 |
Fetching from uHunt |
5.5i, Extended Euclid |
pure Extended Euclid problem |
10105 |
Fetching from uHunt |
non-starred |
similar to UVa 911 |
10106 |
Fetching from uHunt |
non-starred |
BigInteger multiplication |
10107 |
Fetching from uHunt |
non-starred |
find median of a growing/dynamic list of integers; solvable with multiple calls of nth_element in algorithm |
10111 |
Fetching from uHunt |
5.8a, Game Theory |
Tic-Tac-Toe; minimax; backtracking |
10112 |
Fetching from uHunt |
non-starred |
test if point inPolygon/inTriangle; similar with UVa 478 |
10113 |
Fetching from uHunt |
non-starred |
just graph traversal; but uses fraction and GCD |
10114 |
Fetching from uHunt |
non-starred |
just simulate the process |
10115 |
Fetching from uHunt |
6.3j, Ad Hoc String |
simply do as asked in the problem description; uses string |
10116 |
Fetching from uHunt |
non-starred |
traversal on implicit graph |
10118 |
Fetching from uHunt |
non-starred |
DP bitmask; not trivial |
10120 |
Fetching from uHunt |
non-starred |
DP; special case for N >= 49 |
10123 |
Fetching from uHunt |
8.3c, DP level 4 |
DP; s: (bitmask) that describes objects that have been taken; use Physics to determine whether those taken objects will cause the tipping or not |
10125 |
Fetching from uHunt |
non-starred |
sort; 4 nested loops; plus binary search |
10126 |
Fetching from uHunt |
non-starred |
sort the words to simplify this problem |
10127 |
Fetching from uHunt |
non-starred |
no factor of 2 and 5 implies that there is no trailing zero |
10128 |
Fetching from uHunt |
3.2j, Pre-calculate-able |
backtracking with pruning; try up to all N! (13!) permutations that satisfy the requirement; then pre-calculate the results |
10129 |
Fetching from uHunt |
non-starred |
Euler Graph property check |
10130 |
Fetching from uHunt |
3.5d, 0-1 Knapsack |
very basic 0-1 Knapsack problem |
10131 |
Fetching from uHunt |
non-starred |
sort elephants based on decreasing IQ; LIS on increasing weight |
10132 |
Fetching from uHunt |
non-starred |
use map; brute force |
10134 |
Fetching from uHunt |
non-starred |
must be very careful with details |
10136 |
Fetching from uHunt |
non-starred |
complete search; use circle2PtsRad; similar with UVa 10005 |
10137 |
Fetching from uHunt |
5.2k, Just Ad Hoc |
be careful with precision error |
10138 |
Fetching from uHunt |
2.3a, map/TreeMap |
map plates to bills; entrance time; and position |
10139 |
Fetching from uHunt |
5.5e, Prime Factors Related |
compare prime factors of n! and m |
10140 |
Fetching from uHunt |
non-starred |
sieve; linear scan |
10141 |
Fetching from uHunt |
non-starred |
solvable with one linear scan |
10142 |
Fetching from uHunt |
non-starred |
simulation |
10145 |
Fetching from uHunt |
2.3c, unordered_map/HashMap |
use map and set |
10146 |
Fetching from uHunt |
non-starred |
the problem description tries to hide the meaning of 'dictionary'; it is not a hard problem actually |
10147 |
Fetching from uHunt |
non-starred |
'minimum' spanning subgraph |
10149 |
Fetching from uHunt |
non-starred |
DP with bitmask; uses card rules; tedious |
10150 |
Fetching from uHunt |
non-starred |
BFS state is string |
10152 |
Fetching from uHunt |
non-starred |
greedy |
10154 |
Fetching from uHunt |
non-starred |
LIS variant |
10158 |
Fetching from uHunt |
non-starred |
advanced usage of disjoint sets with a nice twist; memorize list of enemies |
10160 |
Fetching from uHunt |
non-starred |
optimization version of Min Vertex Cover on general graph; Dominating Set; which is NP-Hard; strategies: backtracking; sort by decreasing degrees; heavy pruning |
10161 |
Fetching from uHunt |
5.2e, Finding Pattern, Harder |
involves sqrt; ceil... |
10162 |
Fetching from uHunt |
non-starred |
cycle after 100 steps; use Java BigInteger to read the input; precalculate |
10163 |
Fetching from uHunt |
non-starred |
try all possible safe line L and run DP; s: (id; N_left); t: hire/skip person id for looking at K storage; the DP part is similar to DP 0-1 Knapsack |
10164 |
Fetching from uHunt |
non-starred |
a bit number theory (modulo); backtracking; do memoization on DP s: (sum; taken) |
10165 |
Fetching from uHunt |
non-starred |
Nim game; application of Sprague-Grundy theorem |
10166 |
Fetching from uHunt |
non-starred |
this can be modeled as an SSSP problem |
10167 |
Fetching from uHunt |
non-starred |
brute force A and B; ccw tests |
10168 |
Fetching from uHunt |
non-starred |
backtracking with pruning |
10170 |
Fetching from uHunt |
non-starred |
one liner formula exists |
10171 |
Fetching from uHunt |
non-starred |
easy with APSP information |
10172 |
Fetching from uHunt |
2.2f, List/Queue/Deque |
use both queue and stack |
10174 |
Fetching from uHunt |
5.5h, Modulo Arithmetic |
no Spinster number |
10176 |
Fetching from uHunt |
5.5h, Modulo Arithmetic |
convert binary to decimal digit by digit; do modulo 131071 to the intermediate result |
10177 |
Fetching from uHunt |
non-starred |
2/3/4 nested loops; precalculate |
10178 |
Fetching from uHunt |
non-starred |
Euler's Formula; a bit of union find |
10179 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
EulerPhi(N) |
10180 |
Fetching from uHunt |
non-starred |
closest point from AB to origin; arc |
10181 |
Fetching from uHunt |
9.2, A* or IDA* |
similar with UVa 652 but larger (now 15 instead of 8); we can use IDA* |
10182 |
Fetching from uHunt |
5.2f, Grid |
grid |
10183 |
Fetching from uHunt |
non-starred |
get the number of Fibonaccis when generating them; BigInteger |
10187 |
Fetching from uHunt |
non-starred |
special cases: start = destination: 0 litre; starting or destination city not found or destination city not reachable from starting city: no route; the rest: Dijkstra's |
10188 |
Fetching from uHunt |
1.4i, Time Waster |
simulation |
10189 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
simulate the classic Minesweeper game; similar to UVa 10279 |
10190 |
Fetching from uHunt |
non-starred |
simulate the process |
10191 |
Fetching from uHunt |
non-starred |
you may want to apply this to your own schedule |
10192 |
Fetching from uHunt |
non-starred |
Longest Common Subsequence |
10193 |
Fetching from uHunt |
non-starred |
convert two binary strings S1 and S2 to decimal and check see if gcd(s1; s2) > 1 |
10194 |
Fetching from uHunt |
non-starred |
multi-fields sorting; use sort |
10195 |
Fetching from uHunt |
non-starred |
triangle'sincircle; Heron's formula |
10196 |
Fetching from uHunt |
non-starred |
ad hoc; chess; tedious |
10197 |
Fetching from uHunt |
non-starred |
must follow the description very closely |
10198 |
Fetching from uHunt |
non-starred |
recurrences; BigInteger |
10199 |
Fetching from uHunt |
non-starred |
finding articulation points |
10200 |
Fetching from uHunt |
non-starred |
complete search; test if isPrime(n^2 n 41) for all n in [a..b]; finally use DP 1D RSQ to speed up the solution |
10201 |
Fetching from uHunt |
non-starred |
s: (pos; fuel_left) |
10202 |
Fetching from uHunt |
non-starred |
backtracking; pruning |
10203 |
Fetching from uHunt |
4.7e, Eulerian Graph |
the underlying graph is Euler graph |
10205 |
Fetching from uHunt |
non-starred |
card game |
10209 |
Fetching from uHunt |
non-starred |
square; arcs; similar with UVa 10589 |
10210 |
Fetching from uHunt |
non-starred |
basic trigonometry |
10212 |
Fetching from uHunt |
5.5h, Modulo Arithmetic |
multiply numbers from N down to N-M plus 1; repeatedly use /10 to discard the trailing zero(es); and then use %1 Billion to only memorize the last few (maximum 9) non zero digits |
10213 |
Fetching from uHunt |
non-starred |
Moser's circle; the formula is hard to derive; g(n) = nC4 nC2 1 |
10215 |
Fetching from uHunt |
non-starred |
two trivial cases for smallest; derive the formula for largest which involves quadratic equation |
10218 |
Fetching from uHunt |
non-starred |
probability and a bit of binomial coefficients |
10219 |
Fetching from uHunt |
non-starred |
count the length of nCk; BigInteger |
10220 |
Fetching from uHunt |
non-starred |
use Java BigInteger; precalculate |
10221 |
Fetching from uHunt |
non-starred |
finding arc and chord length of a circle |
10222 |
Fetching from uHunt |
non-starred |
simple decoding mechanism |
10223 |
Fetching from uHunt |
5.4c, Catalan Numbers |
you can precalculate the answers as there are only 19 Catalan Numbers < 2^{32}-1 |
10226 |
Fetching from uHunt |
2.3a, map/TreeMap |
map is ok but hashing is better |
10227 |
Fetching from uHunt |
non-starred |
merge two disjoint sets if they are consistent |
10229 |
Fetching from uHunt |
5.9a, Matrix Power |
Fibonacci matrix power; modulo |
10233 |
Fetching from uHunt |
5.2f, Grid |
the number of items in row forms arithmetic progression series; use hypot |
10235 |
Fetching from uHunt |
5.3c, (Prob) Prime Testing |
case analysis: prime/emirp/not prime; emirp is prime number that if reversed is still a prime number |
10238 |
Fetching from uHunt |
5.6a, Probability, Easier |
DP; s: (dice_left; score); try F values; Java BigInteger; we are not asked to simplify the fraction; similar to UVa 10759 |
10239 |
Fetching from uHunt |
non-starred |
convert double to long long first; medium DP; either put this book in the current shelf (if possible) or put it in a new shelf |
10242 |
Fetching from uHunt |
non-starred |
toVector; translate points w.r.t that vector |
10243 |
Fetching from uHunt |
non-starred |
this problem can be reduced to the Min Vertex Cover problem on Tree; there is a polynomial DP solution for this variant |
10245 |
Fetching from uHunt |
non-starred |
classic |
10246 |
Fetching from uHunt |
non-starred |
modify the Floyd Warshall's recurrence a bit to handle the maximum cost to hold feast for Obelix |
10249 |
Fetching from uHunt |
non-starred |
greedy; sorting |
10250 |
Fetching from uHunt |
non-starred |
vector; rotation |
10252 |
Fetching from uHunt |
non-starred |
count freq of each alphabet |
10254 |
Fetching from uHunt |
non-starred |
find pattern; use Java BigInteger |
10256 |
Fetching from uHunt |
7.3b, Polygon, Harder |
nice classic geometry problem: given two convex hulls; the answer is No if there is any point in the first CH that is inside the second one; the answer is Yes otherwise |
10257 |
Fetching from uHunt |
non-starred |
we can brute force the integer ages of spot; puff; and yertle; need some mathematical insights |
10258 |
Fetching from uHunt |
non-starred |
multi-fields sorting; use sort; similar to UVa 790 |
10259 |
Fetching from uHunt |
4.7a, S/L Paths on DAG |
longest paths on implicit DAG; DP |
10260 |
Fetching from uHunt |
non-starred |
Direct Addressing Table for soundex code mapping |
10261 |
Fetching from uHunt |
non-starred |
s: (current_car; left; right) |
10263 |
Fetching from uHunt |
non-starred |
use distToLineSegment |
10264 |
Fetching from uHunt |
2.2d, Bit Manipulation |
heavy bitmask manipulation |
10267 |
Fetching from uHunt |
non-starred |
simulation |
10268 |
Fetching from uHunt |
5.2i, Polynomial |
polynomial derivation; Horner's rule |
10269 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
use modified Floyd Warshall's to pre-compute APSP using only Villages (for Mario's super-runs); use Dijkstra's on modified state-space graph; s: (vertex; super_run_left) |
10271 |
Fetching from uHunt |
non-starred |
Observation: The 3rd chopstick can be any chopstick; we must greedily select adjacent chopstick; DP state: (pos; k_left); transition: Ignore this chopstick; or take this chopstick and the chopstick immediately next to it; then move to pos 2; prune |
10276 |
Fetching from uHunt |
3.2j, Pre-calculate-able |
insert a number one by one |
10278 |
Fetching from uHunt |
non-starred |
Dijkstra's from fire stations to all intersections; need pruning to pass the time limit |
10279 |
Fetching from uHunt |
non-starred |
a 2D array helps; similar to UVa 10189 |
10281 |
Fetching from uHunt |
non-starred |
distance = speed*time elapsed |
10282 |
Fetching from uHunt |
non-starred |
a pure dictionary problem; use map |
10283 |
Fetching from uHunt |
non-starred |
derive the formula |
10284 |
Fetching from uHunt |
1.4b, Game (Chess) |
FEN = Forsyth-Edwards Notation is a standard notation for describing board positions in a chess game |
10285 |
Fetching from uHunt |
4.7a, S/L Paths on DAG |
longest paths on implicit DAG; however; the graph is small enough for recursive backtracking solution |
10286 |
Fetching from uHunt |
non-starred |
Law of Sines |
10287 |
Fetching from uHunt |
non-starred |
derive the formula |
10290 |
Fetching from uHunt |
non-starred |
find number of odd divisors |
10293 |
Fetching from uHunt |
non-starred |
straightforward |
10295 |
Fetching from uHunt |
non-starred |
use map to deal with Hay Points dictionary |
10296 |
Fetching from uHunt |
non-starred |
basic Chinese Postman Problem |
10297 |
Fetching from uHunt |
non-starred |
cones; cylinders; volumes |
10298 |
Fetching from uHunt |
6.4a, String Matching, Standard |
find s in concatenate(s; s); similar with UVa 455 |
10299 |
Fetching from uHunt |
non-starred |
EulerPhi(N) |
10300 |
Fetching from uHunt |
non-starred |
ignore the number of animals |
10301 |
Fetching from uHunt |
non-starred |
circle-circle intersection; backtracking |
10302 |
Fetching from uHunt |
5.2i, Polynomial |
use long double |
10303 |
Fetching from uHunt |
non-starred |
generate Cat(n) as shown in this section; use Java BigInteger |
10304 |
Fetching from uHunt |
non-starred |
classical DP; requires 1D range sum and Knuth-Yao speed up to get O(n^2) solution |
10305 |
Fetching from uHunt |
4.2d, Topological Sort |
simply run toposort algorithm |
10306 |
Fetching from uHunt |
non-starred |
variant: each coin has two components |
10307 |
Fetching from uHunt |
non-starred |
build SSSP graph with BFS; MST |
10308 |
Fetching from uHunt |
non-starred |
diameter of tree |
10309 |
Fetching from uHunt |
non-starred |
brute force the first row in 2^10; the rest follows |
10310 |
Fetching from uHunt |
non-starred |
very basic 0-1 Knapsack problem |
10311 |
Fetching from uHunt |
non-starred |
case analysis; brute force; similar to UVa 543; 686; and 10948 |
10312 |
Fetching from uHunt |
5.4c, Catalan Numbers |
number of binary bracketing = Cat(n); number of bracketing = Super-Catalan numbers |
10313 |
Fetching from uHunt |
non-starred |
modified coin change and DP 1D range sum |
10315 |
Fetching from uHunt |
non-starred |
tedious problem |
10316 |
Fetching from uHunt |
non-starred |
gcDistance |
10318 |
Fetching from uHunt |
non-starred |
the order is not important; so we can try pressing the buttons in increasing order; row by row; column by column; when pressing one button; only the 3*3 square around it is affected; therefore after we press button (i; j); light (i-1; j-1) must be on |
10319 |
Fetching from uHunt |
non-starred |
can be modeled as a 2-SAT problem |
10323 |
Fetching from uHunt |
non-starred |
overflow: n>13/-odd n; underflow: n$<$8/-even n; PS: actually; factorial of negative number is not defined |
10324 |
Fetching from uHunt |
non-starred |
simplify using 1D array: change counter |
10325 |
Fetching from uHunt |
non-starred |
inclusion exclusion principle; brute force subset for small M <= 15; lcm-gcd |
10326 |
Fetching from uHunt |
non-starred |
given roots of the polynomial; reconstruct the polynomial; formatting |
10327 |
Fetching from uHunt |
non-starred |
solvable with O(n^2) bubble sort |
10328 |
Fetching from uHunt |
non-starred |
DP; 1-D state; Java BigInteger |
10330 |
Fetching from uHunt |
non-starred |
max flow; vertex capacities |
10331 |
Fetching from uHunt |
non-starred |
use Floyd Warshall's to obtain the APSP information; then use brute force to count the time an edge is used; report accordingly |
10333 |
Fetching from uHunt |
non-starred |
a real time waster problem |
10334 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
combinatorics; Java BigInteger |
10336 |
Fetching from uHunt |
non-starred |
count and rank CCs with similar color |
10337 |
Fetching from uHunt |
non-starred |
DP; shortest paths on DAG |
10338 |
Fetching from uHunt |
non-starred |
use long long to store up to 20! |
10339 |
Fetching from uHunt |
non-starred |
find the formula |
10340 |
Fetching from uHunt |
3.4d, Non Classical, Easier |
greedy |
10341 |
Fetching from uHunt |
non-starred |
bisection method; for alternative solutions; see http://www.algorithmist.com/index.php/UVa_10341 |
10342 |
Fetching from uHunt |
4.5b, APSP, Variants |
use Floyd Warshall's to obtain the shortest path values; to get the second best shortest path on this small graph; try to make a single mistake by breaking sp(i; j) to sp(i; x) edge(x; y) sp(y; j) at each edge (x; y) |
10344 |
Fetching from uHunt |
3.2f, Backtracking (Easy) |
rearrange the 5 operands and the 3 operators |
10346 |
Fetching from uHunt |
5.2b, Math Simulation, Easier |
interesting simulation problem |
10347 |
Fetching from uHunt |
non-starred |
given 3 medians of a triangle; find its area |
10349 |
Fetching from uHunt |
non-starred |
MIS: V - MCBM |
10350 |
Fetching from uHunt |
4.7a, S/L Paths on DAG |
shortest paths; implicit DAG; DP |
10354 |
Fetching from uHunt |
4.5a, APSP, Standard |
find and remove edges involved in boss's shortest paths; re-run shortest paths from home to market |
10356 |
Fetching from uHunt |
non-starred |
we can attach one extra information to each vertex: whether we come to that vertex using cycle or not; then; run Dijkstra's to solve SSSP on this modified graph |
10357 |
Fetching from uHunt |
non-starred |
Euclidean dist; simple Physics simulation |
10359 |
Fetching from uHunt |
non-starred |
derive the formula; use Java BigInteger |
10360 |
Fetching from uHunt |
non-starred |
also solvable using 1024^2 DP max sum |
10361 |
Fetching from uHunt |
non-starred |
read; tokenize; process as requested |
10363 |
Fetching from uHunt |
non-starred |
check validity of Tic Tac Toe game; tricky |
10364 |
Fetching from uHunt |
non-starred |
bitmask technique can be used |
10365 |
Fetching from uHunt |
non-starred |
use 3 nested loops with pruning |
10368 |
Fetching from uHunt |
5.8a, Game Theory |
minimax; backtracking |
10369 |
Fetching from uHunt |
non-starred |
minimum spanning 'forest' |
10370 |
Fetching from uHunt |
non-starred |
compute average; see how many are above it; also available at Kattis - aboveaverage |
10371 |
Fetching from uHunt |
1.4h, Time, Harder |
follow the problem description |
10372 |
Fetching from uHunt |
non-starred |
binary search the answer and Physics |
10374 |
Fetching from uHunt |
non-starred |
use map for frequency counting |
10375 |
Fetching from uHunt |
non-starred |
the main task is to avoid overflow |
10377 |
Fetching from uHunt |
non-starred |
traversal on implicit graph |
10382 |
Fetching from uHunt |
non-starred |
interval covering |
10385 |
Fetching from uHunt |
non-starred |
the function is unimodal; perfect problem to practice on ternary search |
10387 |
Fetching from uHunt |
non-starred |
expanding surface; trigonometry |
10388 |
Fetching from uHunt |
1.4a, Game (Card) |
card simulation; uses random number to determine moves; need data structure to maintain the face-up and face-down cards |
10389 |
Fetching from uHunt |
non-starred |
use basic geometry skill to build the weighted graph; then run Dijkstra's |
10391 |
Fetching from uHunt |
non-starred |
more like a data structure problem |
10392 |
Fetching from uHunt |
non-starred |
enumerate the prime factors of input |
10393 |
Fetching from uHunt |
6.3j, Ad Hoc String |
follow problem description |
10394 |
Fetching from uHunt |
non-starred |
sieve; check if p and p plus 2 are both primes; if yes; they are twin primes; precalculate the result |
10397 |
Fetching from uHunt |
non-starred |
'minimum' spanning subgraph |
10400 |
Fetching from uHunt |
non-starred |
backtracking with clever pruning is sufficient |
10401 |
Fetching from uHunt |
non-starred |
counting paths in implicit DAG; DP; s: (col; row); t: next col; avoid 2 or 3 adjacent rows |
10404 |
Fetching from uHunt |
non-starred |
2 players game; Dynamic Programming |
10405 |
Fetching from uHunt |
6.5a, DP String, Classic |
very classic Longest Common Subsequence problem |
10406 |
Fetching from uHunt |
non-starred |
vector; rotate; translate; then cutPolygon |
10407 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
subtract the set s with s[0]; find gcd |
10408 |
Fetching from uHunt |
5.2g, Number Systems/Sequences |
first; generate (i; j) pairs such that gcd(i; j) = 1; then sort |
10409 |
Fetching from uHunt |
non-starred |
just simulate the die movement |
10415 |
Fetching from uHunt |
non-starred |
about musical instruments |
10419 |
Fetching from uHunt |
non-starred |
print path; prime |
10420 |
Fetching from uHunt |
non-starred |
word frequency counting; use map |
10422 |
Fetching from uHunt |
non-starred |
simple SSSP solvable with BFS |
10424 |
Fetching from uHunt |
non-starred |
just do as asked |
10426 |
Fetching from uHunt |
non-starred |
for each knight; do unweighted SSSP with BFS when the monster is sleep/awake; then do a simple brute force check to see which one of the the four knights should awake the monster (once) |
10427 |
Fetching from uHunt |
non-starred |
numbers in [10^(k-1)..10^k-1] has k digits |
10430 |
Fetching from uHunt |
non-starred |
BigInteger; derive formula first |
10432 |
Fetching from uHunt |
7.2c, Circles |
simple problem: area of n-sided reg-polygon in a circle |
10433 |
Fetching from uHunt |
non-starred |
BigInteger: pow; substract; mod |
10436 |
Fetching from uHunt |
non-starred |
as there is vertex weight; use vertex splitting technique; run Floyd Warshall's on the still-small graph; print path |
10440 |
Fetching from uHunt |
non-starred |
greedy |
10443 |
Fetching from uHunt |
non-starred |
2D arrays manipulation |
10445 |
Fetching from uHunt |
non-starred |
angle checks; use library code; some corner cases exist |
10446 |
Fetching from uHunt |
non-starred |
edit the given recursive function a bit; add memoization |
10448 |
Fetching from uHunt |
3.5e, Coin-Change |
after dealing with traversal on tree; you can reduce the original problem into coin change; not trivial |
10449 |
Fetching from uHunt |
non-starred |
find the minimum weight path; which may be negative; be careful: INF negative weight is lower than INF |
10450 |
Fetching from uHunt |
non-starred |
combinatorics; the pattern ~ Fibonacci |
10451 |
Fetching from uHunt |
non-starred |
inner/outer circle of n-sided reg polygon |
10452 |
Fetching from uHunt |
non-starred |
at each pos; Indy can go forth/left/right; try all |
10453 |
Fetching from uHunt |
non-starred |
s: (l; r); t: (l 1; r-1) if S[l] == S[r]; or one plus min of(l 1; r) or (l; r-1); also print the required solution; similar with UVa 10739; 11151; and 11404 |
10457 |
Fetching from uHunt |
4.3b, MST, Variants |
interesting MST modeling |
10459 |
Fetching from uHunt |
non-starred |
diameter of tree |
10460 |
Fetching from uHunt |
non-starred |
similar nature with UVa 10063 |
10462 |
Fetching from uHunt |
non-starred |
second best spanning tree |
10464 |
Fetching from uHunt |
non-starred |
Java BigDecimal class |
10465 |
Fetching from uHunt |
non-starred |
one dimensional DP table |
10466 |
Fetching from uHunt |
non-starred |
Euclidean dist |
10469 |
Fetching from uHunt |
non-starred |
super simple if you use xor |
10473 |
Fetching from uHunt |
non-starred |
Decimal to Hexadecimal and vice versa; if you use C/C ; you can use strtol |
10474 |
Fetching from uHunt |
non-starred |
simple: use sort and then lower_bound |
10475 |
Fetching from uHunt |
non-starred |
generate and prune; try all |
10477 |
Fetching from uHunt |
non-starred |
s: (row; col; knight_state); implicit unweighted graph; different edges per different knight_state |
10480 |
Fetching from uHunt |
non-starred |
straightforward min cut problem |
10482 |
Fetching from uHunt |
non-starred |
drop one parameter to save memory |
10483 |
Fetching from uHunt |
non-starred |
2 nested loops for a; b; derive c from a; b; there are 354 answers for range [0.01 .. 255.99]; similar to UVa 11236 |
10484 |
Fetching from uHunt |
non-starred |
prime factors of factorial; D can be negative |
10487 |
Fetching from uHunt |
non-starred |
sort and then do O(n^2) pairings |
10489 |
Fetching from uHunt |
5.5h, Modulo Arithmetic |
keep values small with modulo |
10490 |
Fetching from uHunt |
non-starred |
ad Hoc; precalculate the answers |
10491 |
Fetching from uHunt |
5.6a, Probability, Easier |
two ways to get a car: either pick a cow first; then switch to a car; or pick a car first; and then switch to another car |
10493 |
Fetching from uHunt |
non-starred |
tree; derive the formula |
10494 |
Fetching from uHunt |
non-starred |
BigInteger division |
10496 |
Fetching from uHunt |
3.5f, TSP |
actually; since n <= 11; this problem is still solvable with recursive backtracking and sufficient pruning |
10497 |
Fetching from uHunt |
non-starred |
the pattern ~ Fibonacci |
10499 |
Fetching from uHunt |
non-starred |
simple formula exists |
10500 |
Fetching from uHunt |
6.3g, Output Formatting, Easier |
simulate; output formatting |
10502 |
Fetching from uHunt |
non-starred |
6 nested loops; rectangle; not too hard |
10503 |
Fetching from uHunt |
non-starred |
max 13 spaces only |
10505 |
Fetching from uHunt |
4.2e, Bipartite Graph Check |
bipartite; take max(left; right) |
10506 |
Fetching from uHunt |
non-starred |
any valid solution is AC; generate all possible next digit (up to base 10/digit [0..9]); check if it is still a valid Ouroboros sequence |
10507 |
Fetching from uHunt |
non-starred |
disjoint sets simplifies this problem |
10508 |
Fetching from uHunt |
non-starred |
number of words = number of letters plus 1 |
10509 |
Fetching from uHunt |
non-starred |
there are only three different cases |
10510 |
Fetching from uHunt |
non-starred |
use DFS to identify forward/cross edges; involving Strongly Connected graph |
10511 |
Fetching from uHunt |
non-starred |
matching; max flow; print the assignment |
10514 |
Fetching from uHunt |
non-starred |
use basic geometry routines to compute the weights of the weighted graph of islands and the two riverbanks; it is just a simple SSSP problem afterwards |
10515 |
Fetching from uHunt |
non-starred |
concentrate on the last digit |
10518 |
Fetching from uHunt |
non-starred |
derive the pattern of the answers for small $n$; the answer is 2*fib(n)-1; then use UVa 10229 solution |
10519 |
Fetching from uHunt |
non-starred |
recurrences; BigInteger |
10520 |
Fetching from uHunt |
non-starred |
just write the given formula as a top-down DP with memoization |
10522 |
Fetching from uHunt |
non-starred |
derive the formula; uses Heron's formula |
10523 |
Fetching from uHunt |
5.3a, BigInteger, Basic |
BigInteger addition; multiplication; and power |
10525 |
Fetching from uHunt |
non-starred |
use two adjacency matrices: time and length; use modified Floyd Warshall's |
10527 |
Fetching from uHunt |
non-starred |
similar to UVa 993 |
10528 |
Fetching from uHunt |
non-starred |
music knowledge is in the problem description |
10530 |
Fetching from uHunt |
non-starred |
use a 1D flag array |
10532 |
Fetching from uHunt |
non-starred |
modified binomial coefficient |
10533 |
Fetching from uHunt |
8.5b, Other and DP 1D RSQ/RMQ |
sieve; check if a prime is a digit prime; DP 1D range sum |
10534 |
Fetching from uHunt |
non-starred |
must use O(n log k) LIS twice |
10536 |
Fetching from uHunt |
non-starred |
model the 4*4 board and 48 possible pins as bitmask; then this is a simple two player game |
10537 |
Fetching from uHunt |
non-starred |
there is no 'impossible' case |
10539 |
Fetching from uHunt |
8.5e, Maths and Other |
sieve; get 'almost primes' by listing the powers of each prime; e.g. 3 is a prime number; so 3^2 = 9; 3^3 = 27; etc are 'almost primes'; sort these 'almost primes' and do binary search |
10541 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
a good combinatorics problem |
10543 |
Fetching from uHunt |
non-starred |
s: (pos; speech_given) |
10544 |
Fetching from uHunt |
4.7b, Counting Paths, Easier |
counting paths in implicit DAG; problem statement nicely encapsulates this DAG property |
10550 |
Fetching from uHunt |
non-starred |
simple; do as asked |
10551 |
Fetching from uHunt |
5.3b, Bonus: Base Number |
also involving BigInteger mod |
10554 |
Fetching from uHunt |
non-starred |
are you concerned with your weights? |
10555 |
Fetching from uHunt |
non-starred |
try every single possible repeating decimals |
10557 |
Fetching from uHunt |
non-starred |
check 'positive' cycle; check connectedness |
10559 |
Fetching from uHunt |
8.3c, DP level 4 |
DP with clever state and transitions |
10562 |
Fetching from uHunt |
non-starred |
output formatting with clever recursion |
10564 |
Fetching from uHunt |
non-starred |
counting paths in implicit DAG (top-down); print one solution |
10566 |
Fetching from uHunt |
non-starred |
bisection method |
10567 |
Fetching from uHunt |
3.3a, Binary Search |
store inc indices of each char of S in 52 vectors; binary search for the position of the char in the correct vector |
10570 |
Fetching from uHunt |
non-starred |
brute force all possible final configurations (ascending/descending) and see which one requires the smallest number of exchanges |
10571 |
Fetching from uHunt |
8.4a, NP-hard/complete, small |
hard backtracking problem; it has similar flavor as Su Doku puzzle |
10576 |
Fetching from uHunt |
3.2f, Backtracking (Easy) |
generate all; prune; take max |
10577 |
Fetching from uHunt |
7.2e, Triangles + Circles |
get center radius of outer circle from 3 points; get all vertices; get the min-x/max-x/min-y/max-y of the polygon |
10578 |
Fetching from uHunt |
non-starred |
backtracking; try all; see who wins the game |
10579 |
Fetching from uHunt |
non-starred |
very easy with Java BigInteger |
10582 |
Fetching from uHunt |
non-starred |
simplify complex input first; then backtrack |
10583 |
Fetching from uHunt |
non-starred |
count disjoint sets after all unions |
10585 |
Fetching from uHunt |
non-starred |
sort the points |
10586 |
Fetching from uHunt |
5.2i, Polynomial |
compute number of prime factors of each integer in the desired range; use 1D RSQ DP; binary search |
10589 |
Fetching from uHunt |
non-starred |
check if point is inside intersection of 4 circles |
10591 |
Fetching from uHunt |
non-starred |
this sequence is 'eventually periodic'; similar to UVa 944 |
10592 |
Fetching from uHunt |
non-starred |
floodfill ; two layers |
10594 |
Fetching from uHunt |
non-starred |
basic min cost max flow problem |
10596 |
Fetching from uHunt |
4.7e, Eulerian Graph |
Euler Graph property check |
10600 |
Fetching from uHunt |
non-starred |
second best spanning tree |
10602 |
Fetching from uHunt |
non-starred |
greedy |
10603 |
Fetching from uHunt |
non-starred |
state: (a; b; c); source: (0; 0; c); 6 possible transitions |
10604 |
Fetching from uHunt |
non-starred |
the mixing can be done with any pair of chemicals until there are only two chemicals left; memoize the remaining chemicals with help of map; sorting the remaining chemicals help increasing the number of hits to the memo table |
10606 |
Fetching from uHunt |
non-starred |
the solution is simply the highest square number <= N but this problem involves BigInteger; we can use a (rather slow) binary search the answer technique to obtain sqrt(N) |
10608 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
find the set with the largest element |
10610 |
Fetching from uHunt |
non-starred |
simple SSSP solvable with BFS |
10611 |
Fetching from uHunt |
non-starred |
binary search |
10616 |
Fetching from uHunt |
non-starred |
input can be -ve; use long long |
10617 |
Fetching from uHunt |
non-starred |
s: (l; r); counting substrings that are palindrome |
10620 |
Fetching from uHunt |
non-starred |
just simulate the jumps |
10622 |
Fetching from uHunt |
non-starred |
GCD of all prime powers; note if x is negative |
10624 |
Fetching from uHunt |
non-starred |
backtracking with divisibility check |
10625 |
Fetching from uHunt |
non-starred |
frequency addition n times |
10626 |
Fetching from uHunt |
8.3c, DP level 4 |
drop parameter n1; recover it from b (number of coke bought); n5; and n10 |
10633 |
Fetching from uHunt |
5.5i, Extended Euclid |
let C = N-M (the given input); N = 10a plus b (N is at least two digits; with b as the last digit); and M = a; this problem is now about finding the solution of the Linear Diophantine Equation: 9a plus b = C |
10635 |
Fetching from uHunt |
6.5a, DP String, Classic |
find LCS of two permutations |
10637 |
Fetching from uHunt |
8.5e, Maths and Other |
involving prime numbers and gcd |
10642 |
Fetching from uHunt |
non-starred |
the reverse of UVa 264 |
10643 |
Fetching from uHunt |
non-starred |
Cat(n) is part of a bigger problem |
10645 |
Fetching from uHunt |
non-starred |
s: (days_left; budget_left; prev_dish; prev_dish_count); the first two parameters are knapsack-style parameter; the last two parameters are used to determine the price of that dish as first; second; and subsequent usage of the dish has different valu |
10646 |
Fetching from uHunt |
1.4a, Game (Card) |
shuffle cards with some rules and then get a certain card |
10648 |
Fetching from uHunt |
5.6b, Probability, Harder |
DP; s: (rem_boxes; num_empty) |
10650 |
Fetching from uHunt |
5.5a, Prime Numbers |
3 uni-distance consecutive primes |
10651 |
Fetching from uHunt |
non-starred |
small problem size; doable with backtracking |
10652 |
Fetching from uHunt |
7.3b, Polygon, Harder |
rotate; translate; CH; area |
10653 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
need efficient BFS implementation |
10655 |
Fetching from uHunt |
5.9a, Matrix Power |
tinker with the formula until you can get a square matrix from it |
10656 |
Fetching from uHunt |
3.4d, Non Classical, Easier |
greedy |
10659 |
Fetching from uHunt |
non-starred |
typical presentation programs do this |
10660 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
7 nested loops; Manhattan distance |
10662 |
Fetching from uHunt |
non-starred |
3 nested loops |
10664 |
Fetching from uHunt |
non-starred |
Subset Sum |
10666 |
Fetching from uHunt |
non-starred |
analyze the binary representation of X |
10667 |
Fetching from uHunt |
non-starred |
standard problem |
10668 |
Fetching from uHunt |
non-starred |
bisection method |
10669 |
Fetching from uHunt |
non-starred |
BigInteger is for 3^n; binary rep of set! |
10670 |
Fetching from uHunt |
non-starred |
greedy; sorting |
10672 |
Fetching from uHunt |
non-starred |
greedy |
10673 |
Fetching from uHunt |
5.5i, Extended Euclid |
uses Extended Euclid |
10677 |
Fetching from uHunt |
non-starred |
try all from r2 to r1 |
10678 |
Fetching from uHunt |
7.2c, Circles |
area of an ellipse; generalization of the formula for area of a circle |
10679 |
Fetching from uHunt |
non-starred |
the test data weak; just checking if T is a prefix of S is AC when it should not |
10680 |
Fetching from uHunt |
5.5e, Prime Factors Related |
use primefactors([1..N]) to get LCM(1; 2; ...; N) |
10681 |
Fetching from uHunt |
non-starred |
s: (pos; day_left) |
10682 |
Fetching from uHunt |
non-starred |
s: (current_city; current_speed); output path |
10683 |
Fetching from uHunt |
non-starred |
simple clock system conversion |
10684 |
Fetching from uHunt |
3.5a, Max 1D Range Sum |
standard; Kadane's algorithm |
10685 |
Fetching from uHunt |
non-starred |
find the set with the largest element |
10686 |
Fetching from uHunt |
non-starred |
use map to manage the data |
10687 |
Fetching from uHunt |
non-starred |
build graph; geometry; reachability |
10688 |
Fetching from uHunt |
non-starred |
note that the sample in the problem description is a bit wrong; it should be: 1 (1 3) (1 3) (1 3) = 1 4 4 4 = 13; beating 14; otherwise a simple DP |
10689 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
easy; Pisano period |
10690 |
Fetching from uHunt |
non-starred |
DP Subset Sum with negative offset technique; with addition of simple math |
10693 |
Fetching from uHunt |
non-starred |
derive the short Physics formula |
10696 |
Fetching from uHunt |
non-starred |
very simple formula simplification |
10698 |
Fetching from uHunt |
non-starred |
multi-fields sorting; use sort |
10699 |
Fetching from uHunt |
5.5g, Modified Sieve |
numDiffPF(N) for a range of N |
10700 |
Fetching from uHunt |
non-starred |
greedy |
10701 |
Fetching from uHunt |
non-starred |
reconstructing tree from pre inorder |
10702 |
Fetching from uHunt |
non-starred |
s: (pos; T_left); similar to UVa 12875 |
10703 |
Fetching from uHunt |
non-starred |
use 2D boolean array of size 500*500 |
10706 |
Fetching from uHunt |
non-starred |
binary search some mathematical insights |
10707 |
Fetching from uHunt |
non-starred |
check graph isomorphism; a tedious problem; involving connected components |
10710 |
Fetching from uHunt |
non-starred |
a bit hard to derive the formula; modPow |
10714 |
Fetching from uHunt |
non-starred |
greedy |
10718 |
Fetching from uHunt |
non-starred |
greedy |
10719 |
Fetching from uHunt |
non-starred |
polynomial division and remainder |
10720 |
Fetching from uHunt |
non-starred |
similar to UVa 11414 and 12786; Erdos-Gallai's Theorem |
10721 |
Fetching from uHunt |
non-starred |
s: (n; k); t: try all from 1 to m |
10722 |
Fetching from uHunt |
non-starred |
counting paths in implicit DAG; s: (N_digits_left; B; first; previous_digit_is_one) and use a bit of simple combinatorics to get the answer; need to use Java BigInteger |
10724 |
Fetching from uHunt |
non-starred |
adding one edge only changes a few things |
10730 |
Fetching from uHunt |
non-starred |
2 nested loops with pruning can still pass the time limit; compare this with UVa 11129 |
10731 |
Fetching from uHunt |
non-starred |
SCC printing solution |
10733 |
Fetching from uHunt |
non-starred |
Burnside's lemma |
10734 |
Fetching from uHunt |
non-starred |
a geometry problem involving triangle/cosine rule; use a data structure that tolerates floating point error due to triangle side normalization so that we count each triangle only once |
10738 |
Fetching from uHunt |
non-starred |
numDiffPF(N) for a range of N |
10739 |
Fetching from uHunt |
non-starred |
similar to UVa 10453; 11151; and 11404 |
10740 |
Fetching from uHunt |
non-starred |
standard K-Best Shortest Paths problem |
10741 |
Fetching from uHunt |
non-starred |
similar idea as 2D Magic Square; but now in 3D; just follow the given construction strategy |
10742 |
Fetching from uHunt |
non-starred |
use sieve; binary search |
10746 |
Fetching from uHunt |
non-starred |
min weighted bipartite matching |
10751 |
Fetching from uHunt |
5.2d, Finding Pattern, Easier |
trivial for N = 1 and N = 2; derive the formula first for N > 2; hint: use diagonal as much as possible |
10755 |
Fetching from uHunt |
3.5a, Max 1D Range Sum |
max 2D range sum in 2 of the 3 dimensions; max 1D range sum with Kadane's algorithm on the 3rd dimension |
10759 |
Fetching from uHunt |
non-starred |
DP; s: (dice_left; score); try 6 values; gcd; similar to UVa 10238 |
10761 |
Fetching from uHunt |
non-starred |
tricky with output formatting; note that 'END' is part of input |
10763 |
Fetching from uHunt |
non-starred |
greedy; sorting |
10765 |
Fetching from uHunt |
4.2f, Articulation Points/Bridges |
finding articulation points |
10771 |
Fetching from uHunt |
non-starred |
brute force; input size is small |
10773 |
Fetching from uHunt |
5.2a, The Simpler Ones |
several tricky cases |
10774 |
Fetching from uHunt |
non-starred |
repeated case of Josephus when k = 2 |
10776 |
Fetching from uHunt |
non-starred |
recursive backtracking |
10777 |
Fetching from uHunt |
non-starred |
expected value |
10779 |
Fetching from uHunt |
non-starred |
build a flow graph s.t. each augmenting path corresponds to a series of exchange of duplicate stickers; starting with Bob giving away one of his duplicates; and ending with him receiving a new sticker; repeat until this is no longer possible |
10780 |
Fetching from uHunt |
non-starred |
similar to UVa 10139 |
10783 |
Fetching from uHunt |
non-starred |
input range is very small; just brute force it |
10784 |
Fetching from uHunt |
5.4e, Others, Harder |
the number of diagonals in n-gon = n*(n-3)/2; use it to derive the solution |
10785 |
Fetching from uHunt |
non-starred |
greedy; sorting |
10789 |
Fetching from uHunt |
non-starred |
check if a letter's frequency is prime |
10790 |
Fetching from uHunt |
non-starred |
uses arithmetic progression formula |
10791 |
Fetching from uHunt |
non-starred |
analyze the prime factors of N |
10792 |
Fetching from uHunt |
non-starred |
derive the trigonometry formulas |
10793 |
Fetching from uHunt |
non-starred |
Floyd Warshall's simplifies this problem |
10800 |
Fetching from uHunt |
6.3h, Output Formatting, Harder |
tedious problem |
10801 |
Fetching from uHunt |
non-starred |
model the graph carefully |
10803 |
Fetching from uHunt |
non-starred |
graph is small |
10804 |
Fetching from uHunt |
non-starred |
binary search the answer and MCBM; similar with UVa 11262 |
10805 |
Fetching from uHunt |
4.7d, Tree |
involving diameter of tree |
10806 |
Fetching from uHunt |
non-starred |
send 2 edge-disjoint flows with min cost |
10810 |
Fetching from uHunt |
non-starred |
requires O(n log n) merge sort |
10812 |
Fetching from uHunt |
non-starred |
be careful with boundary cases! |
10813 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
follow the problem description |
10814 |
Fetching from uHunt |
5.3d, Bonus: Others |
BigInteger gcd |
10815 |
Fetching from uHunt |
2.3b, set/TreeSet |
use set and string |
10816 |
Fetching from uHunt |
non-starred |
binary search the answer and Dijkstra's |
10817 |
Fetching from uHunt |
8.3b, DP level 3 |
s: (id; bitmask) |
10819 |
Fetching from uHunt |
non-starred |
0-1 knapsack with 'credit card' twist |
10820 |
Fetching from uHunt |
non-starred |
a[i] = a[i-1] plus 2*EulerPhi(i) |
10821 |
Fetching from uHunt |
3.4e, Non Classical, Harder |
greedy |
10823 |
Fetching from uHunt |
non-starred |
complete search; check if point inside circles/squares |
10827 |
Fetching from uHunt |
3.5b, Max 2D Range Sum |
copy n*n matrix into n*2n matrix; then this problem becomes a standard problem again |
10832 |
Fetching from uHunt |
non-starred |
3D Euclidean distance; simulation |
10842 |
Fetching from uHunt |
non-starred |
find min weighted edge in 'max' spanning tree |
10843 |
Fetching from uHunt |
non-starred |
Cayley's Formula to count the number of spanning trees of a graph with n vertices is n^n-2; use Java BigInteger |
10848 |
Fetching from uHunt |
non-starred |
related to UVa 10453; this problem combines palindrome check; character frequency check; and a few other basic string processing skills |
10849 |
Fetching from uHunt |
non-starred |
chess |
10850 |
Fetching from uHunt |
non-starred |
gossip spread simulation |
10851 |
Fetching from uHunt |
6.3a, Cipher, Easier |
ignore border; treat '/' as 1/0; read from bottom |
10852 |
Fetching from uHunt |
non-starred |
sieve; p = 1; find the first prime number >= n/2 plus 1 |
10854 |
Fetching from uHunt |
6.3e, Recursive Parsing |
recursive parsing plus counting |
10855 |
Fetching from uHunt |
non-starred |
string array; 90 degrees clockwise rotation |
10858 |
Fetching from uHunt |
2.2e, Stack |
use stack |
10862 |
Fetching from uHunt |
non-starred |
the pattern ends up ~ Fibonacci |
10865 |
Fetching from uHunt |
non-starred |
points and quadrants; simple |
10870 |
Fetching from uHunt |
non-starred |
form the required matrix first; power of matrix |
10871 |
Fetching from uHunt |
non-starred |
need 1D Range Sum Query |
10874 |
Fetching from uHunt |
non-starred |
s: (row; left/right); t: go left/right |
10875 |
Fetching from uHunt |
non-starred |
simple but tedious problem |
10876 |
Fetching from uHunt |
non-starred |
binary search the answer and graph connectivity (geometry/Euclidian distance and union find); similar with UVa 295 |
10878 |
Fetching from uHunt |
non-starred |
treat space/'o' as 0/1; then it is binary to decimal conversion |
10879 |
Fetching from uHunt |
non-starred |
just use brute force |
10880 |
Fetching from uHunt |
non-starred |
use sort |
10882 |
Fetching from uHunt |
non-starred |
inclusion-exclusion principle |
10887 |
Fetching from uHunt |
2.3d, unordered_set/HashSet |
Use O(M*N*log(MN)*10) algorithm; concatenate all pairs of strings; put them in a set; report set size |
10888 |
Fetching from uHunt |
non-starred |
BFS/SSSP; min weighted bipartite matching |
10890 |
Fetching from uHunt |
non-starred |
looks like a DP problem but the state---involving bitmask---cannot be memoized; fortunately the grid size is small |
10891 |
Fetching from uHunt |
8.5b, Other and DP 1D RSQ/RMQ |
double DP; the first DP is the standard 1D Range Sum Query between two indices; s: (i; j); the second DP evaluates the decision tree with s: (i; j) and try all splitting points; minimax |
10892 |
Fetching from uHunt |
non-starred |
number of divisor pairs of N: (m; n) such that gcd(m; n) = 1 |
10894 |
Fetching from uHunt |
non-starred |
how fast can you can solve this problem? |
10895 |
Fetching from uHunt |
2.4a, Graph Data Structures |
transpose adjacency list |
10896 |
Fetching from uHunt |
non-starred |
try all possible keys; use tokenizer |
10897 |
Fetching from uHunt |
non-starred |
gcDistance |
10898 |
Fetching from uHunt |
non-starred |
similar to DP bitmask; store state as integer |
10901 |
Fetching from uHunt |
non-starred |
simulation with queue |
10902 |
Fetching from uHunt |
non-starred |
line segment intersection |
10903 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
count wins and losses; output win average |
10905 |
Fetching from uHunt |
non-starred |
modified comparison function; use sort |
10906 |
Fetching from uHunt |
6.3d, Iterative Parsing |
BNF parsing; iterative solution |
10908 |
Fetching from uHunt |
non-starred |
4 nested loops; square; not too hard |
10909 |
Fetching from uHunt |
non-starred |
this problem involves dynamic selection; you can augment balanced BST or use pb_ds |
10910 |
Fetching from uHunt |
non-starred |
two dimensional DP table |
10911 |
Fetching from uHunt |
8.3e, DP Matching |
DP bitmask; graph matching |
10912 |
Fetching from uHunt |
3.5g, DP level 1 |
s: (len; last; sum); t: try next char |
10913 |
Fetching from uHunt |
4.7c, Conversion to DAG |
s: (r; c; neg_left; stat); t: down/(left/right) |
10916 |
Fetching from uHunt |
5.2h, Log, Exp, Pow |
use logarithm; power |
10917 |
Fetching from uHunt |
non-starred |
counting paths in DAG; but first; you have to build the DAG by running Dijkstra's algorithm from 'home' |
10918 |
Fetching from uHunt |
non-starred |
there are two related recurrences here |
10919 |
Fetching from uHunt |
non-starred |
process the requirements as the input is read |
10920 |
Fetching from uHunt |
non-starred |
simulate the process |
10921 |
Fetching from uHunt |
non-starred |
simple conversion problem |
10922 |
Fetching from uHunt |
5.5j, Other Number Theory |
test divisibility by 9 |
10923 |
Fetching from uHunt |
non-starred |
s: (ship_position; location_of_enemies; location_of_obstacles; steps_so_far); implicit weighted graph |
10924 |
Fetching from uHunt |
non-starred |
check if the sum of letter values is a prime |
10925 |
Fetching from uHunt |
5.3a, BigInteger, Basic |
BigInteger addition and division |
10926 |
Fetching from uHunt |
non-starred |
counting paths in DAG; DP |
10927 |
Fetching from uHunt |
7.2a, Points |
sort points by gradient; Euclidean dist |
10928 |
Fetching from uHunt |
non-starred |
counting out-degrees |
10929 |
Fetching from uHunt |
5.5j, Other Number Theory |
test divisibility by 11 |
10930 |
Fetching from uHunt |
non-starred |
ad-hoc; follow the rules given in description |
10931 |
Fetching from uHunt |
5.2j, Base Number Variants |
convert decimal to binary; count number of 1s |
10935 |
Fetching from uHunt |
non-starred |
simulation with queue |
10937 |
Fetching from uHunt |
8.5c, Graph and DP |
BFS -> APSP information for TSP; then DP or backtracking |
10938 |
Fetching from uHunt |
non-starred |
basic Lowest Common Ancestor problem |
10940 |
Fetching from uHunt |
5.2d, Finding Pattern, Easier |
find the pattern with brute force solution; then submit the optimized solution |
10942 |
Fetching from uHunt |
1.4h, Time, Harder |
try all 3! = 6 permutations of 3 integers to form YY MM DD; check validity of the date; pick the earliest valid date |
10943 |
Fetching from uHunt |
non-starred |
s: (n; k); t: try all the possible splitting points; alternative solution is to use the closed form mathematical formula: C(n k-1; k-1) which also needs DP |
10944 |
Fetching from uHunt |
non-starred |
BFS -> APSP information for TSP; then use DP as n <= 16 |
10945 |
Fetching from uHunt |
non-starred |
palindrome check; ignore case and punctuation |
10946 |
Fetching from uHunt |
non-starred |
find CCs and rank them by their size |
10947 |
Fetching from uHunt |
non-starred |
graph is small |
10948 |
Fetching from uHunt |
non-starred |
Goldbach's conjecture; similar to UVa 543; 686; and 10311 |
10950 |
Fetching from uHunt |
3.2g, Backtracking (Medium) |
sort the input; run backtracking; the output should be sorted; only display the first 100 sorted output |
10954 |
Fetching from uHunt |
2.3e, priority_queue/PriorityQueue |
use priority_queue; greedy |
10957 |
Fetching from uHunt |
non-starred |
very similar with UVa 989; if you can solve that one; you can modify your code a bit to solve this one |
10958 |
Fetching from uHunt |
non-starred |
2 * numDiv(n*m*p*p) - 1 |
10959 |
Fetching from uHunt |
non-starred |
SSSP from source 0 to the rest |
10961 |
Fetching from uHunt |
non-starred |
tedious simulation |
10963 |
Fetching from uHunt |
non-starred |
for two blocks to be mergable; the gaps between their columns must be the same |
10964 |
Fetching from uHunt |
non-starred |
convert the coordinates to (x; y); then this problem is just about finding Euclidean distance between two coordinates |
10967 |
Fetching from uHunt |
non-starred |
model the graph; SSSP |
10970 |
Fetching from uHunt |
non-starred |
direct formula exists; or use DP |
10973 |
Fetching from uHunt |
non-starred |
3 nested loops with pruning |
10976 |
Fetching from uHunt |
non-starred |
total solutions is asked upfront; therefore do brute force twice |
10977 |
Fetching from uHunt |
non-starred |
BFS with blocked states |
10978 |
Fetching from uHunt |
non-starred |
1D string array manipulation |
10980 |
Fetching from uHunt |
non-starred |
simple DP |
10982 |
Fetching from uHunt |
non-starred |
greedy |
10983 |
Fetching from uHunt |
8.5a, Bsearch-ans and Others |
binary search the answer and max flow |
10986 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
direct Dijkstra's application |
10987 |
Fetching from uHunt |
4.5b, APSP, Variants |
creative usage of Floyd Warshall's algorithm; if we can detour without increasing cost; then delete the direct edge |
10989 |
Fetching from uHunt |
non-starred |
this is the basic problem solvable with Stoer Wagner's algorithm |
10990 |
Fetching from uHunt |
5.5g, Modified Sieve |
modified sieve to compute a range of Euler Phi values; use DP to compute depth Phi values; then finally use Max 1D Range Sum DP to output the answer |
10991 |
Fetching from uHunt |
non-starred |
Heron's formula; Law of Cosines; area of sector |
10992 |
Fetching from uHunt |
non-starred |
input size is up to 50 digits |
10993 |
Fetching from uHunt |
non-starred |
s: (the current number modulo N); BFS |
10994 |
Fetching from uHunt |
non-starred |
formula simplification |
10997 |
Fetching from uHunt |
non-starred |
not an easy problem; require analysis to realize that the search space is small |
11000 |
Fetching from uHunt |
non-starred |
combinatorics; the pattern is similar to Fibonacci |
11001 |
Fetching from uHunt |
3.2a, Iterative (One Loop) |
brute force math; maximize function |
11002 |
Fetching from uHunt |
non-starred |
a simple DP; use negative offset technique |
11003 |
Fetching from uHunt |
non-starred |
try all max weight from 0 to max(weight[i] capacity[i]); forall i in [0..n-1]; if a max weight is known; how many boxes can be stacked? |
11005 |
Fetching from uHunt |
non-starred |
try all possible bases from 2 to 36 |
11008 |
Fetching from uHunt |
8.5f, Geometry and Other |
use collinear test and DP with bitmask |
11012 |
Fetching from uHunt |
non-starred |
find i and j for which this function is maximal: |x_i-x_j| |y_i-y_j| |z_i-z_j|; the solution must be faster than O(n^2) |
11013 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
check permutations of 5 cards to determine the best run; brute force the sixth card and replace one of your card with it to see if it gives you a better winning chance |
11015 |
Fetching from uHunt |
non-starred |
graph is small |
11021 |
Fetching from uHunt |
non-starred |
probability |
11022 |
Fetching from uHunt |
6.5b, DP String, Non Classic |
s: the min weight of substring [i..j] |
11026 |
Fetching from uHunt |
non-starred |
DP; similar idea with binomial theorem |
11028 |
Fetching from uHunt |
non-starred |
this is a 'dartboard sequence' |
11029 |
Fetching from uHunt |
non-starred |
combination of logarithmic trick to get the first three digits and 'big mod' trick to get the last three digits |
11032 |
Fetching from uHunt |
8.5b, Other and DP 1D RSQ/RMQ |
observation: sod(i) can be only from 1 to 63; use 1D Range Sum Query for fun(a; b) |
11034 |
Fetching from uHunt |
non-starred |
simulation with queue |
11036 |
Fetching from uHunt |
5.7a, Cycle Finding |
cycle-finding; evaluate Reverse Polish f with a stack |
11038 |
Fetching from uHunt |
5.2e, Finding Pattern, Harder |
define a function f that counts the number of 0s from 1 to n |
11039 |
Fetching from uHunt |
non-starred |
use sort then count different signs |
11040 |
Fetching from uHunt |
non-starred |
non trivial 2D array manipulation |
11042 |
Fetching from uHunt |
non-starred |
case analysis; only 4 possible outputs |
11044 |
Fetching from uHunt |
non-starred |
one liner code/formula exists |
11045 |
Fetching from uHunt |
non-starred |
assignment problem; matching with capacity; similar to UVa 259; 10092; and 12873; but actually the input constraint is actually small enough for recursive backtracking |
11047 |
Fetching from uHunt |
non-starred |
print path; special case: if origin = destination; print twice |
11048 |
Fetching from uHunt |
6.3i, String Comparison |
flexible string comparison with respect to a dictionary |
11049 |
Fetching from uHunt |
non-starred |
some restricted moves; print the path |
11052 |
Fetching from uHunt |
non-starred |
first; apply the rules to check if adjacent logs are from two different years; then try deleting each 'can-be-deleted' log one by one; the worst case time complexity of 2^1000 looks scary but the search space is not that big |
11053 |
Fetching from uHunt |
5.7a, Cycle Finding |
cycle-finding; the answer is N-lambda |
11054 |
Fetching from uHunt |
non-starred |
greedy |
11055 |
Fetching from uHunt |
non-starred |
not classic; observation needed to avoid brute-force solution |
11056 |
Fetching from uHunt |
6.3i, String Comparison |
sorting; case-insensitive string comparison |
11057 |
Fetching from uHunt |
3.3a, Binary Search |
sort; for price p[i]; check if price (M - p[i]) exists with binary search |
11059 |
Fetching from uHunt |
non-starred |
3 nested loops; input is small |
11060 |
Fetching from uHunt |
4.2d, Topological Sort |
Kahn's algorithm---modified BFS toposort |
11062 |
Fetching from uHunt |
non-starred |
similar to UVa 10815 with twists |
11063 |
Fetching from uHunt |
non-starred |
see if a number is repeated; be careful with -ve |
11064 |
Fetching from uHunt |
non-starred |
N - EulerPhi(N) - numDiv(N) |
11065 |
Fetching from uHunt |
non-starred |
optimization version of Max Independent Set problem on general graph which is NP-Hard; also need to report the number of Independent Sets; bitmask helps in speeding up the solution |
11067 |
Fetching from uHunt |
non-starred |
counting paths in grid (implicit DAG); DP; similar to UVa 825 and 926 |
11068 |
Fetching from uHunt |
non-starred |
simple 2 linear equations with 2 unknowns |
11069 |
Fetching from uHunt |
5.4e, Others, Harder |
use Dynamic Programming |
11070 |
Fetching from uHunt |
6.3e, Recursive Parsing |
recursive grammar evaluation |
11072 |
Fetching from uHunt |
non-starred |
find CH and then check if the query point inside is inside the convex hull |
11074 |
Fetching from uHunt |
non-starred |
output formatting |
11076 |
Fetching from uHunt |
5.5c, Factorial |
do not use next_permutation for 12!; TLE; observe the digits in all permutations; hint: the solution involves factorial |
11078 |
Fetching from uHunt |
non-starred |
one linear scan |
11080 |
Fetching from uHunt |
4.2e, Bipartite Graph Check |
bipartite graph check; tricky cases |
11081 |
Fetching from uHunt |
non-starred |
DP on string; s: (t; i; j; k) |
11084 |
Fetching from uHunt |
non-starred |
using next_permutation/brute force is probably not the best approach; there is a DP formulation for this |
11085 |
Fetching from uHunt |
non-starred |
see UVa 750; pre-calculation |
11086 |
Fetching from uHunt |
non-starred |
find numbers N with numPF(N) == 2 |
11088 |
Fetching from uHunt |
8.3e, DP Matching |
similar to UVa 10911; the problem used as introduction of Competitive Programming book; but this time it is about matching of emph{three} persons to one team |
11089 |
Fetching from uHunt |
non-starred |
the list of Fi-binary Numbers follow the Zeckendorf's theorem |
11090 |
Fetching from uHunt |
non-starred |
this is the simplest form of Min Mean Cycle problem; however it has small constraints and thus this problem is still solvable with just backtracking |
11093 |
Fetching from uHunt |
non-starred |
linear scan; circular array; a bit challenging |
11094 |
Fetching from uHunt |
non-starred |
tricky flood fill as it involves scrolling |
11095 |
Fetching from uHunt |
8.4a, NP-hard/complete, small |
optimization version of Min Vertex Cover on general graph which is NP-Hard |
11096 |
Fetching from uHunt |
7.3a, Polygon, Easier |
very classic CH problem; perimeter of polygon; start from here if you are new with this problem |
11099 |
Fetching from uHunt |
non-starred |
generate list of small primes; generate all multiples of each prime factor starting from base using backtracking; do not forget to use use long long |
11100 |
Fetching from uHunt |
non-starred |
greedy; sorting |
11101 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
multi-sources BFS from m1; get minimum at border of m2 |
11103 |
Fetching from uHunt |
non-starred |
greedy; sorting |
11105 |
Fetching from uHunt |
8.5b, Other and DP 1D RSQ/RMQ |
need 1D Range Sum Query |
11107 |
Fetching from uHunt |
non-starred |
Longest Common Substring of >1/2 of the strings |
11108 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
try all 2^5 = 32 values with pruning |
11110 |
Fetching from uHunt |
non-starred |
flood fill satisfy the constraints given |
11111 |
Fetching from uHunt |
non-starred |
bracket matching with some twists |
11115 |
Fetching from uHunt |
non-starred |
N^D; use Java BigInteger |
11121 |
Fetching from uHunt |
5.2j, Base Number Variants |
search for the term 'negabinary' |
11125 |
Fetching from uHunt |
8.3d, Counting Paths, Harder |
counting paths in implicit DAG; the implicit DAG is not trivial; 8 parameters |
11127 |
Fetching from uHunt |
non-starred |
backtracking with bitmask |
11130 |
Fetching from uHunt |
5.2c, Math Simulation, Harder |
mirror the billiard table to the right (and/or top) so that we will only deal with one straight line instead of bouncing lines |
11131 |
Fetching from uHunt |
non-starred |
read tree; produce two postorder traversals |
11133 |
Fetching from uHunt |
non-starred |
counting paths in DAG; the implicit DAG is not trivial; 2 parameters |
11136 |
Fetching from uHunt |
2.3b, set/TreeSet |
use multiset |
11137 |
Fetching from uHunt |
non-starred |
use long long |
11138 |
Fetching from uHunt |
4.7f, Bipartite Graph |
a pure MCBM problem; if you are new with MCBM; it is good to start from this problem |
11140 |
Fetching from uHunt |
non-starred |
ad hoc |
11147 |
Fetching from uHunt |
non-starred |
just implement the recursive DnC algorithm in the problem statement |
11148 |
Fetching from uHunt |
non-starred |
extract integers; simple/mixed fractions from a line; a bit of gcd |
11150 |
Fetching from uHunt |
non-starred |
similar to UVa 10346; be careful with boundary cases! |
11151 |
Fetching from uHunt |
non-starred |
s: (l; r); similar to UVa 10453; 10739; and 11404 |
11152 |
Fetching from uHunt |
non-starred |
triangle's (in/circum)circle; Heron's formula |
11157 |
Fetching from uHunt |
non-starred |
greedy |
11159 |
Fetching from uHunt |
non-starred |
MIS; but ans is the MCBM |
11160 |
Fetching from uHunt |
non-starred |
s: (rA; cA; rB; cB; rC; cC); move A; B; C together |
11161 |
Fetching from uHunt |
non-starred |
Fibonacci median |
11163 |
Fetching from uHunt |
9.2, A* or IDA* |
another puzzle game solvable with IDA* |
11164 |
Fetching from uHunt |
non-starred |
use Triangle properties |
11167 |
Fetching from uHunt |
4.6a, Network Flow, Standard |
there are many edges in the flow graph; compress the capacity-1 edges when possible; use O(V^2E) Dinic's |
11170 |
Fetching from uHunt |
non-starred |
key derivation: cos(NA) = 2cos((N-1)A)*cos(A) - cos((N-2)A); cos(NA) is a polynomial of degree N in cos(A) |
11172 |
Fetching from uHunt |
1.3a, Super Easy |
very easy; one liner |
11173 |
Fetching from uHunt |
non-starred |
Divide and Conquer pattern or one liner bit manipulation |
11176 |
Fetching from uHunt |
5.6b, Probability, Harder |
DP; s: (n_left; max_streak); n_left = the number of remaining games; max_streak = the longest consecutive wins; t: lose this game; or win the next W = [1..n_left] games and lose the (W 1)-th game; special case if W = n_left |
11181 |
Fetching from uHunt |
5.6a, Probability, Easier |
iterative brute force; try all possibilities |
11185 |
Fetching from uHunt |
non-starred |
Decimal to base 3 |
11192 |
Fetching from uHunt |
non-starred |
character array |
11195 |
Fetching from uHunt |
non-starred |
use backtracking with bitmask |
11198 |
Fetching from uHunt |
non-starred |
s: (permutation); tricky to code |
11201 |
Fetching from uHunt |
non-starred |
backtracking involving strings |
11202 |
Fetching from uHunt |
non-starred |
consider symmetry and flip |
11203 |
Fetching from uHunt |
6.3c, Frequency Counting |
problem description is convoluted; but this problem is actually easy |
11204 |
Fetching from uHunt |
non-starred |
only first choice matters |
11205 |
Fetching from uHunt |
non-starred |
try all 2^15 bitmask |
11207 |
Fetching from uHunt |
non-starred |
cutting rectangle into 4-equal-sized squares |
11212 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
meet in the middle; similar with UVa 12445 |
11218 |
Fetching from uHunt |
non-starred |
still solvable with complete search |
11219 |
Fetching from uHunt |
non-starred |
be careful with boundary cases! |
11220 |
Fetching from uHunt |
non-starred |
follow instruction in the problem |
11221 |
Fetching from uHunt |
non-starred |
palindrome check; we deal with a matrix (magic square) this time |
11222 |
Fetching from uHunt |
non-starred |
use several 1D arrays to simplify this problem |
11223 |
Fetching from uHunt |
non-starred |
tedious morse code conversion |
11225 |
Fetching from uHunt |
non-starred |
card game |
11226 |
Fetching from uHunt |
non-starred |
sumPF(N); get length; DP |
11227 |
Fetching from uHunt |
8.5f, Geometry and Other |
brute force; collinear test |
11228 |
Fetching from uHunt |
4.3a, MST, Standard |
split output for short vs long edges |
11230 |
Fetching from uHunt |
non-starred |
greedy |
11231 |
Fetching from uHunt |
5.2e, Finding Pattern, Harder |
there is an O(1) formula |
11233 |
Fetching from uHunt |
non-starred |
string comparison |
11234 |
Fetching from uHunt |
non-starred |
converting post-order to level-order; binary tree |
11235 |
Fetching from uHunt |
non-starred |
range maximum query |
11236 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
3 nested loops for a; b; c; derive d from a; b; c; check if you have 949 lines of output |
11239 |
Fetching from uHunt |
2.3a, map/TreeMap |
use map and set to check previous strings |
11240 |
Fetching from uHunt |
non-starred |
greedy |
11241 |
Fetching from uHunt |
non-starred |
the hardest case is computing Dew point given temperature and Humidex; derive it with Algebra |
11242 |
Fetching from uHunt |
non-starred |
plus sorting |
11244 |
Fetching from uHunt |
non-starred |
count number of CCs |
11246 |
Fetching from uHunt |
non-starred |
derive the formula |
11247 |
Fetching from uHunt |
non-starred |
brute force around the answer to be safe |
11254 |
Fetching from uHunt |
5.2c, Math Simulation, Harder |
use sum of AP; brute force all values of r from sqrt(2n) down to 1; stop at the first valid a |
11258 |
Fetching from uHunt |
6.5b, DP String, Non Classic |
dp(i) = int from substring [i..k] dp(k) |
11259 |
Fetching from uHunt |
3.5e, Coin-Change |
part of the problem is DP coin change with restricted number of coins per type; then for each query; we need to use inclusion-exclusion principle |
11262 |
Fetching from uHunt |
non-starred |
binary search the answer and MCBM; similar with UVa 10804 |
11264 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
coin change variant |
11265 |
Fetching from uHunt |
7.3b, Polygon, Harder |
seems to be a complex problem; but essentially just cutPolygon; inPolygon; area |
11267 |
Fetching from uHunt |
non-starred |
bipartite check; MST; accept -ve weight |
11269 |
Fetching from uHunt |
non-starred |
greedy; sorting |
11270 |
Fetching from uHunt |
non-starred |
sequence A004003 in OEIS |
11278 |
Fetching from uHunt |
6.3a, Cipher, Easier |
map QWERTY keys to DVORAK |
11279 |
Fetching from uHunt |
1.4f, Real Life, Harder |
an extension of UVa 11278 problem; it is interesting to compare QWERTY and DVORAK keyboard layout |
11280 |
Fetching from uHunt |
non-starred |
modified Bellman Ford's |
11281 |
Fetching from uHunt |
7.2e, Triangles + Circles |
the min bounding circle of a non obtuse triangle is its circumcircle; if the triangle is obtuse; the the radii of the min bounding circle is the largest side of the triangle |
11282 |
Fetching from uHunt |
non-starred |
derangement and binomial coefficient; use Java BigInteger |
11283 |
Fetching from uHunt |
6.4b, String Matching, 2D Grid |
2D grid; backtracking; do not count twice |
11284 |
Fetching from uHunt |
non-starred |
requires shortest paths pre-processing; TSP variant where we can go home early; we just need to tweak the DP TSP recurrence a bit: at each state; we have one more option: go home early |
11285 |
Fetching from uHunt |
non-starred |
maintain the best CAD and USD each day |
11286 |
Fetching from uHunt |
non-starred |
use map to keep track of the frequencies |
11287 |
Fetching from uHunt |
5.3c, (Prob) Prime Testing |
output yes if !isPrime(p) a.modPow(p; p) = a; use Java BigInteger |
11288 |
Fetching from uHunt |
8.5h, Three Components |
Floyd Warshall's/APSP; iterative brute force bitmask/subset and permutation; DP; also available at Kattis - carpool |
11291 |
Fetching from uHunt |
6.3e, Recursive Parsing |
recursive grammar check |
11292 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
11294 |
Fetching from uHunt |
non-starred |
can be modeled as a 2-SAT problem |
11296 |
Fetching from uHunt |
non-starred |
simple formula exists |
11297 |
Fetching from uHunt |
non-starred |
Quad Tree with updates or use 2D segment tree |
11298 |
Fetching from uHunt |
non-starred |
simple maths; derive the pattern first |
11300 |
Fetching from uHunt |
non-starred |
use sort; involving the median |
11301 |
Fetching from uHunt |
non-starred |
modeling; vertex capacity; MCMF |
11307 |
Fetching from uHunt |
non-starred |
Min Chromatic Sum; max 6 colors |
11308 |
Fetching from uHunt |
2.3a, map/TreeMap |
use map and set to help manage the data |
11309 |
Fetching from uHunt |
non-starred |
palindrome check; on HH:MM format |
11310 |
Fetching from uHunt |
5.4d, Others, Easier |
requires DP: let dp[i] be the number of ways the cakes can be packed for a box 2*i |
11311 |
Fetching from uHunt |
5.8a, Game Theory |
game theory; reducible to Nim game; we can view the game that Handel and Gretel are playing as Nim game; where there are 4 heaps - cakes left/below/right/above the topping; take the Nim sum of these 4 values and if they are equal to 0; Handel loses |
11313 |
Fetching from uHunt |
non-starred |
similar to UVa 10346 |
11314 |
Fetching from uHunt |
non-starred |
a thin line cake that is formed by stretching line segment AB until it hits the y and x-axis is the quadrilateral with smallest perimeter |
11319 |
Fetching from uHunt |
non-starred |
solve the system of the first 7 linear equations; then use all 1500 equations for 'smart sequence' checks |
11321 |
Fetching from uHunt |
non-starred |
be careful with negative mod! |
11324 |
Fetching from uHunt |
8.5c, Graph and DP |
longest paths on DAG; but first; you have to transform the graph into DAG of its SCCs; toposort |
11326 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
trigonometry; tangent; reflection trick |
11327 |
Fetching from uHunt |
non-starred |
pre-calculate EulerPhi(N) |
11329 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
s: (bitmask of 26 bits); 4 to describe the position of the die in the 4*4 grid; 16 to describe if a cell has a flea; 6 to describe the sides of the die that has a flea; use map; tedious to code |
11330 |
Fetching from uHunt |
non-starred |
greedy |
11331 |
Fetching from uHunt |
8.5c, Graph and DP |
bipartite graph checks; compute size of left/right sets per bipartite component; use DP SUBSET-SUM to see if we can sum the sizes to b bulls (or c cows) |
11332 |
Fetching from uHunt |
non-starred |
simple recursion |
11335 |
Fetching from uHunt |
non-starred |
greedy |
11338 |
Fetching from uHunt |
non-starred |
it seems that the test data is weaker than what the problem description says (n <= 10000); we use O(n^2) loop to build the weighted graph and runs Dijkstra's without getting TLE |
11340 |
Fetching from uHunt |
2.2a, 1D Array Manipulation |
Direct Addressing Table |
11341 |
Fetching from uHunt |
non-starred |
s: (id; h_learned; h_left); t: learn module 'id' by 1 hour or skip it |
11342 |
Fetching from uHunt |
non-starred |
pre-calculate squared values from 0^2 to 224^2; use 3 nested loops to generate the answers; use map to avoid duplicates |
11343 |
Fetching from uHunt |
non-starred |
line segment intersection |
11344 |
Fetching from uHunt |
5.5j, Other Number Theory |
use divisibility theory of [1..12] |
11345 |
Fetching from uHunt |
non-starred |
rectangle-rectangle intersection |
11346 |
Fetching from uHunt |
non-starred |
a bit of geometry |
11347 |
Fetching from uHunt |
5.5e, Prime Factors Related |
prime-power factorization; numDiv(N) |
11348 |
Fetching from uHunt |
non-starred |
use map and set to check uniqueness |
11349 |
Fetching from uHunt |
non-starred |
use long long to avoid issues |
11350 |
Fetching from uHunt |
non-starred |
simple tree data structure question |
11351 |
Fetching from uHunt |
non-starred |
use general case Josephus recurrence |
11352 |
Fetching from uHunt |
non-starred |
filter the graph first; then it becomes SSSP |
11353 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
numPF(N); sort variant |
11356 |
Fetching from uHunt |
1.4g, Time, Easier |
very easy if you use Java GregorianCalendar |
11357 |
Fetching from uHunt |
8.4b, NP-hard/complete, special |
an NP-Complete SAT(isfiability) problem?; the presence of BNF grammar makes one think of recursive descent parser; but; only one clause needs to be satisfieds; a clause can be satisfied if for all variables in the clause; its inverse is not in the cl |
11360 |
Fetching from uHunt |
non-starred |
do as asked |
11361 |
Fetching from uHunt |
non-starred |
counting paths in DAG; need insights for efficient implementation; K > 90 is useless; double DP; use prefix-sum idea |
11362 |
Fetching from uHunt |
non-starred |
string sort; matching |
11364 |
Fetching from uHunt |
non-starred |
linear scan to get l and r; answer = 2*(r-l) |
11367 |
Fetching from uHunt |
non-starred |
model the graph carefully; state: (location; fuel); source s = (s; 0); sink t = (e; any); only enqueue fuel 1 |
11368 |
Fetching from uHunt |
non-starred |
sort in one dimension; LIS in the other |
11369 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
11371 |
Fetching from uHunt |
5.5j, Other Number Theory |
the solving strategy is given |
11374 |
Fetching from uHunt |
non-starred |
each vertex has one more parameter: has the Commercial-Xpress ticket been used? |
11375 |
Fetching from uHunt |
non-starred |
counting paths in DAG; 2 parameters; be careful that we can create a 0 with 6 sticks; need to use Java BigInteger |
11377 |
Fetching from uHunt |
non-starred |
a city to another city without/with airport has edge weight 1/0; respectively; Dijkstra's (or BFS with deque); if the start and end city are the same and has no airport; the answer should be 0 |
11378 |
Fetching from uHunt |
non-starred |
also a closest pair problem |
11380 |
Fetching from uHunt |
non-starred |
max flow modeling with vertex capacities; similar to UVa 12125 |
11384 |
Fetching from uHunt |
non-starred |
find the smallest power of two greater than n; can be solved easily using ceil(eps log2(n)) |
11385 |
Fetching from uHunt |
6.3b, Cipher, Harder |
string manipulation and Fibonacci |
11387 |
Fetching from uHunt |
non-starred |
impossible for odd n or when n = 2; derive the formula |
11388 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
understand the relationship of GCD with LCM |
11389 |
Fetching from uHunt |
non-starred |
load balancing |
11391 |
Fetching from uHunt |
8.3d, Counting Paths, Harder |
counting paths in DAG; the implicit DAG is not trivial; 3 parameters with 1 bitmask parameter that describes the 2D grid |
11393 |
Fetching from uHunt |
non-starred |
draw several small Kn; derive the pattern |
11395 |
Fetching from uHunt |
5.5e, Prime Factors Related |
key hint: a square number multiplied by powers of two; i.e. 2^k * i^2 for k >= 0; i >= 1 has odd sum of divisors |
11396 |
Fetching from uHunt |
4.2e, Bipartite Graph Check |
it is just a bipartite graph check |
11398 |
Fetching from uHunt |
non-starred |
just follow the new rules |
11401 |
Fetching from uHunt |
5.4d, Others, Easier |
spot the pattern |
11402 |
Fetching from uHunt |
non-starred |
Segment Tree with lazy updates |
11403 |
Fetching from uHunt |
6.3h, Output Formatting, Harder |
similar with UVa 338; tedious |
11404 |
Fetching from uHunt |
non-starred |
similar to UVa 10453; 10739; and 11151; print the solution in lexicographically smallest manner |
11405 |
Fetching from uHunt |
non-starred |
BFS from k and each P---max 9 items to get APSP information for TSP; then use DP-TSP |
11407 |
Fetching from uHunt |
non-starred |
can be memoized |
11408 |
Fetching from uHunt |
non-starred |
need 1D Range Sum Query |
11412 |
Fetching from uHunt |
non-starred |
next_permutation; find one possibility from 6! |
11413 |
Fetching from uHunt |
non-starred |
binary search the answer simulation |
11414 |
Fetching from uHunt |
non-starred |
similar to UVa 10720 and 12786; Erdos-Gallai's Theorem |
11415 |
Fetching from uHunt |
non-starred |
count the number of factors for each integer; find the number of factors for each factorial number and store it in an array; for each query; search in the array to find the first element with that value with binary search |
11417 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
just use brute force as input is small |
11418 |
Fetching from uHunt |
4.6a, Network Flow, Standard |
two layers of graph matching (not really bipartite matching); use max flow solution |
11419 |
Fetching from uHunt |
non-starred |
MVC; Konig theorem |
11420 |
Fetching from uHunt |
3.5g, DP level 1 |
s: (prev; id; numlck); lock/unlock this chest |
11423 |
Fetching from uHunt |
2.4c, Tree-related DS |
clever usage of Fenwick Tree and large array; important hint: look at the constraints carefully |
11426 |
Fetching from uHunt |
5.5g, Modified Sieve |
pre-calculate EulerPhi(N) |
11428 |
Fetching from uHunt |
non-starred |
complete search and binary search |
11432 |
Fetching from uHunt |
8.3d, Counting Paths, Harder |
counting paths in DAG; the implicit DAG is not trivial; 6 parameters |
11437 |
Fetching from uHunt |
non-starred |
hint: 1/7 |
11439 |
Fetching from uHunt |
non-starred |
binary search the answer to get the minimum weight; use this weight to reconstruct the graph; use Edmonds's Matching algorithm to test if we can get perfect matching on general graph |
11447 |
Fetching from uHunt |
7.3a, Polygon, Easier |
area of polygon |
11448 |
Fetching from uHunt |
non-starred |
BigInteger subtraction |
11450 |
Fetching from uHunt |
non-starred |
standard DP |
11451 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
the input constraints are small; backtracking with bitmask without memoization--as there are not that many overlapping subproblems--is fast enough; DP solution is possible |
11452 |
Fetching from uHunt |
non-starred |
string period; small input; brute force |
11455 |
Fetching from uHunt |
non-starred |
property check |
11456 |
Fetching from uHunt |
3.5c, LIS |
max(LIS(i) LDS(i) - 1); forall i in [0 ... n-1]$ |
11459 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
simulate it; similar to UVa 647 |
11461 |
Fetching from uHunt |
non-starred |
answer is sqrt(b) - sqrt(a-1) |
11462 |
Fetching from uHunt |
non-starred |
standard Counting Sort problem |
11463 |
Fetching from uHunt |
4.5a, APSP, Standard |
solution is easy with APSP information |
11464 |
Fetching from uHunt |
non-starred |
brute force the first row in 2^15; the rest follows |
11466 |
Fetching from uHunt |
5.5d, Finding Prime Factors |
use efficient sieve implementation to get the largest prime factors |
11470 |
Fetching from uHunt |
non-starred |
you can do flood fill layer by layer; however; there is other way to solve this problem; e.g. by finding the patterns |
11471 |
Fetching from uHunt |
non-starred |
reduce search space by grouping tiles of the same type; recursive backtracking |
11472 |
Fetching from uHunt |
8.3d, Counting Paths, Harder |
counting paths in DAG; the implicit DAG is not trivial; 4 parameters with 1 bitmask parameter |
11473 |
Fetching from uHunt |
7.3a, Polygon, Easier |
modified perimeter of polygon |
11474 |
Fetching from uHunt |
8.5g, Efficient DS and Other |
use union find; connect all branches in the tree; connect one tree with another tree if any of their branch has distance less than k (geometry); connect any tree that can reach any doctor; check if the first branch of the first/sick tree is connected |
11475 |
Fetching from uHunt |
non-starred |
similar with UVa 12467; if you can solve that problem; you should be able to solve this problem; although this problem involves palindrome; it is best classified here as it involves 'border' of KMP |
11476 |
Fetching from uHunt |
non-starred |
basic integer factorization problem that requires Pollard's rho algorithm |
11479 |
Fetching from uHunt |
non-starred |
property check |
11480 |
Fetching from uHunt |
non-starred |
try all r; but simpler formula exists |
11482 |
Fetching from uHunt |
non-starred |
tedious |
11483 |
Fetching from uHunt |
6.3j, Ad Hoc String |
straightforward; use 'escape character' |
11485 |
Fetching from uHunt |
non-starred |
the problem description looks scary but the solution is not that complex |
11486 |
Fetching from uHunt |
non-starred |
model as adjacency matrix; raise the adjacency matrix to the power of N in O(log N) to get the number of paths |
11487 |
Fetching from uHunt |
non-starred |
s: (r; c; cur_food; len); t: 4 dirs |
11489 |
Fetching from uHunt |
5.8a, Game Theory |
game theory; reducible to simple math |
11490 |
Fetching from uHunt |
5.2c, Math Simulation, Harder |
let missing_people = 2*a^2; thickness_of_soldiers = b; derive a formula involving a; b; and the given S |
11491 |
Fetching from uHunt |
3.4e, Non Classical, Harder |
greedy |
11492 |
Fetching from uHunt |
non-starred |
vertex = word; edges connect words with common language have different 1st char; connect source/sink to all words in start/finish language; respectively; use vertex splitting technique; Dijkstra's |
11494 |
Fetching from uHunt |
non-starred |
ad hoc;chess |
11495 |
Fetching from uHunt |
non-starred |
requires O(n log n) merge sort |
11496 |
Fetching from uHunt |
non-starred |
store data in 1D array; count the peaks |
11498 |
Fetching from uHunt |
non-starred |
just use if-else statements |
11500 |
Fetching from uHunt |
non-starred |
Gambler's Ruin Problem |
11503 |
Fetching from uHunt |
non-starred |
maintain set attribute (size) in rep item |
11504 |
Fetching from uHunt |
4.2g, SCCs |
interesting problem: count the number of SCCs without incoming edge from a vertex outside that SCC |
11505 |
Fetching from uHunt |
non-starred |
Euclidean dist |
11506 |
Fetching from uHunt |
non-starred |
min cut with vertex capacities |
11507 |
Fetching from uHunt |
1.3c, Medium |
simulation; if-else |
11511 |
Fetching from uHunt |
5.7a, Cycle Finding |
cycle-finding on vectors; the pattern will cycle fast |
11512 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
Longest Repeated Substring |
11513 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
reverse the role of source and destination |
11514 |
Fetching from uHunt |
non-starred |
this problem is like a modified 0-1 Knapsack; Batman can choose to use or skip a certain super power; check if the best configuration uses <= E calories; print yes or no accordingly |
11515 |
Fetching from uHunt |
non-starred |
circle-circle intersection; backtracking |
11516 |
Fetching from uHunt |
non-starred |
binary search the answer and greedy |
11517 |
Fetching from uHunt |
non-starred |
a variation to the coin change problem |
11518 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
unlike UVa 11504; we treat SCCs as CCs |
11519 |
Fetching from uHunt |
7.2b, Lines |
there are n vectors whose sum is 0; we are given n-1 vectors and our job is to find the unknown vector |
11520 |
Fetching from uHunt |
3.4d, Non Classical, Easier |
greedy |
11523 |
Fetching from uHunt |
non-starred |
each part between non-recyclable items must be solved separately; for each part; use O(n^3) DP |
11525 |
Fetching from uHunt |
8.5g, Efficient DS and Other |
use Fenwick Tree and binary search the answer to find the lowest index i that has RSQ(1;i) = Si |
11526 |
Fetching from uHunt |
5.2k, Just Ad Hoc |
brute force up to sqrt(n); find the pattern; avoid TLE |
11530 |
Fetching from uHunt |
non-starred |
handphone users encounter this issue in the past |
11532 |
Fetching from uHunt |
non-starred |
greedy |
11536 |
Fetching from uHunt |
non-starred |
sliding window variant |
11538 |
Fetching from uHunt |
5.4e, Others, Harder |
count along rows; columns; and diagonals |
11541 |
Fetching from uHunt |
non-starred |
read char by char and simulate |
11545 |
Fetching from uHunt |
non-starred |
s: (cPos; cTime; cWTime); t: move forward/rest |
11547 |
Fetching from uHunt |
non-starred |
a one liner O(1) solution exists |
11548 |
Fetching from uHunt |
non-starred |
4 nested loops; string; pruning |
11549 |
Fetching from uHunt |
non-starred |
repeat squaring with limited digits until it cycles; Floyd's cycle-finding algorithm is only used to detect the cycle; we do not use the value of mu or lambda; instead; we keep track the largest iterated function value found before any cycle is encou |
11550 |
Fetching from uHunt |
2.4a, Graph Data Structures |
graph representation; incidence matrix |
11552 |
Fetching from uHunt |
6.5b, DP String, Non Classic |
dp(i; c) = minimum number of chunks after considering the first i segments ending with character c |
11553 |
Fetching from uHunt |
non-starred |
solve by trying all n! permutations; you can also use DP and bitmask; but it is overkill |
11554 |
Fetching from uHunt |
non-starred |
similar to UVa 11401 |
11555 |
Fetching from uHunt |
8.3b, DP level 3 |
sort input; compute the proper tree placement positions; s: (left_remain; right_remain); t: decide to put the next tree on the left or on the right |
11556 |
Fetching from uHunt |
non-starred |
related to power of two; use long long |
11559 |
Fetching from uHunt |
non-starred |
one linear pass |
11561 |
Fetching from uHunt |
non-starred |
flood fill with extra blocking constraint |
11565 |
Fetching from uHunt |
non-starred |
3 nested loops with pruning |
11566 |
Fetching from uHunt |
3.5d, 0-1 Knapsack |
English reading problem; actually just a knapsack variant: double each dim sum and add one parameter to check if we have bought too many dishes |
11567 |
Fetching from uHunt |
non-starred |
greedy |
11569 |
Fetching from uHunt |
4.7b, Counting Paths, Easier |
determine the length of one of the longest paths and then count the number of such longest paths in DAG |
11572 |
Fetching from uHunt |
2.3c, unordered_map/HashMap |
use map to record the occurrence index of a certain snowflake size; use this to determine the answer in O(n log n) |
11573 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
0/1-weighted SSSP; solvable with BFS and deque; put all vertices relaxed by 0/1-weighted edges at the front/back of the deque; respectively |
11574 |
Fetching from uHunt |
8.5f, Geometry and Other |
brute force all pairs of boats; if one pair already collide; the answer is 0.0; otherwise derive a quadratic equation to detect when these two boats will collide; if they will; pick the minimum collision time overall; if there is no collision; output |
11576 |
Fetching from uHunt |
6.4a, String Matching, Standard |
modified string matching; complete search |
11577 |
Fetching from uHunt |
non-starred |
straightforward problem |
11579 |
Fetching from uHunt |
non-starred |
sort; greedily check if three successive sides satisfy triangle inequality and if it is the largest triangle found so far |
11581 |
Fetching from uHunt |
2.2b, 2D Array Manipulation |
simulate the process |
11582 |
Fetching from uHunt |
5.9a, Matrix Power |
Pisano period: the sequence f(i) % n is periodic; we compute the period of the sequence f(i) % n; forall n; f(a^b) % p[n] = f((a^b) % p[n]) \% p[n]; use modPow |
11583 |
Fetching from uHunt |
3.4e, Non Classical, Harder |
greedy |
11584 |
Fetching from uHunt |
non-starred |
use two O(n^2) DP string; one for palindrome check and the other for partitioning |
11585 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
polynomial-time verifier for an NP-complete puzzle Nurikabe; this verifier requires clever usage of flood fill algorithm |
11586 |
Fetching from uHunt |
non-starred |
TLE if brute force; find the pattern |
11588 |
Fetching from uHunt |
non-starred |
sort simplifies the problem |
11594 |
Fetching from uHunt |
non-starred |
use Gomory-Hu tree |
11597 |
Fetching from uHunt |
5.4d, Others, Easier |
uses knowledge of graph theory; the answer is very trivial |
11603 |
Fetching from uHunt |
non-starred |
get the maximum spanning tree of the input table; then check if its all pairs maximum flow equals to the input table |
11608 |
Fetching from uHunt |
non-starred |
use three arrays: created; required; available |
11609 |
Fetching from uHunt |
non-starred |
N * 2^(N-1); use Java BigInteger for the modPow part |
11610 |
Fetching from uHunt |
non-starred |
first; reverse primes less than 10^6; then; append zero(es) if necessary; use Fenwick Tree and binary search |
11614 |
Fetching from uHunt |
non-starred |
find roots of a quadratic equation |
11615 |
Fetching from uHunt |
non-starred |
counting size of subtrees |
11616 |
Fetching from uHunt |
non-starred |
Roman numeral conversion problem |
11621 |
Fetching from uHunt |
3.3a, Binary Search |
generate numbers with factor 2 and/or 3; sort; upper_bound |
11624 |
Fetching from uHunt |
non-starred |
multi-sources BFS |
11626 |
Fetching from uHunt |
non-starred |
find CH; be careful with collinear points |
11627 |
Fetching from uHunt |
3.3b, Binary Search the Answer |
binary search the answer Physics simulation |
11628 |
Fetching from uHunt |
5.6b, Probability, Harder |
p[i] = ticket[i] / total; use gcd to simplify fraction |
11629 |
Fetching from uHunt |
non-starred |
use map |
11631 |
Fetching from uHunt |
4.3a, MST, Standard |
weight of (all graph edges - all MST edges) |
11634 |
Fetching from uHunt |
non-starred |
use Direct Addressing Table (DAT) of size 10K; extract digits; the programming trick to square 4 digits 'a' and get the resulting middle 4 digits is a = (a*a/100) % 10000 |
11635 |
Fetching from uHunt |
non-starred |
Dijkstra's BFS (or 2 Dijkstra's) |
11636 |
Fetching from uHunt |
5.2h, Log, Exp, Pow |
uses logarithm |
11638 |
Fetching from uHunt |
1.4i, Time Waster |
simulation; needs to use bitmask for parameter C |
11639 |
Fetching from uHunt |
non-starred |
rectangle-rectangle intersection; use flag array |
11643 |
Fetching from uHunt |
non-starred |
the distance between any 2 interesting positions can be obtained by using a pre-calculated BFS table (plus handling of the special corner cases); afterwards; this is just classic TSP problem |
11646 |
Fetching from uHunt |
non-starred |
the circle is at the center of track |
11648 |
Fetching from uHunt |
non-starred |
derive the closed form formula |
11650 |
Fetching from uHunt |
non-starred |
some mathematics required; similar to UVa 11677 |
11655 |
Fetching from uHunt |
non-starred |
counting paths in DAG and one more similar task: counting the number of vertices involved in the paths |
11658 |
Fetching from uHunt |
non-starred |
s: (id; share); t: form/ignore coalition with id |
11659 |
Fetching from uHunt |
non-starred |
try all 2^20 bitmask and check |
11660 |
Fetching from uHunt |
non-starred |
simulate; break after $j$-th character |
11661 |
Fetching from uHunt |
non-starred |
linear scan |
11664 |
Fetching from uHunt |
non-starred |
simple simulation involving BigInteger |
11666 |
Fetching from uHunt |
non-starred |
find the formula! |
11670 |
Fetching from uHunt |
non-starred |
binary search the answer and O(N) greedy simulation |
11677 |
Fetching from uHunt |
non-starred |
similar idea with UVa 11650 |
11678 |
Fetching from uHunt |
1.4a, Game (Card) |
just an array manipulation problem |
11679 |
Fetching from uHunt |
non-starred |
check if after simulation all banks have >= 0 reserve |
11683 |
Fetching from uHunt |
non-starred |
one linear pass is enough |
11686 |
Fetching from uHunt |
4.2d, Topological Sort |
toposort cycle check |
11687 |
Fetching from uHunt |
non-starred |
simulation; straightforward |
11689 |
Fetching from uHunt |
non-starred |
similar to UVa 10346 |
11690 |
Fetching from uHunt |
non-starred |
check if total money from each member is 0 |
11692 |
Fetching from uHunt |
non-starred |
use algebraic manipulation to derive a quadratic equation; solve it; special case when H < L |
11693 |
Fetching from uHunt |
non-starred |
compute shotest paths information using Floyd Warshall's; then use DP |
11695 |
Fetching from uHunt |
4.7d, Tree |
cut the worst edge along the tree diameter; link two centers |
11697 |
Fetching from uHunt |
non-starred |
follow the description; a bit tedious |
11699 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
try all the possible row combinations on which we put rooks and keep the best solution; notice that we can find the number of rooks needed if we already determine some rows must have rooks |
11701 |
Fetching from uHunt |
non-starred |
a kind of ternary search |
11703 |
Fetching from uHunt |
non-starred |
can be memoized |
11709 |
Fetching from uHunt |
4.2g, SCCs |
find the number of SCCs |
11710 |
Fetching from uHunt |
non-starred |
output 'Impossible' if the graph is still disconnected after running MST |
11713 |
Fetching from uHunt |
non-starred |
modified string comparison |
11714 |
Fetching from uHunt |
non-starred |
use decision tree model to find min and second min; eventually the solution only involves logarithm |
11715 |
Fetching from uHunt |
non-starred |
physics simulation |
11716 |
Fetching from uHunt |
non-starred |
simple cipher |
11717 |
Fetching from uHunt |
non-starred |
tricky simulation |
11718 |
Fetching from uHunt |
5.2e, Finding Pattern, Harder |
convert loops to a closed form formula; use modPow to compute the results |
11719 |
Fetching from uHunt |
non-starred |
count the number of spanning tree in a complete bipartite graph; use Java BigInteger |
11721 |
Fetching from uHunt |
non-starred |
find nodes that can reach SCCs with neg cycle |
11723 |
Fetching from uHunt |
5.2a, The Simpler Ones |
simple math |
11727 |
Fetching from uHunt |
non-starred |
sort the 3 numbers and get the median |
11728 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
sumDiv(N) |
11729 |
Fetching from uHunt |
non-starred |
greedy; sorting |
11730 |
Fetching from uHunt |
8.5d, Graph and Other |
prime factoring; BFS |
11733 |
Fetching from uHunt |
non-starred |
maintain cost at every update |
11734 |
Fetching from uHunt |
6.3i, String Comparison |
modified string comparison |
11736 |
Fetching from uHunt |
non-starred |
this is a (simplified) introduction to Computer Organization on how computer stores data in memory |
11742 |
Fetching from uHunt |
non-starred |
try all permutations |
11743 |
Fetching from uHunt |
non-starred |
Luhn's algorithm to check credit card numbers; search the Internet to learn more |
11744 |
Fetching from uHunt |
non-starred |
this is another topic on Computer Organization; this time on Digital Logic design |
11747 |
Fetching from uHunt |
4.3a, MST, Standard |
sum the edge weights of the chords |
11749 |
Fetching from uHunt |
non-starred |
find largest CC with highest average PPA |
11752 |
Fetching from uHunt |
5.5a, Prime Numbers |
try base: 2 to 2^16; composite power; sort |
11753 |
Fetching from uHunt |
non-starred |
the state is probably too big if we use DP; but we can pass the time limit with just backtracking |
11757 |
Fetching from uHunt |
4.6b, Network Flow, Variants |
creative problem about min cut; build the flow graph with a bit of simple geometry involving circle; then find the min cut from source (left side) to sink (right side) |
11760 |
Fetching from uHunt |
non-starred |
separate row col checks; use two bitsets |
11762 |
Fetching from uHunt |
non-starred |
use Sieve of Eratosthenes to know the rank of each prime number; DP; expected value |
11764 |
Fetching from uHunt |
non-starred |
one linear scan to count high low jumps |
11765 |
Fetching from uHunt |
4.6b, Network Flow, Variants |
interesting min cut variant |
11770 |
Fetching from uHunt |
non-starred |
similar to UVa 11504 |
11774 |
Fetching from uHunt |
non-starred |
find pattern involving gcd with small test cases |
11777 |
Fetching from uHunt |
non-starred |
sort simplifies the problem |
11780 |
Fetching from uHunt |
non-starred |
the background problem is Fibonacci numbers |
11782 |
Fetching from uHunt |
non-starred |
s: (id; rem_K); t: take root/try left-right subtree |
11783 |
Fetching from uHunt |
7.2b, Lines |
O(N^2) brute force line segment intersection tests |
11786 |
Fetching from uHunt |
1.3c, Medium |
need to observe the pattern |
11787 |
Fetching from uHunt |
non-starred |
follow the description |
11790 |
Fetching from uHunt |
3.5c, LIS |
combination of LIS LDS; weighted |
11792 |
Fetching from uHunt |
non-starred |
be careful with the 'important station' |
11795 |
Fetching from uHunt |
3.5f, TSP |
DP TSP variant; counting paths on DAG; DP and bitmask; simplify Mega Buster by assuming that it is owned by dummy 'Robot 0' that is destroyed at the beginning of the mission |
11797 |
Fetching from uHunt |
non-starred |
simulation with 5 queues |
11799 |
Fetching from uHunt |
1.3b, Easy |
one linear scan; find max value |
11800 |
Fetching from uHunt |
7.2f, Quadrilaterals |
use next_permutation to help you try all possible 4! = 24 permutations of 4 points; check if they can satisfy square; rectangle; rhombus; parallelogram; trapezium; in that order |
11804 |
Fetching from uHunt |
non-starred |
5 nested loops |
11805 |
Fetching from uHunt |
non-starred |
very simple O(1) formula exists |
11806 |
Fetching from uHunt |
non-starred |
counting paths in DAG; s: (r; c; rem_cheerleader; bitmask); bitmask is a 4 bit integer to check if all 4 corners have at least one cheerleader |
11813 |
Fetching from uHunt |
non-starred |
Dijsktra's -> APSP information for TSP; then use DP; n <= 10 |
11816 |
Fetching from uHunt |
non-starred |
simple math; precision required |
11817 |
Fetching from uHunt |
non-starred |
gcDistance |
11821 |
Fetching from uHunt |
5.3d, Bonus: Others |
Java BigDecimal class |
11824 |
Fetching from uHunt |
non-starred |
sort simplifies the problem |
11825 |
Fetching from uHunt |
8.3c, DP level 4 |
first; use iterative brute force: try which subset of vertices can cover all vertices; then use DP to figure out the best possible attacks |
11827 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
GCD of many numbers; small input |
11830 |
Fetching from uHunt |
non-starred |
use BigInteger string representation |
11831 |
Fetching from uHunt |
non-starred |
implicit graph; input order is NSEW |
11832 |
Fetching from uHunt |
3.5d, 0-1 Knapsack |
interesting DP; s: (id; val); use offset to handle negative numbers; t: plus or minus; print solution |
11833 |
Fetching from uHunt |
non-starred |
stop Dijkstra's at service route path plus some modification |
11834 |
Fetching from uHunt |
non-starred |
packing two circles in a rectangle |
11835 |
Fetching from uHunt |
non-starred |
do as asked |
11837 |
Fetching from uHunt |
6.4a, String Matching, Standard |
transform the input of X notes into X-1 distances; then apply KMP |
11838 |
Fetching from uHunt |
4.2g, SCCs |
see if input graph is an SCC |
11839 |
Fetching from uHunt |
non-starred |
illegal if mark 0 or >1 alternatives |
11841 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
implicit graph; check if there is a CC from x = y = z = 0 to say 'Benny wins' |
11847 |
Fetching from uHunt |
5.2h, Log, Exp, Pow |
O(1) math formula exists: floor(log2(n)) |
11849 |
Fetching from uHunt |
2.3d, unordered_set/HashSet |
use set to pass the time limit; better: use hashing! |
11850 |
Fetching from uHunt |
non-starred |
for each integer location from 0 to 1322; can Brenda reach (anywhere within 200 miles of) any charging stations? |
11854 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
Pythagorean theorem/triple |
11855 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
Longest Repeated Substring that appears X times (2 ≤ X < N); also available at Kattis - buzzwords |
11857 |
Fetching from uHunt |
non-starred |
find weight of the last edge added to MST by Kruskal's |
11858 |
Fetching from uHunt |
non-starred |
requires O(n log n) merge sort; 64-bit integer |
11860 |
Fetching from uHunt |
non-starred |
use set and map; linear scan |
11875 |
Fetching from uHunt |
5.2a, The Simpler Ones |
get median of a sorted input |
11876 |
Fetching from uHunt |
non-starred |
[lower|upper]_bound on sorted sequence N |
11877 |
Fetching from uHunt |
non-starred |
similar to UVa 10346 |
11878 |
Fetching from uHunt |
6.3d, Iterative Parsing |
math expression parsing |
11879 |
Fetching from uHunt |
5.3a, BigInteger, Basic |
BigInteger: mod; divide; subtract; equals |
11881 |
Fetching from uHunt |
non-starred |
bisection method |
11888 |
Fetching from uHunt |
non-starred |
to check for 'alindrome'; let ss = concatenate(s; s); find the reverse of s in ss; but it cannot match the first n chars or the last n chars of ss |
11889 |
Fetching from uHunt |
non-starred |
LCM; involving prime factorization |
11890 |
Fetching from uHunt |
3.4e, Non Classical, Harder |
greedy |
11894 |
Fetching from uHunt |
7.2a, Points |
about rotating and translating points |
11900 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
11902 |
Fetching from uHunt |
non-starred |
disable vertex one by one; check if the reachability from vertex 0 changes |
11906 |
Fetching from uHunt |
4.2a, Just Graph Traversal |
DFS/BFS for reachability; several tricky cases; be careful when M = 0; N = 0; or M = N |
11908 |
Fetching from uHunt |
non-starred |
sort the advertisements based on starting level; ending level; and cost; DP 1 dimension |
11909 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
Law of Sines (or tangent); two possible cases |
11917 |
Fetching from uHunt |
non-starred |
use map |
11926 |
Fetching from uHunt |
non-starred |
use 1M bitset to check if a slot is free |
11933 |
Fetching from uHunt |
2.2d, Bit Manipulation |
exercise of bit manipulation |
11934 |
Fetching from uHunt |
non-starred |
just do plain brute-force |
11935 |
Fetching from uHunt |
non-starred |
binary search the answer simulation |
11936 |
Fetching from uHunt |
non-starred |
see if 3 sides form a valid triangle |
11942 |
Fetching from uHunt |
non-starred |
check if input is sorted asc/descending |
11945 |
Fetching from uHunt |
non-starred |
a bit of output formatting |
11946 |
Fetching from uHunt |
non-starred |
ad hoc |
11947 |
Fetching from uHunt |
1.4h, Time, Harder |
easier with Java GregorianCalendar |
11951 |
Fetching from uHunt |
3.5b, Max 2D Range Sum |
use long long; max 2D range sum; prune the search space whenever possible |
11952 |
Fetching from uHunt |
5.3b, Bonus: Base Number |
check base 2 to 18; special case for base 1 |
11953 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
interesting twist of flood fill problem |
11955 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
pure application; DP |
11956 |
Fetching from uHunt |
non-starred |
simulation; ignore '.' |
11957 |
Fetching from uHunt |
4.7b, Counting Paths, Easier |
counting paths in implicit DAG; DP |
11958 |
Fetching from uHunt |
non-starred |
be careful with 'past midnight' |
11959 |
Fetching from uHunt |
non-starred |
try all possible dice positions; compare with the 2nd one |
11960 |
Fetching from uHunt |
8.5g, Efficient DS and Other |
modified Sieve; number of divisors; static Range Maximum Query; use Sparse Table data structure |
11961 |
Fetching from uHunt |
3.2g, Backtracking (Medium) |
there are at most 4^10 possible DNA strings; moreover; the mutation power is at most K <= 5 so the search space is much smaller; sort the output and then remove duplicates |
11962 |
Fetching from uHunt |
non-starred |
find formula; similar to UVa 941; base 4 |
11965 |
Fetching from uHunt |
non-starred |
replace consecutive spaces with only one space |
11966 |
Fetching from uHunt |
non-starred |
use union find to keep track of the number of disjoint sets/constellations; if Euclidian dist <= D; union the two stars |
11967 |
Fetching from uHunt |
8.5g, Efficient DS and Other |
simple brute force; use map as we cannot store the actual tic-tac-toe board; remember n coordinates and check if there are k consecutive coordinates that belong to any one player |
11968 |
Fetching from uHunt |
non-starred |
average; fabs; if ties; choose the smaller one! |
11970 |
Fetching from uHunt |
5.2g, Number Systems/Sequences |
square numbers; divisibility; brute force |
11974 |
Fetching from uHunt |
non-starred |
BFS on implicit unweighted graph |
11975 |
Fetching from uHunt |
non-starred |
3 nested loops; simulate the game as asked |
11984 |
Fetching from uHunt |
non-starred |
F to C conversion and vice versa |
11986 |
Fetching from uHunt |
non-starred |
log2 (N 1); manual check for precision |
11987 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
maintain set attribute (size and sum) in rep item; need to handle new operation: move |
11988 |
Fetching from uHunt |
2.2f, List/Queue/Deque |
rare linked list problem |
11991 |
Fetching from uHunt |
2.4a, Graph Data Structures |
use idea of Adjacency List |
11995 |
Fetching from uHunt |
non-starred |
stack; queue; and priority_queue |
11997 |
Fetching from uHunt |
2.3e, priority_queue/PriorityQueue |
sort the lists; merge two sorted lists using priority_queue to keep the K-th smallest sum every time |
12001 |
Fetching from uHunt |
non-starred |
counting; combinatorics |
12004 |
Fetching from uHunt |
5.2d, Finding Pattern, Easier |
try small n; get the pattern; use long long |
12005 |
Fetching from uHunt |
non-starred |
numDiv(4N-3) |
12015 |
Fetching from uHunt |
non-starred |
traverse the list twice |
12019 |
Fetching from uHunt |
non-starred |
Gregorian Calendar; get DAY_OF_WEEK |
12022 |
Fetching from uHunt |
non-starred |
number of ways n competitors can rank in a competition allowing for the possibility of ties; sequence A000670 in OEIS |
12024 |
Fetching from uHunt |
non-starred |
derangement |
12027 |
Fetching from uHunt |
non-starred |
sqrt trick |
12028 |
Fetching from uHunt |
non-starred |
generate the array; sort it; prepare 1D Range Sum Query; then the solution will be much simpler |
12030 |
Fetching from uHunt |
8.3e, DP Matching |
counting paths in DAG; the implicit DAG is not trivial; s: (idx; bitmask; all1; has2); t: try all shoes that has not been matched to the girl that choose dress 'idx' |
12032 |
Fetching from uHunt |
non-starred |
binary search the answer simulation |
12036 |
Fetching from uHunt |
5.2k, Just Ad Hoc |
use pigeon hole principle |
12043 |
Fetching from uHunt |
5.5g, Modified Sieve |
sumDiv(N) and numDiv(N); brute force |
12047 |
Fetching from uHunt |
non-starred |
clever usage of Dijkstra's; run Dijkstra's from source and from destination; try all edge (u; v) if dist[source][u] weight(u; v) dist[v][destination] <= p; record the largest edge weight found |
12049 |
Fetching from uHunt |
2.3d, unordered_set/HashSet |
unordered_multiset manipulation |
12060 |
Fetching from uHunt |
non-starred |
LA 3012 - Dhaka04; output format |
12063 |
Fetching from uHunt |
non-starred |
counting paths in DAG; s: (zeros; ones; mod); we do not need a parameter to denote the current bit as it can be recovered from zeros ones |
12068 |
Fetching from uHunt |
non-starred |
involving fraction; use LCM and GCD |
12070 |
Fetching from uHunt |
non-starred |
LA 3290 - Dhaka05; BFS brute force |
12083 |
Fetching from uHunt |
non-starred |
LA 3415 - NorthwesternEurope05; MIS |
12085 |
Fetching from uHunt |
1.4i, Time Waster |
LA 2189 - Dhaka06; watch out for PE |
12086 |
Fetching from uHunt |
2.4c, Tree-related DS |
LA 2191 - Dhaka06; pure dynamic RSQ problem; solvable with Fenwick Tree or Segment Tree |
12097 |
Fetching from uHunt |
non-starred |
binary search the answer and geometric formula |
12100 |
Fetching from uHunt |
non-starred |
simulation with queue |
12101 |
Fetching from uHunt |
non-starred |
BFS; involving prime numbers |
12108 |
Fetching from uHunt |
2.2f, List/Queue/Deque |
simulation with N queues |
12114 |
Fetching from uHunt |
non-starred |
simple probability |
12124 |
Fetching from uHunt |
non-starred |
greedy |
12125 |
Fetching from uHunt |
4.6b, Network Flow, Variants |
max flow modeling with vertex capacities; similar to UVa 11380 |
12135 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
LA 4201 - Dhaka08; similar with UVa 11974 |
12136 |
Fetching from uHunt |
1.4g, Time, Easier |
LA 4202 - Dhaka08; check time |
12143 |
Fetching from uHunt |
non-starred |
LA 4209 - Dhaka08; formula simplification---the hard part; use BigInteger---the easy part |
12144 |
Fetching from uHunt |
non-starred |
Dijkstra's; store multiple predecessors |
12148 |
Fetching from uHunt |
1.4g, Time, Easier |
easy with Gregorian Calendar; use method 'add' to add one day to previous date and see if it is the same as the current date |
12149 |
Fetching from uHunt |
non-starred |
finding the pattern; square numbers |
12150 |
Fetching from uHunt |
non-starred |
simple manipulation |
12155 |
Fetching from uHunt |
6.3h, Output Formatting, Harder |
LA 4403 - KualaLumpur08; use proper index manipulation |
12157 |
Fetching from uHunt |
1.3b, Easy |
LA 4405 - KualaLumpur08; compute and compare the two plans |
12159 |
Fetching from uHunt |
non-starred |
LA 4407 - KualaLumpur08; use simple CCW tests (geometry) to build the bipartite graph; MCBM |
12160 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
LA 4408 - KualaLumpur08; s: (the 4-digits number); Link two numbers with an edge if we can use a button push to transform one into another; use BFS |
12168 |
Fetching from uHunt |
4.7f, Bipartite Graph |
LA 4288 - NorthwesternEurope08; MIS |
12186 |
Fetching from uHunt |
non-starred |
the input graph is a tree |
12187 |
Fetching from uHunt |
non-starred |
simulate the process |
12190 |
Fetching from uHunt |
non-starred |
binary search the answer algebra |
12192 |
Fetching from uHunt |
3.3a, Binary Search |
the input array has special sorted properties; use lower_bound to speed up the search |
12195 |
Fetching from uHunt |
non-starred |
count the number of correct measures |
12205 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
brute force; check intervals |
12207 |
Fetching from uHunt |
2.2f, List/Queue/Deque |
use both queue and deque |
12208 |
Fetching from uHunt |
non-starred |
actually just a simple combinatorics; it is classified here due to the usage of map data structure as the DP table as the range is big |
12210 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
greedy; sorting |
12218 |
Fetching from uHunt |
8.5e, Maths and Other |
brute force recursive bitmask with prime check |
12238 |
Fetching from uHunt |
non-starred |
similar to UVa 10938 |
12239 |
Fetching from uHunt |
non-starred |
try all 90^2 pairs; see if all numbers in [0..N] are there |
12243 |
Fetching from uHunt |
non-starred |
simple string tokenizer problem |
12247 |
Fetching from uHunt |
1.4a, Game (Card) |
This is a starred problem; refer to CP3/4 book |
12249 |
Fetching from uHunt |
non-starred |
LA 4994 - KualaLumpur10; try all permutations; a bit of string matching |
12250 |
Fetching from uHunt |
1.3a, Super Easy |
LA 4995 - KualaLumpur10; if-else |
12255 |
Fetching from uHunt |
non-starred |
LA 5000 - KualaLumpur10; binary search the answer and greedy |
12256 |
Fetching from uHunt |
7.2f, Quadrilaterals |
LA 5001 - KualaLumpur 10; start with three sides of 1; 1; 1; then the fourth side onwards must be the sum of the previous three to make a line; repeat until we reach the n-th side |
12269 |
Fetching from uHunt |
non-starred |
sort and check if Guido covers all land (end-to-end and side-to-side) |
12279 |
Fetching from uHunt |
non-starred |
simple linear scan |
12280 |
Fetching from uHunt |
non-starred |
a tedious problem |
12281 |
Fetching from uHunt |
non-starred |
Zeckendorf theorem a bit of combinatorics |
12289 |
Fetching from uHunt |
non-starred |
just use if-else statements |
12290 |
Fetching from uHunt |
non-starred |
no -1 in the answer |
12291 |
Fetching from uHunt |
2.2b, 2D Array Manipulation |
do as asked; a bit tedious |
12293 |
Fetching from uHunt |
non-starred |
analyze the game tree of smaller instances to get the mathematical insight to solve this problem |
12299 |
Fetching from uHunt |
2.4c, Tree-related DS |
Segment Tree with a few point (not range) updates; RMQs |
12318 |
Fetching from uHunt |
non-starred |
brute force with set data structure |
12319 |
Fetching from uHunt |
non-starred |
Floyd Warshall's 2x and compare |
12321 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
interval covering |
12322 |
Fetching from uHunt |
8.5f, Geometry and Other |
first; use atan2 to convert angles to 1D intervals; then sort it and use a greedy scan to get the answer |
12324 |
Fetching from uHunt |
8.3a, DP level 2 |
spheres > n are useless |
12335 |
Fetching from uHunt |
5.5c, Factorial |
given the k-th permutation, recover the 1st permutation; use factorial; use Java BigInteger |
12337 |
Fetching from uHunt |
non-starred |
try all possible row x col size and test if it is beautiful |
12342 |
Fetching from uHunt |
non-starred |
tax computation can be tricky indeed |
12346 |
Fetching from uHunt |
non-starred |
LA 5723 - Phuket11; try all 2^n combinations; pick the best one |
12347 |
Fetching from uHunt |
non-starred |
given pre-order traversal of a BST; use BST property to get the BST; output the post-order traversal that BST |
12348 |
Fetching from uHunt |
non-starred |
LA 5725 - Phuket11; try all 2^n combinations |
12356 |
Fetching from uHunt |
2.2a, 1D Array Manipulation |
similar to deletion in doubly linked lists but we can still use a 1D array for the underlying data structure |
12363 |
Fetching from uHunt |
4.2f, Articulation Points/Bridges |
LA 5796 - Latin America; transform input to graph of its bridges; for each query, see if verte b is reachable from a if we only traverse the bridges; use UFDS to optimize the query part |
12364 |
Fetching from uHunt |
6.3g, Output Formatting, Easier |
2D array check; check all possible digits [0..9] |
12366 |
Fetching from uHunt |
non-starred |
set and pair checks; various corner cases; but the given sample I/O is quite thorough |
12372 |
Fetching from uHunt |
non-starred |
just check if all L; W; H <= 20 |
12376 |
Fetching from uHunt |
non-starred |
simulated greedy traversal on DAG |
12379 |
Fetching from uHunt |
4.7d, Tree |
find the diameter of tree first; we only traverse the diameter once and we traverse the other edges twice |
12392 |
Fetching from uHunt |
non-starred |
brute force permute up to 5!; recursive string parsing (simple BNF) |
12394 |
Fetching from uHunt |
non-starred |
interesting problem with real life back story; be careful of various corner cases |
12397 |
Fetching from uHunt |
non-starred |
conversion; each Roman digit has value |
12398 |
Fetching from uHunt |
non-starred |
simulate backwards; do not forget to mod 10 |
12403 |
Fetching from uHunt |
non-starred |
straightforward |
12405 |
Fetching from uHunt |
non-starred |
simpler interval covering problem |
12406 |
Fetching from uHunt |
non-starred |
try all 2^p possible bitmasks; change '0's to '2's |
12414 |
Fetching from uHunt |
non-starred |
brute force problem involving string |
12416 |
Fetching from uHunt |
non-starred |
the answer is log2 of the max consecutive spaces in a line |
12428 |
Fetching from uHunt |
non-starred |
binary search the answer and a bit of graph theory about bridges |
12439 |
Fetching from uHunt |
non-starred |
inclusion-exclusion; lots of corner cases; be careful |
12442 |
Fetching from uHunt |
4.2a, Just Graph Traversal |
modified DFS; special graph |
12445 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
meet in the middle; similar with UVa 11212; uses heavy bitmasking for the 6 operations |
12455 |
Fetching from uHunt |
non-starred |
Subset Sum; try all; check UVa 12911 for harder version |
12457 |
Fetching from uHunt |
non-starred |
simple expected value problem; use DP |
12459 |
Fetching from uHunt |
non-starred |
draw the ancestor tree to see the pattern |
12461 |
Fetching from uHunt |
non-starred |
brute force small n to see that the answer is very easy |
12463 |
Fetching from uHunt |
5.4d, Others, Easier |
double the socks and the shoes to simplify the problem |
12464 |
Fetching from uHunt |
non-starred |
although n can be very huge; the pattern is actually cyclic; find the length of the cycle l and modulo n with l |
12467 |
Fetching from uHunt |
6.4a, String Matching, Standard |
'border' of KMP; also see UVa 11475 |
12468 |
Fetching from uHunt |
non-starred |
easy; there are only 4 possibilities |
12469 |
Fetching from uHunt |
non-starred |
game playing; Dynamic Programming; pruning |
12470 |
Fetching from uHunt |
non-starred |
similar to UVa 10229; the 3*3 matrix is = [0 1 0; 0 0 1; 1 1 1]; the answer is at matrix[1][1] after it is raised to the power of n and with modulo 1000000009 |
12478 |
Fetching from uHunt |
non-starred |
try one of the eight names |
12482 |
Fetching from uHunt |
3.4d, Non Classical, Easier |
greedy |
12485 |
Fetching from uHunt |
non-starred |
greedy; sorting |
12488 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
2 nested loops; simulate overtaking process |
12498 |
Fetching from uHunt |
non-starred |
3 nested loops |
12502 |
Fetching from uHunt |
non-starred |
must understand the wording trick first |
12503 |
Fetching from uHunt |
non-starred |
easy simulation |
12504 |
Fetching from uHunt |
non-starred |
use map; string to string |
12506 |
Fetching from uHunt |
non-starred |
we can use Trie to solve this problem |
12515 |
Fetching from uHunt |
non-starred |
3 nested loops |
12516 |
Fetching from uHunt |
non-starred |
greedy |
12527 |
Fetching from uHunt |
non-starred |
try all; check repeated digits |
12531 |
Fetching from uHunt |
non-starred |
angles between two clock hands |
12532 |
Fetching from uHunt |
non-starred |
clever usage of Fenwick/Segment Tree |
12541 |
Fetching from uHunt |
non-starred |
LA 6148 - HatYai12; sort; pick youngest and oldest |
12542 |
Fetching from uHunt |
non-starred |
LA 6149 - HatYai12; brute force; use isProbablePrime to test primality |
12543 |
Fetching from uHunt |
non-starred |
LA 6150 - HatYai12; iterative parser |
12545 |
Fetching from uHunt |
non-starred |
analyzing patterns; not that hard |
12554 |
Fetching from uHunt |
non-starred |
easy simulation |
12555 |
Fetching from uHunt |
non-starred |
one of the first question asked when a new baby is born; requires a bit of input processing |
12571 |
Fetching from uHunt |
2.2d, Bit Manipulation |
precalculate AND operations |
12577 |
Fetching from uHunt |
non-starred |
straightforward |
12578 |
Fetching from uHunt |
non-starred |
area of rectangle and circle |
12582 |
Fetching from uHunt |
non-starred |
given graph DFS traversal; count the degree of each vertex |
12583 |
Fetching from uHunt |
non-starred |
2 nested loops; be careful of overcounting |
12592 |
Fetching from uHunt |
non-starred |
use map; string to string |
12602 |
Fetching from uHunt |
non-starred |
simple base conversion |
12608 |
Fetching from uHunt |
non-starred |
simulation with several corner cases |
12611 |
Fetching from uHunt |
non-starred |
a problem involving a rectangle and a circle |
12614 |
Fetching from uHunt |
non-starred |
this problem has nice bitmask story camouflage; the final solution--after some thought--is very easy |
12620 |
Fetching from uHunt |
non-starred |
Pisano period of 10^2 = 300 |
12621 |
Fetching from uHunt |
non-starred |
DP Subset Sum; simplify the multiple of 10 |
12626 |
Fetching from uHunt |
non-starred |
simple frequency counting problem |
12640 |
Fetching from uHunt |
3.5a, Max 1D Range Sum |
standard; Kadane's algorithm |
12641 |
Fetching from uHunt |
9.3, Anagram |
this is an anagram problem variation |
12643 |
Fetching from uHunt |
1.3c, Medium |
it has tricky test cases and therefore a good problem to introduce programming contest |
12644 |
Fetching from uHunt |
non-starred |
classic MCBM problem wrapped inside a creative problem statement |
12646 |
Fetching from uHunt |
non-starred |
simply enumerate all cases |
12648 |
Fetching from uHunt |
non-starred |
simple graph (DAG) traversal; DFS |
12650 |
Fetching from uHunt |
non-starred |
use 1D Boolean array for each person |
12658 |
Fetching from uHunt |
non-starred |
simple character recognition check |
12662 |
Fetching from uHunt |
non-starred |
1D array manipulation; brute force |
12665 |
Fetching from uHunt |
non-starred |
be careful with boundary conditions |
12667 |
Fetching from uHunt |
2.2b, 2D Array Manipulation |
use both 1D and 2D arrays to store submission status |
12668 |
Fetching from uHunt |
4.7f, Bipartite Graph |
LA 6525 - LatinAmerica13; split rows/columns due to the presence of pawns; then run MCBM |
12673 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
LA 6530 - LatinAmerica13; greedy; sorting |
12694 |
Fetching from uHunt |
non-starred |
LA 6606 - Phuket13; it is safest to just brute force all 2^20 possibilities; greedy solution should be possible too |
12696 |
Fetching from uHunt |
1.3b, Easy |
LA 6608 - Phuket 2013; easy problem |
12700 |
Fetching from uHunt |
non-starred |
just do as instructed |
12703 |
Fetching from uHunt |
5.5d, Finding Prime Factors |
uses small Fibonacci numbers up to 40 and simple prime factorization as a and b can be non primes |
12704 |
Fetching from uHunt |
non-starred |
circle; radius; but eventually just about computing Euclidean distance |
12705 |
Fetching from uHunt |
non-starred |
we need to match grid cells to characters; there is a greedy solution; find the required pattern |
12708 |
Fetching from uHunt |
non-starred |
actually we do not need to compute the GCD; simply find an easy pattern to solve this problem |
12709 |
Fetching from uHunt |
non-starred |
LA 6650 - Dhaka13; although the problem has a complicated story; it has a very easy solution with sort routine |
12712 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
the answer is sum i=M to N of C(L*L;i)*i!; but simplify the computation of this formula instead of running it directly |
12718 |
Fetching from uHunt |
non-starred |
LA 6659 - Dhaka13; brute force all substrings while simultaneously count the frequency of characters in those substrings; a palindrome can only have certain character frequency patterns |
12720 |
Fetching from uHunt |
2.2d, Bit Manipulation |
observe the pattern in this binary to decimal conversion variant; involves modulo arithmetic |
12725 |
Fetching from uHunt |
non-starred |
simple O(1) adhoc math formula manipulation |
12747 |
Fetching from uHunt |
6.5a, DP String, Classic |
similar to UVa 10635 |
12748 |
Fetching from uHunt |
non-starred |
brute force and simple in-circle test |
12750 |
Fetching from uHunt |
non-starred |
simply loop through the given dataset in O(n) and output the answer |
12751 |
Fetching from uHunt |
non-starred |
sum of arithmetic series [1..N]; inclusion-exclusion |
12770 |
Fetching from uHunt |
9.3, Anagram |
count the frequencies; print characters with odd frequency except perhaps the last one - can be put in the middle of a palindrome |
12783 |
Fetching from uHunt |
4.2f, Articulation Points/Bridges |
finding bridges |
12786 |
Fetching from uHunt |
non-starred |
similar to UVa 10720 and 11414; Erdos-Gallai's Theorem |
12791 |
Fetching from uHunt |
3.3b, Binary Search the Answer |
binary search the answer math formula to check if the leader pilot can overtake the backmarker pilot at that lap |
12796 |
Fetching from uHunt |
5.9a, Matrix Power |
count the number of paths of length L in an undirected graph where L can be up to 2^30 |
12797 |
Fetching from uHunt |
8.5d, Graph and Other |
use iterative brute force with bitmask to specify which subset of UPPERCASE letters can be used in this round; use BFS to find the SSSP using that constraints; pick the best |
12798 |
Fetching from uHunt |
non-starred |
simply loop through the given dataset in O(N*M) and output the answer |
12801 |
Fetching from uHunt |
non-starred |
3 nested loops; still possible to be optimized further |
12802 |
Fetching from uHunt |
non-starred |
actually a very easy problem; given n; just output 2n; but it has two components: primality check of n and checking if n is a palindrome that requires a bit of string operations |
12805 |
Fetching from uHunt |
5.5d, Finding Prime Factors |
prime check; primes of format 4m-1 and 4m plus 1; simple prime factorization |
12808 |
Fetching from uHunt |
non-starred |
basic Physics formula for freefall is H = 1/2*g*t*t or t = sqrt(2*H/g) and the formula for displacement is X = V*t; they are not given in the problem description |
12820 |
Fetching from uHunt |
6.3c, Frequency Counting |
count letter frequencies; let n be the number of different letter frequencies; n has to be greater or equal to 2; then we sort the frequencies and check if we have [1..n-1] |
12821 |
Fetching from uHunt |
non-starred |
similar to UVa 10806 |
12822 |
Fetching from uHunt |
1.4h, Time, Harder |
convert hh:mm:ss to second to simplify the problem; then this is just a tedious simulation problem |
12826 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
SSSP from (r1; c1) to (r2; c2) avoiding (r3; c3); BFS |
12834 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
greedy; sorting |
12840 |
Fetching from uHunt |
3.2f, Backtracking (Easy) |
simple backtracking |
12841 |
Fetching from uHunt |
3.5f, TSP |
simply find and print the lexicographically smallest Hamiltonian path; use DP-TSP technique |
12844 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
5 nested loops; scaled down version of UVa 10202; do observations first |
12848 |
Fetching from uHunt |
non-starred |
find formula involving fraction and use GCD to simplify it |
12851 |
Fetching from uHunt |
non-starred |
binary search the answer and 3D geometry volume of cone; inclusion-exclusion |
12852 |
Fetching from uHunt |
non-starred |
LCM of the N given numbers times 35 |
12853 |
Fetching from uHunt |
non-starred |
binary search the answer and circumferences of two related circles |
12854 |
Fetching from uHunt |
non-starred |
1D array of size 5; trivial |
12855 |
Fetching from uHunt |
non-starred |
s: (pos; len) that describes the cost to transform the string so that S[0..pos-1] are all already Bs and S[pos..pos len] will be transformed to Bs; t: S[pos] is already a B; do nothing; or use either one swap move with cost A or successive adjacent s |
12861 |
Fetching from uHunt |
non-starred |
sort the timezones first and try adjacent pairings (two possibilities) |
12862 |
Fetching from uHunt |
8.3a, DP level 2 |
use 1D DP to compute the path cost from every vertex that goes up to the mountain top/vertex 1; ans = the combined path costs - common edges - the cost to reach the deepest friend |
12869 |
Fetching from uHunt |
5.5c, Factorial |
LA 6847 - Bangkok 2014; every zero in factorial(n) is due to multiplication of factor 2 and 5; factor 2 grows faster than factor 5; this is a major hint |
12870 |
Fetching from uHunt |
non-starred |
LA 6848 - Bangkok14; DP for fishing and DP for nourishing can be separated into two; then use iterative brute force to find the best combination of K fishing events and 2K nourishing events |
12873 |
Fetching from uHunt |
4.6a, Network Flow, Standard |
LA 6851 - Bangkok14; assignment problem; matching with capacity; similar to UVa 259; 11045; and 10092; use fast max flow solution like Dinic's |
12875 |
Fetching from uHunt |
4.7c, Conversion to DAG |
LA 6853 - Bangkok14; similar to UVa 10702; s: (cur_store; cur_concert); t: pick any next store for next concert |
12876 |
Fetching from uHunt |
non-starred |
LA 6854 - Bangkok14; involving degree of vertex; Handshaking lemma |
12878 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
Dijkstra's but record predecessor graph (not just predecessor array) as there can be multiple shortest paths |
12893 |
Fetching from uHunt |
3.3c, Other DnC Problems |
convert the given code into recursive DnC algorithm that halves the search space at every call |
12894 |
Fetching from uHunt |
non-starred |
continuation of UVa 12611; another problem involving a rectangle and a circle |
12895 |
Fetching from uHunt |
non-starred |
verbatim brute force check |
12896 |
Fetching from uHunt |
6.3a, Cipher, Easier |
simple cipher; use mapper |
12904 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops; brute force a; b; c; use prefix sum to speed up the checks |
12908 |
Fetching from uHunt |
non-starred |
binary search the answer and sum of arithmetic progression formula |
12916 |
Fetching from uHunt |
6.3j, Ad Hoc String |
factorize n; string period; also see UVa 11452 |
12918 |
Fetching from uHunt |
5.2d, Finding Pattern, Easier |
simple formula involving sum of arithmetic progression; use long long |
12930 |
Fetching from uHunt |
5.3d, Bonus: Others |
Java BigDecimal class; compareTo |
12965 |
Fetching from uHunt |
2.2c, algorithm/Collections |
sort producer/consumer prices; the answer is one of the prices mentioned by a producer/consumer; use binary searches to count the number of angry people |
13015 |
Fetching from uHunt |
4.2a, Just Graph Traversal |
Promotions |
13037 |
Fetching from uHunt |
2.3b, set/TreeSet |
we can use set or a sorted array |
13054 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
greedy; sorting |
13055 |
Fetching from uHunt |
2.2e, Stack |
nice problem about stack |
13109 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
13115 |
Fetching from uHunt |
8.4b, NP-hard/complete, special |
just a Sudoku solution verifier; an NP-problem |
13117 |
Fetching from uHunt |
7.2b, Lines |
use dist and distToLineSegment checks |
13127 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
Dijkstra's from multiple sources |
13141 |
Fetching from uHunt |
3.5g, DP level 1 |
s: (level, branch_previously); t: not branching if branch_previously or branching (one side) if not branch_previously |
13142 |
Fetching from uHunt |
3.3b, Binary Search the Answer |
binary search the answer + Physics simulation |
13145 |
Fetching from uHunt |
6.3a, Cipher, Easier |
shift alphabet values by +6 characters to read the problem statement; simple Caesar Cipher problem |
13146 |
Fetching from uHunt |
6.5a, DP String, Classic |
classic Edit Distance problem |
13148 |
Fetching from uHunt |
2.3d, unordered_set/HashSet |
we can store all precomputed answers - which are given - into unordered_set |
13161 |
Fetching from uHunt |
5.2g, Number Systems/Sequences |
sum of arithmetic series [1..N]; -6 for Rita or -3 for Theo; brute force Rita's age; also available at Kattis - candlebox |
13177 |
Fetching from uHunt |
2.3e, priority_queue/PriorityQueue |
use priority_queue; keep the biggest group at the front; use floating point for group size |
13181 |
Fetching from uHunt |
2.2a, 1D Array Manipulation |
find the largest gap between two Xs; special corner cases at the two end points |
13190 |
Fetching from uHunt |
2.3e, priority_queue/PriorityQueue |
similar to UVa 01203; use priority_queue; use drug numbering id as tie-breaker |
13215 |
Fetching from uHunt |
7.2e, Triangles + Circles |
area of rectangle minus area of squares and equilateral triangles |
aaah |
Kattis - aaah |
non-starred |
just compare the length of the two strings |
abc |
Kattis - abc |
non-starred |
sort 3 numbers into ABC; then print output as needed |
acm |
Kattis - acm |
1.3b, Easy |
simple simulation; one pass |
acm2 |
Kattis - acm2 |
3.4b, Involving Sorting, Easier |
greedy; sorting |
administrativeproblems |
Kattis - administrativeproblems |
2.3a, map/TreeMap |
use several maps as the output (of spy names) has to be sorted; be careful of corner cases |
airconditioned |
Kattis - airconditioned |
3.4c, Involving Sorting, Harder |
greedy; sorting |
akcija |
Kattis - akcija |
non-starred |
greedy; sorting |
aliennumbers |
Kattis - aliennumbers |
5.2j, Base Number Variants |
source base to decimal; decimal to target base |
alldifferentdirections |
Kattis - alldifferentdirections |
7.2d, Triangles (Trigonometry) |
use trigonometry to compute x and y displacement |
allpairspath |
Kattis - allpairspath |
4.5b, APSP, Variants |
basic Floyd Warshall's; tricky negative cycle checks |
alphabetspam |
Kattis - alphabetspam |
6.3c, Frequency Counting |
count the frequencies of lower/upper/whitespaces |
amoebas |
Kattis - amoebas |
non-starred |
easy floodfill |
anagramcounting |
Kattis - anagramcounting |
5.4e, Others, Harder |
use Java BigInteger |
anewalphabet |
Kattis - anewalphabet |
6.3a, Cipher, Easier |
simple cipher; 26 characters |
animal |
Kattis - animal |
8.5g, Efficient DS and Other |
Singapore15 preliminary; hashing helps |
anotherbrick |
Kattis - anotherbrick |
non-starred |
simple simulation |
anothercandies |
Kattis - anothercandies |
5.5h, Modulo Arithmetic |
simple modulo arithmetic |
anthonyanddiablo |
Kattis - anthonyanddiablo |
non-starred |
area and perimeter of a circle |
ants |
Kattis - ants |
3.4d, Non Classical, Easier |
greedy |
apaxiaaans |
Kattis - apaxiaaans |
non-starred |
very trivial |
areal |
Kattis - areal |
non-starred |
just output 4*sqrt(a) |
armystrengtheasy |
Kattis - armystrengtheasy |
non-starred |
also see Kattis - armystrengthhard |
armystrengthhard |
Kattis - armystrengthhard |
1.3c, Medium |
also see Kattis - armystrengtheasy; re-read the problem statement several times to unveil a trivial solution |
asciiaddition |
Kattis - asciiaddition |
non-starred |
a+b problem in text format; total gimmick; time waster |
asciifigurerotation |
Kattis - asciifigurerotation |
6.3h, Output Formatting, Harder |
rotate the input 90 degrees clockwise; remove trailing whitespaces; tedious |
autori |
Kattis - autori |
6.3d, Iterative Parsing |
simple string tokenizer problem |
backspace |
Kattis - backspace |
2.2f, List/Queue/Deque |
we can use deque (or vector) to help solve this problem |
baconeggsandspam |
Kattis - baconeggsandspam |
2.3a, map/TreeMap |
use map; sort |
baloni |
Kattis - baloni |
2.2a, 1D Array Manipulation |
clever use of 1D histogram array to decompose the shots as per requirement |
bank |
Kattis - bank |
3.4d, Non Classical, Easier |
greedy |
batterup |
Kattis - batterup |
non-starred |
easy one loop |
battleship |
Kattis - battleship |
1.4d, Game (Others), Harder |
simulation; reading comprehension; many corner cases |
battlesimulation |
Kattis - battlesimulation |
1.3c, Medium |
one pass; special check on 3! = 6 possible combinations of 3 combo moves |
beehives |
Kattis - beehives |
8.5f, Geometry and Other |
2D nested loops; Euclidean dist; use hypot; easy |
beekeeper |
Kattis - beekeeper |
3.2a, Iterative (One Loop) |
single loop; be careful that vowel set here includes 'y' |
bela |
Kattis - bela |
1.4a, Game (Card) |
simple card scoring problem |
bestrelayteam |
Kattis - bestrelayteam |
non-starred |
sort runners based on flying start times; brute force first runner and pick top 3 other flying start runners |
biggest |
Kattis - biggest |
7.2c, Circles |
find biggest area of sector using simulation; use array (not that larget) to avoid precision error |
bigtruck |
Kattis - bigtruck |
8.2d, State-Space, Dijkstra |
s: (city, items_picked); use Dijkstra's |
bilateral |
Kattis - bilateral |
8.4b, NP-hard/complete, special |
Min-Vertex-Cover on Bipartite Graph; MCBM; Konig's theorem that can handle the 1009 case correctly |
billiard |
Kattis - billiard |
7.2d, Triangles (Trigonometry) |
enlarge the billiard table; then this is solvable with atan2 |
birds |
Kattis - birds |
3.4c, Involving Sorting, Harder |
greedy; sorting |
bishops |
Kattis - bishops |
5.2d, Finding Pattern, Easier |
chess pattern involving bishops; from IPSC 2004 |
bitbybit |
Kattis - bitbybit |
2.2d, Bit Manipulation |
be very careful with and + or corner cases |
bits |
Kattis - bits |
non-starred |
use GNU C++ __builtin_popcount |
blackfriday |
Kattis - blackfriday |
non-starred |
2D nested loops; frequency counting |
bobby |
Kattis - bobby |
5.6b, Probability, Harder |
computation of expected value |
bookclub |
Kattis - bookclub |
4.7f, Bipartite Graph |
check if perfect MCBM is possible |
bookingaroom |
Kattis - bookingaroom |
non-starred |
only 100 rooms; use 1D Boolean array |
bottledup |
Kattis - bottledup |
3.5g, DP level 1 |
either take bottle with v1 or with v2; use pair |
boundingrobots |
Kattis - boundingrobots |
non-starred |
maintain separate variables |
bst |
Kattis - bst |
2.3b, set/TreeSet |
simulate special BST [1..N] insertions using set |
bubbletea |
Kattis - bubbletea |
non-starred |
simple simulation |
bus |
Kattis - bus |
non-starred |
involving powers of two |
busnumbers |
Kattis - busnumbers |
non-starred |
only 1000 bus numbers; use 1D Boolean array |
busnumbers2 |
Kattis - busnumbers2 |
8.5g, Efficient DS and Other |
brute force; use unordered_map to help |
busyschedule |
Kattis - busyschedule |
1.4h, Time, Harder |
sort the time; be careful of corner cases |
calculatingdartscores |
Kattis - calculatingdartscores |
3.2d, Three+ Nested Loops, Harder |
6 nested loops but easy; see if a*i +b*j + c*k == n |
candydivision |
Kattis - candydivision |
2.3b, set/TreeSet |
complete search from 1 to sqrt(N); insert all divisors into set for automatic sorting and elimination of duplicates |
cardmagic |
Kattis - cardmagic |
4.7c, Conversion to DAG |
s: (deck, tgt_left); t: val 1 to K that does not exceed tgt_left |
cardtrick2 |
Kattis - cardtrick2 |
3.2j, Pre-calculate-able |
n <= 13, we can simulate the process using queue and precalculate all 13 possible answers |
carefulascent |
Kattis - carefulascent |
3.3b, Binary Search the Answer |
binary search the answer + Physics simulation |
carousel |
Kattis - carousel |
3.2a, Iterative (One Loop) |
single loop; keep best; skip a > m |
carrots |
Kattis - carrots |
1.3a, Super Easy |
just print P |
catalan |
Kattis - catalan |
5.4c, Catalan Numbers |
basic Catalan Numbers |
centsavings |
Kattis - centsavings |
8.5b, Other and DP 1D RSQ/RMQ |
1D RSQ DP for sum of prices from [i..j]; round up/down; s: (idx, d_left); t: try all positioning of the next divider |
cetiri |
Kattis - cetiri |
non-starred |
only 3 different cases |
cetvrta |
Kattis - cetvrta |
non-starred |
sort the x and y points, then you will know the 4th point |
character |
Kattis - character |
5.4d, Others, Easier |
OEIS A000295 |
charlesincharge |
Kattis - charlesincharge |
8.5a, Bsearch-ans and Others |
binary search the max edge that Charles can use; SSSP from 1 to N passing through edges that do not exceed that max edge; check if the SSSP is within X% of Charlotte's tolerance |
chartingprogress |
Kattis - chartingprogress |
non-starred |
sort using modified comparison function (by column); transpose the input |
chess |
Kattis - chess |
1.4b, Game (Chess) |
bishop movements; either impossible, 0, 1, or 2 ways - one of this can be invalid; just use brute force |
chopin |
Kattis - chopin |
1.4e, Real Life, Easier |
you can learn a bit of music with this problem |
chopwood |
Kattis - chopwood |
2.4a, Graph Data Structures |
Prüfer sequence; use priority_queue |
classy |
Kattis - classy |
2.2c, algorithm/Collections |
sort using modified comparison function; a bit of string parsing/tokenization |
closingtheloop |
Kattis - closingtheloop |
non-starred |
sort first |
coast |
Kattis - coast |
4.2c, Flood Fill, Harder |
intelligent flood fill; just run once to avoid TLE as there are many queries |
cokolada |
Kattis - cokolada |
5.2h, Log, Exp, Pow |
the answers involve powers of two and a simulation |
cold |
Kattis - cold |
non-starred |
one pass; array not needed |
commercials |
Kattis - commercials |
3.5a, Max 1D Range Sum |
transform each input by -P; Kadane's algorithm |
communication |
Kattis - communication |
non-starred |
try all possible bytes; apply the bitmask formula |
compass |
Kattis - compass |
1.4e, Real Life, Easier |
your typical smartphone's compass function usually has this small feature |
completingthesquare |
Kattis - completingthesquare |
non-starred |
Euclidean dist checks; then translate a point with a vector |
compositions |
Kattis - compositions |
8.3f, DP in ICPC |
LA 7365 - Greater NY15; s: (N_left); t: try all values, skip some numbers |
compoundwords |
Kattis - compoundwords |
2.3b, set/TreeSet |
use set extensively; iterator |
compromise |
Kattis - compromise |
non-starred |
2D array manipulation; take the majority bits of each column; output either 0 or 1 for ties |
connectthedots |
Kattis - connectthedots |
1.4c, Game (Others), Easier |
classic children game; output formatting |
control |
Kattis - control |
2.4b, Union-Find Disjoint Sets |
LA 7480 - Singapore15; simulation of UFDS; size of set; number of disjoint sets |
conundrum |
Kattis - conundrum |
6.3a, Cipher, Easier |
simple cipher |
conversationlog |
Kattis - conversationlog |
2.3c, unordered_map/HashMap |
use combo data structures: unordered_map, set, plus (sorted) vector |
convex |
Kattis - convex |
7.3b, Polygon, Harder |
must understand the concept of convex polygon; a bit of mathematical insights: GCD; sort |
convexhull |
Kattis - convexhull |
7.3a, Polygon, Easier |
basic convex hull problem; be careful with duplicate points and collinear points |
countingstars |
Kattis - countingstars |
4.2b, Flood Fill, Easier |
basic flood fill problem; count CCs |
creditcard |
Kattis - creditcard |
1.4f, Real Life, Harder |
real life issue; precision error issue if we do not convert double (with just 2 digits after decimal point) into long long |
crne |
Kattis - crne |
5.2d, Finding Pattern, Easier |
simulate the cutting process on small numbers to derive the formula |
cropeasy |
Kattis - cropeasy |
7.2e, Triangles + Circles |
complete search 3 points/tree; check if the center is integer |
cudoviste |
Kattis - cudoviste |
3.2c, Three+ Nested Loops, Easier |
4 nested loops; the inner loops is just 2x2; 5 possibilities of crushed cars; skip 2x2 area that contains building |
cups |
Kattis - cups |
2.2c, algorithm/Collections |
a bit of string parsing; sort |
cursethedarkness |
Kattis - cursethedarkness |
7.2a, Points |
Euclidean dist |
cuttingcorners |
Kattis - cuttingcorners |
7.3a, Polygon, Easier |
simulation of angle checks |
dartscores |
Kattis - dartscores |
non-starred |
simple point in circle test; all integers |
datum |
Kattis - datum |
non-starred |
Java GregorianCalendar, DAY_OF_WEEK |
deathstar |
Kattis - deathstar |
2.2d, Bit Manipulation |
can be solved with bit manipulation |
delivery |
Kattis - delivery |
3.4c, Involving Sorting, Harder |
greedy; sorting |
detaileddifferences |
Kattis - detaileddifferences |
6.3i, String Comparison |
extremely simple string comparison problem |
dicecup |
Kattis - dicecup |
non-starred |
complete search; use map - order needed; pick the sum with the max frequency |
dicegame |
Kattis - dicegame |
5.6a, Probability, Easier |
simple comparison of two expected values |
different |
Kattis - different |
5.2a, The Simpler Ones |
simple; just be careful of long long |
differentdistances |
Kattis - differentdistances |
non-starred |
power |
digitsum |
Kattis - digitsum |
5.2e, Finding Pattern, Harder |
the sum of digits have fattern, find it; use a bit of DP to avoid re-computations |
display |
Kattis - display |
6.3g, Output Formatting, Easier |
unordered_map; map a digit -> enlarged 7x5 version |
doorman |
Kattis - doorman |
5.2e, Finding Pattern, Harder |
find the required formula |
downtime |
Kattis - downtime |
2.2a, 1D Array Manipulation |
1D array; use Fenwick Tree-like operation for Range Update Point Query |
drinkresponsibly |
Kattis - drinkresponsibly |
8.3b, DP level 3 |
DP; s: (cur_drink; money_left; u_left); be careful with precision errors; print solution |
drmmessages |
Kattis - drmmessages |
non-starred |
simple decrypt; follow instruction |
dst |
Kattis - dst |
1.4h, Time, Harder |
straightforward; modulo |
dvaput |
Kattis - dvaput |
6.6a, Suffix Trie/Tree/Array |
easy Longest Repeated Substring problem |
dvds |
Kattis - dvds |
3.4e, Non Classical, Harder |
greedy |
easiest |
Kattis - easiest |
5.2b, Math Simulation, Easier |
complete search; sum of digit |
elevatortrouble |
Kattis - elevatortrouble |
8.2b, State-Space, BFS, Easier |
s: (cur_level); only 1M floors; go up/down; BFS |
eligibility |
Kattis - eligibility |
1.3a, Super Easy |
simple if-else checks |
empleh |
Kattis - empleh |
1.4b, Game (Chess) |
the reverse problem of Kattis - helpme |
encodedmessage |
Kattis - encodedmessage |
6.3a, Cipher, Easier |
simple 2D grid cipher |
engineeringenglish |
Kattis - engineeringenglish |
non-starred |
use unordered_set to remember duplicated words; transform to lowercase |
equalsumseasy |
Kattis - equalsumseasy |
8.4a, NP-hard/complete, small |
Partition; use bitmask to generate all possible subsets; use set to record which sums have been computed before |
erase |
Kattis - erase |
non-starred |
if N is odd, the second line has to be the inverse of the first; if N is even, both lines have to be the same |
esej |
Kattis - esej |
2.3d, unordered_set/HashSet |
use unordered_set to prevent duplicate |
estimatingtheareaofacircle |
Kattis - estimatingtheareaofacircle |
non-starred |
classic PI estimation experiment |
eventplanning |
Kattis - eventplanning |
non-starred |
just simulate; 2D loop |
evenup |
Kattis - evenup |
2.2e, Stack |
use stack to solve this problem |
everywhere |
Kattis - everywhere |
2.3d, unordered_set/HashSet |
use unordered_set |
exactlyeletrical |
Kattis - exactlyeletrical |
non-starred |
Manhattan distance; waste energy at the end by moving 1 cell around target |
faktor |
Kattis - faktor |
5.2a, The Simpler Ones |
simple formula (I-1)*A + 1 |
falling |
Kattis - falling |
5.2c, Math Simulation, Harder |
rework the formula; complete search up to sqrt(D) |
fallingapart |
Kattis - fallingapart |
non-starred |
greedy; sorting |
falsesecurity |
Kattis - falsesecurity |
6.3b, Cipher, Harder |
a bit tedious decoder problem |
fastfood |
Kattis - fastfood |
1.3c, Medium |
actually just one pass due to the constraints; reading comprehension problem |
fbiuniversal |
Kattis - fbiuniversal |
non-starred |
a bit of base number conversion; base 27 to base 10, if valid |
fenwick |
Kattis - fenwick |
2.4c, Tree-related DS |
basic application of Fenwick Tree; use long long |
filip |
Kattis - filip |
non-starred |
simple modulo operations |
fire2 |
Kattis - fire2 |
4.4b, SSSP, BFS, Harder |
very similar to UVa 11624 |
fizzbuzz |
Kattis - fizzbuzz |
5.5j, Other Number Theory |
actually just about easy divisibility properties |
flexible |
Kattis - flexible |
3.2i, Try All Possible Answers |
brute force the answers; interesting search problem |
flipfive |
Kattis - flipfive |
8.2b, State-Space, BFS, Easier |
s: (bitmask); only 2^9 = 512 grid configurations; BFS |
flowergarden |
Kattis - flowergarden |
7.2a, Points |
Euclidean dist; small prime check; simulation |
flowlayout |
Kattis - flowlayout |
non-starred |
simulate the process; output the final answers |
flowshop |
Kattis - flowshop |
2.2b, 2D Array Manipulation |
interesting 2D array manipulation |
flyingsafely |
Kattis - flyingsafely |
2.4a, Graph Data Structures |
trivial solution exists |
fractionallotion |
Kattis - fractionallotion |
5.2b, Math Simulation, Easier |
brute force x > n; compute y; stop when y < x; small range |
friday |
Kattis - friday |
1.4g, Time, Easier |
the answer depends on the start day of the month |
functionalfun |
Kattis - functionalfun |
1.4i, Time Waster |
just follow the description; 5 cases; tedious parsing problem; requires a kind of mapper |
funhouse |
Kattis - funhouse |
non-starred |
2D array manipulation; note the direction update |
gamerank |
Kattis - gamerank |
1.4c, Game (Others), Easier |
simulate the ranking update process |
geneticsearch |
Kattis - geneticsearch |
6.4a, String Matching, Standard |
multiple string matchings |
getshorty |
Kattis - getshorty |
4.4c, SSSP, Dijkstra, Easier |
log of number between [0..1] is negative and log(f1 x f2 x ... x fn) = log(f1) + log(f2) + ... + log(fn), then we want to find longest path, use maximizing Dijkstra's |
glitchbot |
Kattis - glitchbot |
non-starred |
time waster; O(n^2) simulation; do not output more than one possible answer |
goldbach2 |
Kattis - goldbach2 |
non-starred |
simple brute force problem |
grandpabernie |
Kattis - grandpabernie |
2.3c, unordered_map/HashMap |
use unordered_map plus (sorted) vector |
grassseed |
Kattis - grassseed |
non-starred |
one pass; area of rectangle |
greetingcard |
Kattis - greetingcard |
2.3d, unordered_set/HashSet |
use unordered_set; good question; major hint: only 12 neighbors |
gridmst |
Kattis - gridmst |
8.5d, Graph and Other |
Singapore15 preliminary; rectilinear MST problem; small 2D grid; multi-sources BFS to construct short edges; Kruskal's to get the final answer |
grille |
Kattis - grille |
6.3b, Cipher, Harder |
involving 2D array with rotation |
growlinggears |
Kattis - growlinggears |
5.2b, Math Simulation, Easier |
physics of parabola; derivation; try all gears |
guess |
Kattis - guess |
3.3a, Binary Search |
very nice interactive problem about basic binary search concept; use C++ cout << flush |
halfacookie |
Kattis - halfacookie |
non-starred |
simple point rotation (without rotation matrix); circle; chord; segment |
hangingout |
Kattis - hangingout |
non-starred |
simple loop |
happyprime |
Kattis - happyprime |
5.7a, Cycle Finding |
simple cycle finding; TLE otherwise; small prime check |
heartrate |
Kattis - heartrate |
non-starred |
real life problem |
height |
Kattis - height |
3.2b, Iterative (Two Nested Loops) |
insertion sort simulation |
heliocentric |
Kattis - heliocentric |
5.5h, Modulo Arithmetic |
simulate modulo 365 and 687, respectively |
hello |
Kattis - hello |
non-starred |
just print 'Hello World!' |
helpaphd |
Kattis - helpaphd |
non-starred |
if-else |
helpme |
Kattis - helpme |
1.4b, Game (Chess) |
convert the given chess board into chess notation |
herman |
Kattis - herman |
non-starred |
simple; area of circle; normal vs Manhattan/taxicab |
hidden |
Kattis - hidden |
non-starred |
just careful 1D array manipulation |
hidingchickens |
Kattis - hidingchickens |
8.3e, DP Matching |
s: (bitmask); DP matching; simplify the problem by assuming that the fox always goes back to the killing spot first after hiding one or two chickens; subtract final answer with the longest edge at the end |
hidingplaces |
Kattis - hidingplaces |
4.4a, SSSP, BFS, Easier |
SSSP from (r, c); find cells with max distance; print |
hissingmicrophone |
Kattis - hissingmicrophone |
non-starred |
simple loop |
hittingtargets |
Kattis - hittingtargets |
non-starred |
simple inside rectangle and circle tests |
holeynqueensbatman |
Kattis - holeynqueensbatman |
8.2a, Challenging Backtracking |
similar with UVa 11195 |
honey |
Kattis - honey |
5.4d, Others, Easier |
OEIS A002898 |
humancannonball |
Kattis - humancannonball |
8.5f, Geometry and Other |
build the travel time graph with Euclidean distance computations; use Floyd Warshall's to compute the shortest path |
humancannonball2 |
Kattis - humancannonball2 |
non-starred |
trigonometry; simple Physics |
hurricanedanger |
Kattis - hurricanedanger |
7.2b, Lines |
distance from point to line (not vector); be careful of precision error; work with integers |
iboard |
Kattis - iboard |
non-starred |
simulation; LSB to MSB; all ASCII values are 7-bits; we may need to add leading zeroes |
imageprocessing |
Kattis - imageprocessing |
non-starred |
interesting 2D array manipulation |
incognito |
Kattis - incognito |
5.4e, Others, Harder |
count frequencies; combinatorics; minus one |
increasingsubsequence |
Kattis - increasingsubsequence |
3.5c, LIS |
LIS; n ≤ 200$; print lexicographically smallest solution, 99% similar to 'longincsubseq' |
integerlists |
Kattis - integerlists |
2.2f, List/Queue/Deque |
use deque for fast deletion from front (normal) & back (reversed list); use stack to reverse the final list if it is reversed at the end |
irepeatmyself |
Kattis - irepeatmyself |
6.3j, Ad Hoc String |
string period; complete search |
island |
Kattis - island |
3.2i, Try All Possible Answers |
try all possible subsets; prune the non contiguous ones (only 55 valid bitmasks between [0..1023]); check the 'island' property |
judgingmoose |
Kattis - judgingmoose |
non-starred |
if-else |
juryjeopardy |
Kattis - juryjeopardy |
6.3h, Output Formatting, Harder |
tedious problem |
justaminute |
Kattis - justaminute |
1.4g, Time, Easier |
linear pass; total seconds/(total minutes*60) |
karte |
Kattis - karte |
1.4a, Game (Card) |
simple |
kemija08 |
Kattis - kemija08 |
non-starred |
simple vowel checks |
keytocrypto |
Kattis - keytocrypto |
non-starred |
simple decrypt |
kitten |
Kattis - kitten |
4.7d, Tree |
simple rooted tree traversal; from a vertex back to root |
knapsack |
Kattis - knapsack |
3.5d, 0-1 Knapsack |
basic DP knapsack; print the solution |
knightsfen |
Kattis - knightsfen |
8.2a, Challenging Backtracking |
Depth Limited Search |
kolone |
Kattis - kolone |
6.3j, Ad Hoc String |
simulate the requirement; be careful of corner cases |
kornislav |
Kattis - kornislav |
non-starred |
sort the 4 edges; and think which edges should be taken |
ladder |
Kattis - ladder |
non-starred |
simple trigonometry problem |
ladice |
Kattis - ladice |
2.4b, Union-Find Disjoint Sets |
size of set; decrement one per usage |
leftbeehind |
Kattis - leftbeehind |
1.3a, Super Easy |
just 4 different cases |
lindenmayorsystem |
Kattis - lindenmayorsystem |
2.2b, 2D Array Manipulation |
Direct Addressing Table; map a character into a string of up to 5 characters; direct simulation; max answer will not be bigger than 30*5^5 |
lineup |
Kattis - lineup |
non-starred |
sort ascending/descending and compare |
listgame |
Kattis - listgame |
5.5f, Prime Factors Functions |
simply return numPF(X) |
longincsubseq |
Kattis - longincsubseq |
3.5c, LIS |
standard O(n log k) LIS; print any solution |
loworderzeros |
Kattis - loworderzeros |
5.5c, Factorial |
last non zero digit of factorial; classic |
magicallights |
Kattis - magicallights |
8.5g, Efficient DS and Other |
LA 7487 - Singapore15; flatten the tree with DFS; use Fenwick Tree for Range Odd Query; use long long |
mandelbrot |
Kattis - mandelbrot |
7.2a, Points |
the modulus operation in complex number is like Euclidean dist; simulate as asked |
maptiles2 |
Kattis - maptiles2 |
5.2f, Grid |
simple conversion between two grid indexing systems |
marko |
Kattis - marko |
6.3c, Frequency Counting |
frequency counting with unordered_map |
mastermind |
Kattis - mastermind |
non-starred |
1D array manipulation to count r and s |
matrix |
Kattis - matrix |
5.2k, Just Ad Hoc |
use simple linear algebra; one special case when c = 0 |
maxflow |
Kattis - maxflow |
4.6a, Network Flow, Standard |
standard max flow problem for practice; print edges used in the max flow |
measurement |
Kattis - measurement |
non-starred |
going down: multiply; going up: divide |
memorymatch |
Kattis - memorymatch |
1.4d, Game (Others), Harder |
interesting simulation game; many corner cases |
mia |
Kattis - mia |
non-starred |
just if-else check |
minimumscalar |
Kattis - minimumscalar |
3.4b, Involving Sorting, Easier |
greedy; sorting |
minspantree |
Kattis - minspantree |
4.3a, MST, Standard |
very standard MST problem; check if a spanning tree is formed; also output the edges in any spanning tree in lexicographic order |
mirror |
Kattis - mirror |
non-starred |
simple 2D character array formatting |
misa |
Kattis - misa |
3.2d, Three+ Nested Loops, Harder |
4 nested loops; grid; check to 8 directions |
mixedfractions |
Kattis - mixedfractions |
5.2k, Just Ad Hoc |
simply convert the fraction to mixed fraction |
mjehuric |
Kattis - mjehuric |
non-starred |
a direct simulation of a bubble sort algorithm |
modulararithmetic |
Kattis - modulararithmetic |
5.5i, Extended Euclid |
the division operation requires modular inverse; use Extended Euclid algorithm |
mosquito |
Kattis - mosquito |
1.3b, Easy |
direct simulation |
mountainbiking |
Kattis - mountainbiking |
7.2d, Triangles (Trigonometry) |
up to 4 line segments; simple trigonometry; simple Physics/Kinematic equation |
mravi |
Kattis - mravi |
4.7a, S/L Paths on DAG |
reverse edge directions to change the input tree into a DAG; find longest path from leaf that contains ant to root |
musicalnotation |
Kattis - musicalnotation |
6.3g, Output Formatting, Easier |
simple but tedious |
musicalscales |
Kattis - musicalscales |
non-starred |
music lesson; use array(s) to help simplify the code |
musicyourway |
Kattis - musicyourway |
2.2c, algorithm/Collections |
stable_sort; custom comparison function |
narrowartgallery |
Kattis - narrowartgallery |
8.3a, DP level 2 |
interesting DP; s: (row, state_of_prev_row, k_left) |
nastyhacks |
Kattis - nastyhacks |
non-starred |
if-else |
natjecanje |
Kattis - natjecanje |
3.2f, Backtracking (Easy) |
small input size; for each team with kayak, it has 4 options: do nothing, pass to left (if damaged), keep to self (if damaged), pass to right (if damaged) |
natrij |
Kattis - natrij |
non-starred |
convert hh:mm:ss to seconds; make sure the second time is larger than the first time; corner case: 24:00:00 |
nikola |
Kattis - nikola |
3.5g, DP level 1 |
s: (pos, last_jump); t: jump forward or backward |
nine |
Kattis - nine |
5.2e, Finding Pattern, Harder |
find the required formula |
nineknights |
Kattis - nineknights |
non-starred |
2D array checks; 8 directions |
nizovi |
Kattis - nizovi |
6.3h, Output Formatting, Harder |
formatting with indentation; not that trivial but sample input/output helps |
nodup |
Kattis - nodup |
non-starred |
use unordered_set; string |
notamused |
Kattis - notamused |
non-starred |
use map; sorted output |
npuzzle |
Kattis - npuzzle |
3.2c, Three+ Nested Loops, Easier |
4 nested loops; easy |
numberfun |
Kattis - numberfun |
non-starred |
six cases; integer division |
numbertree |
Kattis - numbertree |
2.3e, priority_queue/PriorityQueue |
not a direct priority queue problem, but the indexing strategy is similar to binary heap indexing |
oddgnome |
Kattis - oddgnome |
non-starred |
linear pass |
oddities |
Kattis - oddities |
5.2a, The Simpler Ones |
just check if a number is even or odd |
oddmanout |
Kattis - oddmanout |
non-starred |
use unordered_set to find and eliminate pairs |
odds |
Kattis - odds |
5.6a, Probability, Easier |
complete search; simple probability |
officespace |
Kattis - officespace |
7.2f, Quadrilaterals |
rectangles; small numbers; 2D Boolean arrays |
oktalni |
Kattis - oktalni |
5.3b, Bonus: Base Number |
convert each 3-bits of binary strings into octal |
okvir |
Kattis - okvir |
non-starred |
simple 2D output formatting problem |
okviri |
Kattis - okviri |
non-starred |
use 2D array to simplify the process |
olderbrother |
Kattis - olderbrother |
5.5e, Prime Factors Related |
just check if q = p^k |
onechicken |
Kattis - onechicken |
non-starred |
just two if-else; be careful with (s) |
orders |
Kattis - orders |
3.5d, 0-1 Knapsack |
interesting Knapsack variant; print the solution |
ornaments |
Kattis - ornaments |
7.2c, Circles |
arch length plus two times tangent lengths |
owlandfox |
Kattis - owlandfox |
non-starred |
try all answers; complete search |
pachinkoprobability |
Kattis - pachinkoprobability |
8.3d, Counting Paths, Harder |
s: (pos); t: all edges; super source to all vertices with in-degree 0; super sink 1 from all vertices with out-degree 0; super sink 2 from all vertices with gate; counting paths; long long |
pachydermpeanutpacking |
Kattis - pachydermpeanutpacking |
1.4i, Time Waster |
time waster; simple one loop simulation |
pandachess |
Kattis - pandachess |
6.5a, DP String, Classic |
see UVa 10635; LCS -> LIS; O(n log k) solution |
parking |
Kattis - parking |
non-starred |
a possible real life application; simple loops and if-statements are enough to solve this problem |
parking2 |
Kattis - parking2 |
3.2i, Try All Possible Answers |
try all possible parking spaces; pick the best |
parsinghex |
Kattis - parsinghex |
non-starred |
a bit of string parsing; hexadecimal to decimal |
patuljci |
Kattis - patuljci |
non-starred |
3 nested loops; n = 9 |
pauleigon |
Kattis - pauleigon |
non-starred |
easy to derive |
pebblesolitaire |
Kattis - pebblesolitaire |
8.2a, Challenging Backtracking |
s: (bitmask); simulation; pick the smallest answer |
pebblesolitaire2 |
Kattis - pebblesolitaire2 |
8.3a, DP level 2 |
backtracking suffices for Kattis - pebblesolitair; but this version needs extra memoization |
peg |
Kattis - peg |
non-starred |
2D nested loops; try all possible moves |
perket |
Kattis - perket |
non-starred |
use bitmask to try all subsets |
permcode |
Kattis - permcode |
non-starred |
reading comprehension problem |
permutationdescent |
Kattis - permutationdescent |
3.5g, DP level 1 |
derive the required formula; use memoization |
permutationencryption |
Kattis - permutationencryption |
6.3b, Cipher, Harder |
be careful of newline |
permutedarithmeticsequence |
Kattis - permutedarithmeticsequence |
5.2g, Number Systems/Sequences |
sort differences of adjacent items |
pervasiveheartmonitor |
Kattis - pervasiveheartmonitor |
6.3d, Iterative Parsing |
simple parsing; then finding average |
pet |
Kattis - pet |
non-starred |
very simple 2D nested loops problem |
piglatin |
Kattis - piglatin |
non-starred |
simple; check the vowels that include 'y' and process it |
pivot |
Kattis - pivot |
2.2a, 1D Array Manipulation |
static range min/max query problem; special condition allows this problem to be solvable in O(n) using help of 1D arrays |
pizza2 |
Kattis - pizza2 |
non-starred |
simple; involving circle; the formula is very easy to derive |
planina |
Kattis - planina |
5.4d, Others, Easier |
OEIS A028400 |
plantingtrees |
Kattis - plantingtrees |
non-starred |
greedy; sorting |
platforme |
Kattis - platforme |
7.2b, Lines |
line segment intersection tests; N ≤ 100; complete search |
pointinpolygon |
Kattis - pointinpolygon |
7.3b, Polygon, Harder |
in/out and on polygon |
polymul1 |
Kattis - polymul1 |
5.2i, Polynomial |
basic polynomial multiplication problem |
porpoises |
Kattis - porpoises |
5.9a, Matrix Power |
Fibonacci; matrix power; modulo |
pot |
Kattis - pot |
5.2h, Log, Exp, Pow |
the power is always the last digit |
primereduction |
Kattis - primereduction |
5.5d, Finding Prime Factors |
factorization problem |
primes2 |
Kattis - primes2 |
5.3c, (Prob) Prime Testing |
convert the input to either base 2/8/10/16; skipping those that cause NumberFormatException error; use isProbablePrime test; use gcd |
printingcosts |
Kattis - printingcosts |
1.4i, Time Waster |
clear time waster; the hard part is in parsing the costs of each character in the problem description |
progressivescramble |
Kattis - progressivescramble |
non-starred |
the encode part is trivial; the decode part requires a bit of thinking |
prozor |
Kattis - prozor |
3.5b, Max 2D Range Sum |
2D range sum with fix range; output formatting |
prsteni |
Kattis - prsteni |
5.5b, GCD and/or LCM |
GCD of first circle radius with subsequent circle radiuses |
prva |
Kattis - prva |
non-starred |
2D array manipulation; check vertically and horizontally |
ptice |
Kattis - ptice |
non-starred |
just a simple simulation |
pubs |
Kattis - pubs |
4.2a, Just Graph Traversal |
isolated vertex has no solution; this is not bipartite graph check; just do alternate labeling of vertices using DFS/BFS |
putovanje |
Kattis - putovanje |
3.2b, Iterative (Two Nested Loops) |
clever problem with hint that masks possible brute force solution; just use 2D nested loops |
quadrant |
Kattis - quadrant |
non-starred |
just four if-else cases |
quickbrownfox |
Kattis - quickbrownfox |
6.3c, Frequency Counting |
pangram; frequency counting of 26 alphabets |
quickestimate |
Kattis - quickestimate |
6.3j, Ad Hoc String |
just use strlen |
quiteaproblem |
Kattis - quiteaproblem |
6.4a, String Matching, Standard |
trivial string matching/string comparison |
r2 |
Kattis - r2 |
non-starred |
just print 2*S - R1 |
racingalphabet |
Kattis - racingalphabet |
non-starred |
circle; arc; simulation |
raggedright |
Kattis - raggedright |
non-starred |
just simulate the requirement |
rationalsequence2 |
Kattis - rationalsequence2 |
2.3e, priority_queue/PriorityQueue |
the L/R pattern can be easily derived and indexing strategy is similar to binary heap indexing |
rationalsequence3 |
Kattis - rationalsequence3 |
non-starred |
the reverse problem of rationalsequence2 |
recenice |
Kattis - recenice |
non-starred |
use unordered_map to prepare pronunciation of [1..999]; precalculate the answer afterwards using another unordered_map |
recipes |
Kattis - recipes |
non-starred |
real life problem for a cook; just simulate the requirements |
recount |
Kattis - recount |
2.3a, map/TreeMap |
use map; frequency counting |
rectanglesurrounding |
Kattis - rectanglesurrounding |
7.2f, Quadrilaterals |
rectangles; small; 2D Boolean arrays |
register |
Kattis - register |
non-starred |
clever problem with hint that masks possible brute force solution; just use 2D nested loops |
reseto |
Kattis - reseto |
5.5a, Prime Numbers |
sieve of Eratosthenes until the k-th crossing |
restaurant |
Kattis - restaurant |
2.2e, Stack |
simulation using stack-based concept; drop plates at stack 2 in LIFO order; use move 2->1 to reverse the order; take from stack 1 in FIFO order |
reversebinary |
Kattis - reversebinary |
non-starred |
decimal to binary; reverse it; binary to decimal |
reverserot |
Kattis - reverserot |
non-starred |
simple cipher |
reversingroads |
Kattis - reversingroads |
4.2g, SCCs |
small graph; if #SCC = 1, print 'valid'; otherwise try reversing one of the m directed edges one by one until we either have #SCC = 1, or print 'invalid' otherwise |
rhyming |
Kattis - rhyming |
6.3i, String Comparison |
compare suffix of a common word with the list of other given words |
ridofcoins |
Kattis - ridofcoins |
8.4b, NP-hard/complete, special |
not the minimizing Coin-Change problem; but the maximizing one; greedy pruning; complete search on much smaller instance |
rijeci |
Kattis - rijeci |
3.2a, Iterative (One Loop) |
simple simulation with a single loop |
rings2 |
Kattis - rings2 |
2.2b, 2D Array Manipulation |
more challenging 2D array manipulation; special output formatting style |
roberthood |
Kattis - roberthood |
7.3b, Polygon, Harder |
the classic furthest pair problem; use convex hull and then rotating caliper |
robotmaze |
Kattis - robotmaze |
8.2c, State-Space, BFS, Harder |
s: (r, c, dir, steps); be careful of corner cases |
robotprotection |
Kattis - robotprotection |
7.3a, Polygon, Easier |
simply find the area of convex hull |
robotsonagrid |
Kattis - robotsonagrid |
4.7b, Counting Paths, Easier |
counting paths in grid (implicit DAG); DP; if the number of path is 0, check connectivity from top-left to bottom-right to determine the last two corner cases |
rollcall |
Kattis - rollcall |
non-starred |
use unordered_map to count frequency; sort |
roundedbuttons |
Kattis - roundedbuttons |
7.2f, Quadrilaterals |
in-rectangle/in-square test; in-4-circles tests |
runningmom |
Kattis - runningmom |
4.2a, Just Graph Traversal |
find a cycle in a directed graph |
runningsteps |
Kattis - runningsteps |
4.7b, Counting Paths, Easier |
LA 7360 - Greater NY15; s: (leg, l2, r2, l1, r1); t: left/right leg 1/2 steps; use unordered_map as memo table; use pruning |
safe |
Kattis - safe |
8.2b, State-Space, BFS, Easier |
s: (convert 3x3 grid into a base 4 integer); BFS |
safepassage |
Kattis - safepassage |
8.3c, DP level 4 |
s: (cloak_pos, bitmask); try all possible ways to go back and forth between gate and dorm |
santaklas |
Kattis - santaklas |
non-starred |
another simple trigonometry problem: sine |
savingdaylight |
Kattis - savingdaylight |
1.4g, Time, Easier |
convert hh:mm to minute; compute difference of ending and starting; then convert minute to hh:mm again |
savingforretirement |
Kattis - savingforretirement |
non-starred |
try all possible answers; small constraint |
secretmessage |
Kattis - secretmessage |
non-starred |
just do as asked; use 2D grid |
secretsanta |
Kattis - secretsanta |
5.6a, Probability, Easier |
simple probability; derangement vs factorial; the answer for larger N converges |
securedoors |
Kattis - securedoors |
non-starred |
use unordered_set to keep track of the people |
semafori |
Kattis - semafori |
1.4h, Time, Harder |
simple simulation |
server |
Kattis - server |
non-starred |
one first come first serve pass; we can use queue although overkill |
set |
Kattis - set |
3.2c, Three+ Nested Loops, Easier |
4 nested loops; easy |
sevenwonders |
Kattis - sevenwonders |
non-starred |
one pass |
shopaholic |
Kattis - shopaholic |
3.4b, Involving Sorting, Easier |
greedy; sorting |
shortestpath1 |
Kattis - shortestpath1 |
4.4c, SSSP, Dijkstra, Easier |
very standard Dijkstra's problem |
shuffling |
Kattis - shuffling |
1.4a, Game (Card) |
simulate card shuffling operation |
sibice |
Kattis - sibice |
non-starred |
Euclidean dist |
sidewayssorting |
Kattis - sidewayssorting |
non-starred |
stable_sort or sort multi-fields of columns of a 2D array; ignore case |
simpleaddition |
Kattis - simpleaddition |
5.3a, BigInteger, Basic |
that A+B on BigInteger question |
simplicity |
Kattis - simplicity |
non-starred |
greedy |
skener |
Kattis - skener |
6.3g, Output Formatting, Easier |
enlarging 2D character array |
skocimis |
Kattis - skocimis |
3.4d, Non Classical, Easier |
greedy |
slatkisi |
Kattis - slatkisi |
non-starred |
power of 10; division; rounding |
smallestmultiple |
Kattis - smallestmultiple |
5.5b, GCD and/or LCM |
simple LCMs of all numbers; Java BigInteger |
smartphone |
Kattis - smartphone |
6.3i, String Comparison |
compare prefix of what you have written so far with the target string and the 3 suggestions; output 1 out of the 4 options with shortest number of keypresses |
snapperhard |
Kattis - snapperhard |
2.2d, Bit Manipulation |
bit manipulation; find the pattern; the easier version is also available at Kattis - snappereasy |
sok |
Kattis - sok |
non-starred |
case analysis |
soylent |
Kattis - soylent |
5.2d, Finding Pattern, Easier |
ceiling function |
spavanac |
Kattis - spavanac |
non-starred |
convert hh:mm to minute, reduce by 45 minutes, then convert minute to hh:mm again |
speedlimit |
Kattis - speedlimit |
non-starred |
standard simulation problem |
spiral |
Kattis - spiral |
non-starred |
generate the 2D 100x100 spiraling grid first; involving small primes; BFS |
splat |
Kattis - splat |
8.5f, Geometry and Other |
bruce force N points; bottom to top; point in circle tests |
squawk |
Kattis - squawk |
5.9a, Matrix Power |
count the number of paths of length L in an undirected graph after t steps that are reachable from source s |
stararrangements |
Kattis - stararrangements |
non-starred |
one loop |
statistics |
Kattis - statistics |
1.3b, Easy |
one pass; array not needed |
stickysituation |
Kattis - stickysituation |
7.2e, Triangles + Circles |
see if 3 sides form a triangle; see UVa 11579 |
stockbroker |
Kattis - stockbroker |
3.4e, Non Classical, Harder |
greedy |
stringmatching |
Kattis - stringmatching |
6.4a, String Matching, Standard |
basic KMP; TLE with strstr/Suffix Array |
suffixarrayreconstruction |
Kattis - suffixarrayreconstruction |
6.6a, Suffix Trie/Tree/Array |
clever creative problem involving Suffix Array concept; be careful that '*' can be more than one character |
suffixsorting |
Kattis - suffixsorting |
6.6a, Suffix Trie/Tree/Array |
basic Suffix Array construction problem; be careful with terminating symbol |
sumkindofproblem |
Kattis - sumkindofproblem |
non-starred |
sum of arithmetic progression |
sumoftheothers |
Kattis - sumoftheothers |
non-starred |
parsing; try each number as the sum; sum the rest |
supercomputer |
Kattis - supercomputer |
2.4c, Tree-related DS |
easy problem if we use Fenwick Tree |
suspensionbridges |
Kattis - suspensionbridges |
3.3b, Binary Search the Answer |
binary search the answer + Maths; be careful |
symmetricorder |
Kattis - symmetricorder |
2.2e, Stack |
use stack to help reverse even-indexed names |
synchronizinglists |
Kattis - synchronizinglists |
non-starred |
sort and lower_bound |
t9spelling |
Kattis - t9spelling |
non-starred |
similar to (the reverse of) UVa 12896 |
tajna |
Kattis - tajna |
non-starred |
simple 2D grid cipher |
tarifa |
Kattis - tarifa |
non-starred |
one pass; array not needed |
temperature |
Kattis - temperature |
non-starred |
simple math; two corner cases |
terraces |
Kattis - terraces |
4.2c, Flood Fill, Harder |
group cells with similar height together; if it cannot flow to any other component with lower height, add the size of this CC to answer |
textureanalysis |
Kattis - textureanalysis |
non-starred |
one loop |
thebackslashproblem |
Kattis - thebackslashproblem |
5.2h, Log, Exp, Pow |
actually power of two |
throwns |
Kattis - throwns |
non-starred |
use stack to help with the undo operation; be careful of corner cases |
timebomb |
Kattis - timebomb |
6.3d, Iterative Parsing |
just a tedious input parsing problem; divisibility by 6 |
timeloop |
Kattis - timeloop |
non-starred |
just print 'num Abracadabra' N times |
toilet |
Kattis - toilet |
1.4f, Real Life, Harder |
simulation; be careful of corner cases |
torn2pieces |
Kattis - torn2pieces |
4.2a, Just Graph Traversal |
construct graph from strings; traversal from source to target; print path |
touchscreenkeyboard |
Kattis - touchscreenkeyboard |
non-starred |
follow the requirements; sort |
towering |
Kattis - towering |
non-starred |
try all 6! permutations; get the one that works |
tracksmoothing |
Kattis - tracksmoothing |
non-starred |
actually clever; those round corners will form a circle |
trainpassengers |
Kattis - trainpassengers |
1.4e, Real Life, Easier |
create a verifier; be careful of corner cases |
treasurediving |
Kattis - treasurediving |
8.5c, Graph and DP |
SSSP from source and all idol positions; TSP-like but there is a knapsack style parameter 'air_left'; use backtracking |
treasurehunt |
Kattis - treasurehunt |
non-starred |
simple simulation on 2D grid |
trendingtopic |
Kattis - trendingtopic |
2.2f, List/Queue/Deque |
use queue of length 7 to maintain words in the past 7 days, unordered_map to count frequencies, sort to format the output |
tri |
Kattis - tri |
non-starred |
brute force all possibilities |
triangle |
Kattis - triangle |
non-starred |
use log 10 to compute the required answer |
trik |
Kattis - trik |
1.4c, Game (Others), Easier |
simple simulation game |
trilemma |
Kattis - trilemma |
7.2e, Triangles + Circles |
triangle properties; sort the 3 sides first |
trojke |
Kattis - trojke |
7.2b, Lines |
complete search; 3 nested loops; check if three points have the same gradient |
trollhunt |
Kattis - trollhunt |
non-starred |
brute force; simple |
turbo |
Kattis - turbo |
2.4c, Tree-related DS |
somewhat similar with UVa 01513/Kattis - moviecollection; use DAT (for mapping) and Fenwick Tree (for RSQ) |
turtlemaster |
Kattis - turtlemaster |
1.4d, Game (Others), Harder |
interesting board game to teach programming for children; simulation |
twostones |
Kattis - twostones |
non-starred |
just check odd or even |
unionfind |
Kattis - unionfind |
2.4b, Union-Find Disjoint Sets |
basic application of UFDS; similar to UVa 00793 |
unlockpattern |
Kattis - unlockpattern |
non-starred |
complete search; Euclidean dist |
vacuumba |
Kattis - vacuumba |
non-starred |
trigonometry to measure the X and Y displacements |
variablearithmetic |
Kattis - variablearithmetic |
2.3c, unordered_map/HashMap |
use unordered_map as mapper |
veci |
Kattis - veci |
3.2e, Iterative (Fancy Techniques) |
try 6! permutations; get the one that is lager than X |
vegetables |
Kattis - vegetables |
2.3e, priority_queue/PriorityQueue |
store lengths of cuts as fractions; greedily take the largest portion from priority queue; try to cut half/one-third/one-fourth/etc and store the resulting cut in priority queue |
virus |
Kattis - virus |
3.4e, Non Classical, Harder |
greedy |
volim |
Kattis - volim |
non-starred |
simple simulation |
vote |
Kattis - vote |
non-starred |
follow the requirements |
walrusweights |
Kattis - walrusweights |
8.3a, DP level 2 |
backtracking with memoization; check which weight value closest to 1000 is reachable |
watchdog |
Kattis - watchdog |
7.2c, Circles |
in circle test; brute force |
weakvertices |
Kattis - weakvertices |
2.4a, Graph Data Structures |
graph edge existence checks |
whatdoesthefoxsay |
Kattis - whatdoesthefoxsay |
non-starred |
use unordered_set to record excluded sounds |
wheels |
Kattis - wheels |
8.5h, Three Components |
Euclidean distances; DFS traversal; gcd |
whichbase |
Kattis - whichbase |
non-starred |
try reading input in octal/decimal/hexadecimal; use Java Integer class |
wordcloud |
Kattis - wordcloud |
1.4f, Real Life, Harder |
just a simulation; but be careful of corner cases |
yinyangstones |
Kattis - yinyangstones |
non-starred |
trick question; just check if number of whites equals to number of blacks |
yoda |
Kattis - yoda |
5.2k, Just Ad Hoc |
ad hoc; 9 digits comparison |
zamka |
Kattis - zamka |
non-starred |
Sum of Digit problem; brute force is sufficient |
zanzibar |
Kattis - zanzibar |
non-starred |
one pass; array not needed |
zoo |
Kattis - zoo |
non-starred |
parsing; keep last token; tolower; frequency counting with map; order needed |