BasicProgrammingandFewProblems:
[Link]
AlgorithmsExplanationwithComplexityTutorials:
[Link]
DSandAlgoIndex:
[Link]
Problemsbasedoncategory
[Link]
DP:
1.
[Link]
[Link]
2.
[Link]
[Link]
3.
[Link]
[Link]
4.
[Link]
[Link]
5.
[Link]
[Link]
6.
[Link]
7.
[Link]
[Link]
[Link]
[Link]
[Link]
dlMWQzMTA2/edit?ddrp=1&pli=1&hl=en
Trie
[Link]
[Link]
[Link]
[Link]
(PHRYMESolution)
SegmentTree
[Link]
[Link]
[Link]
[Link]
(HORRIBLESolution)
[Link]
(CHEFDSolution)
FenwickTreeakaBinaryIndexedTree(BIT)
[Link]
[Link]
Problem(s):
[Link]
[Link]
Solution(s):
[Link]
(RANGESUM)
[Link]
(MBOARD)
ProblemSet3
1)
[Link]
2)
[Link]
3)
[Link]
4)
[Link]
5)
[Link]
6)
[Link]
7)
[Link]
8)
[Link]
9)
[Link]
Solutions:
1)FARIDA:
[Link]
2)COINS:
[Link]
3)BEHAPPY:
[Link]
4)ZigZag:
[Link]
5)DELISH:
[Link]
6)FROGV:
[Link]
7)EDIST:
[Link]
8)WACHOVIA:
[Link]
9)Boredom:
[Link]
ProblemSet4
1)
[Link]
2)
[Link]
3)
[Link]
4)
[Link]
5)
[Link]
6)
[Link]
7)
[Link]
8)
[Link]
9)
[Link]
10)
[Link]
Solutions:
1)MFISH:
[Link]
2)LEPAINT:
[Link]
3)SEATSR:
[Link]
4)INS14E:
[Link]
5)MARTIAN:
[Link]
6)VocaloidsAndSongs:
[Link]
7)LEBLOCKS:
[Link]
8)LEMOVIE:
[Link]
9)LEMAGIC:
[Link]
AdvancedDynamicProgramming
ForReading
CommonlyUsedDPstatedomains:
[Link]
GeneralAspectsofDP:
[Link]
OptimizingDPsolutions:
[Link]
DynamicProgrammingOptimizations
ConvexHullTrick1:
[Link]
Problem(s):
[Link]
DivideandConquerOptimization:
[Link]
[Link]
(Solveproblemswiththehelpof
editorialtolearn)
ConvexHullTrick2:
[Link]
Problem(s):
[Link]
[Link]
DigitDP
[Link]
[Link]
Problem(s):
[Link]
[Link]
[Link]
[Link]
DPontrees
[Link]
Problem(s):
[Link]
[Link]
[Link]
BitmaskDP
[Link]
Problem(s):
[Link]
[Link]
[Link]
Solutions:
TSHIRTS:
[Link]
HIST2:
[Link]
GONE:
[Link]
RAONE:
[Link]
LUCIFER:
[Link]
ANUBGC:
[Link]
PT07X:
[Link]
Contest1
:BalticOlympiadinInformatics2010Day1
[Link]:
[Link]
[Link]:
[Link]
[Link]:
[Link]
Contest2
:ArabandNorthAfricaRegionalContest2009
[Link]:
[Link]
[Link]:
[Link]
#
Ifyouwantyoucanmaketeamswithatmost2otherpeople.Thecontestwasof5hourssotry
tosolvealltheproblemsfor5hoursonlyafterthatreadthesolutionsandsolveatleast56
[Link]'t
raiseittoomuch.
Contest3:
USACO2014JanuaryContestSilverDivsionDiscussionThread:
Solutions:
[Link]
SourceCodesbySameerGulati:
1)
[Link]
2)
[Link]
3)
[Link]
Contest4
CodechefJanuaryLongChallengeUpsolvingThread
SameerGulatisSolutions:
1)GCDQ:
[Link]
2)QSET:
[Link]
3)CHEFSTON:
[Link]
4)CLPERM:
[Link]
5)ONEKING:
[Link]
6)XRQRS:
[Link]
7)SEAVOTE:
[Link]
[Link]
NumberTheoryProblems
LCMandGCD
Euler'sFunction
ModulusArithmetic
[Link][
[Link]
]
2.DIV2SPOJ[
[Link]
]
[Link][
[Link]
]
[Link][
[Link]
]
[Link][
[Link]
]
[Link][
[Link]
]
[Link][
[Link]
]
8.IITK2P05FACTORIZATION[
[Link]
]
[Link][
[Link]
]
[Link][
[Link]
]
11.NDIVPHI2SPOJ(Euler'sTotientfunction)[
[Link]
]
[Link][
[Link]
]
[Link][
[Link]
]
[Link][
[Link]
]
[Link][
[Link]
]
GraphTheory
StronglyConnectedComponents
Tarjan'sAlgorithm:
[Link]
Kosaraju'sAlgorithm:
[Link]
Problems:
[Link]
[Link]
[Link]
solution:WEBISL:
[Link]
by
MarinKii
[Link]
byme
BOTTOM:
[Link]
Problem1
.
[Link]
(Div21000)
SolnIdea:
HINT
:
letssaywehave3vertex,u,v,w.
d(u,v)=d(u,w)+d(w,v)(mod2)(thisequationalwayssatisfies).Itmeansparitydoesnot
change.
So,ifdistancerelationofonevertexvalidatestheinputrelationwitheveryothervertex,thenall
[Link],treeisvalid.
Linktocode:
[Link]
.[Link]
isnotworkingcurrently.
Problem2
.
[Link]
(Div21000)
SolnIdea:
Youcannotsolvethisproblemwithoutchineseremaindertheorem.
Hint
:RequiredChineseRemainderTheorem(
CRT
)
Usingchinesetheorem,ifX%n1=a1,X%n2=a2,..,X%nk=akandGCD(ni,nj)=1,i!=[Link]
wecancalculate(X%N)ink*log(N),whereN=n1*n2**nk.
Weneedtocheckforx<10^9asf(x)%10^9isgiven.10^9=2^9*5^9.
Idea:N=10^9,n1=2^9,n2=5^9.N=n1*n2,GCD(n1,n2)=1
AswehavetofindtheXsuchthatf(X)%10^9=0wheref(x)=ax^2+bx+[Link]
findx2andx5suchthatf(x2)%2^9=0andf(x5)%5^9=0,wearedone.Mergebothx2andx5
usingCRTtheoremtogettheX%10^9.(DirectcodeavailableforCRTorReadWikipediafor
CRT).
Linktocode:
[Link]
.[Link]
currently.
(topic:maths)
Problem3:
[Link]
(Div21000)
SolnIdea:
ThisproblemcanbesolvedusingDPapproach.
dp[i][mod1][mod2][mod3][mod4][mod5].Assumen=5whichmeanswehave5Questionsand
weareatithdigit(traversefromi=0towardsi=m1),now,
dp[i][mod1][mod2][mod3][mod4][mod5]willstorethenumberofwaysofdifferentMdigitnumber,
whereremainderfor1stquestiontilli'thdigitismod1,remainderfor2ndquestiontilli'thdigitis
[Link]=1isatithplace,andcalculatetheabovedp.
Transitionforthiswillbe:
dp[i][mod1][mod2][mod3][mod4][mod5]+=dp[i1][mod11][mod21][mod31][mod41][mod51]
Now,dothisforeverydigit,from0to9.
Note:Weneedtocheckifdigitatithplaceisallowedforjthquestiontomakethetransition
accordingly.(Givenintheinputitself)
LinktoCode:
[Link]
.[Link]
[Link]:O(10^n*n*m*10)
topic:
DP
Problem4:
[Link]
(Div1500,
Div21000)
SolnIdea:
[Link]
changethevalueataposition,[Link],store
theanswerfor0pair,[Link]
computationof(0pair,1pairand2pair)totheparentnode.
LinktoCode:
[Link]
.[Link]
isnotworking
[Link]
