This course material is now made available for public usage.

Special acknowledgement to School of Computing, National University of Singapore for allowing Steven to prepare and distribute these teaching materials.

CS3233 CompetitiveProgramming p g g
Dr.StevenHalim Dr. Steven Halim Week06 ProblemSolvingParadigms
(DynamicProgramming2) (D i P i 2)

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

Outline
MiniContest#5+Break+Discussion+Admins AsimpleproblemtorefreshourmemoryaboutDPparadigms DPanditsrelationshipwithDAG(Chapter4)
DPonExplicitDAG/ImplicitDAG
Th TheseareCS2020/CS2010materials CS2020/CS2010 t i l ThosefromCS1102mustcatchup/consultStevenseparately

DPonMathProblems(Chapter5) DP on Math Problems (Chapter 5) DPonStringProblems(Chapter6) DP+bitmask(Chapter8) DP + bitmask (Chapter 8) CompilationofCommonDPStates

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPProblemsonChapter4 5 6ofCP2Book DP Problems on Chapter 456 of CP2 Book

NONCLASSICALDPPROBLEMS

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

NonClassicalDPProblems(1) Non Classical DP Problems (1)

My definitionofNonClassicalDPproblems:
Notthepureform/variantofLIS,MaxSum,CoinChange, 01Knapsack/SubsetSum,TSPwheretheDPstates and transitions canbememorized. R Requiresoriginalformulation ofDPstatesandtransitions i i i lf l ti f DP t t dt iti
Althoughsomeformulationarestillsimilartotheclassicalones

Throughout this lecture we will talk mostly in DP terms Throughoutthislecture,wewilltalkmostlyinDPterms

State (tobeprecise:distinct state) SpaceComplexity(i.e.thenumberofdistinctstates) Space Complexity (i.e. the number of distinct states) Transition (whichentailoverlappingsubproblems) TimeComplexity(i.e.numofdistinctstates*timetofillonestate)
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

NonClassicalDPProblems(2) Non Classical DP Problems (2)

Torefreshourmemory Example:CuttingSticks(UVa 10003) inCLRS3rd ed!
State:dp[l][r],Q:Whythesetwoparameters? SpaceComplexity:Max50x50=2500distinctstates Transition: Try all possible cutting points m between l and r Transition:Tryallpossiblecuttingpointsm betweenl andr,
i.e.cut(l,r)into(l,m)and(m,r)

TimeComplexity:Therecanbeupto50possiblecuttingpoints, thusmax2500x50=125000operations,doable

000 000

025 025

050 050 050

075 075

100 100

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPonDAG(1) ( )
Overview DynamicProgramming(DP)hasacloserelationship with(sometimesimplicit)DirectedAcyclicGraph(DAG)
Thestates arethevertices oftheDAG Spacecomplexity:NumberofverticesoftheDAG Thetransitions aretheedges oftheDAG
Logical,sincearecurrenceisalwaysacyclic

Timecomplexity:NumberofedgesoftheDAG TopdownDP:Processeachvertexjustonceviamemoization BottomupDP:Processtheverticesintopologicalorder

Sometimes,thetopologicalordercanbewrittenbyjustusingsimple (nested)loops (nested) loops
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPonDAG(2) ( )
OnExplicitDAG(1) ThereisaDAGinthisproblem(canyouspotit?)
UVa 10285 (LongestRunonaSnowboard)

GivenaR*Cofheightmatrixh, findwhatisthelongestrunpossible?
Longestrunoflengthk:
h(i1,j1)>h(i2,j2)>>h(ik,jk)

LongestpathinDAG!

WewilllearnacreativeDPtablefillingtechnique g q fromthisshortexample(bottomup)
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPonDAG(2) ( )
OnExplicitDAG(2)
Completesearchrecurrence:
Leth(i,j)=heightoflocation(i,j) Let f(i j) longest run length started at (i j) Letf(i,j)=longestrunlengthstartedat(i,j) f(i,j)=1+max(fvaluesofreachableneighbors:h(i,j)>h(neighborsi,j))
Basecase:Ifh(i,j)isthelowestamongitsneighbor,thenf(i,j)=1

DoitfromallpossibleR*Clocations!
Doyouobservemanyoverlappingsubproblems?

Thisproblemisactuallysolvableusingcompletesearchdue to smallR*C+constraints!
ButwithDP,thesolutionismoreefficient
AnditcanbeusedtosolvelargerR*C

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPonDAG(2) ( )
OnExplicitDAG(3) FillintheTable(BottomUp)Trick:
Sort(i,j)accordingtoh(i,j)inincreasingorder
i.e.Fillthebottomcellsfirst! Fillinf(i,j)inorderbasedonthevalueof f(i 1,j),f(i+1,j),f(i,j 1),f(i,j+1) f(i1 j) f(i+1 j) f(i j1) f(i j+1)
Thisisthetopologicalsort!

Thismayactuallybehardertocode
Forthisproblem,writingtheDPsolutionintopdownfashion maybebetter/easier

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPonDAG(3) ( )
ConvertingaGeneralGraph DAG(1)
Noteverygraphproblemhasareadyalgorithmforit
SomehavetobesolvedwithCompleteSearch Some are solvable with DP as long as we can find a way to make the SomearesolvablewithDP,aslongaswecanfindawaytomakethe DPtransitionacyclic,usuallybyaddingone(ormore)parametersto eachvertex :O RememberthatDijkstrasisagreedyalgorithm,andeverygreedy solution(withoutproofofcorrectness)hasachanceforgettingWA

Example: Fishmonger (SPOJ 101) Example:Fishmonger(SPOJ101)

State:dp[pos][time_left],Q:Whythesetwoparameters? SpaceComplexity:Max50*1000=50000 p p y Transition:TryallremainingNcities,noticethattime_leftalways decreasesaswemovefromonecitytoanother(acyclic!!) TimeComplexity:Max50000*50=2.5M,doable l * d bl
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPonMathProblems(Chapter5) DP on Math Problems (Chapter 5)

SomewellknownmathematicproblemsinvolvesDP
Somecombinatorics problemhaverecursiveformulas whichentailoverlappingsubproblems
e.g.thoseinvolvingFibonaccinumber,f(n)=f(n 1)+f(n2)

S Someprobabilityproblemsrequireustosearchtheentire b bilit bl i t h th ti searchspacetogettherequiredanswer

If some of the sub problems are overlapping use DP Ifsomeofthesubproblemsareoverlapping,useDP, otherwise,usecompletesearch

Mathematicsproblemsinvolvingstatic range sum/min/max!

UsedynamictreeDSfordynamicqueries
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPonStringProblems(Chapter6) DP on String Problems (Chapter 6)

SomestringproblemsinvolvesDP
Usually,wedonotworkwiththestringitself
Toocostlytopass(sub)stringsaroundasfunctionparameters

Butweworkwiththeintegerindicestorepresent suffix/prefix/substring ffi / fi / b t i

Example:UVa 11258 StringPartition

Therearemanywaystosplitastringofdigitsintoalistof nonzeroleading(0itselfisallowed)32bitsigned integers
Th i Thatis,maxintegeris2311=2147483647 i i 2 1 2147483647

Whatisthemaximumsumoftheresultantintegersifthe stringissplitappropriately? string is split appropriately?

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

Lastpartofthislecture,fromChapter8ofCP2Book Last part of this lecture, from Chapter 8 of CP2 Book

DP+BITMASK ANDTIPS/TRICKS

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

EmergingTechnique:DP+bitmask Emerging Technique: DP + bitmask

WehaveseenthisformearlierinDPTSP Bitmasktechniquecanbeusedtorepresentlightweightsetof Boolean ( t 264 if i B l (upto2 ifusingunsignedlonglong) i dl l ) ImportantifoneoftheDPparameterisaset C b Canbeusedtosolvematchinginsmallgeneralgraph d l hi i ll l h Example:FormingQuizTeams(UVa 10911)
St t d [bit State:dp[bitmask] k] SpaceComplexity:2M ~65Kdistinctsubproblems; maxN=8,M=2N,thusmaxM=16 Transition:Cleverversion:O(N),tryallandbreakassoonaswefind thefirstperfectmatching,Notsoclever:O(N2) Ti TimeComplexity:O(N.2M) C l it O(N 2 )orabout524K,doable b t 524K d bl
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

CommonDPStates(1) Common DP States (1)

Position:
Originalproblem:[x1,x2,,xn]
Canbesequence(integer/doublearray),canbestring(chararray)

Subproblems,breaktheoriginalprobleminto
SubproblemandPrefix:[x1,x2,,xn1]+xn Suffixandsubproblem:x1 +[x2,x3,,xn] Two sub problems: [x1,x2,,xi] + [xi+1,xi+2,,xn] Twosubproblems:[x x x ]+[x x x

Example:LIS,1DMaxSum,MatrixChainMultiplication ( (MCM),etc ),

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

CommonDPStates(2) Common DP States (2)

Positions:
Thisissimilartothepreviousslide Originalproblem:[x1,x2,,xn]and[y1,y2,,yn]
Canbetwosequences/strings

Subproblems,breaktheoriginalprobleminto
Subproblemandprefix:[x1,x2,,xn1]+xn and[y1,y2,,yn1]+yn S ffi Suffixandsubproblem:x1 +[x2,x3,,xn] d 1 +[y2,y3,,yn] d b bl [ ]andy [ Twosubproblems: [x1,x2,,xi]+[xi+1,xi+2,,xn]and [y1, y2, , yi] +[yi+1, yi+2, , yn] ,y ,,y ] [y ,y ,,y

Example:StringAlignment/EditDistance,LCS,etc PS: Can also be applied on 2D matrix, like 2D Max Sum, etc PS:Canalsobeappliedon2Dmatrix,like2DMaxSum,etc
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

Tips:WhentoChooseDP Tips: When to Choose DP

DefaultRule:
Ifthegivenproblemisanoptimization orcounting problem
Problem exhibits optimal sub structures Problemexhibitsoptimalsubstructures Problemhasoverlappingsubproblems

InICPC/IOI: /
Ifactualsolutionsarenotneeded(onlyfinalvaluesasked)
Ifwemustcomputethesolutionstoo,amorecomplicatedDPwhich storespredecessorinformation andsomebacktracking arenecessary stores predecessor information and some backtracking are necessary

Thenumberofdistinctsubproblemsissmallenough(<1M) andyouarenotsurewhethergreedyalgorithmworks(whygamble?) Obviousoverlappingsubproblemsdetected:O

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DynamicProgrammingIssues(1) Dynamic Programming Issues (1)

PotentialissueswithDPproblems:
Theymaybedisguisedas(orlookslike)nonDP y y g ( )
Itlookslikegreedycanworkbutsomecasesfails
e.g.problemlookslikeashortestpathwithsomeconstraints g p p ongraph,buttheconstraintsfailgreedy SSSPalgorithm!

Theymayhavesubproblemsbutnotoverlapping
DPdoesnotworkifoverlappingsubproblemsnotexist
Anyway,thisisstillagoodnewsasperhaps DivideandConquertechniquecanbeapplied d d h b l d

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DynamicProgrammingIssues(2) Dynamic Programming Issues (2)

Optimalsubstructuresmaynotbeobvious
1. Findcorrectstatesthatdescribeproblem
Perhapsextraparametersmustbeintroduced?

2. Reduceaproblemto(smaller)subproblems (withthesamestates)untilwereachbasecases ( ith th t t ) til hb

Therecanbemorethanonepossibleformulation
Picktheonethatworks!

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPProblemsinICPC(1) DP Problems in ICPC (1)

ThenumberofproblemsinICPCthat mustbesolvedusingDParegrowing!
Atleastone,likelytwo,maybethreepercontest

Thesenewproblemsarenot theclassicalDP!
Theyrequiredeepthinking Orthosethatlooksolvableusingother(simpler) g ( p ) algorithmsbutactuallymustbesolvedusingDP DonotthinkthatyouhavemasteredDP byonlymemorizingtheclassicalDPsolutions!

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

DPProblemsinICPC(2) DP Problems in ICPC (2)

In1990ies,masteringDPcanmakeyoukingof programmingcontests
Today,itisamusthaveknowledge So,getfamiliarwithDPtechniques!

BymasteringGraph+DP,yourICPCrankisprobably:
fromtop~[2530](solving12problemsoutof10) p [ ]( g p )
Onlyeasyproblems

totop~[1020](solving35problemsoutof10)
Easyproblems+somegraph+greedy/DPproblems

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

ForWeek07homework (Youcandothisoverrecessweektoo) (You can do this over recess week too)

BEAPROBLEMSETTER

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

BeaProblemSetter Be a Problem Setter

ProblemSolver:
A. B. B C. D. E. F. G. Readtheproblem Thinkofagoodalgorithm Think of a good algorithm Writesolution y / CreatetrickyI/O IfWA,gotoA/B/C/D IfTLE/MLE,gotoA/B/C/D IfAC,stop

ProblemSetter:
A. Writeagood problem B. Writegood B Write good solutions
Thecorrect/bestone Theincorrect/slowerones

C. Setagood secretI/O D. Setproblemsettings

A problem setter must Aproblemsettermust thinkfromadifferentangle!

Bysettinggoodproblems, By setting good problems, youwillsimultaneouslybe abetterproblemsolver!!

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

ProblemSetterTasks(1) Problem Setter Tasks (1)

Writeagood problem
Options:
Pickanalgorithm,then findproblem/story,or Find a problem/story Findaproblem/story, thenidentifyagood algorithmforit(harder)

Writegood solutions
Mustbeabletosolve yourownproblem!
Tosethardproblem, onemustincreasehis one must increase his ownprogrammingskill!

Problemdescription mustnotbeambiguous
Specif inp t constraints Specifyinputconstraints GoodEnglish! y g , Easyone:longer, Hardone:shorter!

Usethebestpossible algorithmwithlowest timecomplexity

Usetheinferiorones thatbarelyworkstoset theWA/TLE/MLE settings...

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

ProblemSetterTasks(2) Problem Setter Tasks (2)

SetagoodsecretI/O
Trickytestcasesto checkACvsWA
Usuallyboundarycase

Setproblemsettings
TimeLimit:
Usually2or3timesthe timingsofyourown bestsolutions
JavaslowerthanC++!

L Largetestcasesto t t t checkACvsTLE/MLE
Perhapsuseinput Perhaps use input generatortogenerate largetestcase,then passthislargeinputto pass this large inp t to ourcorrectsolution

MemoryLimit:
CheckOJsetting^ Avoidrevealingthe algorithminthe p problemname

ProblemName:

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

FYI:BeAContestOrganizer FYI: Be A Contest Organizer

ContestOrganizerTasks:
Setproblemsofvarious topic p p
Bettersetby>1problemsetter

Must balance the difficulty of the problem set Mustbalancethedifficultyoftheproblemset

Trytomakeitfun Eachteamsolvessomeproblems Each team solves some problems Eachproblemissolvedbysometeams Noteamsolveallproblems No team solve all problems
Everyteamsmustworkuntiltheendofcontest

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

SpecialHomeworkforWeek07 Special Homework for Week07

Createone problemofyourchoice
Canbeofany problemtype
Regardless we have studied that in CS3233 or not RegardlesswehavestudiedthatinCS3233ornot ForthosewhoarenewwithCompetitiveProgramming,justcreateone fromthese:AdHoc/Libraries/BF/D&C/Greedy/DP/simpleGraph Youcandothisinadvance(useyourmidsembreak?) d h d ( d b k?)

Deliverables:
1html:problemdescription+sampleI/O 1 html: problem description + sample I/O 1sourcecode:cpp/java 1testdatafile(ofmultipleinstancestype) ( p yp ) 1shorttxtwriteupoftheexpectedsolution ZipanduploadyourproblemintospecialfolderinIVLE
CS3233/Homework/BeAProblemSetter
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS

MoreReferences More References

CompetitiveProgramming2
Section3.5,4.7.1,5.4,5.6,6.5,and8.4

IntroductiontoAlgorithms,p323369,Ch15 AlgorithmDesign,p251 336,Ch6 Algorithm Design, p251336, Ch 6 ProgrammingChallenges,p245267,Ch11 http://www.topcoder.com/ htt // t d / tc?module=Static&d1=tutorials&d2=dynProg Bestispractice&morepractice!

CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS