kartik8800's blog

By kartik8800, history, 13 months ago,

Hello Codeforces!

It's been a while since I contributed something useful to the CF community. So here I am trying my best to make some high quality lectures on range query data structures!

For trying out some range query problems: head to cses range query section
For solutions: my previously written cf blog

Video Series for range query DS

Range Query Problems and Data Structures

Welcome to the series on Range Query data structures and problems!! In this video we will discuss:
1. What are range query problems?
2. Types of Range query problems.
3. Online queries vs offline queries.
5. Common Range Query Data Structures for efficiently solving these problems.

Prefix Arrays

1. What are prefix arrays?
2. How to build them.
3. How to use them to answer queries.
4. Why can't we use them for range min or max queries?
5. Building a library for solving range query problems using prefix arrays.

Sparse Table | Range Minimum Query in O(1)

Introduction to Sparse Table.
Solve Range Min Queries in O(1) time.

1. what is sparse table?
2. how to build a sparse table?
3. how to use it to solve queries?
4. Cpp code.

Square Root Decomposition

Gentle introduction to Square Root Decomposition.
implementation of the idea discussed in the video: cpp code

To solve the problem of answering range queries on an Array A[1..N].
Queries are of two types:
1. find function F applied on the range [L,R]. F can be sum, min, max or wide range of other functions.
2. point update. set A[i] = new_value V.

Algorithm:

 1. Break Array A into X smaller chunks each with Y elements. 2. Find F applied over each chunk individually.

Why exactly root N chunks each with root N elements?

Upcoming topics

1. Mo's algorithm over arrays and trees.
2. Segment trees with/without lazy propagation.
3. Fenwick tree
4. Persistent data structures.
5. CF/CC/SPOJ Problem solving using above data structures

Hope people will find this useful.
Will keep updating this blog with more content.

Happy Coding :)

• +110

By kartik8800, history, 16 months ago,

Hello codeforces

I liked solving today's contest(on pen and paper :p) and I am sharing the solutions for problems A to D. hope this might help some of you :)

quick editorial for problems A to D

problem A

given n and b. find a such that a + b is maximum possible.

b = B[0] B[1] .... B[n-1]
a = A[0] A[1] .... A[n-1]

sum[i] = A[i] + B[i]

observations:
since we want sum to be as large as possible we want:
1. sum[0] to be as large as possible(hopefully 2 otherwise 1)
2. an integer with more digits is large, so we would like to retain all digits.

to retain all digits make sure sum[i] != sum[i-1]

go for a brute force to determine a.
find A[0] with no constraint. then find A[i] such that A[i] is not equal to A[i-1] and A[i] is as large as possible(2 > 1 > 0).

problem B

we need to find num such that num has atleast 4 divisors and the divisors have atleast a space of d among them.

any number > 1 has atleast two divisors: 1 and the num itself.
our 3rd divisor(d3) should be atleast 1 + d
and our 4th divisor(d4) should be atleast 3rd_divisor + d

if 3rd and 4th divisors are prime then our number will be equal to d3*d4.
any number can be represented as a product of primes.
num = d3*d4 where both d3 and d4 are prime is the best possible choice.

why? please provide good mathematical proof else I will provide a proof after writing other solutions.

so simply select d3 as the smallest prime number greater than 1 + d and select d4 as the smallest prime number greater than d3 + d.

problem C

sort the array.

observations:
1. always need to select the largest element of the array. why?
2. initially I may select any element a[i] (1 <= i < 2*n) along with a[2*n] and remove them.
3. thus x = a[i] + a[2n]

let us I say I selected the integers a[2n] and a[i] in the first move to delete. so ** x** is fixed.
for the remaining array also the observation 1 holds true.

make a table of the elements you have in the array.
map<int,int> element. where element[i] = j means that i appears j times in your remaining array.

to perform an operation you will select the largest element of the array i.e. L1, now you need an element from the array equal to L2 such that L1 + L2 = x

if element[L2] != 0 then you are good. and you should do:

 element[L1]-- delete L1  element[L2]-- delete L2  x = max(element[L1], element[L2]) new value of x
if element[L2] was already 0 then it is impossible to delete all elements if I initially select a[i] along with a[2n]

Simply try this for all possible i. that is for all possible initial element selected along with a[2n]

problem D(hint)

most crucial observation:

a[1] has only 1 neighbor and same for a[n]. try solving with this in mind.
so a[1] has to be reduced to 0 with complete help from a[2] no matter what(unless we use super power)

let us not use the super power.

after reducing a[1] with help from a[2], remaining portion of a[2] is now in a similar position: only 1 neighbor i.e. a[3]

try using superpower to swap a[i] and a[i+1] then answer is yes if:

you should be able to solve the array[1:i-2] and array[i+3:n] with only help from a[i-1] and a[i+2](precompute these values for all i). after this check if you can solve for array {some portion of a[i-1], a[i+1], a[i], some portion of a[i+2]}

i will shortly add a more detailed editorial for problem D

in more detail

first check if subarray A[1:i] can be solved without the use of superpower.(1 <= i < N)

cool, how to check?
A[1:1] can be solved if and only if A[1] is less than or equal to A[2] otherwise A[1:1] cannot be solved.
A[1:2] can be solved if A[1:1] can be solved and (A[2] — A[1]) <= A[3]
If I choose to solve A[1:1] without superpower it leaves an effect on A[2]. it reduces the value of A[2] to A[2] — A[1].
let me call this reduced_left[2] or reduced_left[i].

A[1:i] can be solved if A[1:i-1] can be solved and reduced[i-1] <= A[i]

reduced_left[i + 1]: in order to solve A[1:i] what was the value of A[i+1] reduced to.

second check if subarray A[i:N] can be solved without the use of superpower.(2 <= i <= N)

A[N:N] can be solved if and only if A[N] is less than or equal to A[N-1] otherwise A[N:N] cannot be solved.
on similar lines you will get a definition of reduced_left[i].

now answer is yes if A[1:N] is solvable assuming A[N+1] = A[0] = 0 (without use of superpower)

answer is also yes if I can swap A[i] and A[i+1] such that:
i. A[1:i-2] can be solved without superpower.
ii. A[i+3:N] can be solved without superpower.
iii. the array { reduced_left[i-1], A[i+1], A[i], reduced_right[i+2] } can be solved without superpower

try this for all i from 1 to N-1.

hope this helped.

• +30

By kartik8800, history, 17 months ago,

Just wanted to share some useful content on binary search with the people here at codeforces!

Binary search is best visualized as searching for a value X at which F(X) = Y where "F" is some function.

This notion of binary search can help efficiently evaluate:
->Local minima and Local maxima of a function.

you can evaluate things like:

1. highest point for a projectile using binary search

2. nth root of a number.

3. Cost minimization techniques like gradient descent and binary search play a crucial role in machine learning.

Here is a short playlist which outlines the essence of binary search in detail with lots of real-life examples and 6 interesting problems that can be solved with binary search.

Do share some fun real-life applications of binary search in comments!

• +29

By kartik8800, history, 17 months ago,

Hello Codeforces!

This blog is here to compile the resources that I have created over the past 6 months. I had started with the goal of creating a useful course on algorithms and problem solving, overall I wanted to provide high quality material which is free.

So I started with the most interesting topic(for me) dynamic programming and developed an extensive course on the same.

I feel the course is extremely useful for beginners as well as intermediates to get better at dp, learn some useful techniques and improve their problem solving skills. From the limited reviews that I have received on the content till now I can say that people have found my the content useful and explanations better than many paid courses which people usually opt-for.

I wanted to share the overview of the course here so it can reach more people.

Overview

Basics of DP:

I start with the very basics of DP so that someone with even 0 knowledge of the subject can follow. I start-off with easy problems from CSES and then slowly take the viewers from there to harder problems like CF div2E or rated-2400 problems on CF. I have created over 20+ illustrative problems for the viewer each with detailed explanation and code.

You can check the playlist here: DP from scratch

DP on Trees:

I have created another playlist/course for dp on trees. Here again the viewer will start with some very simple dp on tree problems and then we slowly ramp up the difficulties to problems from codeforces(rating-2000+). I describe techniques like rerouting, binary lifting and many more in detail. I discuss around 10 problems in detail with code so the viewer can have a good grasp over the concept of dp on trees.

Check the playlist here: DP on Trees

Digit DP:

I start by explaining the concept and application of digit dp followed by some illustrative problems from SPOJ, codechef and google kick start.

Link to the playlist: DIGIT DP

We will start with some classical problems like job assignment and travelling salesman and see how dp can be applied to these problems through the use of bitmasks. I will also describe what bitmasks are in a seperate video. Later we will solve some harder problems which involve the concept of bitmasking and DP from OJ's like codechef and codeforces.

check the playlist here: DP with Bitmasking

More Content

You can also checkout some of the other playlists on my channel like the one's on Binary Search, Coding interview problems, Codeforces problems and many more!

I also plan a series on graphs, hopefully sometime soon!

Make sure to checkout my channel and if you find it useful show support by subscribing to it and letting me know you like the content and effort through some nice comments :)
Hope that this course on dynamic programming will help many!

• +122

By kartik8800, history, 18 months ago,

Hello Codeforces!

This series of videos are focused on explaining dynamic programming by illustrating the application of digit DP through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder.

After going through this series, you should find yourself confident in solving problems which require the use of digit dp and also implementing them in a reasonable amount of time.

I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.

Some Basic elements of Dynamic Programming

Part 1: https://youtu.be/24hk2qW_BCU
1. What is Divide and Conquer?
2. What is Dynamic Programming?
3. Types of DP problems.

Part 2: https://youtu.be/yfgKw6BUZUk
1. What is a DP-state?
2. Characterizing a DP-state.
3. What is a recurrence?
4. Top Down v/s Bottom Up.

Part 3: https://youtu.be/X-3HklSPx6k
1. Directed Acyclic Graph(DAG) Representation of DP solution
2. Visualizing Top-Down and Bottom-Up.
3. Evaluation order for bottom-up codes.
4. Analyzing the space and time complexity for a DP solution(derivation).

You may also want to checkout these video tutorials:
- Beginner Friendly Series on Dynamic Programming
- Dynamic Programming on Trees
- Introduction to DP with Bitmasking

Introduction to Digit DP

I discuss the following concepts in this video:

1. What exactly is Digit DP?
2. What are the types of problems I can solve with Digit DP?
3. Discussing a sample problem and it's brute force solution.
4. Building up an intuition towards a DP based solution.
5. Further discussing another concept required for solving Digit DP problems.
6. Coding the solution which we came up with.

Google Kick Start Round H 2020: Boring Numbers

I'll discuss a problem named boring numbers that comes from a Google kick start round.
Solution: https://youtu.be/2yAEj-0A8bk

Codechef long: Encoding

Solution: https://youtu.be/B7ZWUBfaIq0

CSES: Counting Numbers

Solution: https://youtu.be/lD_irvBkeOk

Will be adding more videos soon!
Hope people find this helpful :)

UPD: added spoj digit sum and codechef enocding. This is the last video for this series(at least for now) unless there are many people who want more.
UPD: added solution to standard digit dp problem from CSES, namely counting numbers.

• +66

By kartik8800, history, 18 months ago,

So I had proposed a problem few months back but didn't get the time to prepare an entire contest. Wanted to share the problem and it's editorial which I wrote while proposing.

Came across something similar while reading and implementing a research paper.

Problem statement
Constraints
Example
Editorial

Problem Origin: equation number 2 in the paper "Exploring Nearest Neighbor Approaches for Image Captioning"

Hope you enjoy solving the problem :)
also let me know what difficulty you think should be assigned to this problem.

• +12

By kartik8800, history, 21 month(s) ago,

Hello Codeforces!

This series of videos are focused on explaining dynamic programming by illustrating the application of DP with bitmasking through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder.

After going through this series, you should find yourself confident in solving problems which require the use of dp and bitmasks and also implementing them in a reasonable amount of time.

I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.

Some Basic elements of Dynamic Programming

Part 1: https://youtu.be/24hk2qW_BCU
1. What is Divide and Conquer?
2. What is Dynamic Programming?
3. Types of DP problems.

Part 2: https://youtu.be/yfgKw6BUZUk
1. What is a DP-state?
2. Characterizing a DP-state.
3. What is a recurrence?
4. Top Down v/s Bottom Up.

Part 3: https://youtu.be/X-3HklSPx6k
1. Directed Acyclic Graph(DAG) Representation of DP solution
2. Visualizing Top-Down and Bottom-Up.
3. Evaluation order for bottom-up codes.
4. Analyzing the space and time complexity for a DP solution(derivation).

You may also want to checkout these video tutorials:
- Beginner Friendly Series on Dynamic Programming
- Dynamic Programming on Trees

Short video where I talk about the playlist: https://youtu.be/6sEFap7hIl4

I talk about what is bitmasking before we actually start solving problems that use dp with bitmasking.
https://youtu.be/7FmL-WpTTJ4

Illustration: Solving the Job Assignment Problem

Using a simple problem, I will illustrate how to solve and implement problems which use dp+bitmask concepts.
Solution: https://youtu.be/685x-rzOIlY

Illustration: Travelling Salesman Problem

Another great problem to illustrate bitmask dp.
I will discuss the following:
1. What is the TSP?
2. Brute force solution.
3. Intuition towards an efficient solution.
4. Define a DP state, write a recurrence.
5. How do I implement this? ANS: bitmasking!
6. Analyzing time and space complexities.

Codeforces Problem: Div2E

I'll discuss a problem named Fish that comes from a Codeforces Divison 2 round.
Solution: https://youtu.be/d7kvyp6dfz8

Codechef long Challenge: Medium

The problem comes from Codechef long challenge and is rated MEDIUM by codechef.
Solution: https://youtu.be/Smem2tVQQXU

CSES: Counting Tilings

The problem comes from CSES problemset and was introduced to the problemset in 2021.
Solution: https://youtu.be/lPLhmuWMRag

If people find this helpful then I will try and add more problems to this list :)

• +148

By kartik8800, history, 22 months ago,

This series of videos are focused on explaining dynamic programming by illustrating the application of DP through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder.

After going through this series, you should find yourself confident in approaching dynamic programming problems and also implementing them in a reasonable amount of time.

I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.

Some Basic elements of Dynamic Programming

Part 1: https://youtu.be/24hk2qW_BCU
1. What is Divide and Conquer?
2. What is Dynamic Programming?
3. Types of DP problems.

Part 2: https://youtu.be/yfgKw6BUZUk
1. What is a DP-state?
2. Characterizing a DP-state.
3. What is a recurrence?
4. Top Down v/s Bottom Up.

Part 3: https://youtu.be/X-3HklSPx6k
1. Directed Acyclic Graph(DAG) Representation of DP solution
2. Visualizing Top-Down and Bottom-Up.
3. Evaluation order for bottom-up codes.
4. Analyzing the space and time complexity for a DP solution(derivation).

Problem 1: Dice Combinations

Source: CSES
Explanation: https://youtu.be/5gd5jptXWAM

Problem 2: Coin Combinations I

Source: CSES
Explanation: https://youtu.be/5BdAl6gfusg

Problem 3: Coin Combinations II

Source: CSES
Explanation: https://youtu.be/-pXjopzMVrE

Problem 4: Removing Digits

Source: CSES
Explanation: https://youtu.be/32qvB7OP4V8

Problem 5: Grid Paths

Source: CSES
Explanation: https://youtu.be/V64F4wlodUM

Problem 6: Book Shop

Source: CSES
Explanation: https://youtu.be/qpNy2nuSuaI

Problem 7: Array Description

Source: CSES
Explanation: https://youtu.be/d1H5JylYG4I

Problem 8: Edit Distance

Source: CSES
Explanation: https://youtu.be/Ev80c1oIRFg

Problem 9: Rectangle Cutting

Source: CSES
Explanation: https://youtu.be/LdynQjWsO5Q

Problem 10: Two Sets II

Source: CSES
Explanation: https://youtu.be/TOsD3BkIKoQ

Problem 11: Beautiful Array

Source: Codeforces
Explanation: https://youtu.be/IgBLv32QFoQ

Problem 12: Number of Valid Arrays

Source: Coding Interview

Problem 13: Longest Increasing Subsequence O(NlogN)

Source: CSES
Proof and optimization to NlogN: https://youtu.be/66w10xKzbRM
Implementation of the algorithm: https://youtu.be/wqLwv7E1GF0

Problem 14: Projects

Source: CSES
Solution Approach: https://youtu.be/MJn3ogwsUbo
Implementation of the algorithm: https://youtu.be/ISuIwMnSyXc

Problem 15: Beauty of Tree

Source: Kick Start
Explanation: https://youtu.be/ueLRceYVcdE

Problem 16: Catch Some

Source: Kick Start
Explanation: https://youtu.be/ljLIrNKLANE

Problem 17: Vasya and Binary Strings

Source: Codeforces (rated:2400)
Explanation: https://youtu.be/NINZAQFW_AE

Problem 18: Counting Towers

Source: CSES 2021 problem
Explanation: https://youtu.be/pMEYMYTX-r0

I am quite confident that many beginners/intermediates will definitely enjoy watching this series on dynamic programming and it will definitely help in getting better at dynamic programming and problem solving in general. I have tried to teach in a way such that not many prior prerequisites are required to understand the explanations even to the harder problems.

If people find this helpful then I will make sure that this list of problems will keep growing, cheers!

Link for introduction to DP on Trees: https://codeforces.com/blog/entry/79857

UPD: Added 2 more problems from CSES: Projects and Removing digits.
UPD: Added 3 parts on basic elements of DP to get you started.

UPD: I have also started a series on DP with bitmasking(starting from the very basics) and in the future will make a separate blog for both Digit DP series and DP with bitmasking series, till then interested people can check: Dynamic Programming with bitmasking
UPD: added solution to problem Vasya and Binary Strings
UPD: added solution to problem Counting towers from CSES

• +120

By kartik8800, history, 23 months ago,

Hello Codeforces!!

In this blog, I want to present to you a beginner-friendly video lecture series on dynamic programming on trees/an editorial for the CSES tree algorithms section.

CSES is a brilliant problemset for people wanting to get started at competitive programming and get good at it.

My aim till now has been to make the explanations intuitive, crisp and clear. I feel even a beginner will be able to benefit from these video lectures.

So let's get started.

Subordinates

Explanation : https://youtu.be/fGznXJ-LTbI
AC code : https://github.com/kartik8800/CSES/blob/master/Subordinates

Tree Matching

Somehow I feel some other nice approaches are also possible, please do share.
Explanation : https://youtu.be/RuNAYVTn9qM
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Matching

Tree Distances I

This problem uses the rerooting technique, we evaluate the answer for every node assuming it to be the root of the tree. If we do this naively this will be O(N^2) time but if we do this using something known as the reroorting technique and propogate partial answers of parent node with respect to the child nodes we can optimize our solution to O(N) overall time complexity.
I feel Tree Distances II is easier compared to Tree Distances I and would recommend to try it first.

Tree Distances II

This problem also uses the rerooting technique.
Explanation : https://youtu.be/nGhE4Ekmzbc
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%202

Distance in Tree

This problem also uses the rerooting technique.
Explanation : https://youtu.be/SOhZqL6HPjQ

Company Queries I

This problem uses a technique(the technique itself uses DP) known as Binary lifting. I will be adding a detailed lecture on binary lifting with code.

Explanation : https://youtu.be/FAfSArGC8KY

Company Queries II

This problems requires us to know a technique to calculate LCA of two nodes in a tree in O(logN) time. Evaluation of LCA in O(logN) can be done using binary lifting. I will add a more detailed video soon.

LCA using binary Search: https://youtu.be/qPxS_rY0OJw
LCA slightly different from standard algorithm: https://youtu.be/s9zZOVsF_eo

Distance Queries

Problem Statement : what is the distance between nodes a and b?
Short explanation : Let LCA(a,b) be node x, what is distance between a and x?
Preprocess the levels of all the nodes in the tree.

lvl[i] : level of node i in the tree.
Ans to query distance(a,b) = (lvl[a] — lvl[x]) + (lvl[b] — lvl[x]) where x is the LCA(a,x).

Again finding LCA of two nodes can be done in O(logN) time and levels of all nodes can be found in O(N) time preprocessing.
Explanation: https://youtu.be/i9ctLWyVSsA

Appleman and tree

problem statement: https://codeforces.com/problemset/problem/461/B
solution video: https://youtu.be/gj0zp--fBL8

Binary Tree Cameras Leetcode

problem statement: https://leetcode.com/problems/binary-tree-cameras/

I am also planning to add video lecture series on more topics which might be helpful to beginners as well intermediates. I will be open to feedback and suggestions.

I hope people find this helpful :)

UPD: added detailed explanation for binary lifting and video solution to Company Queries I.
UPD: added detailed explanation for LCA techniques.
UPD: added solution to distance queries(CSES) and Distance in Tree(CF, VKCup,Problem D).
UPD: added solution to appleman and tree from codeforces.
UPD: added solution to binary tree cameras from leetcode.

• +117

By kartik8800, history, 23 months ago,

Hello Codeforces!!

Recently I was fascinated about two of the most amazing things in the world : money and ofcourse algorihtms xD. I saw some interesting games played at casinos and I thought about one of them for quite a while : The Roulette.

The Roulette

Consider a spinning wheel with numbers from 1 to 12 marked on it. Each number has an equal probability of showing after the wheel has stopped spinning. The player(will avoid the word gambler) has the following power : he may bet some coins on either odd/even. Let's say the player bets x coins on even. If the roulette after spinning shows an even number than the player gets 2x coins otherwise he loses x coins. Similarly if the player bets x coins on odd then he will win 2x coins if roulette shows an odd number after spinning.

Possibility of an Algorithm for winning?

So is it possible for us to design a sure-shot algorithm that can guarantee the player to win some profit?

Spoiler

Then why are we even here?
So it might not be possible to guarantee a profit but maybe we can come up with strategies/algorithms that make a certain amount of profit with a certain confidence/probability.

Motivation : The Martingale Algorithm

So the martingale algorithm in my opinion is simple and brilliant with a great deal of drawbacks.
Suppose that we wish to make a profit of x coins.
Here is the algortihm:

 Let X be an integer. 1. Bet X coins on odd. 2. Let the roulette spin. 3. If outcome is odd, go to step 5. 4. X := 2 * X and go to step 1. 5. END.

Wonderful, isn't it? Sorry to say that it has a great deal of drawback because to be fair it has only 1 drawback.

Drawback

Also another drawback which for now we will overlook : usually casinos have an upper limit on the bet you can place. In the very unlikely event of lots of consecutive loses there will be a disaster.

"I have enough coins and the amount of profit I want to make is considerably smaller, nearly 1% of the coins I have. What is the chance I stand to win this profit using martingale algorithm?"

Probability

Cooool, so now probably I should give some modified or new strategy for higher winning chances? No, instead I am here with a challenge.

The Challenge

You are given 10K coins, you need to come up with an algorithm/strategy which stands a good chance of winning/making profits.

There will be exactly 5K roulette spins, giving you the opportunity to make bets.

I am super interested in people coming up with some algorithms that maximize the chance of winning.

So here is the challenge, design a strategy and implement it to check what profit do you make. Here I am providing a template code in which the user simply needs to implement the make_bet() function. Basically you will be building a betting bot to play roulette for you and earn as much as possible.

What about the bot getting lucky? How will scoring be done?

Scoring

A few rules :
Try to keep your bot deterministic/don't use rand() in your make_bet function.
Do not try to utilize the pseudo-randomness of rand(), if that is a possibility.

I know we all would love to maximize the score of the bot.
Here is the template code : Betting Bot challenge
Hope people find this fun and interesting.

P.S. Do not gamble :)

• +26

By kartik8800, 2 years ago,

Hello Codeforces, In this blog I will try to write a well detailed editorial for the CSES Range Queries section. The motivation for this editorial comes from https://codeforces.com/blog/entry/70018.

Quoting icecuber "I think CSES is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES."

So here I am writing an editorial for the range queries section.

If you find any error or maybe have a better solution to some problem please do share.

Range Sum Queries I

Given array is A[1..N], for each query of form (L,R) we need to output A[L] + A[L+1] + ... + A[R].
Define an array Prefix such that Prefix[i] = A[1] + A[2] + .. + A[i].
Prefix[R] = A[1] + A[2] + ... + A[R] and Prefix[L-1] = A[1] + A[2] + ... + A[L-1].
Consider Prefix[R] — Prefix[L-1] = (A[1] + A[2] + ... + A[R]) — (A[1] + A[2] + ... + A[L-1]) = (A[L] + A[L+1] + ... + A[R]).

So for every query simply output Prefix[R] — Prefix[L-1].

How Do I build the prefix Array.

Time complexity : O(N) to build prefix array and O(1) per query.

Range Minimum Queries I

Two possible ways are as follows :
1. Build a Range minimum query segment tree in O(N) time and answer each query in O(logN).
2. Build a sparse table in O(NlogN) time and answer each query in O(1).

Code for approach 1

Refer https://codeforces.com/blog/entry/71101 for my segment tree template.

Range Sum Queries II

So this one is a direct use of segment tree with point updates and I shall use my segtree template to answer this problem.

Code

Both of these queries can be performed in logN time.
Overall time complexity is O(N) for building segtree and QlogN for Q queries.

Range Minimum Queries II

Again a straightforward segment tree problem and I will use a similar code as I used for the previous problem. This is the same as RMQ1 except that here we also have point updates. Segment tree solution for RMQ1 and RMQ2 will be identical.

Code

Both of these queries can be performed in logN time.
Overall time complexity is O(N) for building segtree and QlogN for Q queries.

Range Xor Queries

For this problem we can maintain a segment tree where each node of the tree will store the xor-sum of the range of elements for which it is responsible.
So root of the tree stores : A[1]^A[2]^....^A[N].

To calculate the answer for a particular interior node of the tree we do :
NODE_VAL = LEFT_CHILD_VAL ^ RIGHT_CHILD_VAL
For leaf nodes :
NODE_VAL = A[x], where [x,x] is the range this leaf node is responsible for and if x > N then NODE_VAL = 0 as 0 is the identity for xor_sum.

Again with these observations we can use the same segtree template as follows :

Code

AC code : https://ideone.com/mPhqas

Range Update Queries

Nice question which can be directly solved with a segment tree with lazy propagation but that is an overkill plus my segtree library does not support lazy propagation as of now.

Let's define a few terms:
SUM[i] = overall update done on the ith element till now
Initially SUM[i] = 0 for all i as no updates have yet been performed, now we would like to track the updates happening so that our answer to a query 2 k can easily be v[k] + SUM[k] where v is the initial array.

How to efficiently maintain the SUM array? Let us build a range sum query segment tree on some array X which has all elements initialized to 0.

DEFINE : RSQ[i] = X[1] + X[2] + .. + X[i] = rangeSumQuery(1,i)

Now say we have a query which tells us to add u to all elements in the range [l,r] then if I perform a point update and make X[l] = X[l] + u think what happens to RSQ[i] for different values of i.

RSQ[i] is unaffected for all i where i < l
and RSQ[i] = RSQ[i] + u for all i >= l.

Effectively we just did a range update on the abstract array RSQ and the range update is equivalent to adding u to all elements of array RSQ from l to N.

But we wanted the range update to be only for the range [l,r], so we should now do a range update in which we subtract u from [r+1,N] and this is the same as doing a point update to X[r+1] such that:

X[r+1] = X[r+1] — u

it must be easy to see the abstract array RSQ is nothing but the required SUM array.

So here is the algorithm :

 For every range update query (l,r,u):   point_update(l,current_val + u)   point_update(r+1,current_val — u) For every query -> value at pos idx:   print SUM[idx] + V[idx]

AC code : https://ideone.com/vBZpYx
Time complexity per query is logN.

Forest Queries

For every query of the form (x1,y1,x2,y2) we need to answer the number of trees inside the rectangle described by the top left cell of rectangle (x1,y1) and the bottom right cell of rectangle (x2,y2).

Define : DP[i][j] as the number of trees in the rectangle described by (1,1) and (i,j).

Can we use DP matrix to evaluate answers for every query?

Spoiler

Ok, but how?

Spoiler

How to build DP matrix?
Let tree[i][j] = 1, if there is a tree at cell (i,j) else tree[i][j] = 0.

 DP[0][0] = DP[-1][0] = DP[0][-1] = 0 for i from 1 to N:    for j from 1 to N:     DP[i][j] = DP[i-1][j] + DP[i][j-1] — DP[i-1][j-1] + tree[i][j]

Time complexity for build O(N*N) and time complexity per query is O(1).
AC code : https://ideone.com/5dGTfY

Hotel Queries

Observation : For each group, we need to find the 1st hotel with enough vacancies and book rooms for the group in that hotel.

Brute force : Start checking every hotel from left to right for the number of rooms it has. As soon as you find a hotel with enough rooms use required number of rooms in this hotel. Repeatedly do this till all groups have been assigned a hotel.

How to optimize?

How do I know if there is any hotel in the first x hotels which can be assigned to the current group?

Spoiler

Algorithm :

 For each group gi with size si:   Find the 1st hotel x such that vacancy(x) >= si.    Do point update : vacancy(x) = vacancy(x) — si.    Print x.   If no valid x exists print 0.

Time complexity is O(Mlog^2N), logN steps for the binarySearch and each step of the binary search uses the Range max query segment tree which works in logN time.

List Removals

Brute force is quite simple if you simply simulate what is mentioned in the problem.
Let us try to optimize. So whenever we are asked to delete some xth element of the list we need to first locate the xth element, print it and then delete it.

How can we make the above processes faster?
Let us keep a boolean array PRESENT of size N and PRESENT[i] = 1 if the ith element of the list has not yet been deleted, 0 otherwise.

Now let us say we have the query : delete the xth element of the list, then this means we are going to delete the element at the jth index of the initial list such that :

1. PRESENT[j] = 1.
2. sum of PRESENT[i] for all i from 1 to j = x.

Why above conditions are necessary and sufficient to locate the correct element?
If are we deleting the element it has to be present in the list currently and so PRESENT[j] should be 1.
If this element at index j(of the initial list) is the xth element of the list(current state of the list) then there are exactly x elements present in the list in range [1,j](of the initial list) and remaining j — x elements got deleted in some previous queries.

How do I find this j?

Spoiler

Ok, elaborate.

Spoiler

How do I find number of elements not yet deleted in the range [1,j]?

Hint : problem comes from range query section

Once you have found the correct j, you need to print it and also mark PRESENT[j] = 0 and make the required point update in the segment tree.

Time complexity analysis is similar to previous problem.

AC code : https://ideone.com/anpuXy

Salary Queries

Okay so, this seems a bit hard. Maybe if the max possible salary of the employees was limited to some smaller amount(instead of a billion) we might be able to solve it.

So try solving the problem under the constraint that p,a,b <= 10^7.
Now the problem is much easier if I maintain the number of people with a given salary, let us define
freq[i] : number of employees with the salary i
We may now build a range sum query segment tree on this array and to answer a query we simply calculate the sum of the range [a,b].

For updating the salary of some employee from x to y, we do the point updates freq[x] -= 1 and freq[x] += 1 because now 1 less employee has salary x and 1 more employee has the salary y.

But the problem is not solved, since we needed to do this for max possible salary = 1billion, but now we know how to do it for 10^7.

observation

So lets group the salaries into 10^7 buckets and each bucket represent a range of 100 different contiguous salary values. The 0th bucket represents salaries from 1 to 100 and ith bucket represents the salaries from (i)*100 + 1 to (i+1)*100.

These buckets will store aggregated number of employees that have salaries in the given range represented by the bucket.

Now for query [a,b] : all the buckets that are entirely in the range [a,b] their aggregate values should be taken and summed up and for the 2 partial buckets(or 1) not entirely included in the range [a,b] we shall do a brute force.

So build a segment tree over the buckets and calculate the sum over all completely included buckets in the range [a,b]. For remaining partially included buckets do a brute force(actually iterate over approx 100 possible values and choose to include those which are required by a particular query, refer code).

A code will make this explanation much more clear.

AC code : https://ideone.com/zg97c8

Time Complexity?

other way to do it is using a dynamic segment tree in which you only build a node of the tree when it is needed.

Distinct Values Queries

This is a direct application of the MO's Algorithm. You may read more about MO's algorithm on https://blog.anudeep2011.com/mos-algorithm/

The brute force can be done by simply iterating from index a to b and maintaining number of distinct elements seen till now and a frequency array to indicate which elements and how many occurrences of those elements is present.

Frequency[i] = count of occurences of i in the current range.

Next we try to build the required ADD and REMOVE functions which help MO's algorithm to function properly.
To ADD a new element in the current range simply check if this element is already present(frequency > 0) and if it is present just increase its frequency else if its frequency was 0 then make it 1 and also increase the number of unique elements in the range.
To REMOVE an element from the current range, decrement its frequency by 1, if its frequency reaches 0 then decrease the number of distinct elements in the current range.

After this sort the queries as described by MO's algorithm and you are done.

Twist : We cannot use frequency array as value of individual element can go upto 10^9. So what I'll simply use an unordered_map?

No, unordered_map solution will time out due to high constant factor involved.

How to continue using the frequency array?

Time complexity : O((N+Q)root(N))

AC code : https://ideone.com/RkC547

Subarray Sum Queries

Let us try to keep track of the max sum subarray in a particular range [L,R]. If we were to build a segment tree in which each node of the tree stores max sum subarray of the range that the node is responsible for then the root keeps track of max sum subarray in the range [1,N].
However for segment trees to be efficient we need to generate the answer of interior nodes of the tree using the answers/information provided by the child nodes.

Now let's try to generate the answer for some interior node P of the segment tree assuming that we already have the answers for the children of the node P.

Node P is responsible for the range [l,r], its left child is responsible for the range [l,mid] and its right child is responsible for the range [mid+1,r].

Now we need to find the sum of max sum subarray in the range [l,r].
Assume you have all necessary information about the child nodes but if you have some information about a child node you also need to generate that piece of information for the parent node as well(since this node also has a parent which will use information given by P to generate it's answer).

Agreed, now what info to keep for every node?

So to summarize, for every node which represents the range [l,r] we should store :
1. sum of max sum subarray in the range [l,r].
2. maximum possible sum of some prefix [l,x] (such value of x is chosen, such that l <= x <= r and sum of elements in range [l,x] is maximum possible.)
3. maximum possible sum of some suffix [x,r].

We now know how to calculate sum of max sum subarray for some node using the above mentioned information about children nodes but as discussed we should also calculate prefix and suffix info for the parent also.

How to calculate prefix and suffix for parent node

Refer the combine function in the code for more clarity.
AC code : https://ideone.com/MhVmBs

Time complexity : logN per update.

Forest Queries II

Problem is almost the same as Forest Queries but we also have point updates.
I will discuss two approaches, one of them is quite efficient while the other one struggles to run in the time limit(passes if constant factor is low).

Approach 1

Let us do build the same DP matrix which we had built for the problem Forest Queries. If somehow we are able to keep our DP matrix consistent with the updates then our answer will be the same as before.

ANSWER TO QUERY (x1,y1,x2,y2) : DP[x2][y2] — DP[x1-1][y2] — DP[x2][y1-1] + DP[x1-1][y1-1]

How to efficiently track the updates that happen on some entry DP[i][j]?

Which entries of the DP matrix change if cell (i,j) is updated?

Alright, so now I need to efficiently add or subtract 1 from all the matrix entries (x,y) where that x >= i and y >= j.

So how do we track these updates?

Time complexity O(Q*N*logN)
Code for fenwick tree is taken from : https://cp-algorithms.com/data_structures/fenwick.html

Approach 2
This approach is more efficient and some might also find it easier to understand.
It uses a 2D Binary Indexed tree to achieve an overall time complexity of O(N^2 + Q*log^2(N)).

No surprises here. My solution will use the data structure and the technique related to that data structure which most would have already guessed after reading the problem statement. The important thing would be a thorough understanding of the concept and a neat implementation(I have tried to make it readable).

what data structure, what technique?

Alright so our segment tree needs to support the following operations :
1. increase values in range [l,r] by x.
2. set values in range [l,r] = x.
3. return sum of values in range [l,r].

Think about what information should we store per node of the tree, so that we are able to lazily update our nodes when a new update comes in and we are able to propagate the updates downward when needed.

To better understand lazy propagation, I recommend reading this : Super amazing theory in 1 comment (My implementation uses applyAggr and compose functions mentioned here).

What info to store per node?
How do I find the actual Sum using these variables?
How do i propagate these updates downward?

Time Complexity is logN per query.
If something is not explained or if something isn't clear feel free to ask but I recommend understanding lazy prop well before attempting the problem or reading the editorial.
AC code : https://ideone.com/8HQxMk

Please feel free to point out mistakes, suggest better/alternate solutions and to contribute.
I'd be glad to know if this helps :)

P.S. Will add remaining problems in a few days.

UPD : Editorial is almost complete with 2 problems left. 2nd last uses segment tree with lazy prop and I am guessing the last one uses some kind of persistent data structure, will add soon.

• +181

By kartik8800, history, 3 years ago,

I have been recently working on preparing libraries for commonly used data structures in competitive programming.

here is a link to the code : https://github.com/kartik8800/segTree

The above segment tree library should (according to me) work for a huge number of range query problems with point updates.

The things you need to specify to declare a segment tree is a function combine that tells the tree how to combine the results of child nodes to form parent node, an array for which the tree is to be constructed and a value such that combine(x, value) = x.

Here are a few examples:

vector dataVector = {5, -8, 6, 12, -9};

int small(int x,int y){return min(x,y);}
SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small);

int sum(int x,int y){return x+y;}
SegmentTree < int > rangeSumQueries(dataVector,0,sum);

long long product(long long x,long long y){return x*y;}
SegmentTree < long long > rangeProductQueries(dataVector,1,product);

also have a look at the following solutions to popular SPOJ segment tree problems:
solution to SPOJ GSS1 using segTree library : https://ideone.com/EFxf6O
solution to SPOJ KGSS using segTree library : https://ideone.com/fUK5Jz

I wonder if it is possible to provide a similar implementation of the segtree with lazy propagation, would be amazing to receive help with that.
It would be great to know if people find this helpful and also check out implementations of other commonly used data structures like tries, DSU, minQueue and more.

UPD: made a video explaining the usage and features https://youtu.be/K-86mKNAsmU