| layout |
|---|
default |
Note: This page will be updated regularly. Moreover, you can find the source code here.
Lecture 1 will be held on 22 January, 2018 (Monday) from 8:00 pm to 10:00 pm at LTC 5101.
Prerequisites: DFS Order (Refer to starting time, finishing time subheading). Also, it'd be great if you can go through Vanilla Mo's Algorithm tutorial (although it would be covered in the lecture)
Target: Three variations of Mo's (Vanilla, with Updates and Trees). We will be teaching the three variations through some problems.
Problems: DQUERY | SPOJ, 86D | CF, COT2 | SPOJ, 58 | UOJ, Tree and Coprime Queries | HE
Resources: Vanilla Mos, Mos on Trees, Mos with Updates
Self Study: Since there is a holiday on 26th January, the next lecture will only be held after a week of Lecture 1. For self study, it is recommended that you go through Segment Trees, because it will be extensively used in the weeks to follow. If you are unacquainted with Segment Trees, you can use this link. If you are unable to understand from there, refer Quora Wiki.
Here is a list of standard problems involving segment trees:
-
Easy Segment Tree: RPLN | SPOJ, CSUMQ | SPOJ, 1112 | LightOJ, KGSS | SPOJ
-
Medium Segment Tree: HORRIBLE | SPOJ, GSS1 | SPOJ, 1083 | Histogram, ORDERSET | SPOJ, 1188 | LightOJ
-
Medium-Hard Segment Tree: 1415 | LightOJ, 1204 | LightOJ
Post Lecture:
Here are the links for the problems discussed during the lecture: Grid of Many Xors, Segment Tree with GCD. The problems that we discussed in relation to Mos Algorithm are already present above.
It is recommended that you at least solve DQUERY, COT2 and a few segment tree questions before Monday, 29 January 2018, as a contest will be conducted on that day. The contest will have both easy and hard problems, so both beginners and advanced students are welcome to give it. The announcement for the contest will be made soon.
Updated on 27 Jan 2018: The first long contest will start on Sunday, 28 January at 9:00 a.m. The contest will be open for three days. The problems have been taken from different OJs, and mostly concentrate on Segment Trees and Mo's Algorithm. I'd like to thank Pranet Verma for collecting the problems.
A lecture will be conducted to discuss the problems of this contest. Details regarding the same will be shared soon.
Here is the contest link. You will need to create an account on vjudge to be able to participate.
Lecture 2 will be held on Friday, 02 February from 8:00 p.m to 10:00 p.m. in LTC 5101. The agenda will be to discuss the problems from Long Contest #1. Anyone who is familiar with Segment Trees should find the class useful. You can checkout the problems of the contest here.
Post Lecture:
You can find the solutions to the problems of long contest #1 on the github repo. There was an issue with the solution of problem C that was discussed in the lecture, this will be addressed in the next lecture.
Post Lecture: We discussed persistent segment trees (PSTs) in the lecture. You can use this blog to understand PST if you weren't able to attend the class. For those who did, be advised that the blog explains in a totally different way compared to the way PSTs were discussed in the lecture.
The problems discussed in the lecture were MKTHNUM and COT. Also, for bitset, you can refer to this comment which discusses the problem that was discussed in the class.
Also, don't forget to think on CRAYON | SPOJ. I will discuss it in the next class if needed.
Note: Please go through all the problems discussed so far and try to code as many as possible. Next long contest is in a week from now, so you should have sufficient time to do the same.
The second long contest of the season will start tonight, 17 February (Saturday) at 9:00 p.m. and will remain open until 18 February (Sunday) 11:00 p.m. (Duration: 26 hours).
The problem set is balanced in my opinion, so I encourage everyone to give it a shot.
Just create an account on https://vjudge.net to participate.
Note: The next lecture will only happen after mid-sems. Till then you are advised to go through all the problems listed in this page, and the problems that have already been covered in the contest.
For this week, there won't be any contest/lecture because of midsems. You can try solving the given problems till the next lecture/contest:
803G | CF, Concerts | Codeagon, Kth Number | MSC2015
Also, try and solve as many problems as possible under Orthogonal Range Search on LightOJ.
The third long contest of the season will start on 10 March (Saturday) at 9:00 p.m. and will close at 11:00 p.m. on 11 March (Sunday).
The next lecture will be held on 16 March (Friday) at 8:00 p.m. in LTC. The agenda will be to discuss one (or more) of the following:
- DSU on Trees
- Centroid Decomposition
- Heavy Light Decomposition
- Discuss previous contest's problems
The exact room number will be updated soon.
Post Lecture: You can use the following resources to complement what was discussed in the class:
We will continue our discussion of centroid decomposition in the next lecture.
In this week, try to solve as many problems as possible from the contest and the following problem bank. The next lecture will only be held after a couple of weeks. The plan for that will be updated soon.
The fourth long contest of the season will start on 17 March (Saturday) at 9:00 p.m. and will close at 11:00 p.m. on 18 March (Sunday).
Note: For the remainder of the week, try and go through the following problems. Moreover, for self study, you can read up on 2-SAT.
375D | CF, 444C | CF, 549F | CF
- Strongly Connected Components (and condensation graphs)
- 2-SAT : Tutorial, 228E | CF, 27D | CF, TORNJEVI | SPOJ
Next CPSIG lecture will be held on Thursday, April 12 at 8:00 p.m. in LTC. The agenda would be to discuss the following problems:
Tree and Coprime Queries | HE, COT2 | SPOJ, 1415 | LightOJ, 1204 | LightOJ, TORNJEVI | SPOJ, 549F | CF NAJKRACI | SPOJ, 946G | CF
Errata: The link for problem 549F on CF was wrong; it has been fixed now.
Long Contest 5 started on 14 April 2018 at 9:00 p.m. The contest will remain open for a week. This time most of the problems are tied to a reusable concept. Hence, I will share hints for some of the problems here soon.
You can find hints for the problems below:
1. Intro | Source
Square Root Decomposition.
2. Show Me Nova | Source
Heavy Light Decomposition.
3. Collision Minds | Source
Range update in Persistent Segment Tree. The key concept here is that there are two ways to implement lazy propagation — one involves splitting the node when we travel down it so as to propagate the lazy value; the other is to store the lazy value in the segment tree node during update, and while querying, pick up the lazy values from the nodes as you are descending them and pass it to the next recursive call of query via one of its parameters.
4. He'll Come | Source
Matrix Exponentiation. You could refer to this HE tutorial to learn it.
5. Boil Over | Source
Coastline Data Structure. You could refer to this TopCoder thread to understand it. I had created a sort of template some years ago. You can refer to it here.
6. As a Candle Burns Down | Source
Topological Sort.
7. Fractured Misery | Source
Parallel Binary Search. Tutorial.
8. Stay, Resist | Source
2-SAT.
9. My Recognition | Source
Gaussian Elimination or Simulation. This problem will be discussed in an upcoming lecture. Although, you should be able to come up with and implement a Gaussian Elimination based solution.
10. Becoming the Maelstorm | Source
Dynamic Programming Optimizations. Post1.
11. Without Senses | Source
Lambda Optimization. This will probably be discussed in class.
Due to numerous reasons, lectures on FFT and Flows couldn't be held. To make up for it, I have provided resources for both of them below:
Tutorials
- Working on a blog post on this