| 00120 |
Fetching from uHunt |
non-starred |
greedy pancake sorting |
| 00348 |
Fetching from uHunt |
non-starred |
DP; s(i, j); output the optimal solution; the optimal sequence is not unique |
| 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 |
| 01266 |
Fetching from uHunt |
non-starred |
LA 3478 - LatinAmerica05; follow the given construction strategy |
| 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 |
| 10989 |
Fetching from uHunt |
non-starred |
this is the basic problem solvable with Stoer Wagner's algorithm |
| 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 |
| 11476 |
Fetching from uHunt |
non-starred |
basic integer factorization problem that requires Pollard's rho algorithm |
| 11594 |
Fetching from uHunt |
non-starred |
use Gomory-Hu tree |
| 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 |
| 01280 |
Fetching from uHunt |
non-starred |
LA 6027 - WorldFinals Warsaw12; binary search the answer and geometric formula |
| 10071 |
Fetching from uHunt |
1.3a, I/O + Sequence Only |
super simple: output 2*v*t |
| 11614 |
Fetching from uHunt |
1.3a, I/O + Sequence Only |
find the correct root of a quadratic equation |
| 11805 |
Fetching from uHunt |
1.3a, I/O + Sequence Only |
very simple O(1) formula exists |
| 12478 |
Fetching from uHunt |
1.3a, I/O + Sequence Only |
try one of the eight names |
| 13025 |
Fetching from uHunt |
1.3a, I/O + Sequence Only |
giveaway, just print the one line answer |
| 00621 |
Fetching from uHunt |
1.3b, Selection Only |
case analysis for only 4 possible outputs |
| 11172 |
Fetching from uHunt |
1.3b, Selection Only |
very easy; one liner |
| 11723 |
Fetching from uHunt |
1.3b, Selection Only |
simple math |
| 11727 |
Fetching from uHunt |
1.3b, Selection Only |
sort the 3 numbers and get the median |
| 12250 |
Fetching from uHunt |
1.3b, Selection Only |
LA 4995 - KualaLumpur10; if-else |
| 12289 |
Fetching from uHunt |
1.3b, Selection Only |
just use if-else statements |
| 12372 |
Fetching from uHunt |
1.3b, Selection Only |
just check if all L, W, H ≤ 20 |
| 12468 |
Fetching from uHunt |
1.3b, Selection Only |
easy; there are only 4 possibilities |
| 12577 |
Fetching from uHunt |
1.3b, Selection Only |
straightforward |
| 12646 |
Fetching from uHunt |
1.3b, Selection Only |
simply enumerate all cases |
| 12917 |
Fetching from uHunt |
1.3b, Selection Only |
simple O(1) check |
| 01124 |
Fetching from uHunt |
1.3c, Repetition Only |
LA 2681 - SouthEasternEurope06; just echo/re-print the input again |
| 10300 |
Fetching from uHunt |
1.3c, Repetition Only |
ignore the number of animals |
| 11044 |
Fetching from uHunt |
1.3c, Repetition Only |
one liner code/formula exists |
| 11547 |
Fetching from uHunt |
1.3c, Repetition Only |
a one liner O(1) solution exists |
| 11799 |
Fetching from uHunt |
1.3c, Repetition Only |
one linear scan; find max value |
| 00272 |
Fetching from uHunt |
1.3d, Control Flow |
replace all double quotes to TeX style quotes |
| 01585 |
Fetching from uHunt |
1.3d, Control Flow |
LA 3354 - Seoul05; very easy one pass algorithm |
| 11364 |
Fetching from uHunt |
1.3d, Control Flow |
linear scan to get l and r; answer = 2*(r-l) |
| 11498 |
Fetching from uHunt |
1.3d, Control Flow |
just use if-else statements |
| 11764 |
Fetching from uHunt |
1.3d, Control Flow |
one linear scan to count high low jumps |
| 12279 |
Fetching from uHunt |
1.3d, Control Flow |
simple linear scan |
| 12403 |
Fetching from uHunt |
1.3d, Control Flow |
straightforward |
| 13012 |
Fetching from uHunt |
1.3d, Control Flow |
giveaway |
| 01709 |
Fetching from uHunt |
1.3e, Function |
LA 7150 - WorldFinals Marrakech15; linear scan; probably one of the easiest WorldFinals problem; also available at Kattis - artichoke |
| 10055 |
Fetching from uHunt |
1.3e, Function |
absolute function; the only trap is to use long long |
| 10424 |
Fetching from uHunt |
1.3e, Function |
just do as asked |
| 10550 |
Fetching from uHunt |
1.3e, Function |
simple; do as asked; also available at Kattis - combinationlock |
| 11078 |
Fetching from uHunt |
1.3e, Function |
one linear scan; max function |
| 11332 |
Fetching from uHunt |
1.3e, Function |
simple recursion |
| 11687 |
Fetching from uHunt |
1.3e, Function |
direct simulation; also available at Kattis - digits |
| 01641 |
Fetching from uHunt |
1.3f, Easy |
scan row by row; flip the status of inside/outside polygon due to the presence of character slash or backslash |
| 10963 |
Fetching from uHunt |
1.3f, Easy |
for two blocks to be mergable; the gaps between their columns must be the same |
| 11679 |
Fetching from uHunt |
1.3f, Easy |
check if after simulation all banks have >= 0 reserve |
| 11942 |
Fetching from uHunt |
1.3f, Easy |
check if input is sorted in ascending or descending order |
| 12015 |
Fetching from uHunt |
1.3f, Easy |
traverse the list twice |
| 12503 |
Fetching from uHunt |
1.3f, Easy |
easy simulation |
| 12554 |
Fetching from uHunt |
1.3f, Easy |
easy simulation |
| 12658 |
Fetching from uHunt |
1.3f, Easy |
simple character recognition check |
| 12696 |
Fetching from uHunt |
1.3f, Easy |
LA 6608 - Phuket 2013; easy problem |
| 12750 |
Fetching from uHunt |
1.3f, Easy |
simply loop through the given dataset in O(n) and output the answer |
| 12798 |
Fetching from uHunt |
1.3f, Easy |
simply loop through the given dataset in O(N*M) and output the answer |
| 13034 |
Fetching from uHunt |
1.3f, Easy |
giveaway, simple loop 13 times |
| 13130 |
Fetching from uHunt |
1.3f, Easy |
simple |
| 10114 |
Fetching from uHunt |
1.3g, Still Easy |
just simulate the process |
| 10141 |
Fetching from uHunt |
1.3g, Still Easy |
solvable with one linear scan |
| 10324 |
Fetching from uHunt |
1.3g, Still Easy |
simplify using 1D array: change counter |
| 10919 |
Fetching from uHunt |
1.3g, Still Easy |
process the requirements as the input is read; also available at Kattis - prerequisites |
| 11559 |
Fetching from uHunt |
1.3g, Still Easy |
one linear pass |
| 11586 |
Fetching from uHunt |
1.3g, Still Easy |
TLE if brute force; find the pattern |
| 11661 |
Fetching from uHunt |
1.3g, Still Easy |
linear scan |
| 11683 |
Fetching from uHunt |
1.3g, Still Easy |
one linear pass is enough |
| 11786 |
Fetching from uHunt |
1.3g, Still Easy |
need to observe the pattern |
| 12614 |
Fetching from uHunt |
1.3g, Still Easy |
this problem has nice bitmask story camouflage; the final solution--after some thought--is very easy |
| 13007 |
Fetching from uHunt |
1.3g, Still Easy |
simple simulation |
| 00119 |
Fetching from uHunt |
1.3h, Medium |
simulate the give and receive process |
| 00573 |
Fetching from uHunt |
1.3h, Medium |
simulation; several corner cases |
| 00661 |
Fetching from uHunt |
1.3h, Medium |
simulation |
| 01237 |
Fetching from uHunt |
1.3h, Medium |
LA 4142 - Jakarta08; input is small |
| 11507 |
Fetching from uHunt |
1.3h, Medium |
simulation; if-else |
| 11956 |
Fetching from uHunt |
1.3h, Medium |
simulation; ignore '.' |
| 12157 |
Fetching from uHunt |
1.3h, Medium |
LA 4405 - KualaLumpur08; compute and compare the two plans |
| 12545 |
Fetching from uHunt |
1.3h, Medium |
analyzing patterns; not that hard; also available at Kattis - bitsequalizer |
| 12643 |
Fetching from uHunt |
1.3h, Medium |
it has tricky test cases |
| 00162 |
Fetching from uHunt |
1.4a, Game (Card) |
card game simulation; straightforward |
| 00462 |
Fetching from uHunt |
1.4a, Game (Card) |
simulation; card |
| 00555 |
Fetching from uHunt |
1.4a, Game (Card) |
card game |
| 10205 |
Fetching from uHunt |
1.4a, Game (Card) |
card game |
| 10315 |
Fetching from uHunt |
1.4a, Game (Card) |
tedious problem |
| 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 |
| 10646 |
Fetching from uHunt |
1.4a, Game (Card) |
shuffle cards with some rules and then get a certain card |
| 11225 |
Fetching from uHunt |
1.4a, Game (Card) |
card game |
| 11678 |
Fetching from uHunt |
1.4a, Game (Card) |
just an array manipulation problem |
| 12247 |
Fetching from uHunt |
1.4a, Game (Card) |
This is a starred problem; refer to CP3/4 book |
| 12366 |
Fetching from uHunt |
1.4a, Game (Card) |
set and pair checks; various corner cases; but the given sample I/O is quite thorough |
| 12952 |
Fetching from uHunt |
1.4a, Game (Card) |
returning the max of (A, B) is always the best strategy for this problem |
| 00255 |
Fetching from uHunt |
1.4b, Game (Chess) |
check the validity of chess moves |
| 00278 |
Fetching from uHunt |
1.4b, Game (Chess) |
basic chess knowledge is needed; derive the closed form formulas |
| 00696 |
Fetching from uHunt |
1.4b, Game (Chess) |
ad hoc; chess |
| 10196 |
Fetching from uHunt |
1.4b, Game (Chess) |
ad hoc; chess; tedious |
| 10284 |
Fetching from uHunt |
1.4b, Game (Chess) |
FEN = Forsyth-Edwards Notation is a standard notation for describing board positions in a chess game |
| 10849 |
Fetching from uHunt |
1.4b, Game (Chess) |
chess |
| 11494 |
Fetching from uHunt |
1.4b, Game (Chess) |
ad hoc;chess |
| 00340 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
determine strong and weak matches |
| 00489 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
just do as asked |
| 00947 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
similar to UVa 340 |
| 10189 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
simulate the classic Minesweeper game; similar to UVa 10279 |
| 10279 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
a 2D array helps; similar to UVa 10189 |
| 10409 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
just simulate the die movement |
| 10530 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
use a 1D flag array; also available at Kattis - guessinggame |
| 11459 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
simulate it; similar to UVa 647 |
| 12239 |
Fetching from uHunt |
1.4c, Game (Others), Easier |
try all 90^2 pairs; see if all numbers in [0..N] are there |
| 00114 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
simulation of pinball machine |
| 00141 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
solvable with one linear scan |
| 00220 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
follow the game rules; a bit tedious |
| 00227 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
parse the input; array manipulation |
| 00232 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
complex array manipulation problem |
| 00339 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
follow problem description |
| 00379 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
follow problem description |
| 00584 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
simulation; games; reading comprehension |
| 00647 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
childhood board game; also see UVa 11459 |
| 10363 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
check validity of Tic Tac Toe game; tricky; also available at Kattis - tictactoe2 |
| 10443 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
2D arrays manipulation; also available at Kattis - rockscissorspaper |
| 10813 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
follow the problem description |
| 10903 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
count wins and losses; output win average; also available at Kattis - rockpaperscissors |
| 11013 |
Fetching from uHunt |
1.4d, Game (Others), Harder |
check permutations of 5 cards to determine the best run; brute force the 6th card and replace one of your card with it |
| 00362 |
Fetching from uHunt |
1.4e, Real Life, Easier |
typical file download situation |
| 00637 |
Fetching from uHunt |
1.4e, Real Life, Easier |
application in printer driver software |
| 01586 |
Fetching from uHunt |
1.4e, Real Life, Easier |
LA 3900 - Seoul07; basic Chemistry |
| 10082 |
Fetching from uHunt |
1.4e, Real Life, Easier |
use 2D mapper array to simplify the problem; also available at Kattis - wertyu |
| 10554 |
Fetching from uHunt |
1.4e, Real Life, Easier |
are you concerned with your weights? |
| 11530 |
Fetching from uHunt |
1.4e, Real Life, Easier |
handphone users encounter this issue in the past |
| 11744 |
Fetching from uHunt |
1.4e, Real Life, Easier |
this is another topic on Computer Organization; this time on Digital Logic design |
| 11945 |
Fetching from uHunt |
1.4e, Real Life, Easier |
a bit of output formatting |
| 11984 |
Fetching from uHunt |
1.4e, Real Life, Easier |
F to C conversion and vice versa |
| 12195 |
Fetching from uHunt |
1.4e, Real Life, Easier |
count the number of correct measures |
| 12808 |
Fetching from uHunt |
1.4e, Real Life, Easier |
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 |
| 13151 |
Fetching from uHunt |
1.4e, Real Life, Easier |
marking programming exam; ad hoc; straightforward |
| 00161 |
Fetching from uHunt |
1.4f, Real Life, Medium |
this is a typical situation on the road |
| 00187 |
Fetching from uHunt |
1.4f, Real Life, Medium |
an accounting problem |
| 00447 |
Fetching from uHunt |
1.4f, Real Life, Medium |
life simulation model |
| 00457 |
Fetching from uHunt |
1.4f, Real Life, Medium |
simplified game of life simulation; similar idea with UVa 00447; explore the Internet for that term |
| 00857 |
Fetching from uHunt |
1.4f, Real Life, Medium |
MIDI; application in computer music |
| 10191 |
Fetching from uHunt |
1.4f, Real Life, Medium |
you may want to apply this to your own schedule |
| 10528 |
Fetching from uHunt |
1.4f, Real Life, Medium |
music knowledge in problem description |
| 10812 |
Fetching from uHunt |
1.4f, Real Life, Medium |
be careful with boundary cases! |
| 11736 |
Fetching from uHunt |
1.4f, Real Life, Medium |
this is a (simplified) introduction to Computer Organization on how computer stores data in memory |
| 11743 |
Fetching from uHunt |
1.4f, Real Life, Medium |
Luhn's algorithm to check credit card numbers; search the Internet to learn more |
| 12555 |
Fetching from uHunt |
1.4f, Real Life, Medium |
one of the first question asked when a new baby is born; requires a bit of input processing |
| 00139 |
Fetching from uHunt |
1.4g, Real Life, Harder |
calculate phone bill; string manipulation |
| 00145 |
Fetching from uHunt |
1.4g, Real Life, Harder |
similar to UVa 00139 |
| 00333 |
Fetching from uHunt |
1.4g, Real Life, Harder |
this problem has buggy test data with blank lines that potentially cause lots of Presentation Errors |
| 00346 |
Fetching from uHunt |
1.4g, Real Life, Harder |
musical chord; major/minor |
| 00403 |
Fetching from uHunt |
1.4g, Real Life, Harder |
emulation of printer driver; tedious |
| 00448 |
Fetching from uHunt |
1.4g, Real Life, Harder |
tedious hexadecimal to assembly language conversion |
| 00449 |
Fetching from uHunt |
1.4g, Real Life, Harder |
easier if you have a musical background |
| 00538 |
Fetching from uHunt |
1.4g, Real Life, Harder |
the problem's premise is quite true |
| 00706 |
Fetching from uHunt |
1.4g, Real Life, Harder |
like in old digital display |
| 01061 |
Fetching from uHunt |
1.4g, Real Life, Harder |
LA 3736 - WorldFinals Tokyo07; try all eight possible blood + Rh types with the information given |
| 01091 |
Fetching from uHunt |
1.4g, Real Life, Harder |
LA 4786 - WorldFinals Harbin10; tedious simulation and reading comprehension |
| 10415 |
Fetching from uHunt |
1.4g, Real Life, Harder |
about musical instruments; also available at Kattis - saxophone |
| 10659 |
Fetching from uHunt |
1.4g, Real Life, Harder |
typical presentation programs do this |
| 11223 |
Fetching from uHunt |
1.4g, Real Life, Harder |
tedious morse code conversion |
| 11279 |
Fetching from uHunt |
1.4g, Real Life, Harder |
an extension of UVa 11278 problem; it is interesting to compare QWERTY and DVORAK keyboard layout |
| 12342 |
Fetching from uHunt |
1.4g, Real Life, Harder |
tax computation can be tricky indeed |
| 12394 |
Fetching from uHunt |
1.4g, Real Life, Harder |
interesting problem with real life back story; be careful of various corner cases |
| 00579 |
Fetching from uHunt |
1.4h, Time, Easier |
be careful with corner cases |
| 00893 |
Fetching from uHunt |
1.4h, Time, Easier |
use Java GregorianCalendar; similar to UVa 11356 |
| 10683 |
Fetching from uHunt |
1.4h, Time, Easier |
simple clock system conversion |
| 11219 |
Fetching from uHunt |
1.4h, Time, Easier |
be careful with boundary cases! |
| 11356 |
Fetching from uHunt |
1.4h, Time, Easier |
very easy if you use Java GregorianCalendar |
| 11650 |
Fetching from uHunt |
1.4h, Time, Easier |
some mathematics required; similar to UVa 11677 |
| 11677 |
Fetching from uHunt |
1.4h, Time, Easier |
similar idea with UVa 11650 |
| 11958 |
Fetching from uHunt |
1.4h, Time, Easier |
be careful with 'past midnight' |
| 12019 |
Fetching from uHunt |
1.4h, Time, Easier |
Gregorian Calendar; get DAY_OF_WEEK |
| 12136 |
Fetching from uHunt |
1.4h, Time, Easier |
LA 4202 - Dhaka08; check time |
| 12148 |
Fetching from uHunt |
1.4h, 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 |
| 12531 |
Fetching from uHunt |
1.4h, Time, Easier |
angles between two clock hands |
| 13275 |
Fetching from uHunt |
1.4h, Time, Easier |
QY-Y (if not 29 Feb) or NumOfLeapYears(QY)-NumOfLeapYears(Y) otherwise |
| 00150 |
Fetching from uHunt |
1.4i, Time, Harder |
convert between Julian and Gregorian dates |
| 00158 |
Fetching from uHunt |
1.4i, Time, Harder |
a simulation of calendar manager; it requires sorting and a bit of string processing |
| 00170 |
Fetching from uHunt |
1.4i, Time, Harder |
simulation; time |
| 00300 |
Fetching from uHunt |
1.4i, Time, Harder |
ad hoc; time |
| 00602 |
Fetching from uHunt |
1.4i, Time, Harder |
Gregorian versus Julian calendar |
| 10070 |
Fetching from uHunt |
1.4i, Time, Harder |
more than ordinary leap years |
| 10339 |
Fetching from uHunt |
1.4i, Time, Harder |
find the formula |
| 10371 |
Fetching from uHunt |
1.4i, Time, Harder |
follow the description, tedious; also available at Kattis - timezones |
| 10942 |
Fetching from uHunt |
1.4i, 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 |
| 11947 |
Fetching from uHunt |
1.4i, Time, Harder |
easier with Java GregorianCalendar |
| 12439 |
Fetching from uHunt |
1.4i, Time, Harder |
inclusion-exclusion; lots of corner cases; be careful |
| 12822 |
Fetching from uHunt |
1.4i, Time, Harder |
convert hh:mm:ss to second to simplify the problem; then this is just a tedious simulation problem |
| 00144 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
simulation |
| 00214 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
just simulate the process; be careful with subtract (-); divide (/); and negate (@); tedious |
| 00335 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
simulation |
| 00349 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
simulation |
| 00556 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
simulation |
| 01721 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
LA 7162 - WorldFinals Marrakech15; tedious simulation problem; also available at Kattis - windows |
| 10028 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
tedious simulation with several corner cases |
| 10033 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
adhoc; simulation |
| 10134 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
must be very careful with details |
| 10281 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
distance = speed*time elapsed; also available at Kattis - averagespeed |
| 10850 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
gossip spread simulation |
| 11638 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
simulation; needs to use bitmask for parameter C |
| 12060 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
LA 3012 - Dhaka04; output format |
| 12085 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
LA 2189 - Dhaka06; watch out for PE |
| 12608 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
simulation with several corner cases |
| 12700 |
Fetching from uHunt |
1.4j, Time Waster, Easier |
just do as instructed |
| 00337 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
simulation; output related |
| 00381 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
simulation |
| 00405 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
simulation |
| 00603 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
simulation |
| 00618 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
tedious |
| 00830 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
very hard to get AC; one minor error = WA; not recommended |
| 00945 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
simulate the given cargo loading process |
| 10142 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
simulation |
| 10188 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
simulation |
| 10267 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
simulation |
| 10961 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
tedious simulation |
| 11140 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
ad hoc |
| 11717 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
tricky simulation |
| 12280 |
Fetching from uHunt |
1.4k, Time Waster, Harder |
a tedious problem |
| 00414 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
get the longest stretch of Bs |
| 00482 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
you may need to use a string tokenizer as the size of the array is not specified |
| 00591 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
sum all items; get the average; sum the total absolute differences of each item from the average divided by two |
| 10038 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
1D Boolean flags to check [1..n-1]; also available at Kattis - jollyjumpers |
| 10050 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
1D boolean flag |
| 11192 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
character array |
| 11496 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
store data in 1D array; count the peaks |
| 11608 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
use three arrays: created; required; available |
| 11875 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
get median of a sorted input |
| 12150 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
simple manipulation |
| 12356 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
similar to deletion in doubly linked lists but we can still use a 1D array for the underlying data structure |
| 12854 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
1D array of size 5; trivial |
| 12959 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
just go through the 1D array |
| 12996 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
we need 1D array to store the number of N mango types first |
| 13026 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
you have to store the N strings in an array first |
| 13181 |
Fetching from uHunt |
2.2a, 1D Array, Easier |
find the largest gap between two Xs; special corner cases at the two end points |
| 00230 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
string parsing; maintain sorted books by author names then by title; the input size is small; we do not need balanced BST |
| 00394 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
any n-dimensional array is stored in computer memory as a single dimensional array; follow the problem description |
| 00467 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
linear scan; 1D boolean flag |
| 00665 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
use 1D boolean flags; each =; <; or > tells us an information; check if there is only one candidate false coin left at the end |
| 00946 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
just 1D array manipulation; be careful with the special restriction |
| 10978 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
1D string array |
| 11093 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
linear scan; circular array; a bit challenging |
| 11222 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
use several 1D arrays |
| 11850 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
for each integer location from 0 to 1322; can Brenda reach (anywhere within 200 miles of) any charging stations? |
| 12662 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
1D array manipulation; brute force |
| 13048 |
Fetching from uHunt |
2.2b, 1D Array, Harder |
use 1D Boolean array; simulate |
| 00541 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
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 |
| 00585 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
recursive grammar check and output formatting |
| 10703 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
use 2D boolean array of size 500*500 |
| 10920 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
simulate the process |
| 11040 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
non trivial 2D array manipulation |
| 11349 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
use long long to avoid issues |
| 11581 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
simulate the process |
| 11835 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
do as asked |
| 12187 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
simulate the process |
| 12667 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
use both 1D and 2D arrays to store submission status |
| 12981 |
Fetching from uHunt |
2.2c, 2D Array, Easier |
small 2x2 matrix rotation |
| 00101 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
stack-like simulation; but we need to access the content of each stack too; so it is better to use 2D array |
| 00434 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
a kind of visibility problem in geometry; solvable with using 2D array manipulation |
| 00466 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
core functions: rotate and reflect |
| 00512 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
apply all rows/columns modifications in descending order; for each query; report the new position of the cell or report GONE |
| 00707 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
this requires 3D array; but as there is no such category; it is classified here |
| 10016 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
tedious |
| 10855 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
string array; 90 degrees clockwise rotation |
| 11360 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
do as asked |
| 12291 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
do as asked; a bit tedious |
| 12398 |
Fetching from uHunt |
2.2d, 2D Array, Harder |
simulate backwards; do not forget to mod 10 |
| 00400 |
Fetching from uHunt |
2.2e, Sorting, Easier |
this command is very frequently used in UNIX |
| 00855 |
Fetching from uHunt |
2.2e, Sorting, Easier |
sort; median |
| 10107 |
Fetching from uHunt |
2.2e, Sorting, Easier |
find median of a growing/dynamic list of integers; we can use multiple calls of nth_element in algorithm |
| 10880 |
Fetching from uHunt |
2.2e, Sorting, Easier |
use sort |
| 10905 |
Fetching from uHunt |
2.2e, Sorting, Easier |
modified comparison function; use sort |
| 11039 |
Fetching from uHunt |
2.2e, Sorting, Easier |
use sort then count different signs |
| 11588 |
Fetching from uHunt |
2.2e, Sorting, Easier |
sort simplifies the problem |
| 11777 |
Fetching from uHunt |
2.2e, Sorting, Easier |
sort simplifies the problem |
| 11824 |
Fetching from uHunt |
2.2e, Sorting, Easier |
sort simplifies the problem |
| 12071 |
Fetching from uHunt |
2.2e, Sorting, Easier |
reading comprehension; sort the input; compute something |
| 12541 |
Fetching from uHunt |
2.2e, Sorting, Easier |
LA 6148 - HatYai12; sort; youngest + oldest |
| 12709 |
Fetching from uHunt |
2.2e, Sorting, Easier |
LA 6650 - Dhaka13; although the problem has a complicated story; it has a very easy solution with sort routine |
| 12861 |
Fetching from uHunt |
2.2e, Sorting, Easier |
sort the timezones first and try adjacent pairings (two possibilities) |
| 13113 |
Fetching from uHunt |
2.2e, Sorting, Easier |
count the votes; sort; pick the top 2 |
| 00123 |
Fetching from uHunt |
2.2f, Sorting, Harder |
modified comparison function; use sort |
| 00450 |
Fetching from uHunt |
2.2f, Sorting, Harder |
tedious sorting problem |
| 00790 |
Fetching from uHunt |
2.2f, Sorting, Harder |
multi-fields sorting; use sort; similar to UVa 10258 |
| 01610 |
Fetching from uHunt |
2.2f, Sorting, Harder |
LA 6196 - MidAtlanticUSA12; median |
| 10194 |
Fetching from uHunt |
2.2f, Sorting, Harder |
multi-fields sorting; use sort |
| 10258 |
Fetching from uHunt |
2.2f, Sorting, Harder |
multi-fields sorting; use sort; similar to UVa 00790 |
| 10698 |
Fetching from uHunt |
2.2f, Sorting, Harder |
multi-fields sorting; use sort |
| 11300 |
Fetching from uHunt |
2.2f, Sorting, Harder |
use sort; involving the median |
| 11321 |
Fetching from uHunt |
2.2f, Sorting, Harder |
be careful with negative mod! |
| 12269 |
Fetching from uHunt |
2.2f, Sorting, Harder |
sort and check if Guido covers all land (end-to-end and side-to-side); also available at Kattis - lawnmower |
| 00594 |
Fetching from uHunt |
2.2g, Bit Manipulation |
manipulate bit string with bitset |
| 00700 |
Fetching from uHunt |
2.2g, Bit Manipulation |
can be solved with bitset |
| 01241 |
Fetching from uHunt |
2.2g, Bit Manipulation |
LA 4147 - Jakarta08; easy |
| 10264 |
Fetching from uHunt |
2.2g, Bit Manipulation |
heavy bitmask manipulation |
| 10469 |
Fetching from uHunt |
2.2g, Bit Manipulation |
super simple if you use xor |
| 11173 |
Fetching from uHunt |
2.2g, Bit Manipulation |
Divide and Conquer pattern or one liner bit manipulation |
| 11760 |
Fetching from uHunt |
2.2g, Bit Manipulation |
separate row col checks; use two bitsets |
| 11926 |
Fetching from uHunt |
2.2g, Bit Manipulation |
use 1M bitset to check if a slot is free |
| 11933 |
Fetching from uHunt |
2.2g, Bit Manipulation |
simple bit exercise |
| 12571 |
Fetching from uHunt |
2.2g, Bit Manipulation |
precalculate AND operations |
| 12720 |
Fetching from uHunt |
2.2g, Bit Manipulation |
observe the pattern in this binary to decimal conversion variant; involves modulo arithmetic |
| 00127 |
Fetching from uHunt |
2.2h, Stack |
shuffling stack |
| 00514 |
Fetching from uHunt |
2.2h, Stack |
use stack to simulate the process |
| 00732 |
Fetching from uHunt |
2.2h, Stack |
use stack to simulate the process |
| 01062 |
Fetching from uHunt |
2.2h, Stack |
LA 3752 - WorldFinals Tokyo07; simulation with stack; maximum answer is 26 stacks; O(n) solution exists |
| 10858 |
Fetching from uHunt |
2.2h, Stack |
use stack |
| 13055 |
Fetching from uHunt |
2.2h, Stack |
nice problem about stack |
| 00246 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
card simulation with queue and deque |
| 00540 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
modified queue |
| 10172 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
use both queue and stack |
| 10901 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
simulation with queue; also available at Kattis - ferryloading3 |
| 10935 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
simulation with queue |
| 11034 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
simulation with queue; also available at Kattis - ferryloading4 |
| 11797 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
simulation with 5 queues |
| 11988 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
rare linked list problem |
| 12100 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
simulation with queue |
| 12108 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
simulation with N queues |
| 12207 |
Fetching from uHunt |
2.2i, List/Queue/Deque |
use both queue and deque |
| 01203 |
Fetching from uHunt |
2.3a, Priority Queue |
LA 3135 - Beijing04; use priority_queue |
| 11995 |
Fetching from uHunt |
2.3a, Priority Queue |
stack; queue; and priority_queue |
| 11997 |
Fetching from uHunt |
2.3a, Priority Queue |
sort the lists; merge two sorted lists using priority_queue to keep the K-th smallest sum every time |
| 13190 |
Fetching from uHunt |
2.3a, Priority Queue |
similar to UVa 01203; use PQ; use drug numbering id as tie-breaker |
| 00499 |
Fetching from uHunt |
2.3b, Direct Addressing Table |
use 1D array for frequency counting |
| 00755 |
Fetching from uHunt |
2.3b, Direct Addressing Table |
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 |
| 00895 |
Fetching from uHunt |
2.3b, Direct Addressing Table |
get the letter frequency of each word; compare with puzzle line |
| 01368 |
Fetching from uHunt |
2.3b, Direct Addressing Table |
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 |
| 10062 |
Fetching from uHunt |
2.3b, Direct Addressing Table |
ASCII character frequency count |
| 10260 |
Fetching from uHunt |
2.3b, Direct Addressing Table |
Direct Addressing Table for soundex code mapping |
| 11340 |
Fetching from uHunt |
2.3b, Direct Addressing Table |
Direct Addressing Table |
| 12650 |
Fetching from uHunt |
2.3b, Direct Addressing Table |
use 1D Boolean array for each person |
| 10887 |
Fetching from uHunt |
2.3c, Hash Table (set) |
Use O(M*N*log(MN)*10) algorithm; concatenate all pairs of strings; put them in a set; report set size |
| 11849 |
Fetching from uHunt |
2.3c, Hash Table (set) |
unordered_set is faster than set here; or use modified merge as the input is sorted; also available at Kattis - cd |
| 12049 |
Fetching from uHunt |
2.3c, Hash Table (set) |
unordered_multiset manipulation |
| 13148 |
Fetching from uHunt |
2.3c, Hash Table (set) |
we can store all precomputed answers - which are given - into unordered_set |
| 00417 |
Fetching from uHunt |
2.3d, Hash Table (map) |
generate all words; add to map for auto sorting |
| 00484 |
Fetching from uHunt |
2.3d, Hash Table (map) |
maintain frequency with map |
| 00860 |
Fetching from uHunt |
2.3d, Hash Table (map) |
frequency counting |
| 10132 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use map; brute force |
| 10145 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use map and set |
| 10282 |
Fetching from uHunt |
2.3d, Hash Table (map) |
a pure dictionary problem; use unordered_map; also available at Kattis - babelfish |
| 10295 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use unordered_map to deal with Hay Points dictionary; also available at Kattis - haypoints |
| 10686 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use map to manage the data |
| 11286 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use unordered_map to count frequencies of the sorted permutations of 5 ids; also available at Kattis - conformity |
| 11348 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use map and set to check uniqueness |
| 11572 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use unordered_map to record the occurrence index of a certain snowflake size; use this to determine the answer in linear time; also available at Kattis - snowflakes |
| 11629 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use map |
| 11860 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use set and map; linear scan |
| 11917 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use map |
| 12592 |
Fetching from uHunt |
2.3d, Hash Table (map) |
use map; string to string |
| 00501 |
Fetching from uHunt |
2.3e, Balanced BST (set) |
use multiset with efficient iterator manipulation |
| 00978 |
Fetching from uHunt |
2.3e, Balanced BST (set) |
simulation; use multiset |
| 10815 |
Fetching from uHunt |
2.3e, Balanced BST (set) |
use set and string |
| 11062 |
Fetching from uHunt |
2.3e, Balanced BST (set) |
similar to UVa 10815 with twists |
| 11136 |
Fetching from uHunt |
2.3e, Balanced BST (set) |
use multiset |
| 13037 |
Fetching from uHunt |
2.3e, Balanced BST (set) |
we can use set or a sorted array |
| 00939 |
Fetching from uHunt |
2.3f, Balanced BST (map) |
map child name to his/her gene and parents' names |
| 10138 |
Fetching from uHunt |
2.3f, Balanced BST (map) |
map plates to bills; entrance time; and position |
| 10226 |
Fetching from uHunt |
2.3f, Balanced BST (map) |
use map; sorted output; also available at Kattis - hardwoodspecies |
| 11239 |
Fetching from uHunt |
2.3f, Balanced BST (map) |
use map and set to check previous strings; order needed; also available at Kattis - opensource |
| 11308 |
Fetching from uHunt |
2.3f, Balanced BST (map) |
use map and set to help manage the data |
| 12504 |
Fetching from uHunt |
2.3f, Balanced BST (map) |
use map; string to string |
| 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 |
| 10895 |
Fetching from uHunt |
2.4a, Graph Data Structures |
transpose adjacency list |
| 10928 |
Fetching from uHunt |
2.4a, Graph Data Structures |
counting out-degrees |
| 11550 |
Fetching from uHunt |
2.4a, Graph Data Structures |
graph representation; incidence matrix |
| 11991 |
Fetching from uHunt |
2.4a, Graph Data Structures |
Adjacency List |
| 00793 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
trivial; application of disjoint sets |
| 01197 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
LA 2817 - Kaohsiung03; Connected Components |
| 01329 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
LA 3027 - SouthEasternEurope04; interesting UFDS variant; modify the union and find routine |
| 10158 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
advanced usage of disjoint sets with a nice twist; memorize list of enemies |
| 10227 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
merge two disjoint sets if they are consistent; also available at Kattis - forests |
| 10507 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
disjoint sets simplifies this problem |
| 10583 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
count disjoint sets after all unions |
| 10608 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
find the set with the largest element |
| 10685 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
find the set with the largest element |
| 11503 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
maintain set attribute (size) in rep item; also available at Kattis - virtualfriends |
| 11690 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
check if total money from each member is 0 |
| 11987 |
Fetching from uHunt |
2.4b, Union-Find Disjoint Sets |
maintain set attribute (size and sum) in rep item; new operation: move; key idea: do not destroy the parent array structure; also available at Kattis - almostunionfind |
| 00297 |
Fetching from uHunt |
2.4c, Tree-related DS |
simple quadtree problem |
| 01232 |
Fetching from uHunt |
2.4c, Tree-related DS |
LA 4108 - Singapore07; we have to use a Segment Tree; note that this problem is not about RSQ/RMQ |
| 01513 |
Fetching from uHunt |
2.4c, Tree-related DS |
LA 5902 - NorthWesternEurope11; not stack but dynamic RSQ problem; use DAT (for mapping) and Fenwick Tree (for RSQ); also available at Kattis - moviecollection |
| 11235 |
Fetching from uHunt |
2.4c, Tree-related DS |
range maximum query |
| 11297 |
Fetching from uHunt |
2.4c, Tree-related DS |
Quad Tree with updates or use 2D segment tree |
| 11350 |
Fetching from uHunt |
2.4c, Tree-related DS |
simple tree data structure question |
| 11402 |
Fetching from uHunt |
2.4c, Tree-related DS |
Segment Tree with lazy updates |
| 11423 |
Fetching from uHunt |
2.4c, Tree-related DS |
clever usage of Fenwick Tree and large array; important hint: look at the constraints carefully |
| 12086 |
Fetching from uHunt |
2.4c, Tree-related DS |
LA 2191 - Dhaka06; pure dynamic RSQ problem; solvable with Fenwick Tree or Segment Tree |
| 12299 |
Fetching from uHunt |
2.4c, Tree-related DS |
Segment Tree with a few point (not range) updates; RMQs |
| 12532 |
Fetching from uHunt |
2.4c, Tree-related DS |
clever usage of Fenwick/Segment Tree |
| 00165 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
requires some DP too; can be pre-calculated |
| 00167 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
8-queens chess problem |
| 00256 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
brute force; math; pre-calculate-able |
| 00347 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
simulate the process; pre-calculate-able |
| 00750 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
classic backtracking problem; only 92 possible 8-queens positions |
| 00861 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
backtracking with pruning as in 8-queens recursive backtracking solution; then pre-calculate the results |
| 10128 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
backtracking with pruning; try all $N!$ permutations that satisfy the requirement; 13! will TLE; pre-calculate the results |
| 10177 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
2/3/4 nested loops; precalculate |
| 10276 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
insert a number one by one |
| 11085 |
Fetching from uHunt |
3.2a, Pre-calculate-able |
see UVa 750; pre-calculation |
| 00105 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
height map; sweep left-right |
| 00592 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
key idea: there are only 3^5*2 possible states: the status of each person and whether it is day or night |
| 00617 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
try all integer speeds from 30 to 60 mph |
| 01260 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
LA 4843 - Daejeon10; check all |
| 01588 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
LA 3712 - NorthEasternEurope06; good iterative brute force problem; beware of corner cases |
| 10041 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
try all possible locations |
| 10487 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
sort and then do O(n^2) pairings; also available at Kattis - closestsums |
| 10570 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
brute force all possible final configurations (ascending/descending) and see which one requires the smallest number of exchanges |
| 10670 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
2 nested loops; with sorting; also available at Kattis - reduction |
| 10730 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
2 nested loops with pruning can still pass the time limit; compare this with UVa 11129; also available at Kattis - antiarithmetic |
| 11242 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
brute force plus sorting; also available at Kattis - tourdefrance |
| 12205 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
brute force; check intervals; also available at Kattis - telephones |
| 12488 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
2 nested loops; simulate overtaking process |
| 12583 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
2 nested loops; be careful of overcounting |
| 13018 |
Fetching from uHunt |
3.2b, Iterative (Two Nested Loops) |
2 dices, small range; 2 nested loops |
| 00154 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops |
| 00441 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
6 nested loops; easy |
| 00626 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops |
| 00703 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops |
| 00735 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops; then count |
| 10102 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
4 nested loops will do; we do not need BFS; get max of minimum Manhattan distance from a 1 to a 3 |
| 10662 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops |
| 11059 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops; input is small |
| 12498 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops |
| 12515 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops |
| 12801 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
3 nested loops; still possible to be optimized further |
| 12844 |
Fetching from uHunt |
3.2c, Three+ Nested Loops, Easier |
5 nested loops; scaled down version of UVa 10202; do observations first |
| 00253 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
try all; similar problem in UVa 11959 |
| 00296 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
try all 10000 possible codes; 4 nested loops; use similar solution as Master-Mind game |
| 00386 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
4 nested loops with pruning |
| 10360 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
also solvable using 1024^2 DP max sum |
| 10365 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
use 3 nested loops with pruning |
| 10483 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
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 |
| 10502 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
6 nested loops; rectangle |
| 10660 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
7 nested loops; Manhattan distance |
| 10973 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
3 nested loops with pruning |
| 11108 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
try all 2^5 = 32 values with pruning; also available at Kattis - tautology |
| 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 |
| 11342 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
pre-calculate squared values from 0^2 to 224^2; use 3 nested loops to generate the answers; use map to avoid duplicates |
| 11548 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
4 nested loops; string; pruning |
| 11565 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
3 nested loops with pruning |
| 11804 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
5 nested loops |
| 11959 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
try all possible dice positions; compare with the 2nd one |
| 11975 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
3 nested loops; simulate the game as asked |
| 12337 |
Fetching from uHunt |
3.2d, Three+ Nested Loops, Harder |
try all possible row x col size and test if it is beautiful |
| 00140 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
max n is just 8; use next_permutation; the algorithm inside next_permutation is iterative |
| 00146 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
use next_permutation |
| 00234 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
LA 5173 - WorldFinals Phoenix94; use next_permutation; simulation |
| 00418 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
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 |
| 01064 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
LA 3808 - WorldFinals Tokyo07; permutation of up to 5 messages; simulation; mind the word 'consecutive' |
| 01209 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
LA 3173 - Manila06; STL next and prev_permutation |
| 10997 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
not an easy problem; require analysis to realize that the search space is small; also available at Kattis - medals |
| 11412 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
next_permutation; find one possibility from 6! |
| 11742 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
try all permutations |
| 12249 |
Fetching from uHunt |
3.2e, Iterative (Permutation) |
LA 4994 - KualaLumpur10; try all permutations; a bit of string matching |
| 00435 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
only 2^20 possible coalition combinations |
| 00517 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
convert (a; b) to (0; 1) first so that we only work with integers; there can only be 2^16 possibilities although s can be gigantic; stop upon encountering a cycle |
| 00639 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
generate 2^(4x4) = 2^16 combinations and prune |
| 01047 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
LA 3278 - WorldFinals Shanghai05; try all 2^n subsets of towers to be taken; use inclusion-exclusion principle |
| 11205 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
try all 2^15 bitmask |
| 11659 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
try all 2^20 bitmask and check |
| 12346 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
LA 5723 - Phuket11; try all 2^n combinations; pick the best one |
| 12348 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
LA 5725 - Phuket11; try all 2^n combinations |
| 12406 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
try all 2^p possible bitmasks; change '0's to '2's |
| 12694 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
LA 6606 - Phuket13; it is safest to just brute force all 2^20 possibilities; greedy solution should be possible too |
| 13103 |
Fetching from uHunt |
3.2f, Iterative (Combination) |
try all 2^k combinations; swapping a 0-bit with another 0-bit or 1-bit with another 1-bit has no effect |
| 00102 |
Fetching from uHunt |
3.2g, Try All Possible Answers |
try all 6 combinations of possible answers |
| 00188 |
Fetching from uHunt |
3.2g, Try All Possible Answers |
3 nested loops; keep trying until an answer is found |
| 00725 |
Fetching from uHunt |
3.2g, Try All Possible Answers |
try all possible answers |
| 10908 |
Fetching from uHunt |
3.2g, Try All Possible Answers |
4 nested loops; try all possible odd square lengths |
| 00380 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
simple backtracking; but we have to work with strings |
| 00471 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
somewhat similar to UVa 00725 |
| 00487 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
use map to store the generated words |
| 00524 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
involving prime number |
| 00571 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
solution can be suboptimal; add flag to avoid cycling |
| 00598 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
print all solutions with backtracking |
| 00628 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
backtracking; follow the rules in description |
| 00677 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
print all solutions with backtracking |
| 00729 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
generate all possible bit strings |
| 00868 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
backtracking from row 1 to N; 4 choices per step; some constraints |
| 10344 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
5 operands + 3 operators |
| 10452 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
at each pos; Indy can go forth/left/right; try all |
| 10503 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
max 13 spaces only |
| 10576 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
generate all; prune; take max |
| 10776 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
recursive backtracking |
| 10950 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
sort the input; run backtracking; the output should be sorted; only display the first 100 sorted output |
| 11201 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
backtracking involving strings |
| 11961 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
up to 4^10 possible DNA strings; mutation power is at most K ≤ 5 so the search space is much smaller; sort the output; remove duplicates |
| 12840 |
Fetching from uHunt |
3.2h, Backtracking (Easier) |
simple backtracking |
| 00129 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
backtracking; string processing check; a bit of output formatting |
| 00208 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
LA 5147 - WorldFinals SanAntonio91; backtracking with some pruning |
| 00222 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
LA 5161 - WorldFinals Indianapolis93; cannot use DP 'tank' is floating-point; use backtracking |
| 00301 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
2^22 with pruning is possible |
| 00307 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
sort the sticks in descending length; group similar lengths; brute force the number of sticks; backtracking to check feasibility |
| 00331 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
n <= 5... |
| 00416 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
backtrack; try all |
| 00433 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
similar to UVa 416 |
| 00565 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
backtracking with lots of pruning |
| 01262 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
LA 4845 - Daejeon10; sort grid columns; process common passwords in lexicographic order; skip two similar passwords |
| 10001 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
the upperbound of 2^32 is scary but with efficient pruning; we can pass the time limit as the test case is not extreme |
| 10063 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
do as asked |
| 10094 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
this problem is like the n-queens chess problem; but must find/use the pattern! |
| 10460 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
similar nature with UVa 10063 |
| 10475 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
generate and prune; try all |
| 10506 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
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 |
| 10582 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
simplify complex input first; then backtrack |
| 11052 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
the worst case time complexity of 2^1000 looks scary but the search space is apparently not that big |
| 11753 |
Fetching from uHunt |
3.2i, Backtracking (Harder) |
the state is probably too big if we use DP; but we can pass the time limit with just backtracking |
| 00679 |
Fetching from uHunt |
3.3a, Binary Search |
binary search; bit manipulation solutions exist |
| 00957 |
Fetching from uHunt |
3.3a, Binary Search |
complete search binary search: upper_bound |
| 10057 |
Fetching from uHunt |
3.3a, Binary Search |
involves the median; use STL sort; upper_bound; lower_bound and some checks |
| 10077 |
Fetching from uHunt |
3.3a, Binary Search |
binary search |
| 10474 |
Fetching from uHunt |
3.3a, Binary Search |
simple: use sort and then lower_bound |
| 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 |
| 10611 |
Fetching from uHunt |
3.3a, Binary Search |
binary search |
| 10706 |
Fetching from uHunt |
3.3a, Binary Search |
binary search some mathematical insights |
| 10742 |
Fetching from uHunt |
3.3a, Binary Search |
use sieve; binary search |
| 11057 |
Fetching from uHunt |
3.3a, Binary Search |
sort; target pair problem |
| 11621 |
Fetching from uHunt |
3.3a, Binary Search |
generate numbers with factor 2 and/or 3; sort; upper_bound |
| 11876 |
Fetching from uHunt |
3.3a, Binary Search |
[lower|upper]_bound on sorted sequence N |
| 12192 |
Fetching from uHunt |
3.3a, Binary Search |
input array is specially sorted; lower_bound |
| 12965 |
Fetching from uHunt |
3.3a, Binary Search |
sort producer/consumer prices; the answer is one of the prices mentioned; use binary searches to count the answer |
| 01753 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
LA 8043 - WorldFinals RapidCity17; BSTA + Physics; also available at Kattis - speed |
| 10341 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
bisection method; for alternative solutions; see http://www.algorithmist.com/index.php/UVa_10341 |
| 11413 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
BSTA + simulation |
| 11627 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
binary search the answer + Physics simulation; also available at Kattis - slalom2 |
| 11881 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
bisection method |
| 11935 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
BSTA + simulation |
| 12032 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
BSTA + simulation |
| 12190 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
BSTA + algebra |
| 12791 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
BSTA + math formula to check if the leader pilot can overtake the backmarker pilot at that lap |
| 13142 |
Fetching from uHunt |
3.3b, Bisection and BSTA (Easier) |
BSTA + Physics simulation |
| 00183 |
Fetching from uHunt |
3.3c, Ternary Search and Others |
simple exercise of DnC |
| 00608 |
Fetching from uHunt |
3.3c, Ternary Search and Others |
classical problem; after each weighing; we can halve the search space |
| 01738 |
Fetching from uHunt |
3.3c, Ternary Search and Others |
LA 7578 - WorldFinals Phuket16; a problem about BST insertion+tree equality check; we do not actually use set here; also available at Kattis - ceiling |
| 10385 |
Fetching from uHunt |
3.3c, Ternary Search and Others |
the function is unimodal; ternary search |
| 11147 |
Fetching from uHunt |
3.3c, Ternary Search and Others |
implement the given recursive DnC |
| 11701 |
Fetching from uHunt |
3.3c, Ternary Search and Others |
a kind of ternary search |
| 12893 |
Fetching from uHunt |
3.3c, Ternary Search and Others |
convert the given code into recursive DnC |
| 00410 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
load balancing |
| 01193 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
LA 2519 - Beijing02; interval covering |
| 10020 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
interval covering |
| 10249 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
greedy; sorting |
| 10382 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
interval covering; also available at Kattis - grass |
| 11264 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
coin change variant |
| 11292 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
sort; greedy matching; also available at Kattis - loowater |
| 11389 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
load balancing |
| 12210 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
greedy; sorting |
| 12321 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
interval covering |
| 12405 |
Fetching from uHunt |
3.4a, Greedy (Classical) |
simpler interval covering problem |
| 10763 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
| 10785 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
| 11269 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
| 11369 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
| 11729 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
| 11900 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
| 12485 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
| 13031 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
| 13109 |
Fetching from uHunt |
3.4b, Involving Sorting, Easier |
greedy; sorting |
| 10026 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
greedy; sorting |
| 10037 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
greedy; sorting |
| 11100 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
greedy; sorting; also available at Kattis - trip2007 |
| 11103 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
greedy; sorting; also available at Kattis - wffnproof |
| 12673 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
LA 6530 - LatinAmerica13; greedy; sorting |
| 12834 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
greedy; sorting |
| 13054 |
Fetching from uHunt |
3.4c, Involving Sorting, Harder |
greedy; sorting |
| 01153 |
Fetching from uHunt |
3.4d, Involving Priority Queue |
greedy; priority queue |
| 10954 |
Fetching from uHunt |
3.4d, Involving Priority Queue |
greedy; priority queue |
| 12390 |
Fetching from uHunt |
3.4d, Involving Priority Queue |
greedy; priority queue |
| 13177 |
Fetching from uHunt |
3.4d, Involving Priority Queue |
greedy; priority queue |
| 10152 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 10340 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 10440 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 10602 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 10656 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 10672 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy; also available at Kattis - marblestree |
| 10700 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 10714 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy; also available at Kattis - ants |
| 11054 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 11520 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 11532 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 12482 |
Fetching from uHunt |
3.4e, Non Classical, Easier |
greedy |
| 00311 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 00668 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 10718 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 10821 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 10982 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 11157 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 11230 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 11240 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 11330 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 11335 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 11491 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 11567 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 11583 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 11890 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 12124 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 12516 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 13082 |
Fetching from uHunt |
3.4f, Non Classical, Harder |
greedy |
| 00108 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
max 2D range sum |
| 00507 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
standard problem |
| 00787 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
max 1D range product; be careful with 0; use Java BigInteger |
| 00836 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
convert '0' to -INF |
| 00983 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
max 2D range sum; get submatrix |
| 01105 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
LA 5132 - WorldFinals Orlando11; more advanced 2D Range Sum Queries |
| 10074 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
standard problem |
| 10667 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
standard problem |
| 10684 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
standard; Kadane's algorithm |
| 10755 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
max 2D range sum in 2 of the 3 dimensions; max 1D range sum with Kadane's algorithm on the 3rd dimension |
| 10827 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
copy n*n matrix into n*2n matrix; then this problem becomes a standard max 2D range sum problem again |
| 11951 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
use long long; max 2D range sum; prune the search space whenever possible |
| 12640 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
standard; Kadane's algorithm |
| 13095 |
Fetching from uHunt |
3.5a, Max 1D/2D Range Sum |
create 10 range sum queries; you don't need Fenwick Tree actually |
| 00111 |
Fetching from uHunt |
3.5b, LIS |
be careful of the ranking system |
| 00231 |
Fetching from uHunt |
3.5b, LIS |
straightforward |
| 00437 |
Fetching from uHunt |
3.5b, LIS |
can be modeled as LIS |
| 00481 |
Fetching from uHunt |
3.5b, LIS |
O(n log k) LIS+solution |
| 00497 |
Fetching from uHunt |
3.5b, LIS |
solution must be printed |
| 01196 |
Fetching from uHunt |
3.5b, LIS |
LA 2815 - Kaohsiung03; sort all the blocks in increasing L[i]; then we get the classical LIS problem |
| 10131 |
Fetching from uHunt |
3.5b, LIS |
sort elephants based on decreasing IQ; LIS on increasing weight |
| 10154 |
Fetching from uHunt |
3.5b, LIS |
LIS variant |
| 10534 |
Fetching from uHunt |
3.5b, LIS |
must use O(n log k) LIS twice |
| 11456 |
Fetching from uHunt |
3.5b, LIS |
max(LIS(i)+LDS(i)-1), ∀i ∈ [0...n-1]; also available at Kattis - trainsorting |
| 11790 |
Fetching from uHunt |
3.5b, LIS |
combination of LIS LDS; weighted |
| 00431 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
classic 0-1 Knapsack Problem; output any optimal solution as there is a special checker for this problem |
| 00562 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
use a one dimensional table |
| 00990 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
print the solution |
| 01213 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
LA 3619 - Yokohama06; extension of 0-1 KNAPSACK; s: (id, remN, remK) instead of s: (id, remN) |
| 10130 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
very basic 0-1 KNAPSACK problem |
| 10261 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
s: (current_car; left; right) |
| 10616 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
input can be -ve; use long long |
| 10664 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
Subset Sum |
| 10690 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
DP Subset Sum with negative offset technique; with addition of simple math |
| 10819 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
0-1 knapsack with 'credit card' twist |
| 11003 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
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? |
| 11341 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
s: (id; h_learned; h_left); t: learn module 'id' by 1 hour or skip it |
| 11566 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
KNAPSACK variant: double each dim sum; add one parameter to see if we have bought too many dishes |
| 11658 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
s: (id; share); t: form/ignore coalition with id |
| 11832 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
interesting DP; s: (id; val); use offset to handle negative numbers; t: plus or minus; print solution |
| 12621 |
Fetching from uHunt |
3.5c, 0-1 KNAPSACK |
DP Subset Sum; simplify the multiple of 10 |
| 00147 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
similar to UVa 357 and 674 |
| 00166 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
two coin change variants in one problem |
| 00242 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
LA 5181 - WorldFinals Nashville95; Complete Search + DP Coin-Change |
| 00357 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
similar to UVa 147 and 674 |
| 00674 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
basic coin change problem |
| 10313 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
modified coin change and DP 1D range sum |
| 10448 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
after dealing with traversal on tree; you can reduce the original problem into coin change; not trivial |
| 11137 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
use long long |
| 11259 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
part of the problem is DP COIN-CHANGE with restricted number of coins per type; inclusion-exclusion |
| 11517 |
Fetching from uHunt |
3.5d, COIN-CHANGE |
a variation to the coin change problem; also available at Kattis - exactchange2 |
| 00216 |
Fetching from uHunt |
3.5e, TSP |
LA 5155 - WorldFinals KansasCity92; DP TSP problem; but still solvable with backtracking |
| 01281 |
Fetching from uHunt |
3.5e, TSP |
LA 6028 - WorldFinals Warsaw12; DP TSP variant; also available at Kattis - bustour |
| 10496 |
Fetching from uHunt |
3.5e, TSP |
DP or recursive backtracking with sufficient pruning; also available at Kattis - beepers |
| 11795 |
Fetching from uHunt |
3.5e, TSP |
DP TSP variant; counting paths on DAG; DP+bitmask; let Mega Buster owned by a dummy 'Robot 0' |
| 12841 |
Fetching from uHunt |
3.5e, TSP |
simply find and print the lexicographically smallest Hamiltonian path; use DP-TSP technique |
| 00116 |
Fetching from uHunt |
3.5f, DP level 1 |
similar to UVa 10337 |
| 00196 |
Fetching from uHunt |
3.5f, DP level 1 |
3.5g |
| 00215 |
Fetching from uHunt |
3.5f, DP level 1 |
3.5g |
| 01261 |
Fetching from uHunt |
3.5f, DP level 1 |
LA 4844 - Daejeon10; a simple backtracking problem; but we use a setÿto prevent the same state (a substring) from being checked twice |
| 10003 |
Fetching from uHunt |
3.5f, DP level 1 |
s: (l; r) |
| 10036 |
Fetching from uHunt |
3.5f, DP level 1 |
must use offset technique as value can be negative |
| 10086 |
Fetching from uHunt |
3.5f, DP level 1 |
3.5g |
| 10337 |
Fetching from uHunt |
3.5f, DP level 1 |
DP; shortest paths on DAG |
| 10446 |
Fetching from uHunt |
3.5f, DP level 1 |
edit the given recursive function a bit; add memoization |
| 10520 |
Fetching from uHunt |
3.5f, DP level 1 |
just write the given formula as a top-down DP with memoization |
| 10721 |
Fetching from uHunt |
3.5f, DP level 1 |
s: (n; k); t: try all from 1 to m |
| 10910 |
Fetching from uHunt |
3.5f, DP level 1 |
two dimensional DP table |
| 10912 |
Fetching from uHunt |
3.5f, DP level 1 |
s: (len; last; sum); t: try next char |
| 10943 |
Fetching from uHunt |
3.5f, DP level 1 |
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 |
| 10980 |
Fetching from uHunt |
3.5f, DP level 1 |
simple DP |
| 11026 |
Fetching from uHunt |
3.5f, DP level 1 |
DP; similar idea with binomial theorem |
| 11407 |
Fetching from uHunt |
3.5f, DP level 1 |
can be memoized |
| 11420 |
Fetching from uHunt |
3.5f, DP level 1 |
s: (prev; id; numlck); lock/unlock this chest |
| 11450 |
Fetching from uHunt |
3.5f, DP level 1 |
standard DP |
| 11703 |
Fetching from uHunt |
3.5f, DP level 1 |
can be memoized |
| 12654 |
Fetching from uHunt |
3.5f, DP level 1 |
s: (hole); t: use patch T1 or patch T2 |
| 12951 |
Fetching from uHunt |
3.5f, DP level 1 |
s: (day, has_stock); t: ignore, buy (if does not have stock), or sell (if has stock) |
| 13141 |
Fetching from uHunt |
3.5f, DP level 1 |
s: (level, branch_previously); t: not branching if branch_previously or branching (one side) otherwise |
| 00662 |
Fetching from uHunt |
3.5g, DP level 2 |
s: (L; R; k); that denotes the minimum distance sum to cover restaurants at index [L..R] with k depots left |
| 10039 |
Fetching from uHunt |
3.5g, DP level 2 |
create the graph first; then apply DP; s: (city; curtime); t: try all feasible trains |
| 10069 |
Fetching from uHunt |
3.5g, DP level 2 |
use Java BigInteger |
| 10081 |
Fetching from uHunt |
3.5g, DP level 2 |
s: (i, j); #tight words of length i that end in digit j divided by #words: (k+1)^n; also available at Kattis - tight |
| 10120 |
Fetching from uHunt |
3.5g, DP level 2 |
DP; special case for N >= 49 |
| 10164 |
Fetching from uHunt |
3.5g, DP level 2 |
a bit number theory (modulo); backtracking; do memoization on DP s: (sum; taken) |
| 10239 |
Fetching from uHunt |
3.5g, DP level 2 |
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 |
| 10400 |
Fetching from uHunt |
3.5g, DP level 2 |
backtracking with clever pruning is sufficient |
| 10465 |
Fetching from uHunt |
3.5g, DP level 2 |
one dimensional DP table |
| 10651 |
Fetching from uHunt |
3.5g, DP level 2 |
small problem size; doable with backtracking |
| 11485 |
Fetching from uHunt |
3.5g, DP level 2 |
the problem description looks scary but the solution is not that complex |
| 11514 |
Fetching from uHunt |
3.5g, DP level 2 |
modified 0-1 Knapsack; Batman can use or skip a certain super power; check if the best configuration uses ≤ E calories; print 'yes' or 'no' accordingly |
| 11908 |
Fetching from uHunt |
3.5g, DP level 2 |
sort the advertisements based on starting level; ending level; and cost; DP 1 dimension |
| 12324 |
Fetching from uHunt |
3.5g, DP level 2 |
spheres > n are useless |
| 12862 |
Fetching from uHunt |
3.5g, DP level 2 |
1D DP to compute the path cost from every vertex that goes up to the mountain top; compute answer |
| 12955 |
Fetching from uHunt |
3.5g, DP level 2 |
there are only 8 eligible factorials under 100000; we can use DP; s: (i, sum); t: take/stay, take/move, don't take/move |
| 00260 |
Fetching from uHunt |
4.2a, Finding CCs |
6 neighbors per cell |
| 00280 |
Fetching from uHunt |
4.2a, Finding CCs |
reachability check; traverse the graph |
| 00459 |
Fetching from uHunt |
4.2a, Finding CCs |
also solvable with UFDS |
| 10687 |
Fetching from uHunt |
4.2a, Finding CCs |
build graph; geometry; reachability |
| 11518 |
Fetching from uHunt |
4.2a, Finding CCs |
unlike UVa 11504, we treat SCCs as CCs; also available at Kattis - dominoes2 |
| 11749 |
Fetching from uHunt |
4.2a, Finding CCs |
find the largest CC with highest average PPA; also solvable with UFDS |
| 11841 |
Fetching from uHunt |
4.2a, Finding CCs |
implicit graph; check if there is a CC from x = y = z = 0 to say 'Benny wins' |
| 11902 |
Fetching from uHunt |
4.2a, Finding CCs |
disable vertex one by one; check if the reachability from vertex 0 changes |
| 11906 |
Fetching from uHunt |
4.2a, Finding CCs |
DFS/BFS for reachability; several tricky cases; be careful when M = 0; N = 0; or M = N |
| 00352 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
count number of CCs; see UVa 00572 |
| 00469 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
count size of a CC |
| 00572 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
count number of CCs |
| 00657 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
there are three colors here; non-standard but still relatively easy floodfill problem |
| 00722 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
count the size of CCs |
| 00871 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
find the largest CC size |
| 10336 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
count and rank CCs with similar color |
| 11244 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
count number of CCs |
| 11470 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
you can do flood fill layer by layer; however; there is other way to solve this problem; e.g. by finding the patterns |
| 11561 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
flood fill with extra blocking constraint; also available at Kattis - gold |
| 11953 |
Fetching from uHunt |
4.2b, Flood Fill, Easier |
interesting twist of flood fill problem |
| 00601 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
floodfill is one of the component |
| 00705 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
build the implicit graph first |
| 00758 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
floodfill |
| 00776 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
label CCs with indices; format output |
| 00782 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
replace spaces with hexes in the grid; similar to UVa 784 and 785 |
| 00784 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
similar to UVa 782 and 785 |
| 00785 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
similar to UVa 782 and 784 |
| 00852 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
interesting board game 'Go' |
| 01103 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
LA 5130 - WorldFinals Orlando11; major hint: each hieroglyph has unique number of white CCs |
| 10592 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
floodfill ; two layers |
| 10707 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
check graph isomorphism; a tedious problem; involving connected components |
| 10946 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
find CCs and rank them by their size |
| 11094 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
tricky flood fill; scrolling |
| 11110 |
Fetching from uHunt |
4.2c, Flood Fill, Harder |
flood fill satisfy the constraints given |
| 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 |
| 00124 |
Fetching from uHunt |
4.2d, Topological Sort |
use backtracking to generate valid toposorts |
| 00200 |
Fetching from uHunt |
4.2d, Topological Sort |
toposort |
| 00872 |
Fetching from uHunt |
4.2d, Topological Sort |
similar to UVa 00124; use backtracking |
| 10305 |
Fetching from uHunt |
4.2d, Topological Sort |
simply run toposort algorithm |
| 11060 |
Fetching from uHunt |
4.2d, Topological Sort |
Kahn's algorithm---modified BFS toposort |
| 11686 |
Fetching from uHunt |
4.2d, Topological Sort |
cycle check + toposort if DAG; also available at Kattis - pickupsticks |
| 00840 |
Fetching from uHunt |
4.2e, Graph Properties Check |
a simple problem to detect cycle in a graph; however the output format is not clearly specified |
| 10004 |
Fetching from uHunt |
4.2e, Graph Properties Check |
bipartite graph check |
| 10116 |
Fetching from uHunt |
4.2e, Graph Properties Check |
traversal on implicit graph; cycle check |
| 10505 |
Fetching from uHunt |
4.2e, Graph Properties Check |
bipartite; take max(left; right) |
| 10510 |
Fetching from uHunt |
4.2e, Graph Properties Check |
use DFS to identify forward/cross edges; involving Strongly Connected graph |
| 11080 |
Fetching from uHunt |
4.2e, Graph Properties Check |
bipartite graph check; tricky cases |
| 11396 |
Fetching from uHunt |
4.2e, Graph Properties Check |
it is just a bipartite graph check |
| 00315 |
Fetching from uHunt |
4.2f, Cut Vertices/Bridges |
finding articulation points |
| 00610 |
Fetching from uHunt |
4.2f, Cut Vertices/Bridges |
finding bridges |
| 00796 |
Fetching from uHunt |
4.2f, Cut Vertices/Bridges |
finding bridges |
| 10199 |
Fetching from uHunt |
4.2f, Cut Vertices/Bridges |
finding articulation points |
| 10765 |
Fetching from uHunt |
4.2f, Cut Vertices/Bridges |
finding articulation points |
| 12363 |
Fetching from uHunt |
4.2f, Cut Vertices/Bridges |
LA 5796 - Latin America; transform input to graph of its bridges; see if b is reachable from a with only the bridges |
| 12783 |
Fetching from uHunt |
4.2f, Cut Vertices/Bridges |
finding bridges |
| 00247 |
Fetching from uHunt |
4.2g, Finding SCCs |
SCC + printing solution |
| 01229 |
Fetching from uHunt |
4.2g, Finding SCCs |
LA 4099 - Iran07; identify the SCC of the graph; these vertices and the vertices that have path towards them are the answers of the question |
| 10731 |
Fetching from uHunt |
4.2g, Finding SCCs |
SCC + printing solution; also available at Kattis - test2 |
| 11504 |
Fetching from uHunt |
4.2g, Finding SCCs |
count the number of SCCs without incoming edge from a vertex outside that SCC; also available at Kattis - dominos |
| 11709 |
Fetching from uHunt |
4.2g, Finding SCCs |
find the number of SCCs |
| 11770 |
Fetching from uHunt |
4.2g, Finding SCCs |
similar to UVa 11504 |
| 11838 |
Fetching from uHunt |
4.2g, Finding SCCs |
see if input graph is an SCC |
| 00118 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
traversal on implicit graph |
| 00168 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
Adjacency Matrix; parsing; traversal |
| 00173 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
non classic graph traversal variant; use bitmask to record vertices visited by Paskill and Lisper as they move through the graph |
| 00318 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
graph traversal; be careful of corner cases |
| 00614 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
traversal on implicit graph |
| 00824 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
traversal on implicit graph |
| 10113 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
just graph traversal; but uses fraction and GCD |
| 10377 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
traversal on implicit graph |
| 11831 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
traversal on implicit graph |
| 12376 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
simulated greedy traversal on DAG |
| 12442 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
modified DFS; special graph |
| 12582 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
given graph DFS traversal; count the degree of each vertex |
| 12648 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
simple graph (DAG) traversal; DFS |
| 13015 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
modified DFS; special graph; DAG; also available at Kattis - promotions |
| 13038 |
Fetching from uHunt |
4.2h, Really Ad Hoc |
simple, use DFS to find the length of the deepest branch |
| 00908 |
Fetching from uHunt |
4.3a, MST, Standard |
basic MST problem |
| 01174 |
Fetching from uHunt |
4.3a, MST, Standard |
LA 3988 - SouthWesternEurope07; classic MST; just need a mapper to map city names to indices |
| 01208 |
Fetching from uHunt |
4.3a, MST, Standard |
LA 3171 - Manila06; MST |
| 01235 |
Fetching from uHunt |
4.3a, MST, Standard |
LA 4138 - Jakarta08; the underlying problem is MST |
| 10034 |
Fetching from uHunt |
4.3a, MST, Standard |
straightforward MST problem; also available at Kattis - freckles |
| 11228 |
Fetching from uHunt |
4.3a, MST, Standard |
split output for short vs long edges |
| 11631 |
Fetching from uHunt |
4.3a, MST, Standard |
weight of (all graph edges - all MST edges) |
| 11710 |
Fetching from uHunt |
4.3a, MST, Standard |
output 'Impossible' if the graph is still disconnected after running MST |
| 11733 |
Fetching from uHunt |
4.3a, MST, Standard |
maintain cost at every update |
| 11747 |
Fetching from uHunt |
4.3a, MST, Standard |
sum the edge weights of the chords |
| 11857 |
Fetching from uHunt |
4.3a, MST, Standard |
find weight of the last edge added to MST by Kruskal's; also available at Kattis - drivingrange |
| 00534 |
Fetching from uHunt |
4.3b, MST, Variants |
minimax; also solvable with Floyd Warshall's |
| 00544 |
Fetching from uHunt |
4.3b, MST, Variants |
maximin; also solvable with Floyd Warshall's |
| 01013 |
Fetching from uHunt |
4.3b, MST, Variants |
LA 2478 - WorldFinals Honolulu02; very interesting MST variant |
| 01160 |
Fetching from uHunt |
4.3b, MST, Variants |
LA 3644 - SouthWesternEurope06; count the number of edges not taken by Kruskal's |
| 01216 |
Fetching from uHunt |
4.3b, MST, Variants |
LA 3678 - Kaohsiung06; minimum 'spanning forest' |
| 01234 |
Fetching from uHunt |
4.3b, MST, Variants |
LA 4110 - Singapore07; 'maximum' spanning tree |
| 01265 |
Fetching from uHunt |
4.3b, MST, Variants |
LA 4848 - Daejeon10; very interesting non-standard variant of 'maximum' spanning tree |
| 10048 |
Fetching from uHunt |
4.3b, MST, Variants |
classic MiniMax path problem |
| 10099 |
Fetching from uHunt |
4.3b, MST, Variants |
maximin; also solvable with Floyd Warshall's |
| 10147 |
Fetching from uHunt |
4.3b, MST, Variants |
'minimum' spanning subgraph |
| 10369 |
Fetching from uHunt |
4.3b, MST, Variants |
minimum spanning 'forest'; also available at Kattis - arcticnetwork |
| 10397 |
Fetching from uHunt |
4.3b, MST, Variants |
'minimum' spanning subgraph |
| 10457 |
Fetching from uHunt |
4.3b, MST, Variants |
interesting MST modeling |
| 10462 |
Fetching from uHunt |
4.3b, MST, Variants |
second best spanning tree |
| 10600 |
Fetching from uHunt |
4.3b, MST, Variants |
second best spanning tree |
| 10842 |
Fetching from uHunt |
4.3b, MST, Variants |
find min weighted edge in 'max' spanning tree |
| 00336 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
simple SSSP; BFS |
| 00388 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
key idea: we want to minimize planet movements because every edge used decreases value by 5% |
| 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 |
| 00627 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
also print the path |
| 00762 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
simple SSSP solvable with BFS; use mapper |
| 00924 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
the spread is like BFS traversal |
| 01148 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
LA 3502 - SouthWesternEurope05; single source single target shortest path problem but exclude endpoints |
| 10009 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
simple SSSP solvable with BFS |
| 10610 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
simple SSSP solvable with BFS |
| 10653 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
need efficient BFS implementation |
| 10959 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
SSSP from source 0 to the rest |
| 12160 |
Fetching from uHunt |
4.4a, SSSP, BFS, Easier |
LA 4408 - KualaLumpur08; s: (4-digits number); edges: button pushes; BFS |
| 00314 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
pre-process the input graph first; s: (r, c, dir); 5 edges: turn left/right or move 1/2/3 steps; BFS |
| 00383 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
simple SSSP solvable with BFS; use mapper |
| 00532 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
3D BFS; also available at Kattis - dungeon |
| 00859 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
BFS |
| 00949 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
interesting graph data structure twist |
| 10044 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
the input parsing part is troublesome |
| 10067 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
implicit graph in problem statement |
| 10977 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
BFS with blocked states |
| 10993 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
s: (the current number modulo N); BFS |
| 11049 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
some restricted moves; print the path |
| 11101 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
multi-sources BFS from m1; get minimum at border of m2; also available at Kattis - mallmania |
| 11352 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
filter the graph first; then it becomes SSSP |
| 11377 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
a city to another city without/with airport has edge weight 1/0, respectively; BFS+deque; if the start and end city are the same and has no airport, the answer should be 0 |
| 11573 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
0/1-weighted SSSP; BFS+deque; also available at Kattis - oceancurrents |
| 11624 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
multi-sources BFS; also available at Kattis - fire3 |
| 11792 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
be careful with 'important station' |
| 12826 |
Fetching from uHunt |
4.4b, SSSP, BFS, Harder |
SSSP from (r1; c1) to (r2; c2) avoiding (r3; c3); BFS |
| 00929 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
on a 2D maze/implicit graph |
| 01112 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
LA 2425 - SouthwesternEurope01; SDSP |
| 10389 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
use basic geometry skill to build the weighted graph; then run Dijkstra's; also available at Kattis - subway2 |
| 10986 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
direct Dijkstra's application |
| 12878 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
Dijkstra's; record predecessor graph as there can be multiple shortest paths; also available at Kattis - flowerytrails |
| 13127 |
Fetching from uHunt |
4.4c, SSSP, Dijkstra, Easier |
Dijkstra's from multiple sources |
| 00157 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
tedious input parsing; SSSP on graph with 2-valued weighted graph (1 or 3 units of time); print the shortest path |
| 00523 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
this is actually an SSSP problem on weighted graph solvable with Dijkstra's; use the vertex splitting technique to handle vertex weight |
| 00589 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
weighted SSSP: move box from s to t + unweighted SSSP: move player to correct position to push the box |
| 00721 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
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 |
| 01202 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
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 |
| 10166 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
this can be modeled as an SSSP problem |
| 10187 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
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 |
| 10278 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
Dijkstra's from fire stations to all intersections; need pruning to pass the time limit; also available at Kattis - firestation |
| 10280 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
Dijkstra's; also available at Kattis - wine |
| 10356 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
attach one extra info to each vertex: do we come to that vertex using cycle or not; Dijkstra's |
| 10603 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
state: (a; b; c); source: (0; 0; c); 6 possible transitions |
| 10801 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
model the graph carefully |
| 10967 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
model the graph; SSSP |
| 11338 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
the test data is weaker than what the problem description says (n ≤ 10 000); we use O(n^2) loop to build the weighted graph and runs Dijkstra's without getting TLE |
| 11367 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
model the graph carefully; state: (location, fuel), source s = (s, 0), sink t = (e, any), only enqueue fuel+1; also available at Kattis - fulltank |
| 11492 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
vertex = word; edges as per problem description; connect source/sink to all words in start/finish language, respectively; vertex split; Dijkstra's |
| 11833 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
stop Dijkstra's at service route path plus some modification |
| 12047 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
clever usage of Dijkstra's; run Dijkstra's from source and from d from destination |
| 12144 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
Dijkstra's; store multiple predecessors |
| 12950 |
Fetching from uHunt |
4.4d, SSSP, Dijkstra, Harder |
clever usage of Dijstra's; instead of extending by one edge, we can extend by two edges at a time |
| 00423 |
Fetching from uHunt |
4.4e, SSSP, -ve weight |
the graph is small; Bellman Ford's or Floyd Warshall's |
| 00558 |
Fetching from uHunt |
4.4e, SSSP, -ve weight |
check if negative cycle exists |
| 10449 |
Fetching from uHunt |
4.4e, SSSP, -ve weight |
find the minimum weight path; which may be negative; be careful: INF negative weight is lower than INF |
| 10557 |
Fetching from uHunt |
4.4e, SSSP, -ve weight |
check 'positive' cycle; check connectedness; also available at Kattis - xyzzy |
| 11280 |
Fetching from uHunt |
4.4e, SSSP, -ve weight |
modified Bellman Ford's |
| 12768 |
Fetching from uHunt |
4.4e, SSSP, -ve weight |
insert -F as edge weight; see if negative cycle exists; or find min SSSP value from s = 1 |
| 00341 |
Fetching from uHunt |
4.5a, APSP, Standard |
the graph is small |
| 00567 |
Fetching from uHunt |
4.5a, APSP, Standard |
simple SSSP solvable with BFS; but the graph is small; so can be solved easier with Floyd Warshall's |
| 00821 |
Fetching from uHunt |
4.5a, APSP, Standard |
LA 5221 - WorldFinals Orlando00; one of the easiest ICPC WorldFinals problem |
| 01233 |
Fetching from uHunt |
4.5a, APSP, Standard |
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 |
| 01247 |
Fetching from uHunt |
4.5a, APSP, Standard |
LA 4524 - Hsinchu09; Floyd Warshall's with modification: prefer shortest path with less intermediate vertices |
| 10171 |
Fetching from uHunt |
4.5a, APSP, Standard |
easy with APSP information |
| 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 |
| 10525 |
Fetching from uHunt |
4.5a, APSP, Standard |
use two adjacency matrices: time and length; use modified Floyd Warshall's |
| 10724 |
Fetching from uHunt |
4.5a, APSP, Standard |
adding one edge only changes a few things |
| 10793 |
Fetching from uHunt |
4.5a, APSP, Standard |
Floyd Warshall's simplifies this problem |
| 10803 |
Fetching from uHunt |
4.5a, APSP, Standard |
graph is small |
| 10947 |
Fetching from uHunt |
4.5a, APSP, Standard |
graph is small |
| 11015 |
Fetching from uHunt |
4.5a, APSP, Standard |
graph is small |
| 11463 |
Fetching from uHunt |
4.5a, APSP, Standard |
solution is easy with APSP information |
| 12319 |
Fetching from uHunt |
4.5a, APSP, Standard |
Floyd Warshall's 2x and compare |
| 00104 |
Fetching from uHunt |
4.5b, APSP, Variants |
small arbitrage problem solvable with Floyd Warshall's |
| 00125 |
Fetching from uHunt |
4.5b, APSP, Variants |
modified Floyd Warshall's |
| 00186 |
Fetching from uHunt |
4.5b, APSP, Variants |
graph is small; print path |
| 00274 |
Fetching from uHunt |
4.5b, APSP, Variants |
variant of transitive closure problem |
| 00334 |
Fetching from uHunt |
4.5b, APSP, Variants |
transitive closure |
| 00436 |
Fetching from uHunt |
4.5b, APSP, Variants |
another arbitrage problem |
| 00869 |
Fetching from uHunt |
4.5b, APSP, Variants |
run Warshall's 2x on different graph; compare the two Adjacency Matrices |
| 00925 |
Fetching from uHunt |
4.5b, APSP, Variants |
transitive closure |
| 01056 |
Fetching from uHunt |
4.5b, APSP, Variants |
LA 3569 - WorldFinals SanAntonio06; finding diameter of a small graph with Floyd Warshall's |
| 01198 |
Fetching from uHunt |
4.5b, APSP, Variants |
LA 2818 - Kaohsiung03; transitive closure |
| 01757 |
Fetching from uHunt |
4.5b, APSP, Variants |
LA 8047 - WorldFinals RapidCity17; Warshall's transitive closure; also available at Kattis - secretchamber |
| 10246 |
Fetching from uHunt |
4.5b, APSP, Variants |
modify the Floyd Warshall's recurrence a bit to handle the maximum cost to hold feast for Obelix |
| 10331 |
Fetching from uHunt |
4.5b, APSP, Variants |
use Floyd Warshall's to obtain the APSP information; then use brute force to count the time an edge is used; report accordingly |
| 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 |
| 10436 |
Fetching from uHunt |
4.5b, APSP, Variants |
as there is vertex weight; use vertex splitting technique; run Floyd Warshall's on the still-small graph; print path |
| 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 |
| 11047 |
Fetching from uHunt |
4.5b, APSP, Variants |
print path; special case: if origin = destination; print twice |
| 00103 |
Fetching from uHunt |
4.6a, S/Longest Paths on DAG |
longest paths on DAG; backtracking OK |
| 00452 |
Fetching from uHunt |
4.6a, S/Longest Paths on DAG |
longest paths on DAG |
| 10000 |
Fetching from uHunt |
4.6a, S/Longest Paths on DAG |
longest paths on DAG; backtracking OK |
| 10051 |
Fetching from uHunt |
4.6a, S/Longest Paths on DAG |
longest paths on DAG; DP |
| 10259 |
Fetching from uHunt |
4.6a, S/Longest Paths on DAG |
longest paths on implicit DAG; DP |
| 10285 |
Fetching from uHunt |
4.6a, S/Longest Paths on DAG |
longest paths on implicit DAG; however; the graph is small enough for recursive backtracking solution |
| 10350 |
Fetching from uHunt |
4.6a, S/Longest Paths on DAG |
shortest paths; implicit DAG; DP |
| 00825 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in grid (implicit DAG); DP; similar to UVa 00926 and 11067 |
| 00926 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in grid (implicit DAG); DP; similar to UVa 825 and 11067 |
| 00986 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in DAG; DP; s: (x; y; lastmove; peaksfound); t: try NE/SE |
| 00988 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in DAG; DP |
| 10401 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in implicit DAG; DP; s: (col; row); t: next col; avoid 2 or 3 adjacent rows |
| 10544 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in implicit DAG |
| 10564 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in implicit DAG (top-down); print one solution |
| 10926 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in DAG; DP |
| 11067 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in grid (implicit DAG); DP; similar to UVa 825 and 926 |
| 11569 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
determine the length of one of the longest paths and then count the number of such longest paths in DAG |
| 11655 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in DAG and one more similar task: counting the number of vertices involved in the paths |
| 11957 |
Fetching from uHunt |
4.6b, Counting Paths, Easier |
counting paths in implicit DAG; DP |
| 00590 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (pos; day_left) |
| 00607 |
Fetching from uHunt |
4.6c, Conversion to DAG |
returns pair of information |
| 00757 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (lake_id, time_left); this time_left is best left as multiple of 5 minutes; output the optimal solution too |
| 00907 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (pos; night_left) |
| 00910 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (pos; move_left) |
| 01025 |
Fetching from uHunt |
4.6c, Conversion to DAG |
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 |
| 10201 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (pos, fuel_left); also available at Kattis - adventuremoving4 |
| 10271 |
Fetching from uHunt |
4.6c, Conversion to DAG |
Observation: The 3rd chopstick can be any chopstick; s: (pos, K_left); t: ignore this chopstick, or take this chopstick and the chopstick immediately next to it |
| 10543 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (pos; speech_given) |
| 10681 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (pos; day_left) |
| 10702 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (pos; T_left); similar to UVa 12875 |
| 10874 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (row; left/right); t: go left/right |
| 10913 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (r; c; neg_left; stat); t: down/(left/right) |
| 11307 |
Fetching from uHunt |
4.6c, Conversion to DAG |
Min Chromatic Sum; max 6 colors |
| 11487 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (r; c; cur_food; len); t: 4 dirs |
| 11545 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (cPos; cTime; cWTime); t: move forward/rest |
| 11782 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (id; rem_K); t: take root/try left-right subtree |
| 12875 |
Fetching from uHunt |
4.6c, Conversion to DAG |
LA 6853 - Bangkok14; similar to UVa 10702; s: (cur_store; cur_concert); t: pick any next store for next concert |
| 13122 |
Fetching from uHunt |
4.6c, Conversion to DAG |
s: (pos, K_left); knapsack style DP; jump 1, 2, ..., K_left points; connect with the two points with a line with cost equals to their Euclidean distance; keep the minimum |
| 00112 |
Fetching from uHunt |
4.6d, Tree |
backtracking |
| 00115 |
Fetching from uHunt |
4.6d, Tree |
tree traversal to determine relationships between vertices |
| 00122 |
Fetching from uHunt |
4.6d, Tree |
tree traversal |
| 00536 |
Fetching from uHunt |
4.6d, Tree |
reconstructing binary tree from preorder and inorder binary tree traversal |
| 00548 |
Fetching from uHunt |
4.6d, Tree |
reconstructing tree from in postorder |
| 00615 |
Fetching from uHunt |
4.6d, Tree |
graph property check |
| 00699 |
Fetching from uHunt |
4.6d, Tree |
preorder traversal |
| 00712 |
Fetching from uHunt |
4.6d, Tree |
simple binary tree traversal variant |
| 00839 |
Fetching from uHunt |
4.6d, Tree |
can be viewed as a recursive problem on tree |
| 10308 |
Fetching from uHunt |
4.6d, Tree |
diameter of tree |
| 10459 |
Fetching from uHunt |
4.6d, Tree |
diameter of tree |
| 10701 |
Fetching from uHunt |
4.6d, Tree |
reconstructing tree from pre inorder |
| 10805 |
Fetching from uHunt |
4.6d, Tree |
involving diameter of tree |
| 11131 |
Fetching from uHunt |
4.6d, Tree |
read tree; produce two postorder traversals |
| 11234 |
Fetching from uHunt |
4.6d, Tree |
converting post-order to level-order; binary tree |
| 11615 |
Fetching from uHunt |
4.6d, Tree |
counting size of subtrees |
| 11695 |
Fetching from uHunt |
4.6d, Tree |
cut the worst edge along the tree diameter; link two centers; also available at Kattis - flight |
| 12186 |
Fetching from uHunt |
4.6d, Tree |
the input graph is a tree |
| 12347 |
Fetching from uHunt |
4.6d, Tree |
given pre-order traversal of a BST; use BST property to get the BST; output the post-order traversal that BST |
| 12379 |
Fetching from uHunt |
4.6d, Tree |
find the diameter of tree first; we only traverse the diameter once and we traverse the other edges twice |
| 00663 |
Fetching from uHunt |
4.6e, Bipartite Graph |
try disallowing an edge to see if MCBM changes; which implies that the edge has to be used |
| 00670 |
Fetching from uHunt |
4.6e, Bipartite Graph |
MCBM |
| 00753 |
Fetching from uHunt |
4.6e, Bipartite Graph |
initially a non standard matching problem but this problem can be reduced to a simple MCBM problem |
| 10080 |
Fetching from uHunt |
4.6e, Bipartite Graph |
MCBM; also available at Kattis - gopher2 |
| 11138 |
Fetching from uHunt |
4.6e, Bipartite Graph |
a pure MCBM problem |
| 12644 |
Fetching from uHunt |
4.6e, Bipartite Graph |
classic MCBM problem wrapped inside a creative problem statement |
| 12668 |
Fetching from uHunt |
4.6e, Bipartite Graph |
LA 6525 - LatinAmerica13; split rows/columns due to the presence of pawns; then run MCBM |
| 00117 |
Fetching from uHunt |
4.6f, Eulerian Graph |
Euler tour; get cost of tour |
| 00291 |
Fetching from uHunt |
4.6f, Eulerian Graph |
Euler tour on a small graph; backtracking is sufficient |
| 00302 |
Fetching from uHunt |
4.6f, Eulerian Graph |
Euler tour; print the tour |
| 10054 |
Fetching from uHunt |
4.6f, Eulerian Graph |
printing the Euler tour |
| 10129 |
Fetching from uHunt |
4.6f, Eulerian Graph |
Euler Graph property check |
| 10203 |
Fetching from uHunt |
4.6f, Eulerian Graph |
the underlying graph is Euler graph |
| 10596 |
Fetching from uHunt |
4.6f, Eulerian Graph |
Euler Graph property check |
| 00100 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
simply do as asked; the only trap is that j can be < i |
| 00371 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
similar to UVa 100 |
| 00382 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
do trial division |
| 00654 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
just use brute force |
| 00906 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
compute c from d = 1 until a/b < c/d |
| 01225 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
LA 3996 - Danang07; N is small |
| 01583 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
N is small; prepare an array of size 100044; that is the largest possible digit sum for this problem |
| 10346 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
interesting simulation problem |
| 10370 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
compute average; see how many are above it; also available at Kattis - aboveaverage |
| 10783 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
input range is very small; just brute force it |
| 10879 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
just use brute force |
| 11001 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
brute force math; maximize function |
| 11150 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
similar to UVa 10346; be careful with boundary cases! |
| 11247 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
brute force around the answer to be safe |
| 11313 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
similar to UVa 10346 |
| 11689 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
similar to UVa 10346; also available at Kattis - sodasurpler |
| 11877 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
similar to UVa 10346 |
| 11934 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
just do plain brute-force |
| 12527 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
try all; check repeated digits |
| 12895 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
verbatim brute force check |
| 12938 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
complete search; 4 digits; square numbers |
| 13059 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
just simulate the counting; it will only runs in logarithmic steps; use long long |
| 13131 |
Fetching from uHunt |
5.2a, Math Simulation, Easier |
brute force version of modified sumDiv(N) function |
| 00493 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
simulate the spiral process |
| 00529 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
use backtracking to get the solution |
| 00550 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
rotamult property; try one by one starting from 1 digit |
| 00616 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
brute force up to sqrt(n); get pattern |
| 00697 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
output formatting and basic Physics |
| 00846 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
uses the sum of arithmetic progression formula |
| 10025 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
simplify the formula first; iterative |
| 10035 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
count the number of carry operations |
| 10624 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
backtracking with divisibility check |
| 11130 |
Fetching from uHunt |
5.2b, 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 |
| 11254 |
Fetching from uHunt |
5.2b, 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 |
| 11490 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
let missing_people = 2*a^2; thickness_of_soldiers = b; derive a formula involving a; b; and the given S |
| 11968 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
average; fabs; if ties; choose the smaller one! |
| 12169 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
brute force constants a and b between [0..10 000] and do O(n) checks; break early as soon as a solution is found; also available at Kattis - disgruntledjudge |
| 12290 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
no -1 in the answer |
| 12665 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
be careful with boundary conditions |
| 12792 |
Fetching from uHunt |
5.2b, Math Simulation, Harder |
simulate the process to get the answer |
| 01315 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
find the pattern; hint: odd indices |
| 10014 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
derive the required formula |
| 10110 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
check if n is a square number |
| 10170 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
one liner formula exists |
| 10499 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
simple formula exists |
| 10696 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
very simple formula simplification |
| 10751 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
trivial for N = 1 and N = 2; derive the formula first for N > 2; hint: use diagonal as much as possible |
| 10773 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
several tricky cases |
| 10940 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
find the pattern with brute force solution; then submit the optimized solution |
| 11202 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
consider symmetry and flip |
| 12004 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
try small n; get the pattern; use long long |
| 12027 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
sqrt trick |
| 12502 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
must understand the wording trick first |
| 12725 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
simple O(1) adhoc math formula manipulation |
| 12918 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
simple formula involving sum of arithmetic progression; use long long |
| 12992 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
simple formula, just 2*N-1 |
| 13049 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
simple; for each digit, you should not do more than 5 steps |
| 13071 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
simple formula involving sum of arithmetic progression |
| 13216 |
Fetching from uHunt |
5.2c, Finding Pattern, Easier |
print the first few answer to see the clear pattern; use Big Integer |
| 00651 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
use the given sample I/O to derive the simple formula |
| 00913 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
derive the short formulas |
| 10161 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
sqrt and ceil |
| 10257 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
need some mathematical insights; also available at Kattis - dickandjane |
| 10493 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
tree; derive the formula |
| 10509 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
there are only three different cases |
| 10666 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
analyze the binary representation of X |
| 10693 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
derive the short Physics formula |
| 10710 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
a bit hard to derive the formula; modPow |
| 10882 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
inclusion-exclusion principle |
| 10970 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
direct formula exists; or use DP |
| 10994 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
formula simplification |
| 11038 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
define a function f that counts the number of 0s from 1 to n; also available at Kattis - howmanyzeros |
| 11170 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
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) |
| 11231 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
there is an O(1) formula |
| 11246 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
derive the formula |
| 11296 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
simple formula exists |
| 11298 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
simple maths; derive the pattern first |
| 11387 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
impossible for odd n or when n = 2; derive the formula |
| 11393 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
draw several small Kn; derive the pattern |
| 11718 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
convert loops to a closed form formula; use modPow to compute the results |
| 12909 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
find the pattern; OEIS A001108 |
| 13096 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
there are patterns; but the formula is quite hard to find |
| 13140 |
Fetching from uHunt |
5.2d, Finding Pattern, Harder |
write a brute force program; answer is when i ∈ [9 999..10 005] |
| 00121 |
Fetching from uHunt |
5.2e, Grid |
use Pythagorean theorem; grid |
| 00264 |
Fetching from uHunt |
5.2e, Grid |
grid; pattern |
| 00808 |
Fetching from uHunt |
5.2e, Grid |
grid; similar to UVa 10182 |
| 00880 |
Fetching from uHunt |
5.2e, Grid |
grid; similar to UVa 264 |
| 10022 |
Fetching from uHunt |
5.2e, Grid |
this is not an SSSP problem; find the pattern in this grid (triangle)-like system |
| 10182 |
Fetching from uHunt |
5.2e, Grid |
grid |
| 10233 |
Fetching from uHunt |
5.2e, Grid |
the number of items in row forms arithmetic progression series; use hypot |
| 10620 |
Fetching from uHunt |
5.2e, Grid |
just simulate the jumps; also available at Kattis - fleaonachessboard |
| 10642 |
Fetching from uHunt |
5.2e, Grid |
the reverse of UVa 264 |
| 10964 |
Fetching from uHunt |
5.2e, Grid |
convert the coordinates to (x; y); then this problem is just about finding Euclidean distance between two coordinates |
| 12705 |
Fetching from uHunt |
5.2e, Grid |
we need to match grid cells to characters; there is a greedy solution; find the required pattern |
| 00136 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
use similar technique as UVa 443 |
| 00138 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
arithmetic progression formula; precalculation |
| 00413 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
simulate; array manipulation |
| 00443 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
try all 2^i * 3^j * 5^k * 7^l; sort |
| 00640 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
DP bottom up; generate the numbers; flag once |
| 00694 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
similar to UVa 100 |
| 00927 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
use sum of arithmetic series |
| 00962 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
pre-calculate the answer |
| 00974 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
there are not that many Kaprekar numbers |
| 10006 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
non prime which has >= 3 prime factors |
| 10042 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
prime factorization; sum the digits |
| 10049 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
enough to get past > 2G by storing only the first 700K numbers of the Self-describing sequence |
| 10101 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
follow the problem description carefully |
| 10408 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
first; generate (i; j) pairs such that gcd(i; j) = 1; then sort |
| 10930 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
ad-hoc; follow the rules given in description |
| 11028 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
this is a 'dartboard sequence' |
| 11063 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
see if a number is repeated; be careful with -ve |
| 11461 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
answer is sqrt(b) - sqrt(a-1) |
| 11660 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
simulate; break after $j$-th character |
| 11970 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
square numbers; divisibility; brute force |
| 12149 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
finding the pattern; square numbers |
| 12751 |
Fetching from uHunt |
5.2f, Number Systems/Sequences |
sum of arithmetic series [1..N]; inclusion-exclusion |
| 13161 |
Fetching from uHunt |
5.2f, 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 |
| 00107 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
use logarithm; power |
| 00113 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
use exp(ln(x)*y) |
| 00474 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
this is just a log and pow exercise |
| 00545 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
use logarithm; power; similar to UVa 474 |
| 00701 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
use log to count number of digits |
| 10916 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
use logarithm; power; also available at Kattis - factstone |
| 11384 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
find the smallest power of two greater than n; can be solved easily using ceil(eps log2(n)) |
| 11556 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
related to power of two; use long long; also available at Kattis - bestcompression |
| 11636 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
uses logarithm |
| 11666 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
find the formula! |
| 11714 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
use decision tree model to find min and second min; eventually the solution only involves logarithm |
| 11847 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
O(1) math formula exists: floor(log2(n)) |
| 11986 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
log2 (N 1); manual check for precision |
| 12416 |
Fetching from uHunt |
5.2g, Log, Exp, Pow |
the answer is log2 of the max consecutive spaces in a line |
| 00126 |
Fetching from uHunt |
5.2h, Polynomial |
polynomial multiplication and tedious output formatting |
| 00392 |
Fetching from uHunt |
5.2h, Polynomial |
follow the orders; output formatting |
| 00498 |
Fetching from uHunt |
5.2h, Polynomial |
polynomial evaluation |
| 00930 |
Fetching from uHunt |
5.2h, Polynomial |
Ruffini's rule; roots of quadratic eq |
| 10215 |
Fetching from uHunt |
5.2h, Polynomial |
two trivial cases for smallest; derive the formula for largest which involves quadratic equation |
| 10268 |
Fetching from uHunt |
5.2h, Polynomial |
polynomial derivation; Horner's rule |
| 10302 |
Fetching from uHunt |
5.2h, Polynomial |
use long double |
| 10326 |
Fetching from uHunt |
5.2h, Polynomial |
given roots of the polynomial; reconstruct the polynomial; formatting |
| 10586 |
Fetching from uHunt |
5.2h, Polynomial |
compute number of prime factors of each integer in the desired range; use 1D RSQ DP; binary search |
| 10719 |
Fetching from uHunt |
5.2h, Polynomial |
polynomial division and remainder |
| 00377 |
Fetching from uHunt |
5.2i, Base Number Variants |
base 4 operations |
| 00575 |
Fetching from uHunt |
5.2i, Base Number Variants |
base modification |
| 00636 |
Fetching from uHunt |
5.2i, Base Number Variants |
base number conversion up to base 99; Java BigInteger cannot be used as it is MAX_RADIX is limited to 36 |
| 10093 |
Fetching from uHunt |
5.2i, Base Number Variants |
try all |
| 10677 |
Fetching from uHunt |
5.2i, Base Number Variants |
try all from r2 to r1 |
| 10931 |
Fetching from uHunt |
5.2i, Base Number Variants |
convert decimal to binary; count number of 1s |
| 11005 |
Fetching from uHunt |
5.2i, Base Number Variants |
try all possible bases from 2 to 36 |
| 11121 |
Fetching from uHunt |
5.2i, Base Number Variants |
search for the term 'negabinary' |
| 11398 |
Fetching from uHunt |
5.2i, Base Number Variants |
just follow the new rules |
| 12602 |
Fetching from uHunt |
5.2i, Base Number Variants |
simple base conversion |
| 00332 |
Fetching from uHunt |
5.2j, Fractions |
use GCD |
| 00834 |
Fetching from uHunt |
5.2j, Fractions |
do as asked |
| 10555 |
Fetching from uHunt |
5.2j, Fractions |
try every single possible repeating decimals |
| 10976 |
Fetching from uHunt |
5.2j, Fractions |
total solutions is asked upfront; therefore do brute force twice |
| 12068 |
Fetching from uHunt |
5.2j, Fractions |
involving fraction; use LCM and GCD |
| 00276 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
multiplication of Egyptian hieroglyphs |
| 00496 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
set manipulation |
| 00613 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
analyze the number; determine the type; similar spirit with the cycle finding problem |
| 10137 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
be careful with precision error; also available at Kattis - trip |
| 10190 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
simulate the process |
| 11055 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
not classic; observation needed to avoid brute-force solution |
| 11241 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
the hardest case is computing Dew point given temperature and Humidex; derive it with Algebra |
| 11526 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
brute force up to sqrt(n); find the pattern; avoid TLE |
| 11715 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
physics simulation |
| 11816 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
simple math; precision required |
| 12036 |
Fetching from uHunt |
5.2k, Really Ad Hoc |
use pigeon hole principle |
| 00424 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger addition |
| 00465 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger add/multiply; compare with 2^31-1$ |
| 00619 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger |
| 00713 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger StringBuffer reverse() |
| 00748 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger exponentiation |
| 01226 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
LA 3997 - Danang07; mod operation |
| 01647 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
find the simple pattern first using brute force; then precompute the answers using BigInteger |
| 10013 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger addition |
| 10083 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger number theory |
| 10106 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger multiplication |
| 10198 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
recurrences; BigInteger |
| 10430 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger; derive formula first |
| 10433 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger: pow; substract; mod |
| 10494 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger division |
| 10519 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
recurrences; BigInteger |
| 10523 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger addition; multiplication; and power |
| 10669 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
Big Integer is for 3^n; binary rep of set; also available at Kattis - threepowers |
| 10925 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger addition and division |
| 10992 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
input size is up to 50 digits |
| 11448 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger subtraction |
| 11664 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
simple simulation involving BigInteger |
| 11830 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
use BigInteger string representation |
| 11879 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
BigInteger: mod; divide; subtract; equals |
| 12143 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
LA 4209 - Dhaka08; formula simplification---the hard part; use BigInteger---the easy part |
| 12459 |
Fetching from uHunt |
5.3a, Big Integer, Basic |
draw the ancestor tree to see the pattern |
| 00960 |
Fetching from uHunt |
5.3b, (Prob) Prime Testing |
there is a number theory behind this |
| 01180 |
Fetching from uHunt |
5.3b, (Prob) Prime Testing |
LA 2350 - Dhaka01; small prime check |
| 01210 |
Fetching from uHunt |
5.3b, (Prob) Prime Testing |
LA 3399 - Tokyo05; simple |
| 10235 |
Fetching from uHunt |
5.3b, (Prob) Prime Testing |
case analysis: prime/emirp/not prime; emirp is prime number that if reversed is still a prime number |
| 10924 |
Fetching from uHunt |
5.3b, (Prob) Prime Testing |
check if the sum of letter values is a prime |
| 11287 |
Fetching from uHunt |
5.3b, (Prob) Prime Testing |
yes if !isPrime(p) && a.modPow(p, p) = a; Big Integer; also available at Kattis - pseudoprime |
| 12542 |
Fetching from uHunt |
5.3b, (Prob) Prime Testing |
LA 6149 - HatYai12; brute force; use isProbablePrime to test primality |
| 00290 |
Fetching from uHunt |
5.3c, Bonus: Base Number |
also involving palindrome |
| 00343 |
Fetching from uHunt |
5.3c, Bonus: Base Number |
try all possible pair of bases |
| 00355 |
Fetching from uHunt |
5.3c, Bonus: Base Number |
basic base number conversion |
| 00389 |
Fetching from uHunt |
5.3c, Bonus: Base Number |
use Java Integer class |
| 00446 |
Fetching from uHunt |
5.3c, Bonus: Base Number |
base number conversion |
| 10473 |
Fetching from uHunt |
5.3c, Bonus: Base Number |
Decimal to Hexadecimal and vice versa; if you use C/C ; you can use strtol |
| 10551 |
Fetching from uHunt |
5.3c, Bonus: Base Number |
also involving BigInteger mod; also available at Kattis - basicremains |
| 11185 |
Fetching from uHunt |
5.3c, Bonus: Base Number |
Decimal to base 3 |
| 11952 |
Fetching from uHunt |
5.3c, Bonus: Base Number |
check base 2 to 18; special case for base 1 |
| 01230 |
Fetching from uHunt |
5.3d, Bonus: Others |
LA 4104 - Singapore07; modPow |
| 10023 |
Fetching from uHunt |
5.3d, Bonus: Others |
code Newton's method with BigInteger |
| 10193 |
Fetching from uHunt |
5.3d, Bonus: Others |
convert two binary strings S1 and S2 to decimal and check see if gcd(s1; s2) > 1 |
| 10464 |
Fetching from uHunt |
5.3d, Bonus: Others |
Java BigDecimal class |
| 10814 |
Fetching from uHunt |
5.3d, Bonus: Others |
BigInteger gcd |
| 11821 |
Fetching from uHunt |
5.3d, Bonus: Others |
Java BigDecimal class |
| 12930 |
Fetching from uHunt |
5.3d, Bonus: Others |
Java BigDecimal class; compareTo |
| 00495 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
O(n) DP; Big Integer |
| 00580 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
related to Tribonacci series |
| 00763 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
Zeckendorf representation; greedy; Big Integer |
| 00900 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
combinatorics; the pattern ~ Fibonacci |
| 00948 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
Zeckendorf representation; greedy |
| 01258 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
LA 4721 - Phuket09; Fibonacci variant; Zeckendorf representation; greedy |
| 10183 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
get the number of Fibonaccis when generating them; BigInteger |
| 10334 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
combinatorics; Big Integer |
| 10450 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
combinatorics; the pattern ~ Fibonacci |
| 10497 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
the pattern ~ Fibonacci |
| 10579 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
very easy with Java BigInteger |
| 10689 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
easy; Pisano period |
| 10862 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
the pattern ends up ~ Fibonacci |
| 11000 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
combinatorics; the pattern is similar to Fibonacci |
| 11089 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
the list of Fi-binary Numbers follow the Zeckendorf's theorem |
| 11161 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
Fibonacci median |
| 11780 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
the background problem is Fibonacci numbers |
| 12281 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
Zeckendorf theorem a bit of combinatorics |
| 12620 |
Fetching from uHunt |
5.4a, Fibonacci Numbers |
Pisano period of 10^2 = 300 |
| 00326 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
difference table |
| 00369 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
be careful with overflow issue |
| 00485 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
binomial coefficients BigInteger |
| 00530 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
work with doubles; optimize computation |
| 00911 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
there is a formula for this: result = n! / (z_1! * z_2! * z_3! * ... * z_k!$) |
| 10105 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
similar to UVa 911 |
| 10375 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
the main task is to avoid overflow |
| 10532 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
modified binomial coefficient |
| 10541 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
a good combinatorics problem |
| 11955 |
Fetching from uHunt |
5.4b, Binomial Coefficients |
pure application; DP |
| 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 |
| 00991 |
Fetching from uHunt |
5.4c, Catalan Numbers |
Catalan Numbers |
| 10007 |
Fetching from uHunt |
5.4c, Catalan Numbers |
answer is Cat(n) * n!; BigInteger |
| 10223 |
Fetching from uHunt |
5.4c, Catalan Numbers |
you can precalculate the answers as there are only 19 Catalan Numbers < 2^{32}-1 |
| 10303 |
Fetching from uHunt |
5.4c, Catalan Numbers |
generate Cat(n) as shown in this section; use Java BigInteger |
| 10312 |
Fetching from uHunt |
5.4c, Catalan Numbers |
number of binary bracketing = Cat(n); number of bracketing = Super-Catalan numbers |
| 10643 |
Fetching from uHunt |
5.4c, Catalan Numbers |
Cat(n) is part of a bigger problem |
| 10079 |
Fetching from uHunt |
5.4d, Others, Easier |
derive the one liner formula |
| 11115 |
Fetching from uHunt |
5.4d, Others, Easier |
N^D; use Java BigInteger |
| 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 |
| 11401 |
Fetching from uHunt |
5.4d, Others, Easier |
spot the pattern |
| 11480 |
Fetching from uHunt |
5.4d, Others, Easier |
try all r; but simpler formula exists |
| 11597 |
Fetching from uHunt |
5.4d, Others, Easier |
uses knowledge of graph theory; the answer is very trivial |
| 11609 |
Fetching from uHunt |
5.4d, Others, Easier |
N * 2^(N-1); use Java BigInteger for the modPow part |
| 12463 |
Fetching from uHunt |
5.4d, Others, Easier |
double the socks and the shoes to simplify the problem |
| 01224 |
Fetching from uHunt |
5.4e, Others, Harder |
LA 3904 - Seoul07; derive formula from observing the small instances first |
| 10359 |
Fetching from uHunt |
5.4e, Others, Harder |
derive the formula; use Java BigInteger |
| 10733 |
Fetching from uHunt |
5.4e, Others, Harder |
Burnside's lemma |
| 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 |
| 10790 |
Fetching from uHunt |
5.4e, Others, Harder |
uses arithmetic progression formula |
| 10918 |
Fetching from uHunt |
5.4e, Others, Harder |
there are two related recurrences here |
| 11069 |
Fetching from uHunt |
5.4e, Others, Harder |
use Dynamic Programming |
| 11204 |
Fetching from uHunt |
5.4e, Others, Harder |
only first choice matters |
| 11270 |
Fetching from uHunt |
5.4e, Others, Harder |
sequence A004003 in OEIS |
| 11538 |
Fetching from uHunt |
5.4e, Others, Harder |
count along rows; columns; and diagonals |
| 11554 |
Fetching from uHunt |
5.4e, Others, Harder |
similar to UVa 11401 |
| 12001 |
Fetching from uHunt |
5.4e, Others, Harder |
counting; combinatorics |
| 12022 |
Fetching from uHunt |
5.4e, Others, Harder |
number of ways n competitors can rank in a competition allowing for the possibility of ties; sequence A000670 in OEIS |
| 00406 |
Fetching from uHunt |
5.5a, Prime Numbers |
sieve; take the middle ones |
| 00543 |
Fetching from uHunt |
5.5a, Prime Numbers |
sieve; complete search; Goldbach's conjecture; similar to UVa 00686, 10311, and 10948 |
| 00686 |
Fetching from uHunt |
5.5a, Prime Numbers |
similar to UVa 543; 10311; and 10948 |
| 00897 |
Fetching from uHunt |
5.5a, Prime Numbers |
sieve; just need to check digit rotations |
| 00914 |
Fetching from uHunt |
5.5a, Prime Numbers |
sieve; be careful with L and U < 2 |
| 01644 |
Fetching from uHunt |
5.5a, Prime Numbers |
LA 3883 - Tokyo07; sieve; prime check; upper bound - lower bound |
| 10140 |
Fetching from uHunt |
5.5a, Prime Numbers |
sieve; linear scan |
| 10168 |
Fetching from uHunt |
5.5a, Prime Numbers |
backtracking with pruning |
| 10311 |
Fetching from uHunt |
5.5a, Prime Numbers |
case analysis; brute force; similar to UVa 543; 686; and 10948 |
| 10394 |
Fetching from uHunt |
5.5a, Prime Numbers |
sieve; check if p and p plus 2 are both primes; if yes; they are twin primes; precalculate the result |
| 10490 |
Fetching from uHunt |
5.5a, Prime Numbers |
ad Hoc; precalculate the answers |
| 10650 |
Fetching from uHunt |
5.5a, Prime Numbers |
3 uni-distance consecutive primes |
| 10852 |
Fetching from uHunt |
5.5a, Prime Numbers |
sieve; p = 1; find the first prime number >= n/2 plus 1 |
| 10948 |
Fetching from uHunt |
5.5a, Prime Numbers |
Goldbach's conjecture; similar to UVa 543; 686; and 10311 |
| 11752 |
Fetching from uHunt |
5.5a, Prime Numbers |
try base: 2 to 2^16; composite power; sort |
| 00106 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
brute force; use GCD to get relatively prime triples |
| 00412 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
brute force; GCD to find elements with no common factor |
| 10407 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
subtract the set s with s[0]; find gcd |
| 10892 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
number of divisor pairs of N: (m; n) such that gcd(m; n) = 1 |
| 11388 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
understand the relationship of GCD with LCM |
| 11417 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
just use brute force as input is small |
| 11774 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
find pattern involving gcd with small test cases |
| 11827 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
GCD of many numbers; small input |
| 12708 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
actually we do not need to compute the GCD; simply find an easy pattern to solve this problem |
| 12848 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
find formula involving fraction and use GCD to simplify it |
| 12852 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
LCM of the N given numbers times 35 |
| 12970 |
Fetching from uHunt |
5.5b, GCD and/or LCM |
simple Physics time comparison; GCD to simplify fraction |
| 00324 |
Fetching from uHunt |
5.5c, Factorial |
count digits of n! up to 366! |
| 00568 |
Fetching from uHunt |
5.5c, Factorial |
can use Java BigInteger; slow but AC |
| 00623 |
Fetching from uHunt |
5.5c, Factorial |
easy with Java BigInteger |
| 10220 |
Fetching from uHunt |
5.5c, Factorial |
use Java BigInteger; precalculate |
| 10323 |
Fetching from uHunt |
5.5c, Factorial |
overflow: n>13/-odd n; underflow: n$<$8/-even n; PS: actually; factorial of negative number is not defined |
| 10338 |
Fetching from uHunt |
5.5c, Factorial |
use long long to store up to 20! |
| 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 |
| 12335 |
Fetching from uHunt |
5.5c, Factorial |
given the k-th permutation, recover the 1st permutation; use factorial; use Java BigInteger |
| 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 |
| 12934 |
Fetching from uHunt |
5.5c, Factorial |
can use brute force; stop at n not more than sqrt(k); m smaller than n |
| 00516 |
Fetching from uHunt |
5.5d, Finding Prime Factors |
problem involving prime-power factorization |
| 00583 |
Fetching from uHunt |
5.5d, Finding Prime Factors |
basic factorization problem |
| 10392 |
Fetching from uHunt |
5.5d, Finding Prime Factors |
enumerate the prime factors of input |
| 11466 |
Fetching from uHunt |
5.5d, Finding Prime Factors |
use efficient sieve implementation to get the largest prime factors |
| 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 |
| 12805 |
Fetching from uHunt |
5.5d, Finding Prime Factors |
prime check; primes of format 4m-1 and 4m plus 1; simple prime factorization |
| 00160 |
Fetching from uHunt |
5.5e, Prime Factors Related |
precalculate small primes as prime factors of 100! is < 100$ |
| 00993 |
Fetching from uHunt |
5.5e, Prime Factors Related |
find divisors from 9 down to 1; similar to UVa 10527 |
| 10061 |
Fetching from uHunt |
5.5e, Prime Factors Related |
in Decimal; '10' with 1 zero is due to factor 2*5 |
| 10139 |
Fetching from uHunt |
5.5e, Prime Factors Related |
compare prime factors of n! and m; also available at Kattis - factovisors |
| 10484 |
Fetching from uHunt |
5.5e, Prime Factors Related |
prime factors of factorial; D can be negative |
| 10527 |
Fetching from uHunt |
5.5e, Prime Factors Related |
similar to UVa 00993; also available at Kattis - persistent |
| 10622 |
Fetching from uHunt |
5.5e, Prime Factors Related |
GCD of all prime powers; note if x is negative; also available at Kattis - perfectpowers |
| 10680 |
Fetching from uHunt |
5.5e, Prime Factors Related |
use primefactors([1..N]) to get LCM(1; 2; ...; N) |
| 10780 |
Fetching from uHunt |
5.5e, Prime Factors Related |
similar to UVa 10139 |
| 10791 |
Fetching from uHunt |
5.5e, Prime Factors Related |
analyze the prime factors of N |
| 11347 |
Fetching from uHunt |
5.5e, Prime Factors Related |
prime-power factorization; numDiv(N) |
| 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 |
| 11889 |
Fetching from uHunt |
5.5e, Prime Factors Related |
LCM; involving prime factorization |
| 13067 |
Fetching from uHunt |
5.5e, Prime Factors Related |
cryptic problem description, it turns out that the restaurant uses prime power system; output sum of prime powers |
| 00294 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
numDiv(N) |
| 00884 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
numPF(N); precalculate |
| 01246 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
LA 4340 - Amrita08; numDiv(N) |
| 10179 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
EulerPhi(N) |
| 10290 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
find number of odd divisors |
| 10299 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
EulerPhi(N); also available at Kattis - relatives |
| 10820 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
a[i] = a[i-1] plus 2*EulerPhi(i) |
| 10958 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
2 * numDiv(n*m*p*p) - 1 |
| 11064 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
N - EulerPhi(N) - numDiv(N) |
| 11086 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
find numbers N with numPF(N) == 2 |
| 11226 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
sumPF(N); get length; DP |
| 11353 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
numPF(N); sort variant |
| 11728 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
sumDiv(N) |
| 12005 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
numDiv(4N-3) |
| 13185 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
just see UVa 13194 |
| 13194 |
Fetching from uHunt |
5.5f, Prime Factors Functions |
similar to Kattis - almostperfect; sumDiv(N)-N; long long |
| 10699 |
Fetching from uHunt |
5.5g, Modified Sieve |
numDiffPF(N) for a range |
| 10738 |
Fetching from uHunt |
5.5g, Modified Sieve |
numDiffPF(N) for a range of N |
| 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 |
| 11327 |
Fetching from uHunt |
5.5g, Modified Sieve |
pre-calculate EulerPhi(N) |
| 11426 |
Fetching from uHunt |
5.5g, Modified Sieve |
pre-calculate EulerPhi(N) |
| 12043 |
Fetching from uHunt |
5.5g, Modified Sieve |
sumDiv(N) and numDiv(N); brute force |
| 00128 |
Fetching from uHunt |
5.5h, Modulo Arithmetic |
(a * b) % s = ((a % s) * (b % s)) % s |
| 10127 |
Fetching from uHunt |
5.5h, Modulo Arithmetic |
no factor of 2 and 5 implies that there is no trailing zero |
| 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 |
| 10212 |
Fetching from uHunt |
5.5h, Modulo Arithmetic |
multiply numbers from N down to N-M+1; use / 10 to discard the trailing zero(es); use % 1 Billion |
| 10489 |
Fetching from uHunt |
5.5h, Modulo Arithmetic |
keep values small with modulo |
| 00756 |
Fetching from uHunt |
5.5i, Extended Euclid and CRT |
Chinese Remainder Theorem |
| 10090 |
Fetching from uHunt |
5.5i, Extended Euclid and CRT |
use solution for Linear Diophantine Equation |
| 10104 |
Fetching from uHunt |
5.5i, Extended Euclid and CRT |
pure Ext Euclid problem |
| 10633 |
Fetching from uHunt |
5.5i, Extended Euclid and CRT |
let C = N-M, N = 10a+b, and M = a; Linear Diophantine Equation: 9a+b = C |
| 10673 |
Fetching from uHunt |
5.5i, Extended Euclid and CRT |
uses Extended Euclid |
| 10922 |
Fetching from uHunt |
5.5j, Other Number Theory |
test divisibility by 9 |
| 10929 |
Fetching from uHunt |
5.5j, Other Number Theory |
test divisibility by 11 |
| 11042 |
Fetching from uHunt |
5.5j, Other Number Theory |
case analysis; only 4 possible outputs |
| 11344 |
Fetching from uHunt |
5.5j, Other Number Theory |
use divisibility theory of [1..12] |
| 11371 |
Fetching from uHunt |
5.5j, Other Number Theory |
the solving strategy is given |
| 01636 |
Fetching from uHunt |
5.6a, Probability, Easier |
LA 4596 - NorthEasternEurope09; ad hoc probability question, one tricky special case involving all zeroes |
| 10238 |
Fetching from uHunt |
5.6a, Probability, Easier |
DP; s: (dice_left, score); try F values; Big Integer; no need to simplify the fraction; see UVa 10759 |
| 10328 |
Fetching from uHunt |
5.6a, Probability, Easier |
DP; 1-D state; Big Integer |
| 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 |
| 10759 |
Fetching from uHunt |
5.6a, Probability, Easier |
DP; s: (dice_left; score); try 6 values; gcd; similar to UVa 10238 |
| 11181 |
Fetching from uHunt |
5.6a, Probability, Easier |
iterative brute force; try all possibilities |
| 12024 |
Fetching from uHunt |
5.6a, Probability, Easier |
derangement |
| 12114 |
Fetching from uHunt |
5.6a, Probability, Easier |
simple probability |
| 12230 |
Fetching from uHunt |
5.6a, Probability, Easier |
simple expected value problem |
| 12457 |
Fetching from uHunt |
5.6a, Probability, Easier |
simple expected value problem; use DP |
| 12461 |
Fetching from uHunt |
5.6a, Probability, Easier |
brute force small n to see that the answer is very easy |
| 00542 |
Fetching from uHunt |
5.6b, Probability, Harder |
divide and conquer |
| 00557 |
Fetching from uHunt |
5.6b, Probability, Harder |
one possible solution involves combinatorics which can be computed with DP |
| 10056 |
Fetching from uHunt |
5.6b, Probability, Harder |
get the closed form formula |
| 10218 |
Fetching from uHunt |
5.6b, Probability, Harder |
probability and a bit of binomial coefficients |
| 10648 |
Fetching from uHunt |
5.6b, Probability, Harder |
DP; s: (rem_boxes; num_empty) |
| 10777 |
Fetching from uHunt |
5.6b, Probability, Harder |
expected value |
| 11021 |
Fetching from uHunt |
5.6b, Probability, Harder |
probability |
| 11176 |
Fetching from uHunt |
5.6b, Probability, Harder |
DP, s: (rem_games, streak); t: lose this game, or win the next W = [1..n] games and lose the (W+1)-th game |
| 11346 |
Fetching from uHunt |
5.6b, Probability, Harder |
a bit of geometry |
| 11500 |
Fetching from uHunt |
5.6b, Probability, Harder |
Gambler's Ruin Problem |
| 11628 |
Fetching from uHunt |
5.6b, Probability, Harder |
p[i] = ticket bought by i at the last round/total tickets bought at the last round by all n; gcd |
| 11762 |
Fetching from uHunt |
5.6b, Probability, Harder |
use Sieve of Eratosthenes to know the rank of each prime number; DP; expected value |
| 00202 |
Fetching from uHunt |
5.7a, Cycle Finding |
do expansion digit by digit until it cycles |
| 00275 |
Fetching from uHunt |
5.7a, Cycle Finding |
similar to UVa 202 except the output format |
| 00350 |
Fetching from uHunt |
5.7a, Cycle Finding |
very basic cycle-finding problem; simply run Floyd's cycle-finding algorithm |
| 00408 |
Fetching from uHunt |
5.7a, Cycle Finding |
cycle finding problem with easier solution: it is a good choice if step < mod and GCD(step; mod) == 1 |
| 00547 |
Fetching from uHunt |
5.7a, Cycle Finding |
a problem about 'eventually constant' sequence; similar flavor as cycle-finding |
| 00942 |
Fetching from uHunt |
5.7a, Cycle Finding |
similar to UVa 202 |
| 00944 |
Fetching from uHunt |
5.7a, Cycle Finding |
similar to UVa 10591 |
| 10162 |
Fetching from uHunt |
5.7a, Cycle Finding |
cycle after 100 steps; use Java BigInteger to read the input; precalculate |
| 10515 |
Fetching from uHunt |
5.7a, Cycle Finding |
concentrate on the last digit |
| 10591 |
Fetching from uHunt |
5.7a, Cycle Finding |
this sequence is 'eventually periodic'; similar to UVa 944 |
| 11036 |
Fetching from uHunt |
5.7a, Cycle Finding |
cycle-finding; evaluate Reverse Polish f with a stack |
| 11053 |
Fetching from uHunt |
5.7a, Cycle Finding |
cycle-finding; the answer is N-lambda |
| 11511 |
Fetching from uHunt |
5.7a, Cycle Finding |
cycle-finding on vectors; the pattern will cycle fast |
| 11549 |
Fetching from uHunt |
5.7a, Cycle Finding |
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 |
| 11634 |
Fetching from uHunt |
5.7a, Cycle Finding |
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 |
| 12464 |
Fetching from uHunt |
5.7a, Cycle Finding |
although n can be very huge; the pattern is actually cyclic; find the length of the cycle l and modulo n with l |
| 13217 |
Fetching from uHunt |
5.7a, Cycle Finding |
the given function cycles very early so we can pre-calculate the answers although $n$ is very big |
| 00847 |
Fetching from uHunt |
5.8a, Game Theory |
simulate the perfect play; also available at Kattis - amultiplicationgame |
| 10111 |
Fetching from uHunt |
5.8a, Game Theory |
Tic-Tac-Toe; minimax; backtracking |
| 10165 |
Fetching from uHunt |
5.8a, Game Theory |
Nim game; application of Sprague-Grundy theorem |
| 10368 |
Fetching from uHunt |
5.8a, Game Theory |
minimax; backtracking; also available at Kattis - euclidsgame |
| 10404 |
Fetching from uHunt |
5.8a, Game Theory |
2 players game; Dynamic Programming; also available at Kattis - bachetsgame |
| 10536 |
Fetching from uHunt |
5.8a, Game Theory |
model the 4*4 board and 48 possible pins as bitmask; then this is a simple two player game |
| 10578 |
Fetching from uHunt |
5.8a, Game Theory |
backtracking; try all; see who wins the game |
| 11311 |
Fetching from uHunt |
5.8a, Game Theory |
there are 4 heaps; take the Nim sum of these 4 values and if they are equal to 0, Handel loses |
| 11489 |
Fetching from uHunt |
5.8a, Game Theory |
game theory; reducible to simple math |
| 12293 |
Fetching from uHunt |
5.8a, Game Theory |
analyze the game tree of smaller instances to get the mathematical insight to solve this problem |
| 12469 |
Fetching from uHunt |
5.8a, Game Theory |
game playing; Dynamic Programming; pruning |
| 00374 |
Fetching from uHunt |
5.9a, Matrix Power |
solvable with Java BigInteger modPow; or write your own code |
| 10229 |
Fetching from uHunt |
5.9a, Matrix Power |
Fibonacci; modPow |
| 10518 |
Fetching from uHunt |
5.9a, Matrix Power |
derive the pattern of the answers for small $n$; the answer is 2*fib(n)-1; then use UVa 10229 solution |
| 10655 |
Fetching from uHunt |
5.9a, Matrix Power |
tinker with the formula until you can get a square matrix from it |
| 10870 |
Fetching from uHunt |
5.9a, Matrix Power |
form the required matrix first; power of matrix |
| 11029 |
Fetching from uHunt |
5.9a, Matrix Power |
combination of logarithmic trick to get the first three digits and 'big mod' trick to get the last three digits |
| 11486 |
Fetching from uHunt |
5.9a, Matrix Power |
model as adjacency matrix; raise the adjacency matrix to the power of N in O(log N) to get the number of paths |
| 11582 |
Fetching from uHunt |
5.9a, Matrix Power |
Pisano period: The sequence f(i)%n is periodic; use modPow |
| 12470 |
Fetching from uHunt |
5.9a, Matrix Power |
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 |
| 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 |
| 00444 |
Fetching from uHunt |
6.3a, Cipher, Easier |
each char is mapped to 2 or 3 digits |
| 00458 |
Fetching from uHunt |
6.3a, Cipher, Easier |
shift ASCII values by -7 |
| 00641 |
Fetching from uHunt |
6.3a, Cipher, Easier |
reverse the given formula and simulate |
| 00795 |
Fetching from uHunt |
6.3a, Cipher, Easier |
prepare an 'inverse mapper' |
| 00865 |
Fetching from uHunt |
6.3a, Cipher, Easier |
simple character substitution mapping |
| 01339 |
Fetching from uHunt |
6.3a, Cipher, Easier |
count character frequencies of both strings; sort and compare |
| 10019 |
Fetching from uHunt |
6.3a, Cipher, Easier |
find the pattern |
| 10222 |
Fetching from uHunt |
6.3a, Cipher, Easier |
simple decoding mechanism |
| 10851 |
Fetching from uHunt |
6.3a, Cipher, Easier |
ignore border; treat '/' as 1/0; read from bottom |
| 10878 |
Fetching from uHunt |
6.3a, Cipher, Easier |
treat space/'o' as 0/1; then it is binary to decimal conversion |
| 10896 |
Fetching from uHunt |
6.3a, Cipher, Easier |
try all possible keys; use tokenizer |
| 10921 |
Fetching from uHunt |
6.3a, Cipher, Easier |
simple conversion problem |
| 11220 |
Fetching from uHunt |
6.3a, Cipher, Easier |
follow instruction in the problem |
| 11278 |
Fetching from uHunt |
6.3a, Cipher, Easier |
map QWERTY keys to DVORAK |
| 11541 |
Fetching from uHunt |
6.3a, Cipher, Easier |
read char by char and simulate |
| 11946 |
Fetching from uHunt |
6.3a, Cipher, Easier |
ad hoc |
| 12896 |
Fetching from uHunt |
6.3a, Cipher, Easier |
simple cipher; use mapper |
| 13107 |
Fetching from uHunt |
6.3a, Cipher, Easier |
simple encode; be careful with 20-26 |
| 13145 |
Fetching from uHunt |
6.3a, Cipher, Easier |
shift alphabet values by +6 characters to read the problem statement; simple Caesar Cipher problem |
| 00245 |
Fetching from uHunt |
6.3b, Cipher, Medium |
LA 5184 - WorldFinals Nashville95; use the given algorithm |
| 00483 |
Fetching from uHunt |
6.3b, Cipher, Medium |
read char by char from left to right |
| 00492 |
Fetching from uHunt |
6.3b, Cipher, Medium |
ad hoc; similar to UVa 483 |
| 00632 |
Fetching from uHunt |
6.3b, Cipher, Medium |
simulate the process; use sorting |
| 00739 |
Fetching from uHunt |
6.3b, Cipher, Medium |
straightforward conversion problem |
| 00740 |
Fetching from uHunt |
6.3b, Cipher, Medium |
just simulate the process |
| 11716 |
Fetching from uHunt |
6.3b, Cipher, Medium |
simple cipher |
| 11787 |
Fetching from uHunt |
6.3b, Cipher, Medium |
follow the description |
| 00179 |
Fetching from uHunt |
6.3c, Cipher, Harder |
use brute force |
| 00213 |
Fetching from uHunt |
6.3c, Cipher, Harder |
LA 5152 - WorldFinals SanAntonio91; decrypt the message |
| 00306 |
Fetching from uHunt |
6.3c, Cipher, Harder |
can be made faster by avoiding cycle |
| 00385 |
Fetching from uHunt |
6.3c, Cipher, Harder |
a kind of decryption problem; tedious |
| 00468 |
Fetching from uHunt |
6.3c, Cipher, Harder |
letter frequency mapping |
| 00554 |
Fetching from uHunt |
6.3c, Cipher, Harder |
try all shifts; output formatting |
| 00726 |
Fetching from uHunt |
6.3c, Cipher, Harder |
frequency cypher |
| 00741 |
Fetching from uHunt |
6.3c, Cipher, Harder |
simulate the process |
| 00850 |
Fetching from uHunt |
6.3c, Cipher, Harder |
plaintext attack; tricky test cases |
| 00856 |
Fetching from uHunt |
6.3c, Cipher, Harder |
3 nested loops; one for each digit |
| 11385 |
Fetching from uHunt |
6.3c, Cipher, Harder |
string manipulation and Fibonacci |
| 11697 |
Fetching from uHunt |
6.3c, Cipher, Harder |
follow the description; a bit tedious; also available at Kattis - playfair |
| 00902 |
Fetching from uHunt |
6.3d, Frequency Counting |
read char by char; count word freq |
| 10008 |
Fetching from uHunt |
6.3d, Frequency Counting |
character frequency count |
| 10252 |
Fetching from uHunt |
6.3d, Frequency Counting |
count freq of each alphabet |
| 10293 |
Fetching from uHunt |
6.3d, Frequency Counting |
straightforward |
| 10374 |
Fetching from uHunt |
6.3d, Frequency Counting |
use map for frequency counting |
| 10420 |
Fetching from uHunt |
6.3d, Frequency Counting |
word frequency counting; use map |
| 10625 |
Fetching from uHunt |
6.3d, Frequency Counting |
frequency addition n times |
| 10789 |
Fetching from uHunt |
6.3d, Frequency Counting |
check if a letter's frequency is prime |
| 11203 |
Fetching from uHunt |
6.3d, Frequency Counting |
problem description is convoluted; but this problem is actually easy |
| 11577 |
Fetching from uHunt |
6.3d, Frequency Counting |
straightforward problem |
| 12626 |
Fetching from uHunt |
6.3d, Frequency Counting |
simple frequency counting problem |
| 12820 |
Fetching from uHunt |
6.3d, 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] |
| 00271 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
grammar check; linear scan |
| 00327 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
implementation can be tricky |
| 00391 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
use flags; tedious parsing |
| 00397 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
iteratively perform the next operation |
| 00442 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
properties of matrix chain multiplication |
| 00486 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
parsing |
| 00537 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
simple formula; parsing is difficult |
| 01200 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
LA 2972 - Tehran03; the hard part is to parse and tokenize the linear equation |
| 10906 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
BNF parsing; iterative solution |
| 11148 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
extract integers; simple/mixed fractions from a line; a bit of gcd |
| 11878 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
expression parsing |
| 12543 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
LA 6150 - HatYai12; iterative parser |
| 13047 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
simple parsing; left-to-right or right-to-left checks |
| 13093 |
Fetching from uHunt |
6.3e, Input Parsing (Iterative) |
simple string tokenize; take first characters of each word |
| 00134 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar check; tedious |
| 00171 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar check; tedious |
| 00172 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
another recursive parser; tedious |
| 00384 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar check |
| 00464 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
generate output based on the given BNF grammar |
| 00533 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar check |
| 00586 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar check and output formatting |
| 00620 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar check |
| 00622 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar check/evaluation |
| 00743 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar check |
| 10854 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive parsing plus counting |
| 11070 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar evaluation |
| 11291 |
Fetching from uHunt |
6.3f, Input Parsing (Recursive) |
recursive grammar check |
| 00325 |
Fetching from uHunt |
6.3g, Regular Expression |
trivial with regex |
| 00494 |
Fetching from uHunt |
6.3g, Regular Expression |
trivial with regex |
| 00576 |
Fetching from uHunt |
6.3g, Regular Expression |
solvable with regex |
| 10058 |
Fetching from uHunt |
6.3g, Regular Expression |
solvable with regex |
| 00110 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
actually an ad hoc sorting problem |
| 00320 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
requires flood fill technique |
| 00445 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
simulation; output formatting |
| 00488 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
use several loops |
| 00490 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
2d array manipulation; output formatting |
| 01605 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
LA 4044 - NortheasternEurope07; we can answer this problem with just h=2 levels |
| 10146 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
the problem description tries to hide the meaning of 'dictionary'; it is not a hard problem actually |
| 10500 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
simulate; output formatting |
| 10894 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
how fast can you can solve this problem? |
| 11074 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
output formatting |
| 11482 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
tedious |
| 11965 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
replace consecutive spaces with only one space |
| 12364 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
2D array check; check all possible digits [0..9] |
| 13091 |
Fetching from uHunt |
6.3h, Output Formatting, Easier |
just output formatting |
| 00159 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
tedious output formatting problem |
| 00330 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
use map to help |
| 00338 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
tedious |
| 00373 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
check 'g' versus 'p'; ad hoc |
| 00426 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
tokenize; sort; reformat output |
| 00570 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
use map to help |
| 00645 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
use recursion to simulate directory structure as it helps the output formatting |
| 00848 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
tedious string processing |
| 00890 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
simulation; follow the steps; tedious |
| 00918 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
tedious; follow the steps |
| 01219 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
LA 3791 - Tehran06 |
| 10333 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
a real time waster problem |
| 10562 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
output formatting with clever recursion |
| 10761 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
tricky with output formatting; note that 'END' is part of input |
| 10800 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
tedious problem |
| 10875 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
simple but tedious problem |
| 11403 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
similar with UVa 00338; tedious |
| 12155 |
Fetching from uHunt |
6.3i, Output Formatting, Harder |
LA 4403 - KualaLumpur08; use proper index manipulation |
| 00409 |
Fetching from uHunt |
6.3j, String Comparison |
tokenize and compare with list of excuses |
| 00644 |
Fetching from uHunt |
6.3j, String Comparison |
use brute force |
| 00671 |
Fetching from uHunt |
6.3j, String Comparison |
string comparison |
| 00912 |
Fetching from uHunt |
6.3j, String Comparison |
simulation; find and replace |
| 11048 |
Fetching from uHunt |
6.3j, String Comparison |
flexible string comparison with respect to a dictionary |
| 11056 |
Fetching from uHunt |
6.3j, String Comparison |
sorting; case-insensitive string comparison |
| 11233 |
Fetching from uHunt |
6.3j, String Comparison |
string comparison |
| 11713 |
Fetching from uHunt |
6.3j, String Comparison |
modified string comparison |
| 11734 |
Fetching from uHunt |
6.3j, String Comparison |
custom comparison |
| 00153 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
find formula for this; similar with UVa 941 |
| 00263 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
sort digits; convert to integers; check cycle |
| 00892 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
basic string processing problem |
| 00941 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
formula to get the n-th permutation |
| 00943 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
the Portuguese rule is not given; use translation service in the Internet to help you solve this problem |
| 01215 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
LA 3669 - Hanoi06 |
| 10045 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
brute force string processing |
| 10115 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
simply do as asked in the problem description; uses string |
| 10126 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
sort the words to simplify this problem; also available at Kattis - zipfslaw |
| 10197 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
must follow the description very closely |
| 10361 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
read; tokenize; process as requested |
| 10391 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
more like a data structure problem |
| 10393 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
follow problem description |
| 10508 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
number of words = number of letters plus 1 |
| 10679 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
the test data weak; just checking if T is a prefix of S is AC when it should not |
| 11452 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
string period; small input; brute force |
| 11483 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
straightforward; use 'escape character' |
| 11839 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
illegal if mark 0 or >1 alternatives |
| 11962 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
find formula; similar to UVa 941; base 4 |
| 12243 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
simple string tokenizer problem |
| 12414 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
brute force problem involving string |
| 12916 |
Fetching from uHunt |
6.3k, Really Ad Hoc |
factorize n; string period; also see UVa 11452 |
| 00455 |
Fetching from uHunt |
6.4a, String Matching, Standard |
find s in concatenate(s; s); similar with UVa 10298 |
| 00886 |
Fetching from uHunt |
6.4a, String Matching, Standard |
convert first letter of given name and all the letters of the surname into digits; special string matching where we want the matching to start at the prefix of a string |
| 01449 |
Fetching from uHunt |
6.4a, String Matching, Standard |
LA 4670 - Hefei09; just use strstr; Suffix Array will get TLE as there are too many long strings to be processed |
| 10298 |
Fetching from uHunt |
6.4a, String Matching, Standard |
find s in s+s; similar with UVa 00455; also available at Kattis - powerstrings |
| 11362 |
Fetching from uHunt |
6.4a, String Matching, Standard |
string sort; matching |
| 11475 |
Fetching from uHunt |
6.4a, String Matching, Standard |
similar with UVa 12467 although this problem involves palindrome, it involves 'border' of KMP |
| 11576 |
Fetching from uHunt |
6.4a, String Matching, Standard |
modified string matching; complete search; also available at Kattis - scrollingsign |
| 11837 |
Fetching from uHunt |
6.4a, String Matching, Standard |
transform the input of X notes into X-1 distances; then apply KMP |
| 12467 |
Fetching from uHunt |
6.4a, String Matching, Standard |
'border' of KMP; also see UVa 11475 |
| 00422 |
Fetching from uHunt |
6.4b, String Matching, 2D Grid |
2D grid; backtracking |
| 00604 |
Fetching from uHunt |
6.4b, String Matching, 2D Grid |
2D grid; backtracking; sort and compare |
| 00736 |
Fetching from uHunt |
6.4b, String Matching, 2D Grid |
2D grid; a bit modified |
| 10010 |
Fetching from uHunt |
6.4b, String Matching, 2D Grid |
2D grid; backtracking |
| 11283 |
Fetching from uHunt |
6.4b, String Matching, 2D Grid |
2D grid; backtracking; do not count twice |
| 00164 |
Fetching from uHunt |
6.5a, DP String, Classic |
String Alignment/Edit Distance |
| 00526 |
Fetching from uHunt |
6.5a, DP String, Classic |
String Alignment/Edit Distance |
| 00531 |
Fetching from uHunt |
6.5a, DP String, Classic |
Longest Common Subsequence; print the solution |
| 01192 |
Fetching from uHunt |
6.5a, DP String, Classic |
LA2460 - Singapore01; classic String Alignment DP problem with a bit of (unclear) output formatting |
| 01207 |
Fetching from uHunt |
6.5a, DP String, Classic |
LA 3170 - Manila06; classical String Edit problem |
| 01244 |
Fetching from uHunt |
6.5a, DP String, Classic |
LA 4336 - Amritapuri08; store the best path between i; j; the DP table contains strings |
| 10066 |
Fetching from uHunt |
6.5a, DP String, Classic |
Longest Common Subsequence problem; but not on 'string' |
| 10100 |
Fetching from uHunt |
6.5a, DP String, Classic |
Longest Common Subsequence |
| 10192 |
Fetching from uHunt |
6.5a, DP String, Classic |
Longest Common Subsequence |
| 10405 |
Fetching from uHunt |
6.5a, DP String, Classic |
very classic Longest Common Subsequence problem |
| 10635 |
Fetching from uHunt |
6.5a, DP String, Classic |
find LCS of two permutations; also available at Kattis - princeandprincess |
| 12747 |
Fetching from uHunt |
6.5a, DP String, Classic |
similar to UVa 10635 |
| 13146 |
Fetching from uHunt |
6.5a, DP String, Classic |
classic Edit Distance problem |
| 11022 |
Fetching from uHunt |
6.5b, DP String, Non Classic |
s: the min weight of substring [i..j]; also available at Kattis - stringfactoring |
| 11081 |
Fetching from uHunt |
6.5b, DP String, Non Classic |
DP on string; s: (t; i; j; k) |
| 11084 |
Fetching from uHunt |
6.5b, DP String, Non Classic |
using next_permutation/brute force is probably not the best approach; there is a DP formulation for this |
| 11258 |
Fetching from uHunt |
6.5b, DP String, Non Classic |
dp(i) = int from substring [i..k] dp(k) |
| 11361 |
Fetching from uHunt |
6.5b, DP String, Non Classic |
counting paths in DAG; need insights for efficient implementation; K > 90 is useless; double DP; use prefix-sum idea |
| 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 |
| 12855 |
Fetching from uHunt |
6.5b, DP String, Non Classic |
s: (pos, len) that describes the cost to transform the string so that S[0..pos-1] are all already 'B's and S[pos..pos+len] will be transformed to Bs |
| 00719 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
min lexicographic rotation; O(n log n) build SA |
| 00760 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
Longest Common Substring of two strings |
| 01223 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
LA 3901 - Seoul07; Longest Repeated Substring (or KMP) |
| 01254 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
LA 4657 - Jakarta09; Suffix Array with Segment Tree |
| 01584 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
LA 3225 - Seoul04; min lexicographic rotation; similar with UVa 00719; other solutions exist |
| 11107 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
Longest Common Substring of > 1/2 of the strings; also available at Kattis - lifeforms |
| 11512 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
Longest Repeated Substring |
| 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 |
| 12506 |
Fetching from uHunt |
6.6a, Suffix Trie/Tree/Array |
we can use Trie to solve this problem |
| 00152 |
Fetching from uHunt |
7.2a, Points |
sort the 3D points first |
| 00587 |
Fetching from uHunt |
7.2a, Points |
Euclidean dist |
| 00920 |
Fetching from uHunt |
7.2a, Points |
Euclidean dist |
| 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? |
| 10357 |
Fetching from uHunt |
7.2a, Points |
Euclidean dist; simple Physics simulation |
| 10466 |
Fetching from uHunt |
7.2a, Points |
Euclidean dist |
| 10585 |
Fetching from uHunt |
7.2a, Points |
sort the points |
| 10832 |
Fetching from uHunt |
7.2a, Points |
3D Euclidean distance; simulation |
| 10865 |
Fetching from uHunt |
7.2a, Points |
points and quadrants; simple; also available at Kattis - browniepoints |
| 10927 |
Fetching from uHunt |
7.2a, Points |
sort points by gradient; Euclidean dist |
| 11012 |
Fetching from uHunt |
7.2a, Points |
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) |
| 11505 |
Fetching from uHunt |
7.2a, Points |
Euclidean dist; also available at Kattis - logo |
| 11894 |
Fetching from uHunt |
7.2a, Points |
about rotating and translating points |
| 12704 |
Fetching from uHunt |
7.2a, Points |
circle; radius; but eventually just about computing Euclidean distance |
| 00191 |
Fetching from uHunt |
7.2b, Lines |
line segment intersection |
| 00378 |
Fetching from uHunt |
7.2b, Lines |
library routines: areParallel; areSame; areIntersect |
| 00833 |
Fetching from uHunt |
7.2b, Lines |
recursive check; use the ccw tests |
| 00837 |
Fetching from uHunt |
7.2b, Lines |
line segments; sort x-coords first |
| 00866 |
Fetching from uHunt |
7.2b, Lines |
use line segment intersection library; O(n^2) solution can pass |
| 01249 |
Fetching from uHunt |
7.2b, Lines |
LA 4601 - SoutheastUSA09; vector |
| 10242 |
Fetching from uHunt |
7.2b, Lines |
toVector; translate points w.r.t that vector |
| 10250 |
Fetching from uHunt |
7.2b, Lines |
vector; rotation |
| 10263 |
Fetching from uHunt |
7.2b, Lines |
use distToLineSegment |
| 10902 |
Fetching from uHunt |
7.2b, Lines |
line segment intersection |
| 11068 |
Fetching from uHunt |
7.2b, Lines |
simple 2 linear equations with 2 unknowns |
| 11343 |
Fetching from uHunt |
7.2b, Lines |
line segment intersection |
| 11519 |
Fetching from uHunt |
7.2b, Lines |
n vectors that sum to 0; given n-1 vectors, find the unknown vector; also available at Kattis - logo2 |
| 11783 |
Fetching from uHunt |
7.2b, Lines |
O(N^2) brute force line segment intersection tests |
| 13117 |
Fetching from uHunt |
7.2b, Lines |
dist + distToLineSegment |
| 01388 |
Fetching from uHunt |
7.2c, Circles |
LA 3708 - NortheasternEurope06; divide the circle into n sectors first and then into (n m) sectors |
| 10005 |
Fetching from uHunt |
7.2c, Circles |
complete search; use circle2PtsRad |
| 10136 |
Fetching from uHunt |
7.2c, Circles |
complete search; use circle2PtsRad; similar with UVa 10005 |
| 10180 |
Fetching from uHunt |
7.2c, Circles |
closest point from AB to origin; arc |
| 10209 |
Fetching from uHunt |
7.2c, Circles |
square; arcs; similar with UVa 10589 |
| 10221 |
Fetching from uHunt |
7.2c, Circles |
finding arc and chord length of a circle |
| 10283 |
Fetching from uHunt |
7.2c, Circles |
derive the formula |
| 10287 |
Fetching from uHunt |
7.2c, Circles |
derive the formula |
| 10432 |
Fetching from uHunt |
7.2c, Circles |
simple problem: area of n-sided reg-polygon in a circle |
| 10451 |
Fetching from uHunt |
7.2c, Circles |
inner/outer circle of n-sided reg polygon |
| 10573 |
Fetching from uHunt |
7.2c, Circles |
there is no 'impossible' case |
| 10589 |
Fetching from uHunt |
7.2c, Circles |
check if point is inside intersection of 4 circles |
| 10678 |
Fetching from uHunt |
7.2c, Circles |
area of an ellipse; generalization of the formula for area of a circle |
| 12578 |
Fetching from uHunt |
7.2c, Circles |
area of rectangle and circle |
| 12748 |
Fetching from uHunt |
7.2c, Circles |
brute force and simple in-circle test |
| 00313 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
use trigonometry to project the light to the ground through the pipes; sort the intervals; merge overlapping intervals; if any |
| 00427 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
for each 2 consecutive corridors, try rotating the piano by a angle α ∈ [0.1..89.9] degrees; trigonometry |
| 10210 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
basic trigonometry |
| 10286 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
Law of Sines |
| 10387 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
expanding surface; trigonometry |
| 10792 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
derive the trigonometry formulas |
| 11326 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
trigonometry; tangent; reflection trick |
| 11854 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
Pythagorean theorem/triple; also available at Kattis - egypt |
| 11909 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
Law of Sines (or tangent); two possible cases |
| 12901 |
Fetching from uHunt |
7.2d, Triangles (Trigonometry) |
tangent, sine, arcsin, etc |
| 00143 |
Fetching from uHunt |
7.2e, Triangles + Circles |
count integer points in triangle; beware of precision issue |
| 00190 |
Fetching from uHunt |
7.2e, Triangles + Circles |
triangle's circumcircle |
| 00375 |
Fetching from uHunt |
7.2e, Triangles + Circles |
triangle'sincircles |
| 00438 |
Fetching from uHunt |
7.2e, Triangles + Circles |
compute triangle's circumcircle |
| 10195 |
Fetching from uHunt |
7.2e, Triangles + Circles |
triangle'sincircle; Heron's formula |
| 10347 |
Fetching from uHunt |
7.2e, Triangles + Circles |
given 3 medians of a triangle; find its area |
| 10522 |
Fetching from uHunt |
7.2e, Triangles + Circles |
derive the formula; uses Heron's formula |
| 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 |
| 10991 |
Fetching from uHunt |
7.2e, Triangles + Circles |
Heron's formula; Law of Cosines; area of sector |
| 11152 |
Fetching from uHunt |
7.2e, Triangles + Circles |
triangle's (in/circum)circle; Heron's formula |
| 11164 |
Fetching from uHunt |
7.2e, Triangles + Circles |
use Triangle properties |
| 11281 |
Fetching from uHunt |
7.2e, Triangles + Circles |
circumcircle for a non obtuse triangle; largest side of the triangle for an obtuse triangle |
| 11437 |
Fetching from uHunt |
7.2e, Triangles + Circles |
hint: 1/7 |
| 11479 |
Fetching from uHunt |
7.2e, Triangles + Circles |
property check |
| 11579 |
Fetching from uHunt |
7.2e, Triangles + Circles |
sort; greedily check if three successive sides satisfy triangle inequality and if it is the largest triangle found so far |
| 11936 |
Fetching from uHunt |
7.2e, Triangles + Circles |
see if 3 sides form a valid triangle |
| 13215 |
Fetching from uHunt |
7.2e, Triangles + Circles |
area of rectangle minus area of squares and equilateral triangles |
| 00155 |
Fetching from uHunt |
7.2f, Quadrilaterals |
recursive counting |
| 00209 |
Fetching from uHunt |
7.2f, Quadrilaterals |
LA 5148 - WorldFinals SanAntonio91; brute force check; answer is either triangle, parallelogram, or hexagon |
| 00460 |
Fetching from uHunt |
7.2f, Quadrilaterals |
rectangle-rectangle intersection |
| 00476 |
Fetching from uHunt |
7.2f, Quadrilaterals |
basic problem; also see related problems: UVa 00477 and 00478 |
| 00477 |
Fetching from uHunt |
7.2f, Quadrilaterals |
similar with UVa 00476 and 00478 |
| 11207 |
Fetching from uHunt |
7.2f, Quadrilaterals |
cutting rectangle into 4-equal-sized squares |
| 11314 |
Fetching from uHunt |
7.2f, Quadrilaterals |
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 |
| 11345 |
Fetching from uHunt |
7.2f, Quadrilaterals |
rectangle-rectangle intersection |
| 11455 |
Fetching from uHunt |
7.2f, Quadrilaterals |
property check |
| 11639 |
Fetching from uHunt |
7.2f, Quadrilaterals |
rectangle-rectangle intersection; use flag array |
| 11648 |
Fetching from uHunt |
7.2f, Quadrilaterals |
derive the closed form formula |
| 11800 |
Fetching from uHunt |
7.2f, Quadrilaterals |
use next_permutation to try all possible 4! = 24 permutations of 4 points; check the requirements |
| 11834 |
Fetching from uHunt |
7.2f, Quadrilaterals |
packing two circles in a rectangle |
| 12256 |
Fetching from uHunt |
7.2f, Quadrilaterals |
LA 5001 - KualaLumpur10; first 3 sides are 1, 1, 1; the 4th side onwards are sum of previous threes |
| 12611 |
Fetching from uHunt |
7.2f, Quadrilaterals |
a problem involving a rectangle and a circle |
| 12894 |
Fetching from uHunt |
7.2f, Quadrilaterals |
continuation of UVa 12611; another problem involving a rectangle and a circle |
| 00478 |
Fetching from uHunt |
7.3a, Polygon, Easier |
inPolygon/Triangle/Circle/Rectangle |
| 00634 |
Fetching from uHunt |
7.3a, Polygon, Easier |
basic inPolygon routine; notice that the input polygon can be convex or concave |
| 00681 |
Fetching from uHunt |
7.3a, Polygon, Easier |
CH; with output formatting |
| 01206 |
Fetching from uHunt |
7.3a, Polygon, Easier |
LA 3169 - Manila06; CH; input is formatted in complex manner |
| 10060 |
Fetching from uHunt |
7.3a, Polygon, Easier |
area of polygon; area of circle |
| 10112 |
Fetching from uHunt |
7.3a, Polygon, Easier |
test if point inPolygon/inTriangle; similar with UVa 478 |
| 11072 |
Fetching from uHunt |
7.3a, Polygon, Easier |
find CH and then check if the query point inside is inside the convex hull |
| 11096 |
Fetching from uHunt |
7.3a, Polygon, Easier |
very classic CH problem; perimeter of polygon |
| 11447 |
Fetching from uHunt |
7.3a, Polygon, Easier |
area of polygon |
| 11473 |
Fetching from uHunt |
7.3a, Polygon, Easier |
modified perimeter of polygon |
| 11626 |
Fetching from uHunt |
7.3a, Polygon, Easier |
find CH; be careful with collinear points |
| 00109 |
Fetching from uHunt |
7.3b, Polygon, Harder |
find CH; test if point inPolygon; compute area of polygon |
| 00132 |
Fetching from uHunt |
7.3b, Polygon, Harder |
brute force as instructed in problem description; use polygon routines |
| 00137 |
Fetching from uHunt |
7.3b, Polygon, Harder |
convex polygon intersection; line segment intersection; inPolygon; CH; area; inclusion-exclusion principle |
| 00218 |
Fetching from uHunt |
7.3b, Polygon, Harder |
LA 5157 - WorldFinals KansasCity92; find CH; perimeter of polygon |
| 00361 |
Fetching from uHunt |
7.3b, Polygon, Harder |
check if a point is inside CH of Cop/Robber; if $pt$ is inside CH, pt satisfies the requirement |
| 00596 |
Fetching from uHunt |
7.3b, Polygon, Harder |
basic CH problem; but output formatting is a bit tedious |
| 00858 |
Fetching from uHunt |
7.3b, Polygon, Harder |
vertical line and polygon intersection; sort; alternating segments |
| 01111 |
Fetching from uHunt |
7.3b, Polygon, Harder |
LA 5138 - WorldFinals Orlando11; CH; output minimax distance of each CH side to the other vertices |
| 10002 |
Fetching from uHunt |
7.3b, Polygon, Harder |
centroid; center of CH; area of polygon |
| 10065 |
Fetching from uHunt |
7.3b, Polygon, Harder |
find area of polygon; the CH; then area of CH |
| 10256 |
Fetching from uHunt |
7.3b, Polygon, Harder |
given 2 CHs, output 'No' if there is a point in 1st CH inside the 2nd one; 'Yes' otherwise |
| 10406 |
Fetching from uHunt |
7.3b, Polygon, Harder |
vector; rotate; translate; then cutPolygon |
| 10445 |
Fetching from uHunt |
7.3b, Polygon, Harder |
angle checks; use library code; some corner cases exist |
| 10652 |
Fetching from uHunt |
7.3b, Polygon, Harder |
rotate; translate; CH; area; also available at Kattis - wrapping |
| 11265 |
Fetching from uHunt |
7.3b, Polygon, Harder |
seems to be a complex problem; but essentially just cutPolygon; inPolygon; area |
| 00131 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
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 |
| 00211 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
map the complex bone IDs to pips using 2D array; use backtracking to try the placement of various domino bones |
| 00387 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
use backtracking to try placement of various puzzle pieces |
| 00710 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
backtracking with memoization/pruning |
| 00711 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
backtracking with pruning |
| 01052 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
LA 3565 - WorldFinals SanAntonio06; backtracking with some form of bitmask |
| 10202 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
backtracking; pruning |
| 10309 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
brute force the first row in 2^10; the rest follows |
| 10318 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
the order is not important, so we can try pressing the buttons in increasing order, row by row, column by column |
| 10890 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
looks like a DP problem but the state---involving bitmask---cannot be memoized; fortunately the grid size is small |
| 11127 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
backtracking with bitmask |
| 11195 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
use backtracking with bitmask |
| 11451 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
the input constraints are small; backtracking with bitmask without memoization; or use DP |
| 11464 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
brute force the first row in 2^15; the rest follows |
| 11471 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
reduce search space by grouping tiles of the same type; recursive backtracking |
| 11699 |
Fetching from uHunt |
8.2a, Challenging Backtracking |
try all the possible row combinations on which we put rooks and keep the best |
| 00298 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
s: (row; col; 49 possible speeds) |
| 00928 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
s: (row; col; direction; step) |
| 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 |
| 10047 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
s: (row, col, dir, color) |
| 10097 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
s: (N1; N2); implicit unweighted graph |
| 10306 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
s: (conventional-value, infotechnological value); BFS; also available at Kattis - ecoins |
| 10682 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
s: (current_city; current_speed); output path |
| 11513 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
reverse the role of source and destination |
| 11974 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
BFS on implicit unweighted graph |
| 12135 |
Fetching from uHunt |
8.2b, State-Space, BFS, Easier |
LA 4201 - Dhaka08; similar with UVa 11974 |
| 00321 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
s: (position; bitmask 2^10); print the path |
| 00704 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
state-space search; use meet-in-the-middle to bring down 4^16 to 2*4^8 |
| 00816 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
LA 5216 - WorldFinals Orlando00; build the graph; then run BFS with state s: (row; col; dir) |
| 00985 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
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 |
| 01251 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
LA 4637 - Tokyo09 |
| 01253 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
LA 4645 - Tokyo09; tedious state modeling |
| 01714 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
LA 7155 - WorldFinals Marrakech15; s: (row, col, char_typed); also available at Kattis - keyboard |
| 10021 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
s: (row; col; cube position; which is a permutation of 6 sides) or up to 10*10*720 = 72000 distinct states |
| 10085 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
each vertex is the 9 puzzle configuration; BFS from starting configuration to all vertices; print longest shortest path |
| 11160 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
s: (rA; cA; rB; cB; rC; cC); move A; B; C together |
| 11198 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
s: (permutation); tricky to code |
| 11212 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
meet in the middle |
| 11329 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
s: (bitmask); 4 bits for die position; 16 bits for cells with fleas; 6 bits for side with a flea; use map; tedious |
| 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 |
| 12569 |
Fetching from uHunt |
8.2c, State-Space, BFS, Harder |
s: (robot_pos, obstacle_mask); BFS |
| 00658 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
s: (bitmask---whether a bug is present or not); the state-space graph is weighted |
| 01048 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
LA 3561 - WorldFinals SanAntonio06; tedious state-space search problem; use Dijkstra's |
| 01057 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
LA 3570 - WorldFinals SanAntonio06; Floyd Warshall's; APSP; reduce to weighted SSSP problem; Dijkstra's |
| 10269 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
use Floyd Warshall's to pre-compute APSP using only Villages; use Dijkstra's on s: (u, super_run_left) |
| 10923 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
s: (ship_position; location_of_enemies; location_of_obstacles; steps_so_far); implicit weighted graph |
| 11374 |
Fetching from uHunt |
8.2d, State-Space, Dijkstra |
each vertex has one more parameter: has the Commercial-Xpress ticket been used? |
| 00672 |
Fetching from uHunt |
8.3a, DP level 3 |
s: (gangster_id, openness_level); do not use cur_time as part of the state |
| 00882 |
Fetching from uHunt |
8.3a, DP level 3 |
s: (lo, hi, mailbox_left); try all; also available at Kattis - mailbox |
| 01172 |
Fetching from uHunt |
8.3a, DP level 3 |
LA 3986 - SouthWesternEurope07; weighted bipartite matching with additional constraints |
| 01211 |
Fetching from uHunt |
8.3a, DP level 3 |
LA 3404 - Tokyo05; precompute T[L], the time to run a path of length L; s: (i) - checkpoint i is we change tire |
| 10163 |
Fetching from uHunt |
8.3a, DP level 3 |
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 |
| 10604 |
Fetching from uHunt |
8.3a, DP level 3 |
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 |
| 10645 |
Fetching from uHunt |
8.3a, DP level 3 |
s: (days_left, budget_left, prev_dish, prev_dish_cnt); the first 2 params are knapsack-style; the last 2 params to determine price |
| 10898 |
Fetching from uHunt |
8.3a, DP level 3 |
similar to DP bitmask; store state as integer |
| 11002 |
Fetching from uHunt |
8.3a, DP level 3 |
a simple DP; use negative offset technique |
| 11285 |
Fetching from uHunt |
8.3a, DP level 3 |
maintain the best CAD and USD each day; also available at Kattis - exchangerates |
| 11523 |
Fetching from uHunt |
8.3a, DP level 3 |
each part between non-recyclable items must be solved separately; for each part; use O(n^3) DP |
| 11555 |
Fetching from uHunt |
8.3a, DP level 3 |
sort; compute tree positions; s: (l_left, r_left), t: put next tree on the left/right; also available at Kattis - aspenavenue |
| 12208 |
Fetching from uHunt |
8.3a, DP level 3 |
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 |
| 12563 |
Fetching from uHunt |
8.3a, DP level 3 |
knapsack style DP; sing or skip a song; special base case; memo of pairs |
| 00473 |
Fetching from uHunt |
8.3b, DP level 4 |
the input constraint is not clear; therefore use resizeable vector and compact states |
| 00812 |
Fetching from uHunt |
8.3b, DP level 4 |
LA 5212 - WorldFinals Eindhoven99; mix between greedy and DP |
| 01222 |
Fetching from uHunt |
8.3b, DP level 4 |
LA 3797 - Tehran06; DP on Tree |
| 01231 |
Fetching from uHunt |
8.3b, DP level 4 |
LA 4106 - Singapore07; dimension reduction |
| 01238 |
Fetching from uHunt |
8.3b, DP level 4 |
LA 4143 - Jakarta08; offset technique |
| 10029 |
Fetching from uHunt |
8.3b, DP level 4 |
use map as memo table |
| 10118 |
Fetching from uHunt |
8.3b, DP level 4 |
DP bitmask; not trivial |
| 10304 |
Fetching from uHunt |
8.3b, DP level 4 |
classical DP; requires 1D range sum and Knuth-Yao speed up to get O(n^2) solution |
| 10482 |
Fetching from uHunt |
8.3b, DP level 4 |
drop one parameter to save memory |
| 10559 |
Fetching from uHunt |
8.3b, DP level 4 |
DP with clever state and transitions |
| 10626 |
Fetching from uHunt |
8.3b, DP level 4 |
drop parameter n1; recover it from b (number of coke bought), n5, and n10; also available at Kattis - coke |
| 12870 |
Fetching from uHunt |
8.3b, DP level 4 |
LA 6848 - Bangkok14; split DP for fishing and nourishing; try all combination of K fishing + 2K nourishing events |
| 00702 |
Fetching from uHunt |
8.3c, Counting Paths, Harder |
s: (n_above, n_below, go_up) |
| 10722 |
Fetching from uHunt |
8.3c, Counting Paths, Harder |
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 |
| 11125 |
Fetching from uHunt |
8.3c, Counting Paths, Harder |
counting paths in implicit DAG; the implicit DAG is not trivial; 8 parameters |
| 11133 |
Fetching from uHunt |
8.3c, Counting Paths, Harder |
counting paths in DAG; the implicit DAG is not trivial; 2 parameters |
| 11375 |
Fetching from uHunt |
8.3c, Counting Paths, Harder |
counting paths in DAG; 2 parameters; be careful that we can create a 0 with 6 sticks; need to use Java BigInteger |
| 11432 |
Fetching from uHunt |
8.3c, Counting Paths, Harder |
counting paths in DAG; the implicit DAG is not trivial; 6 parameters |
| 12063 |
Fetching from uHunt |
8.3c, Counting Paths, Harder |
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 |
| 01076 |
Fetching from uHunt |
8.3d, DP with Bitmask |
LA 4126 - WorldFinals Banff08; preprocess the strings; challenging DP bitmask; output up to 42 possible solutions |
| 01099 |
Fetching from uHunt |
8.3d, DP with Bitmask |
LA 4794 - WorldFinals Harbin10; s: (w; bitmask); recover parameter value h |
| 01240 |
Fetching from uHunt |
8.3d, DP with Bitmask |
LA 4146 - Jakarta08; a medium-level DP problem |
| 01252 |
Fetching from uHunt |
8.3d, DP with Bitmask |
LA 4643 - Tokyo09; DP, s: (mask1, mask2) where mask1/mask2 describes the features/answers, respectively |
| 10123 |
Fetching from uHunt |
8.3d, DP with Bitmask |
DP; s: (bitmask) that describes objects that have been taken; use Physics to determine whether those taken objects will cause the tipping or not |
| 10149 |
Fetching from uHunt |
8.3d, DP with Bitmask |
DP with bitmask; uses card rules; tedious |
| 10364 |
Fetching from uHunt |
8.3d, DP with Bitmask |
bitmask technique can be used |
| 10817 |
Fetching from uHunt |
8.3d, DP with Bitmask |
s: (id; bitmask) |
| 10911 |
Fetching from uHunt |
8.3d, DP with Bitmask |
the intro problem of this book; DP with bitmask; weighted MCM; small complete weighted graph |
| 11218 |
Fetching from uHunt |
8.3d, DP with Bitmask |
still solvable with complete search |
| 11391 |
Fetching from uHunt |
8.3d, DP with Bitmask |
counting paths in DAG; the implicit DAG is not trivial; 3 parameters with 1 bitmask parameter that describes the 2D grid |
| 11472 |
Fetching from uHunt |
8.3d, DP with Bitmask |
counting paths in DAG; the implicit DAG is not trivial; 4 parameters with 1 bitmask parameter |
| 11806 |
Fetching from uHunt |
8.3d, DP with Bitmask |
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 |
| 11825 |
Fetching from uHunt |
8.3d, DP with Bitmask |
first; use iterative brute force: try which subset of vertices can cover all vertices; then use DP to figure out the best possible attacks |
| 12030 |
Fetching from uHunt |
8.3d, DP with Bitmask |
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' |
| 00259 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
assignment problem; matching with capacity; similar to UVa 10092; 11045; and 12873; but actually the input constraint is actually small enough for recursive backtracking |
| 00820 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
LA 5220 - WorldFinals Orlando00; very basic max flow problem |
| 10092 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
assignment problem; matching with capacity; similar to UVa 259; 11045; and 12873 |
| 10511 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
matching; max flow; print the assignment; also available at Kattis - councilling |
| 10779 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
build a flow graph s.t. each augmenting path corresponds to a series of exchange of duplicate stickers; repeat until this is no longer possible |
| 11045 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
assignment problem; matching with capacity; similar to UVa 259; 10092; and 12873; but actually the input constraint is actually small enough for recursive backtracking |
| 11082 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
very similar to Kattis - tomography |
| 11167 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
many edges in the flow graph; compress the capacity-1 edges when possible; use Dinic's |
| 11418 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
two layers of graph matching (not really bipartite matching); use max flow solution |
| 12873 |
Fetching from uHunt |
8.4a, Network Flow, Standard |
LA 6851 - Bangkok14; assignment problem; similar to UVa 00259, 11045, and 10092; use Dinic's |
| 00563 |
Fetching from uHunt |
8.4b, Network Flow, Variants |
check whether the maximum number of independent paths on the flow graph equals to b banks |
| 01242 |
Fetching from uHunt |
8.4b, Network Flow, Variants |
LA 4271 - Hefei08; to have a necklace; we need to be able to two edge-disjoint s-t flows |
| 10330 |
Fetching from uHunt |
8.4b, Network Flow, Variants |
max flow; vertex capacities |
| 10480 |
Fetching from uHunt |
8.4b, Network Flow, Variants |
straightforward min cut problem |
| 11380 |
Fetching from uHunt |
8.4b, Network Flow, Variants |
max flow modeling with vertex capacities; similar to UVa 12125 |
| 11506 |
Fetching from uHunt |
8.4b, Network Flow, Variants |
min cut with vertex capacities |
| 11757 |
Fetching from uHunt |
8.4b, 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) |
| 11765 |
Fetching from uHunt |
8.4b, Network Flow, Variants |
interesting min cut variant |
| 12125 |
Fetching from uHunt |
8.4b, Network Flow, Variants |
max flow modeling with vertex capacities; similar to UVa 11380; also available at Kattis - marchofpenguins |
| 00193 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
optimization version of Max Independent Set problem on general graph which is NP-Hard with small input |
| 00539 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
LONGEST-PATH problem; small input/general graph |
| 00574 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
print all solutions with backtracking |
| 00624 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
input size is small; backtracking is enough |
| 00775 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
backtracking suffices as the search space is small; it is more likely to have a HAMILTONIAN-TOUR in a dense graph, so we can prune early |
| 00989 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
classic SUDOKU puzzle; the small 9x9 instance is solvable with backtracking with pruning; use bitmask to speed up |
| 10957 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
very similar with UVa 989; if you can solve that one; you can modify your code a bit to solve this one |
| 11088 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
similar to UVa 10911 but partitioning of three persons to one team; PARTITION-INTO-TRIANGLES |
| 12455 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
SUBSET-SUM; try all; see the harder UVa 12911 that requires meet in the middle |
| 01098 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
LA 4793 - WorldFinals Harbin10; HAMILTONIAN-TOUR; backtracking+pruning; meet in the middle |
| 01217 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
LA 3681 - Kaohsiung06; TSP-like optimization problem; which is NP-Hard; solvable with A*/IDA* |
| 10032 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
PARTITION; DP Knapsack with optimization to avoid TLE; also available at Kattis - tugofwar |
| 10160 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
optimization version of Min Vertex Cover on general graph; Dominating Set; which is NP-Hard; strategies: backtracking; sort by decreasing degrees; heavy pruning |
| 10571 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
hard backtracking problem; it has similar flavor as Su Doku puzzle |
| 11065 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
optimization version of MAX-INDEPENDENT-SET problem on general graph; also report the number of Independent Sets; bitmask helps in speeding up the solution |
| 11095 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
optimization version of Min Vertex Cover on general graph which is NP-Hard |
| 12911 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
SUBSET-SUM; we cannot use DP as 1 ≤ N ≤ 40 and -10^9 ≤ T ≤ 10^9; use meet in the middle |
| 01194 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
LA 2523 - Beijing02; Min Vertex Cover/MVC |
| 01347 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
LA 3305 - SoutheasternEurope05; this is the pure version of Bitonic TSP problem; you may want to start from here |
| 10243 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
this problem can be reduced to the Min Vertex Cover problem on Tree; there is a polynomial DP solution for this variant |
| 10349 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
MIS: V-MCBM; also available at Kattis - antennaplacement |
| 10859 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
Min-Vertex-Cover; on several trees; maximize number of edges with its two endpoints covered |
| 11159 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
MAX-INDEPENDENT-SET; on Bipartite Graph; ans equals to its MCBM |
| 11357 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
not a pure CNF SAT(isfiability) problem; it is a special case as only one clause needs to be satisfied |
| 11419 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
MVC; Konig theorem |
| 12083 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
LA 3415 - NorthwesternEurope05; MIS; also available at Kattis - guardianofdecency |
| 12168 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
LA 4288 - NorthwesternEurope08; MIS; also available at Kattis - catvsdog |
| 13115 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
just a SUDOKU solution verifier; an NP-problem |
| 01086 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 4452 - WorldFinals Stockholm09; can be modeled as a 2-SAT problem |
| 01096 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 4791 - WorldFinals Harbin10; Bitonic TSP variant; print the actual path |
| 01184 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 2696 - Dhaka02; MPC on DAG ~ MCBM |
| 01201 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 3126 - NorthwesternEurope04; MPC on DAG; also available at Kattis - taxicab |
| 01212 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 3483 - Hangzhou05; MWIS on Bipartite Graph |
| 01220 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 3794 - Tehran06; Maximum Independent Set (MIS) problem on tree; DP; also check if the MIS is unique |
| 10319 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
can be modeled as a 2-SAT problem |
| 11294 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
can be modeled as a 2-SAT problem; also available at Kattis - wedding |
| 00714 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and greedy |
| 01221 |
Fetching from uHunt |
8.7a, BSTA and Others |
LA 3795 - Tehran06; +MCBM |
| 01577 |
Fetching from uHunt |
8.7a, BSTA and Others |
LA 6398 - WorldFinals StPetersburg13; BSTA+greedy; also available at Kattis - low |
| 10372 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and Physics |
| 10537 |
Fetching from uHunt |
8.7a, BSTA and Others |
+Dijkstra's on State-Space graph |
| 10566 |
Fetching from uHunt |
8.7a, BSTA and Others |
bisection method |
| 10606 |
Fetching from uHunt |
8.7a, BSTA and Others |
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) |
| 10668 |
Fetching from uHunt |
8.7a, BSTA and Others |
bisection method; also available at Kattis - expandingrods |
| 10804 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and MCBM; similar with UVa 11262 |
| 10816 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and Dijkstra's |
| 10983 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and max flow |
| 11262 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and MCBM; similar with UVa 10804 |
| 11516 |
Fetching from uHunt |
8.7a, BSTA and Others |
+greedy; also available at Kattis - wifi |
| 11646 |
Fetching from uHunt |
8.7a, BSTA and Others |
the circle is at the center of track |
| 11670 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and O(N) greedy simulation |
| 12097 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and geometric formula |
| 12255 |
Fetching from uHunt |
8.7a, BSTA and Others |
LA 5000 - KualaLumpur10; binary search the answer and greedy |
| 12428 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and a bit of graph theory about bridges |
| 12851 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and 3D geometry volume of cone; inclusion-exclusion |
| 12853 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and circumferences of two related circles |
| 12908 |
Fetching from uHunt |
8.7a, BSTA and Others |
binary search the answer and sum of arithmetic progression formula |
| 00843 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
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 |
| 00922 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
compute the area of the polygon; define a rectangle with every pair of points; use set to see if a third point of the rectangle is on the polygon; keep the current best |
| 10125 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
use unordered_map to map sum of a and b in S and their two indices; also available at Kattis - sumsets |
| 10150 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
s: (string); BFS; use trie to quickly identify neighbor that is one Hamming distance away; also available at Kattis - doublets |
| 10734 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
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 |
| 11474 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
UFDS; connect all tree branches; connect two reachable trees (use geometry); connect trees that can reach doctor |
| 11525 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
use Fenwick Tree and binary search the answer to find the lowest index i that has RSQ(1;i) = Si |
| 11960 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
modified Sieve; number of divisors; static Range Maximum Query; use Sparse Table data structure |
| 11966 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
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.7b, Efficient DS and Other |
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 |
| 12318 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
brute force with set data structure |
| 12460 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
a simple BFS problem; use set of string data structure to speed up the check if a word is inside dictionary |
| 13135 |
Fetching from uHunt |
8.7b, Efficient DS and Other |
simple DP; use unordered_map to map the (large) answer S back to (small) N, which turns out to be not more than 10 000 |
| 00142 |
Fetching from uHunt |
8.7c, Geometry and Other |
brute force; point-in-rectangle; dist |
| 00184 |
Fetching from uHunt |
8.7c, Geometry and Other |
brute force; collinear test |
| 00201 |
Fetching from uHunt |
8.7c, Geometry and Other |
counting square of various sizes; try all |
| 00270 |
Fetching from uHunt |
8.7c, Geometry and Other |
gradient sorting; complete search |
| 00356 |
Fetching from uHunt |
8.7c, Geometry and Other |
Euclidean distance; brute force |
| 00638 |
Fetching from uHunt |
8.7c, Geometry and Other |
brute force 4 corner points |
| 00688 |
Fetching from uHunt |
8.7c, Geometry and Other |
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 |
| 10012 |
Fetching from uHunt |
8.7c, Geometry and Other |
try all 8! permutations; Euclidean dist |
| 10167 |
Fetching from uHunt |
8.7c, Geometry and Other |
brute force A and B; ccw tests |
| 10301 |
Fetching from uHunt |
8.7c, Geometry and Other |
circle-circle intersection; backtracking |
| 10310 |
Fetching from uHunt |
8.7c, Geometry and Other |
complete search; Euclidean distance dist; also available at Kattis - doggopher |
| 10514 |
Fetching from uHunt |
8.7c, Geometry and Other |
use basic geometry to compute edge weights of the graph of islands and the two riverbanks; SSSP; Dijkstra's |
| 10823 |
Fetching from uHunt |
8.7c, Geometry and Other |
complete search; check if point inside circles/squares |
| 11008 |
Fetching from uHunt |
8.7c, Geometry and Other |
use collinear test and DP with bitmask |
| 11227 |
Fetching from uHunt |
8.7c, Geometry and Other |
brute force; collinear test |
| 11515 |
Fetching from uHunt |
8.7c, Geometry and Other |
circle-circle intersection; backtracking or brute force subsets with bitmask; also available at Kattis - cranes |
| 11574 |
Fetching from uHunt |
8.7c, Geometry and Other |
try all pairs of boats; 0.0 if one pair collide; or, use a quadratic equation; also available at Kattis - collidingtraffic |
| 12322 |
Fetching from uHunt |
8.7c, Geometry and Other |
first; use atan2 to convert angles to 1D intervals; then sort it and use a greedy scan to get the answer |
| 00273 |
Fetching from uHunt |
8.7d, Graph and Other |
line segment intersection and Warshall's transitive closure algorithm |
| 00393 |
Fetching from uHunt |
8.7d, Graph and Other |
build the small visibility graph with line segment intersection checks; run Floyd Warshall's routine to get the answer |
| 00521 |
Fetching from uHunt |
8.7d, Graph and Other |
vertices = drivers; add an edge between two drivers if they can meet (determined with mathematical rule (gcd)); if the graph is connected, then the answer is 'yes' |
| 01039 |
Fetching from uHunt |
8.7d, Graph and Other |
LA 3270 - WorldFinals Shanghai05; build the graph with simple geometry; then use Floyd Warshall's |
| 01092 |
Fetching from uHunt |
8.7d, Graph and Other |
LA 4787 - WorldFinals Harbin10; compress graph; traversal from exit with S/W direction; inclusion-exclusion |
| 01243 |
Fetching from uHunt |
8.7d, Graph and Other |
LA 4272 - Hefei08; Warshall's transitive closure; SCC; transitive reduction of a directed graph |
| 01263 |
Fetching from uHunt |
8.7d, Graph and Other |
LA 4846 - Daejeon10; geometry; SCC; see two related problems: UVa 11504 and 11770 |
| 10068 |
Fetching from uHunt |
8.7d, Graph and Other |
use BFS from each position to create the APSP data; use backtracking with bitmask and pruning to get the best solution |
| 10075 |
Fetching from uHunt |
8.7d, Graph and Other |
Great Circle Distance (gcDistance) with APSP |
| 11267 |
Fetching from uHunt |
8.7d, Graph and Other |
bipartite check; MST; accept -ve weight |
| 11635 |
Fetching from uHunt |
8.7d, Graph and Other |
Dijkstra's BFS (or 2 Dijkstra's) |
| 11721 |
Fetching from uHunt |
8.7d, Graph and Other |
find nodes that can reach SCCs with neg cycle |
| 11730 |
Fetching from uHunt |
8.7d, Graph and Other |
factoring; BFS |
| 12070 |
Fetching from uHunt |
8.7d, Graph and Other |
LA 3290 - Dhaka05; BFS brute force |
| 12101 |
Fetching from uHunt |
8.7d, Graph and Other |
BFS; involving prime numbers |
| 12159 |
Fetching from uHunt |
8.7d, Graph and Other |
LA 4407 - KualaLumpur08; use simple CCW tests (geometry) to build the bipartite graph; MCBM |
| 12797 |
Fetching from uHunt |
8.7d, Graph and Other |
iterative subset; pick subset of UPPERCASE letters for this round; BFS to find the SSSP; pick the best |
| 01069 |
Fetching from uHunt |
8.7e, Maths and Other |
LA 4119 - WorldFinals Banff08; string parsing, divisibility of polynomial, brute force, and modPow |
| 01195 |
Fetching from uHunt |
8.7e, Maths and Other |
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 |
| 10325 |
Fetching from uHunt |
8.7e, Maths and Other |
inclusion exclusion principle; brute force subset for small M <= 15; lcm-gcd |
| 10419 |
Fetching from uHunt |
8.7e, Maths and Other |
print path; prime |
| 10427 |
Fetching from uHunt |
8.7e, Maths and Other |
numbers in [10^(k-1)..10^k-1] has k digits |
| 10539 |
Fetching from uHunt |
8.7e, Maths and Other |
sieve; get 'almost primes' by listing the powers of each prime, sort them; binary search |
| 10637 |
Fetching from uHunt |
8.7e, Maths and Other |
involving prime numbers and gcd |
| 10717 |
Fetching from uHunt |
8.7e, Maths and Other |
complete search + GCD/LCM |
| 11099 |
Fetching from uHunt |
8.7e, Maths and Other |
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 |
| 11282 |
Fetching from uHunt |
8.7e, Maths and Other |
derangement and binomial coefficient; Big Integer |
| 11415 |
Fetching from uHunt |
8.7e, Maths and Other |
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; use binary search |
| 11428 |
Fetching from uHunt |
8.7e, Maths and Other |
complete search and binary search |
| 12218 |
Fetching from uHunt |
8.7e, Maths and Other |
brute force recursive bitmask with prime check; also available at Kattis - industrialspy |
| 12802 |
Fetching from uHunt |
8.7e, Maths and Other |
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 |
| 00976 |
Fetching from uHunt |
8.7f, Graph and DP |
flood fill to separate North and South banks; compute the cost of installing a bridge at each column; DP |
| 10917 |
Fetching from uHunt |
8.7f, Graph and DP |
counting paths in DAG; build the DAG; Dijkstra's from 'home'; also available at Kattis - walkforest |
| 10937 |
Fetching from uHunt |
8.7f, Graph and DP |
BFS -> APSP information for TSP; then DP or backtracking |
| 10944 |
Fetching from uHunt |
8.7f, Graph and DP |
BFS -> APSP information for TSP; then use DP as n <= 16 |
| 11284 |
Fetching from uHunt |
8.7f, Graph and DP |
SSSP pre-processing; TSP variant = we can go home early; tweak DP TSP recurrence a bit: at each state, we have one more option: go home early |
| 11324 |
Fetching from uHunt |
8.7f, Graph and DP |
LONGEST-PATH on DAG; first, transform the graph into DAG of its SCCs; toposort |
| 11331 |
Fetching from uHunt |
8.7f, Graph and DP |
bipartite graph checks; compute size of left/right sets per bipartite component; DP SUBSET-SUM |
| 11405 |
Fetching from uHunt |
8.7f, Graph and DP |
BFS from k and each P---max 9 items to get APSP information for TSP; then use DP-TSP |
| 11693 |
Fetching from uHunt |
8.7f, Graph and DP |
compute shotest paths information using Floyd Warshall's; then use DP; also available at Kattis - speedyescape |
| 11813 |
Fetching from uHunt |
8.7f, Graph and DP |
Dijsktra's -> APSP information for TSP; then use DP; n <= 10 |
| 00967 |
Fetching from uHunt |
8.7g, Other and DP 1D RSQ/RMQ |
similar to UVa 00897; but this time the output part can be speed up using DP 1D range sum |
| 10200 |
Fetching from uHunt |
8.7g, Other and DP 1D RSQ/RMQ |
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 |
| 10533 |
Fetching from uHunt |
8.7g, Other and DP 1D RSQ/RMQ |
sieve; check if a prime is a digit prime; DP 1D range sum |
| 10871 |
Fetching from uHunt |
8.7g, Other and DP 1D RSQ/RMQ |
need 1D Range Sum Query |
| 10891 |
Fetching from uHunt |
8.7g, Other and DP 1D RSQ/RMQ |
Double DP; 1D RSQ plus another DP to evaluate decision tree; s: (i, j); try all splitting points; minimax |
| 11032 |
Fetching from uHunt |
8.7g, 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) |
| 11105 |
Fetching from uHunt |
8.7g, Other and DP 1D RSQ/RMQ |
need 1D Range Sum Query; also available at Kattis - hnumbers |
| 11408 |
Fetching from uHunt |
8.7g, Other and DP 1D RSQ/RMQ |
need 1D Range Sum Query |
| 12028 |
Fetching from uHunt |
8.7g, Other and DP 1D RSQ/RMQ |
generate the array; sort it; prepare 1D Range Sum Query; then the solution will be much simpler |
| 12904 |
Fetching from uHunt |
8.7g, Other and DP 1D RSQ/RMQ |
3 nested loops; brute force a; b; c; use prefix sum to speed up the checks |
| 00295 |
Fetching from uHunt |
8.7h, Three Components |
BSTA x: if the person has diameter x, can he go from left to right? graph connectivity; similar with UVa 10876 |
| 00811 |
Fetching from uHunt |
8.7h, Three Components |
LA 5211 - WorldFinals Eindhoven99; get CH and perimeter of polygon; generate all subsets iteratively with bitmask |
| 01040 |
Fetching from uHunt |
8.7h, Three Components |
LA 3271 - WorldFinals Shanghai05; try all subsets of 2^20 cities; MST; complex output formatting |
| 01079 |
Fetching from uHunt |
8.7h, Three Components |
LA 4445 - WorldFinals Stockholm09; iterative complete search (permutation); then binary search the answer and greedy |
| 01093 |
Fetching from uHunt |
8.7h, Three Components |
LA 4788 - WorldFinals Harbin10; try all possible roots; DP on tree |
| 01250 |
Fetching from uHunt |
8.7h, Three Components |
LA 4607 - SoutheastUSA09; geometry; SSSP on DAG -> DP; DP 1D range sum |
| 10856 |
Fetching from uHunt |
8.7h, Three Components |
compute number of prime factors of each integer in the desired range; use 1D RSQ DP; binary search |
| 10876 |
Fetching from uHunt |
8.7h, Three Components |
binary search the answer and graph connectivity (geometry/Euclidian distance and union find); similar with UVa 295 |
| 11288 |
Fetching from uHunt |
8.7h, Three Components |
Floyd Warshall's/APSP; iterative brute force subset and permutation; DP; also available at Kattis - carpool |
| 11610 |
Fetching from uHunt |
8.7h, Three Components |
first; reverse primes less than 10^6; then; append zero(es) if necessary; use Fenwick Tree and binary search |
| 12392 |
Fetching from uHunt |
8.7h, Three Components |
brute force permute up to 5!; recursive string parsing (simple BNF) |
| 00737 |
Fetching from uHunt |
9.3dge, 3D Geometry |
cube and cube intersection |
| 00815 |
Fetching from uHunt |
9.3dge, 3D Geometry |
LA 5215 - WorldFinals Eindhoven99; volume; greedy; sort by height; simulation |
| 10297 |
Fetching from uHunt |
9.3dge, 3D Geometry |
cones; cylinders; volumes |
| 00148 |
Fetching from uHunt |
9.anag, Anagram |
uses backtracking |
| 00156 |
Fetching from uHunt |
9.anag, Anagram |
easier with algorithm::sort |
| 00195 |
Fetching from uHunt |
9.anag, Anagram |
use algorithm::next_permutation |
| 00454 |
Fetching from uHunt |
9.anag, Anagram |
anagram |
| 00630 |
Fetching from uHunt |
9.anag, Anagram |
ad hoc; string |
| 00642 |
Fetching from uHunt |
9.anag, Anagram |
go through the given small dictionary for the list of possible anagrams |
| 10098 |
Fetching from uHunt |
9.anag, Anagram |
very similar to UVa 195 |
| 12641 |
Fetching from uHunt |
9.anag, Anagram |
this is an anagram problem variation |
| 12770 |
Fetching from uHunt |
9.anag, Anagram |
count the frequencies; print characters with odd frequency except perhaps the last one - can be put in the middle of a palindrome |
| 00588 |
Fetching from uHunt |
9.artg, Art Gallery |
cutPolygon |
| 01304 |
Fetching from uHunt |
9.artg, Art Gallery |
LA 2512 - SouthEasternEurope02; cutPolygon and area of polygon |
| 01571 |
Fetching from uHunt |
9.artg, Art Gallery |
LA 3617 - Yokohama06; cutPolygon |
| 10078 |
Fetching from uHunt |
9.artg, Art Gallery |
isConvex |
| 00652 |
Fetching from uHunt |
9.asta, A* or IDA* |
classic sliding block 8-puzzle; IDA* |
| 00656 |
Fetching from uHunt |
9.asta, A* or IDA* |
we can use IDDFS with pruning |
| 10181 |
Fetching from uHunt |
9.asta, A* or IDA* |
similar with UVa 652 but larger (now 15 instead of 8); we can use IDA* |
| 11163 |
Fetching from uHunt |
9.asta, A* or IDA* |
another puzzle game solvable with IDA* |
| 00551 |
Fetching from uHunt |
9.brac, Bracket Matching |
use stack |
| 00673 |
Fetching from uHunt |
9.brac, Bracket Matching |
similar to UVa 551; classic |
| 11111 |
Fetching from uHunt |
9.brac, Bracket Matching |
bracket matching with some twists |
| 10296 |
Fetching from uHunt |
9.chin, Chinese Postman Problem |
basic Chinese Postman Problem; also available at Kattis - joggingtrails |
| 10245 |
Fetching from uHunt |
9.clos, Closest Pair Problem |
classic |
| 11378 |
Fetching from uHunt |
9.clos, Closest Pair Problem |
also a closest pair problem |
| 11439 |
Fetching from uHunt |
9.edmo, Edmonds Matching |
BSTA (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 |
| 10934 |
Fetching from uHunt |
9.eggd, Egg Dropping Puzzle |
Egg dropping puzzle; interesting DP; try all possible answers |
| 01185 |
Fetching from uHunt |
9.form, Formulas or Theorems |
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) |
| 01645 |
Fetching from uHunt |
9.form, Formulas or Theorems |
LA 6368 - Chengdu12; number of rooted trees with n vertices in which vertices at the same level have the same degree |
| 10088 |
Fetching from uHunt |
9.form, Formulas or Theorems |
Pick's Theorem |
| 10178 |
Fetching from uHunt |
9.form, Formulas or Theorems |
Euler's Formula; a bit of union find |
| 10213 |
Fetching from uHunt |
9.form, Formulas or Theorems |
Moser's circle; the formula is hard to derive; g(n) = nC4 nC2 1 |
| 10219 |
Fetching from uHunt |
9.form, Formulas or Theorems |
count the length of nCk; BigInteger |
| 10720 |
Fetching from uHunt |
9.form, Formulas or Theorems |
similar to UVa 11414 and 12786; Erdos-Gallai's Theorem |
| 10843 |
Fetching from uHunt |
9.form, Formulas or Theorems |
Cayley's Formula to count the number of spanning trees of a graph with n vertices is n^n-2; use Java BigInteger |
| 11414 |
Fetching from uHunt |
9.form, Formulas or Theorems |
similar to UVa 10720 and 12786; Erdos-Gallai's Theorem |
| 11719 |
Fetching from uHunt |
9.form, Formulas or Theorems |
count the number of spanning tree in a complete bipartite graph; use Java BigInteger |
| 12786 |
Fetching from uHunt |
9.form, Formulas or Theorems |
similar to UVa 10720 and 11414; Erdos-Gallai's Theorem |
| 12876 |
Fetching from uHunt |
9.form, Formulas or Theorems |
LA 6854 - Bangkok14; involving degree of vertex; Handshaking lemma |
| 12967 |
Fetching from uHunt |
9.form, Formulas or Theorems |
OEIS A173033 |
| 13108 |
Fetching from uHunt |
9.form, Formulas or Theorems |
Moser's circle; the formula is hard to derive; g(n) = nC4 + nC2 + 1 |
| 00684 |
Fetching from uHunt |
9.gaus, Gaussian Elimination |
modified Gaussian elimination to find (integral) determinant of a square matrix |
| 11319 |
Fetching from uHunt |
9.gaus, Gaussian Elimination |
solve the system of the first 7 linear equations; then use all 1500 equations for 'smart sequence' checks |
| 00535 |
Fetching from uHunt |
9.grea, Great Circle Distance |
gcDistance |
| 10316 |
Fetching from uHunt |
9.grea, Great Circle Distance |
gcDistance; also available at Kattis - airlinehub |
| 10897 |
Fetching from uHunt |
9.grea, Great Circle Distance |
gcDistance |
| 11817 |
Fetching from uHunt |
9.grea, Great Circle Distance |
gcDistance |
| 00299 |
Fetching from uHunt |
9.inve, Inversion Index |
can use O(n^2) bubble sort |
| 00612 |
Fetching from uHunt |
9.inve, Inversion Index |
needs O(n^2) stable_sort |
| 10327 |
Fetching from uHunt |
9.inve, Inversion Index |
solvable with O(n^2) bubble sort |
| 10810 |
Fetching from uHunt |
9.inve, Inversion Index |
requires O(n log n) merge sort; also available at Kattis - ultraquicksort |
| 11495 |
Fetching from uHunt |
9.inve, Inversion Index |
requires O(n log n) merge sort |
| 11858 |
Fetching from uHunt |
9.inve, Inversion Index |
requires O(n log n) merge sort; 64-bit integer; also available at Kattis - froshweek |
| 13212 |
Fetching from uHunt |
9.inve, Inversion Index |
requires O(n log n) merge sort |
| 00130 |
Fetching from uHunt |
9.jose, Josephus Problem |
the original Josephus problem |
| 00133 |
Fetching from uHunt |
9.jose, Josephus Problem |
brute force; similar to UVa 130 |
| 00151 |
Fetching from uHunt |
9.jose, Josephus Problem |
the original Josephus problem |
| 00305 |
Fetching from uHunt |
9.jose, Josephus Problem |
the answer can be precalculated |
| 00402 |
Fetching from uHunt |
9.jose, Josephus Problem |
modified Josephus; simulation |
| 00440 |
Fetching from uHunt |
9.jose, Josephus Problem |
brute force; similar to UVa 151 |
| 01176 |
Fetching from uHunt |
9.jose, Josephus Problem |
LA 2346 - Dhaka01; special case when k = 2; use Josephus recurrence; simulation |
| 10015 |
Fetching from uHunt |
9.jose, Josephus Problem |
modified Josephus; dynamic k; variant of UVa 305 |
| 10771 |
Fetching from uHunt |
9.jose, Josephus Problem |
brute force; input size is small |
| 10774 |
Fetching from uHunt |
9.jose, Josephus Problem |
repeated case of Josephus when k = 2 |
| 11351 |
Fetching from uHunt |
9.jose, Josephus Problem |
use general case Josephus recurrence |
| 00439 |
Fetching from uHunt |
9.knig, Knight Moves |
one BFS per query is enough |
| 00633 |
Fetching from uHunt |
9.knig, Knight Moves |
a modified Knight Moves problem with alternating Knight Moves and Bishop Moves (limited to distance 2)); solvable with just one BFS per query |
| 10422 |
Fetching from uHunt |
9.knig, Knight Moves |
Depth Limited Search (up to 11 moves); also available at Kattis - knightsfen |
| 10426 |
Fetching from uHunt |
9.knig, Knight Moves |
for each knight; do unweighted SSSP with BFS when the monster is sleep/awake; then brute force to see which one of the the four knights should awake the monster (once) |
| 10477 |
Fetching from uHunt |
9.knig, Knight Moves |
s: (row; col; knight_state); implicit unweighted graph; different edges per different knight_state |
| 11643 |
Fetching from uHunt |
9.knig, Knight Moves |
distance between any 2 interesting positions are computed using a pre-calculated BFS table (corner cases exist); DP TSP |
| 01045 |
Fetching from uHunt |
9.kuhn, Kuhn Munkres's Algorithm |
LA 3276 - WorldFinals Shanghai05; try all possible final configuration; do a weighted matching; and pick the best configuration; use Kuhn Munkres's algorithm |
| 10746 |
Fetching from uHunt |
9.kuhn, Kuhn Munkres's Algorithm |
min weighted bipartite matching |
| 10888 |
Fetching from uHunt |
9.kuhn, Kuhn Munkres's Algorithm |
BFS/SSSP; min weighted bipartite matching |
| 11553 |
Fetching from uHunt |
9.kuhn, Kuhn Munkres's Algorithm |
solve by trying all n! permutations; you can also use DP and bitmask; but it is overkill |
| 10938 |
Fetching from uHunt |
9.lowe, Lowest Common Ancestor |
basic LCA problem |
| 12238 |
Fetching from uHunt |
9.lowe, Lowest Common Ancestor |
similar to UVa 10938 |
| 10594 |
Fetching from uHunt |
9.minc, Min Cost (Max) Flow |
basic min cost max flow problem |
| 10806 |
Fetching from uHunt |
9.minc, Min Cost (Max) Flow |
send 2 edge-disjoint flows with min cost |
| 11301 |
Fetching from uHunt |
9.minc, Min Cost (Max) Flow |
modeling; vertex capacity; MCMF |
| 12821 |
Fetching from uHunt |
9.minc, Min Cost (Max) Flow |
similar to UVa 10806 |
| 10909 |
Fetching from uHunt |
9.orde, Order Statistics Tree |
this problem involves dynamic selection; you can augment balanced BST or use pb_ds |
| 00257 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
palindrome check (DP-able) plus brute force checks for non embedding criteria |
| 00353 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
brute force all substrings; count how many substrings are palindrome |
| 00401 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
simple palindrome check |
| 10848 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
related to UVa 10453; palindrome check, character frequency check, and a few others |
| 10945 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
palindrome check; ignore case and punctuation |
| 11221 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
palindrome check; we deal with a matrix (magic square) this time |
| 11309 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
palindrome check; on HH:MM format |
| 11584 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
use two O(n^2) DP string; one for palindrome check and the other for partitioning |
| 11888 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
let ss = s+s; find reverse(s) in ss, but it cannot match the first n chars or the last n chars of ss |
| 12960 |
Fetching from uHunt |
9.pala, Palindrome (Checking) |
additional twist; special positioning; DP pair |
| 01239 |
Fetching from uHunt |
9.palb, Palindrome (Generating) |
LA 4144 - Jakarta08; as S <= 1000; brute-force is enough; consider odd and even length palindromes |
| 10018 |
Fetching from uHunt |
9.palb, Palindrome (Generating) |
generating palindrome with specific math simulation; very easy |
| 10453 |
Fetching from uHunt |
9.palb, Palindrome (Generating) |
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 |
| 10617 |
Fetching from uHunt |
9.palb, Palindrome (Generating) |
s: (l; r); counting substrings that are palindrome |
| 10739 |
Fetching from uHunt |
9.palb, Palindrome (Generating) |
similar to UVa 10453; 11151; and 11404 |
| 11151 |
Fetching from uHunt |
9.palb, Palindrome (Generating) |
s: (l; r); similar to UVa 10453; 10739; and 11404 |
| 11404 |
Fetching from uHunt |
9.palb, Palindrome (Generating) |
similar to UVa 10453; 10739; and 11151; print the solution in lexicographically smallest manner |
| 12718 |
Fetching from uHunt |
9.palb, Palindrome (Generating) |
LA 6659 - Dhaka13; try all substrings; count character frequencies in them and analyze |
| 00727 |
Fetching from uHunt |
9.post, Postfix |
Infix to Postfix conversion problem |
| 00185 |
Fetching from uHunt |
9.roma, Roman Numerals |
also involving backtracking |
| 00344 |
Fetching from uHunt |
9.roma, Roman Numerals |
count how many Roman characters are used to make all numbers from 1 to N |
| 00759 |
Fetching from uHunt |
9.roma, Roman Numerals |
simple problem of validating Roman numbers |
| 11616 |
Fetching from uHunt |
9.roma, Roman Numerals |
Roman numeral conversion problem |
| 12397 |
Fetching from uHunt |
9.roma, Roman Numerals |
conversion; each Roman digit has value |
| 00261 |
Fetching from uHunt |
9.slid, Sliding Window |
sliding window variant |
| 01121 |
Fetching from uHunt |
9.slid, Sliding Window |
LA 2678 - SouthEasternEurope06; sliding window variant |
| 11536 |
Fetching from uHunt |
9.slid, Sliding Window |
sliding window variant |
| 11462 |
Fetching from uHunt |
9.sort, Sorting in O(n) |
standard Counting Sort problem |
| 00254 |
Fetching from uHunt |
9.towe, Tower of Hanoi |
define a recursive formula |
| 10017 |
Fetching from uHunt |
9.towe, Tower of Hanoi |
classical problem |
| 10254 |
Fetching from uHunt |
9.towe, Tower of Hanoi |
find pattern; use Java BigInteger |