AlRntn's blog

By AlRntn, 3 months ago, In English
TL; DR

Note : i don't know the original name of this data structure (if it has one) if you know comment it, in this blog i will name it Dynamic Prefix Sum

Prefix Sums

if you have an arbitrary array $$$a$$$ of size $$$n$$$ and had $$$q$$$ queries in pairs of $$$(l, r)$$$ and wanted $$$\sum_{i=l}^{r} a_i$$$, you can brute force it and it will take $$$O(nq)$$$ time which is going to get TLE, so you can use a method called prefix sums(which if you are interested in you can discover more things about it in this link). this method uses somewhat dynamic programming (beginner level) to solve the problem, basically you define another array $$$ps$$$ of length $$$n+1$$$($$$ps$$$ array is 0-based indexed) and you assign $$$ps_0 = 0$$$, then for each $$$i$$$ from $$$1$$$ to $$$n+1$$$ you are going to use the following formula:

$$$ps_i = ps_{i-1} + a_{i-1}$$$ (assuming 0-based indexing for $$$a$$$, if its 1-based you should do $$$a_i$$$)

after the prefix sum array is completed each element like $$$ps_i$$$ is storing the sum of elements from the beginning of the array to $$$i$$$, so: $$$ps_i = \sum_{j=0}^{i-1} a_j$$$

using this to answer each query you should print $$$ps_r - ps_{l-1}$$$, so it can be solved in $$$O(n + q)$$$ time complexity.

Faster Updates!

but now what if we want to update some points, like we want to set the value of some $$$a_i$$$ to $$$k$$$, we should update all prefix sums from $$$i$$$ to $$$n$$$ which in worst case is $$$O(n)$$$ which is slow. what we do now is we use a data structure called Square Root Decomposition, but not on the original array but on the prefix sum array, for more info about square root (sqrt) decomposition you can refer to this link, but for now the only thing you should know about it is that it can answer point queries (what is the i'th element in the array right now after the updates) in $$$O(1)$$$ and can do range updates(updates that require increasing all of the elements from $$$l$$$ to $$$r$$$ in an array) in $$$O(\sqrt n)$$$, now we can use this to boost up our prefix sum, so we decompose our prefix sum array, then we can do updates in $$$O(\sqrt n)$$$ how? we basically need a range update from $$$i$$$(updated position) to $$$n$$$ in the prefix sum array. now why we can't use Segment Trees with Lazy updates instead of Square Root Decomposition? because i don't know how to do point queries in Segment Trees in $$$O(1)$$$ (if you know comment it!), and if we can't do that we can't access the prefix sum array for range sum queries.

so here is the code:

code

and now we will have a data structure with time complexity of $$$O(n)$$$ build time, $$$O(1)$$$ range query time, $$$O(\sqrt n)$$$ point update time.

Comparing it with other similar data structures

after comparing the actual runtime of this data structure and some other similar ones i found out that: for a place which has nearly 50% updates and 50% queries, the best option is Fenwick Tree which is very easy to implement and has very low constant factor, also having $$$O(n)$$$ build, $$$O(\log n)$$$ query & update, but for a place with more queries than updates the method said in the blog is also a valid option, also if you have a lot of updates, either take the Fenwick which is superfast, or the normal square root decomposition. if you don't have updates use the normal prefix sums.

Comparing the Time Complexity of different data structures: the notation $$$[O(b), O(q), O(u)]$$$ means(from left to right): build — query — update time complexity:

Brute Force = $$$[O(1), O(n), O(1)]$$$

Fenwick & Segment Tree = $$$[O(n), O(\log n), O(\log n)]$$$

Prefix Sum = $$$[O(n), O(1), O(n)]$$$

Dynamic Prefix Sum = $$$[O(n), O(1), O(\sqrt n)]$$$

Square Root Decomposition = $$$[O(n), O(\sqrt n), O(1)]$$$

Square Root Tree = $$$[O(n \log \log n), O(1), O(\sqrt n)]$$$

one of the biggest disadvantages of this method is that its not useful for minimum / maximum / gcd / lcm / ... queries, but it can be used for multiplication , bitwise operations(| and & are don't have an optimal way and is not recommended but for ^ there is no problem)

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By AlRntn, history, 3 months ago, In English

tourist in the last contest has achieved 1st place and crossed 4000 rating and become the first person on codeforces in the rank Tourist

Full text and comments »

  • Vote: I like it
  • +15
  • Vote: I do not like it

By AlRntn, history, 5 months ago, In English

Backtracking: This algorithm helps you solve problems in a specific way using your skills in recursive programming. It comes in handy whenever you have a set of valid answers to a problem and need to search through them all or construct a suitable answer, this algorithm is a general algorithm for finding all or some solutions in some computational problems. The backtracking method is an algorithmic method to solve some kind of problems in which we need to build and examine all possible situations or a number of good situations of an arrangement(combination), in this algorithm all possible situations are created , and after examining each one, if it is approved based on the request of the problem we will accept it as a answer(kind of like brute force we find each possible combination). Note that this method is useful when we cant use a faster algorithm(like: Greedy or Dp).

the General Backtracking Method is like this(pseudocode):

solve(X):
if X is accepted:
   X is answer
   exit
while we can change X:
   change X
   if X is valid:
      solve(X)
   undo last change from X

The base of the algorithm is in 4 parts: the condition of finding the answer (lines 1 to 3) — finding all the different states of the answer (lines 4 to 6) — recursive call (line 7) — return the last change made (line 8).

Some Backtracking Problems:

1-Print all strings of length n that are made only of letters a, b, and c.

The Answer

2-A horse is in the cell (0,0) in a n*n chessboard. That is, in the upper-left corner, you have to say the number of cells that the horse can reach with exactly k moves.

The Answer

3-476B - Dreamoon and WiFi

The Answer

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By AlRntn, history, 5 months ago, In English

Here are Some easy to intermediate codeforces graph and backtracking problems this problems normally only use some basic knowledge of graphs/trees + basic algorithms , I hope it helps

1944A - Destroying Bridges rate : 800 -> basic of graphs [Very Simple]

1598A - Computer Game rate : 800 -> not so much graph [Very Simple]

1797A - Li Hua and Maze rate : 800 -> not so much graph + edge cases [Very Simple]

1843C - Sum in Binary Tree rate : 800 -> not so much graph or tree [Very Simple]

939A - Love Triangle rate : 800 -> can be solved with graph or not [Very Simple]

115A - Party and 116C - Party rate : 900 -> bfs [Simple]

500A - New Year Transportation rate : 1000 -> dfs [Simple]

727A - Transformation: from A to B rate : 1000 -> backtracking / dfs [Simple]

476A - Dreamoon and Stairs rate : 1000 -> backtracking + some optimization [Simple]

1020B - Badge rate : 1000 -> dfs [Simple]

122A - Lucky Division rate : 1000 -> backtracking [Simple]

1324C - Frog Jumps rate : 1100 -> not so much graph but can be solved with dfs [Very Simple]

445A - DZY Loves Chessboard rate : 1200 -> can be solved with dfs [Simple(simpler than it's rating)]

217A - Ice Skating rate : 1200 -> dfs [Simple/Intermediate]

893C - Rumor rate : 1300 -> dfs [Simple]

476B - Dreamoon and WiFi rate : 1300 -> backtracking [Simple]

1638C - Inversion Graph rate : 1300 -> creativity [Simple/Intermediate]

1970C1 - Game on Tree (Easy) rate : 1300 -> trees + dfs/bfs [Simple/Intermediate]

96B - Lucky Numbers (easy) rate : 1300 -> backtracking [Simple]

1143C - Queen rate : 1400 -> trees + you can use dfs/bfs [Simple]

520B - Two Buttons rate : 1400 -> bfs [Simple/Intermediate]

580C - Kefa and Park rate : 1500 -> trees + dfs/bfs [Intermediate]

977E - Cyclic Components rate : 1500 -> dfs [Intermediate]

377A - Maze rate : 1600 -> bfs [Intermediate]

601A - The Two Routes rate : 1600 -> bfs / matrix [Intermediate/Hard]

1363C - Game On Leaves rate : 1600 -> trees / some edge cases only [Simple/Intermediate]

1144F - Graph Without Long Directed Paths rate : 1700 -> bipartite graphs [Intermediate/Hard]

1093D - Beautiful Graph rate : 1700 -> bipartite graphs [Intermediate/Hard]

1970C2 - Game on Tree (Medium) rate : 1700 -> a little hard + dfs/bfs [Intermediate/Hard]

Full text and comments »

  • Vote: I like it
  • +14
  • Vote: I do not like it