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 Week02 DataStructures&Libraries FocusonBitManipulation&BinaryIndexedTree
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
Outline
MiniContest1+Break(discussionofA/B) / SomeAdmins DataStructuresWithBuiltinLibraries
Justaquickwalkthrough
Read/experiment with the details on your own Read/experimentwiththedetailsonyourown
LinearDataStructures(CS1010/1st halfofCS2020) NonLinearDataStructures(CS2010/2nd halfofCS2020) ( )
Focusontheredhighlights
TopCoderCodingStyle (overview) +Break DataStructuresWithOurOwnLibraries
FocusonBinaryIndexed(Fenwick)Tree
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
BasicknowledgethatallICPC/IOI ersmusthave! Basic knowledge that all ICPC/IOIers must have!
LINEARDATASTRUCTURES WITHBUILTINLIBRARIES
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
Iam I am
1. ApureCcoder 2. A pure C++ coder ApureC++coder 3. Amixbetween C/C++coder C/C d 4. ApureJavacoder p 5. Amultilingual coder:C/C++/Java d C/C++/J
0
0 of 120
CS3233 CompetitiveProgramming, 1 StevenHalim,SoC,NUS
0
2
0
3
0
4
0
5
LinearDS+BuiltInLibraries(1) Linear DS + Built In Libraries (1)
1. StaticArray,builtinsupportinC/C++/Java 2. Resizeable: C++ STL vector, Java Vector Resize able:C++STLvector,JavaVector
BothareveryusefulinICPCs/IOIs
There are 2 very common operations on Array: Thereare2verycommonoperationsonArray:
Sorting S Searching hi Letstakealookatefficientwaystodothem
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
Two fundamental CS problems Two fundamentalCSproblems
SORTING+SEARCHING INVOLVINGARRAY
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
Sorting(1) Sorting (1)
Definition:
Givenunsortedstuffs,sortthem* ,
PopularSortingAlgorithms
O( 2) l i h O(n )algorithms:Bubble/Selection/InsertionSort B bbl /S l i /I i S O(nlogn)algorithms:Merge/Quick^/HeapSort Specialpurpose:Counting/Radix/BucketSort
Reference:
http://en.wikipedia.org/wiki/Sorting_algorithm
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
Sorting(2) Sorting (2)
InICPC,youcanforgetallthese
Ingeneral,ifyouneedtosortsomething, g , y g , justusetheO(nlogn)sortinglibrary:
C++STLalgorithm::sort C STL algorithm:: sort JavaCollections.sort
In ICPC sorting is either used as preliminary step InICPC,sortingiseitherusedaspreliminarystep formorecomplexalgorithmortobeautifyoutput
Familiarity with sorting libraries is a must! Familiaritywithsortinglibrariesisamust!
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
Sorting(3) Sorting (3)
SortingroutinesinC++STLalgorithm
sort abugfreeimplementationofintrosort* g p
Fast,itrunsinO(nlogn) Can sort basic data types (ints, doubles, chars), Abstract Cansortbasicdatatypes(ints,doubles,chars),Abstract DataTypes(C++class),multifieldsorting(2criteria)
partial sort implementation of heapsort partial_sort implementationofheapsort
CandoO(klogn)sorting,ifwejustneedtopksorted!
stable sort stable_sort
Ifyouneedtohavethesortingstable,keyswithsame valuesappearinthesameorderasininput values appear in the same order as in input
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
SearchinginArray Searching in Array
Twovariants:
Whenthearrayissortedversusnotsorted y
MustdoO(n)linearscanifnotsorted trivial CanuseO(logn)binarysearchwhensorted ( )
PS:mustrunanO(nlogn)sortingalgorithmonce ( g ) g g
Binarysearchistrickytocode!
I t d Instead,useC++STLalgorithm::lower_bound C STL l ith l b d
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
LinearDS+BuiltInLibraries(2) Linear DS + Built In Libraries (2)
3. ArrayofBoolean:C++STLbitset
Fasterthanarrayofbools orvector<bool>! y NospecificAPIinJavathatissimilartothis
4. Bitmask 4 Bit k
a.k.a.lightweightsetofBooleanorbitstring Explanationvia:
http://www.comp.nus.edu.sg/~stevenha/visualization/bitmask.html
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
LinearDS+BuiltInLibraries(3) Linear DS + Built In Libraries (3)
5. LinkedList,C++STLlist,JavaLinkedList
UsuallynotusedinICPCs/IOIs y / Ifyouneedaresizeable list,justusevector!
6. Stack,C++STLstack,JavaStack 6 St k C STL t k J St k
UsedbydefaultinRecursion,PostfixCalculation, BracketMatching,etc
7. Queue, C++STLqueue,JavaQueue Queue,C STL queue, Java Queue
UsedinBreadthFirstSearch,TopologicalSort,etc PS D PS:Deque,usedinSlidingWindowalgorithm d i Slidi Wi d l ith
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
Moreefficientdatastructures More efficient data structures
NONLINEARDATASTRUCTURES WITHBUILTINLIBRARIES
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
BinarySearchTree(1) Binary Search Tree (1)
ADTTable(key data) Binary Search Tree (BST) BinarySearchTree(BST)
AdvertisedO(logn)forinsert,search,anddelete R Requirement:theBSTmustbebalanced! i h BST b b l d!
AVLtree,RedBlackTree,etc*argh*
Fretnot,justuse:C++STLmap(JavaTreeMap)
UVa 10226 (Hardwood Species)* UVa10226 (HardwoodSpecies)
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
BinarySearchTree(2) Binary Search Tree (2)
ADTTable(keyexistsornot) Set (Single Set) Set(SingleSet)
C++STLset,similartoC++STLmap
mapstoresa(key,data) pair t (k d t ) i setstoresjustthekey
InJava:TreeSet
Example: p
UVa 11849 CD
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
Heap
Heap
C++STLalgorithm hassomeheapalgorithms g p g
partial_sort usesheapsort
C++ STL priority queue (Java PriorityQueue) is heap C++STLpriority_queue (JavaPriorityQueue)isheap
PrimsandDijkstras algorithmsusepriorityqueue
B t But,werarelyseepureheapproblemsinICPC l h bl i ICPC
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
HashTable Hash Table
HashTable
AdvertisedO(1)forinsert,search,anddelete,but: ( ) , , ,
Thehashfunctionmustbegood! There is no Hash Table in C++ STL ( in Java API) ThereisnoHashTableinC++STL( inJavaAPI)
Nevertheless,O(logn)usingmap isusuallyok
Di t Add DirectAddressingTable(DAT) i T bl (DAT)
Ratherthanhashing,wemorefrequentlyuseDAT UVa11340 (Newspaper)
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
TopCoderCodingStyle Top Coder Coding Style
SUPPLEMENTARY
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
TopCoderCodingStyle(1) Top Coder Coding Style (1)
Youmaywanttofollowthiscodingstyle(C++) 1. Include important headers Includeimportant headers
#include <algorithm> #include <cmath> #include <cstdio> cstdio #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> #i l d < t > using namespace std;
Want More? Add libraries that you frequently use into this template, e.g.: ctype.h t h bitset etc
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
TopCoderCodingStyle(2) Top Coder Coding Style (2)
2. Useshortcutsforcommondatatypes
typedef typedef typedef typedef long long vector<int> pair<int, int> vector<ii> ll; vi; ii; vii;
3. SimplifyRepetitions/Loops! 3 Si lif R titi /L !
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++) #define REPN(i, n) REP (i, 1, int(n)) #define REPD(i, a, b) for (int i = int(a); i >= int(b); i--) #define TRvi(c, it) \ for (vi::iterator it = (c).begin(); it != (c).end(); it++) #define TRvii(c it) \ TRvii(c, for (vii::iterator it = (c).begin(); it != (c).end(); it++)
Define your own loops style and stick with it!
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
TopCoderCodingStyle(3) Top Coder Coding Style (3)
4. Moreshortcuts
for (i = ans = 0; i < n; i++) // do variable assignment in for loop while (scanf( %d , n), n) { // read input + do value test together (scanf("%d", while (scanf("%d", n) != EOF) { // read input and do EOF test
5. STL/Librariesalltheway! / y
isalpha (ctype.h) inline bool isletter(char c) { return (c>='A'&&c<='Z')||(c>='a'&&c<='z'); } abs (math.h) inline int abs(int a) { return a >= 0 ? a : -a; } pow (math.h) a, int power(int a int b) { int res=1; for (; b>=1; b--) res*=a; return res; }
UseSTLdatastructures:vector,stack,queue,priority_queue,map,set,etc UseSTLalgorithms:sort,lower_bound,max,min,max_element,next_p g , , , , , permutation,etc ,
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
TopCoderCodingStyle(4) Top Coder Coding Style (4)
6. UseI/ORedirection
int main() { // freopen( input.txt , "r", stdin); // don t retype test cases! freopen("input.txt", r , don't // freopen("output.txt", "w", stdout); scanf and printf as per normal; // I prefer scanf/printf than // cin/cout, C style is much easier
7. Usememset/assign/constructoreffectively!
memset(dist, 127, sizeof(dist)); // useful to initialize shortest path distances, set INF to 127! memset(dp_memo, -1, sizeof(dp_memo)); // useful to initialize DP memoization table memset(arr, 0, sizeof(arr)); // useful to clear array of integers ( , , ( )); y g vector<int> dist(v, 2000000000); dist.assign(v, -1);
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
TopCoderCodingStyle(5) Top Coder Coding Style (5)
8. Declare(large)staticDSasglobalvariable
Allinputsizeisknown,declaredatastructuresizeLARGERthanneededtoavoidsillybugs Avoid dynamic data structures that involve pointers etc Avoiddynamicdatastructuresthatinvolvepointers,etc Useglobalvariabletoreducestacksizeissue
Nowourcodingtasksaremuchsimpler Typing less code = shorter coding time Typinglesscode=shortercodingtime =betterrankinprogrammingcontests
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
QuickCheck Quick Check
1. Icancopewiththis p pace 2. Iamlostwithso manynew many new informationinthe pastfewslides f
0
0 of 120
CS3233 CompetitiveProgramming, 1 StevenHalim,SoC,NUS
0
2
5MinutesBreak 5 Minutes Break
Onedatastructureswithout builtinlibraries willbediscussedinthelastpart p
BinaryIndexed(Fenwick)Tree Graph Union Find Disjoint Sets and Segment Tree Graph,UnionFindDisjointSets,andSegmentTree arenotdiscussedinthisyearsCS3233Week02
G h DS i GraphDSiscoveredindetailsinCS2010/CS2020 d i d t il i CS2010/CS2020 UFDSiscoveredbrieflyinCS2010/CS2020 Pl PleasestudySegmentTreeonyourown t d S tT
WetrynotsetanycontestprobleminvolvingSegmentTree
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
Time Check: 8.30pm
Graph (notdiscussedtoday,revisitedinWeek05/08) UnionFindDisjointSets (notdiscussedtoday,readCh2onyourown) U i Fi d Di j i t S t ( t di dt d d Ch2 ) SegmentTree (notdiscussedtoday,readCh2onyourown) FenwickTree (discussedtoday) Fenwick Tree (discussed today)
DATASTRUCTURES WITHOUTBUILTINLIBRARIES
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
FenwickTree(1) Fenwick Tree (1)
CumulativeFrequencyTable
Example,s={2,4,5,5,6,6,6,7,7,8}(alreadysorted)
Index/Score/Symbol 0 1 2 3 4 5 6 7 8 Frequency 0 0 1 0 1 2 3 2 1 CumulativeFrequency 0 0 1 1 2 4 7 9 10
FenwickTree(2) Fenwick Tree (2)
FenwickTree(inventor=PeterM.Fenwick)
AlsoknownasBinaryIndexed Tree,veryaptly named Implementedasanarray,letcallthearraynameasft
Eachindex offt isresponsibleforcertainrange (seediagram)
Key/Index 0 1 2 3 4 5 6 7 8 9 Binary 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 Range N/A 1 1..2 3 1..4 5 5..6 7 1..8 9 F N/A 0 1 0 1 2 3 2 1 0 CF N/A 0 1 1 2 4 7 9 10 10 FT N/A 0 1 0 2 2 5 2 10 0
Do you notice any particular pattern?
FenwickTree(3) Fenwick Tree (3)
Togetthecumulativefrequencyfromindex1 tob, h l f f d useft_rsq(ft, b)
The answer is the sum of sub frequencies stored in array ft with Theansweristhesumofsubfrequenciesstoredinarrayft with indicesrelatedtob viathisformulab' = b - LSOne(b)
RecallthatLSOne(b) = b & (-b)
Thatis,striptheleastsignificantbit ofb
Applythisformulaiterativelyuntilb is0
Analysis: A l i This is O(log n) Why? Example: ft rsq(ft, 6) Example:ft_rsq(ft,
b=6=0110,b=b LSOne(b)=0110 0010,b'=4=0100 b'=4=0100,b=b LSOne(b)=0100 0100,b''=0,stop
Sum ft[6] + ft[4] = 5 + 2 = 7 Sumft[6]+ft[4]=5+2=7 (seethebluearea thatcoversrange [1..4]+[5..6]=[1..6]) [1 4] + [5 6] = [1 6])
FenwickTree(4) Fenwick Tree (4)
Togetthecumulativefrequencyfromindexa tob, h l f f d useft_rsq(ft, a, b)
If a is not one we can use: Ifa isnotone,wecanuse: ft_rsq(ft, b) ft_rsq(ft, a - 1) togettheanswer
Analysis: This is O(2 log n) = O(l n) O(log ) Why? Example:ft_rsq(ft, 3, 6) =
ft_rsq(ft, 6) ft_rsq(ft, 3 1) = ft_rsq(ft, 6) ft_rsq(ft, 2) =
blue area minus green area = bluearea minusgreenarea (5+2) (0+1) = 7 1 =6
FenwickTree(5) Fenwick Tree (5)
Toupdatethefrequencyofankey/indexk,byv ( h d h f f k / d b (either positiveornegative),useft_adjust(ft, k, v)
Indices that are related to k via k' = k + LSOne(k) Indicesthatarerelatedtok viak' willbeupdatedbyv whenk < ft.size()
Example:ft_adjust(ft, 5, 2) Analysis: A l i This is also O(log n) Why?
k=5=0101,k'=k+LSOne(k)=0101 +0001,k'=6=0110 k'=6=0110,k''=k'+LSOne(k')=0110+0010,k''=8=1000 Andsoonwhilek<ft.size()
Observethatthedottedredline inthefigurebelowstabsthrough therangesthatareundertheresponsibilityofindices5,6,and8
ft[5] 2 updated to 4 ft[5], 2updatedto4 ft[6], 5updatedto7 ft[8], 10updatedto12
FenwickTree(6) Fenwick Tree (6) Library
typedef vector<int> vi; t d f t <i t> i #define LSOne(S) (S & (-S)) ft_create(vi void ft create(vi &ft, int n) { ft.assign(n + 1, 0); } int ft_rsq(const vi &ft, int b) { int sum = 0; for (; b; b -= LSOne(b)) sum += ft[b]; return sum; } // init: n+1 zeroes n 1 // returns RSQ(1, b)
int ft_rsq(const vi &t, int a, int b) { // returns RSQ(a, b) return ft t ft_rsq(t, b) - ( == 1 ? 0 : ft (t (a ft_rsq(t, a - 1)) } (t 1)); // adjusts value of the k-th element by v (v can be +ve/inc or -ve/dec) j ( , , ) void ft_adjust(vi &ft, int k, int v) { for (; k < (int)ft.size(); k += LSOne(k)) ft[k] += v; }
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
FT/BIT is in IOI syllabus!
FenwickTree(7) Fenwick Tree (7) Application
FenwickTreeisverysuitablefordynamic RSQs (cumulativefrequencytable)whereeachupdate occursonacertainindexonly Now,thinkofpotentialreallifeapplications!
http://uhunt.felixhalim.net/id/32900
Considercoderunningtimeof[0.000 9.999] foraparticularUVa problem Thereareupto9+millionsubmissions/codes
About thousands submissions per problem Aboutthousandssubmissionsperproblem
Ifyourcoderunsin0.342secs,whatisyourrank?
HowtouseFenwickTreetodealwiththisproblem? p
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
QuickCheck Quick Check
1. IamlostwithFenwickTree 2. Iunderstandthebasicsof FenwickTree,butsincethis F i kT b t i thi isnewforme,Imay/may notbeabletorecognize not be able to recognize problemssolvablewithFT 3. IhavesolvedseveralFT relatedproblemsbefore
0
0 of 120
CS3233 CompetitiveProgramming, 1 StevenHalim,SoC,NUS
0
2
0
3
Summary
TherearealotofgreatDataStructuresoutthere
Weneedthemostefficientoneforourproblem
DifferentDSsuitsdifferentproblem!
Manyofthemhavebuiltinlibraries
Forsomeothers,wehavetobuildourown(focusonFT)
Studytheselibraries!Donotrebuildthemduringcontests!
FromWeek03onwardsandfutureICPCs/IOIs, useC++STLand/orJavaAPIandourbuiltinlibraries!
Now,yourteamshouldbeinrank3045(from60) (stillsolving~12problemsoutof10,butfaster)
CS3233 CompetitiveProgramming, StevenHalim,SoC,NUS
