rachitjain's blog

By rachitjain, history, 7 days ago, In English,

Hi everybody,

If you can recall, I had written a tutorial for a relatively new Data Structure: Wavelet Trees.
The link to that post is here.

I have made a video tutorial for the same. Check out the video here.
Tutorial — Wavelet Trees | Introduction to New Data Structure

Happy Coding!

Read more »

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

By rachitjain, history, 2 weeks ago, In English,

Hi everybody,

I recently solved an interesting problem based on matrices, math, data structures and dp.
I made a YouTube Video in 2 parts for it.
The 1st video talks about the problem and approaching the solution.
The 2nd video talks about the squareroot decomposition part.

Solving this problem, you will learn:
1. How DP problems can be mixed with Data Structures to make them complex.
2. How SquareRoot Decomposition can be useful and its another application in the world of Competitive Programming(CP).

To read more about it, go to this link on my blog.

If you want to view more such videos, checkout my YouTube channel or follow my Facebook Page.

I hope you guys will like it!
I think it'll be a very good read for beginners especially!

Read more »

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

By rachitjain, history, 3 weeks ago, In English,

Hi

I've explained the solution for problem D from today's contest in my YouTube video.
It was a nice math based problem, solved using tries. Code link will be added later in the video description.
I will be adding the video for C tomorrow.

If you want daily updates about my channel,
1. Subscribe to the channel.
2. Follow the facebook page.

Cheers!

Read more »

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

By rachitjain, history, 4 weeks ago, In English,

Hi everybody :)
Incase you don't know, I had recently started a YouTube Channel for Competitive Programming, Math, etc.
Here is the 2nd video of my Dynamic Programming Playlist that teaches how Matrix Exponentiation can be used to solve DP problems faster.
The link to 1st video is here.
Next video is coming soon which is a DP problem from GOOGLE APAC contest.
So if you haven't already subscribed to the channel, do it now so that you don't miss the future videos.
You can also like and follow my facebook page to get updates regarding the same.

And finally, I am happy to announce that the family has grown to 500+ subscribers in less than a week.
Thanks a lot for your love and support.

Read more »

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

By rachitjain, history, 4 weeks ago, In English,

Hi

I have already released the playlist for Codechef August Long Challenge 2017 here.
A lot of coders face issues with DP as a beginner..
It can be very scary at first, and I understand that.

This is my attempt where I have started a playlist on YouTube where in I will publish videos starting from beginner level, and slowly delve into complex yet interesting problems associated with Dynamic Programming.

DP Playlist Link
DP Tutorial Video Link

In my first video, I've taken a "E" level problem(its easy, but the contraints can be upgraded to make it tougher) from Codeforces and explained
1. The intuition behind the DP states.
2. How do we decide the DP states.
3. How do we find the DP recurrence relations.

My next video for Dynamic Programming + Matrix Exponentiation is coming soon ;)

So stay tuned! Follow the Facebook Page : Click here

Happy Coding B-)

Read more »

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

By rachitjain, history, 5 weeks ago, In English,

Hi

I've put in a lot of my efforts this time, kept the video detailed so that a lot of people including beginners are able to understand how to solve this tough squareroot decomposition problem HILLJUMPING from Codechef August 17 Long Challenge.

Check out the video here.

Read more »

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

By rachitjain, history, 5 weeks ago, In English,

EDT1: Guys its a really needed request to please LIKE the videos if it helped you. This is very much important for me as more likes builds more trust for the future viewers.

Hi CF community,

I always wanted to make my own YouTube Channel dedicated for Competitive Programming.
I had already started off with my blog at http://rachitiitr.blogspot.com
Check that if you haven't already. I talk about some tips for CP, and discuss interesting problems that I encounter on daily contests from AtCoder, Codeforces, Hackerrank or Codechef.

At present, I plan to upload my video screencasts of online contests and video tutorials of some interesting programming problems that I encounter during daily online contests.

The pattern each video follows is:
1. Problem Description
2. Explanation/Solution
3. Code Implementation/Discussion

As a beginner, I was a bit slow while talking and I request all of you to watch the videos at 1.25x or 1.5x speed for better experience.

To begin off, I've covered some problems from the Codechef August Long Challenge.

  1. Palindromic Game(Analysis based, medium)
    => Video Link

  2. Chef and Fibonacci Array(Medium DP)
    => Video Link

  3. Strings and Graphs(Interesting analysis, medium-hard)
    => Video Link

Video for Hill Jumping will be coming soon :)

Why should you subscribe to this channel:
1. You couldn't solve problems I make videos about: majorly covers beginners and intermediate level coders.
2. You face difficulty in understanding the text editorial.
3. You enjoy engaging yourself with difficult yet interesting problems.
4. You really wanted some YouTube channel that talks about problems based on data structures and algorithms, and discuss how they can be solved.

I hope this will help many people. Please subscribe and like the videos if you found them helpful.
Comment if you face any difficulties or if you have any recommendations for me.

With my common sense and your feedback, I hope the future videos will be of much greater quality :)

Have a good day!

Read more »

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

By rachitjain, history, 3 months ago, In English,

Hi CF community,

http://rachitiitr.blogspot.in/2017/06/an-interesting-problem-on-array.html

Continuing my journey of sharing the problems that I really liked, please read the above blog post talking about a problem where you have to convert an array into another given array.

This is a problem I really liked from AGC 16. The editorial mentioned can be overwhelming for some of the beginners, and I tried my best to explain the theory behind the solution.

By this problem, you might also learn a scenario that frequently appears in the world of competitive programming which is the property of graph obtained when edges are directed from a[i] to b[i], where a is an array and b is a permutation of array a.

Overall, I had fun solving this problem and working on the analysis. It will be better if you read my blog + editorial mentioned at AtCoder too.

Read more »

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

By rachitjain, history, 3 months ago, In English,

Hi CF Community,

http://rachitiitr.blogspot.in/2017/06/wavelet-trees-wavelet-trees-editorial.html

I think it's safe to assume that this is a new data structure for most of us.
Consider the following problems:
1. Number of elements in subarray A[L...R] that are less than or equal to y.
(Persistence Segment Tree? Ordered multiset + BIT ?)
2. Number of occurrences of element x in subarray A[L...R].
(Subpart of 1st problem)
3. The kth smallest element in subarray A[L...R].
(Ordered multiset + BIT would work for subarrays beginning from index 1)

I know you might have many other solutions, and you might think what I am trying to prove.

What if I told you, all of the above can be easily done in O(logn) using Wavelet Trees :o. Plus, its very easy to code :D Awesome, isn't it?

Check the implementation here.

The post just introduces the basic usage of wavelet trees. There is still more that you can do with them.
I will write about them later, once I gain enough sleep maybe?

Read more »

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

By rachitjain, history, 3 months ago, In English,

http://rachitiitr.blogspot.in/2017/06/a-superb-problem-on-hashing-queries-on.html

This was my favorite problem from the recent long contest from CodeChef.
I solved the problem by building up a solution from scratch, and feel it's worth sharing.
Here is what other things you can learn from this post:
1. How to check whether two sets are identical using hashing.
2. An easy data structure to find the number of elements less than K in subarray A[L...R].
3. A variant of BIT i.e fenwick tree. We can use BITs for a lot of purposes :)

Have a good day!

Read more »

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

By rachitjain, history, 4 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

By rachitjain, history, 4 months ago, In English,

Hi CF Community,

Here is my blog rachitiitr.blogspot.in.
I have started to write about the interesting problems I encounter during contests. Interesting means really interesting, the problems that kept me thinking for hours or those having beautiful solution worth mentioning.
After explaining the underlying concept and solution, I usually also attach the code at the end of post.

So if you are bored and need a place where you can find good problems, see how they were solved, learn something new, you should check out the posts I make on the blog.
I suggest to read one post everyday before going to bed. Also people in DIV2 can certainly learn a lot by reading the posts. I have 5 posts as for now:
1. A Hard Combinatorics Problem
2. A Longest SubArray Problem
3. A Greedy, Math Problem
4. A Connectivity Problem on Directed Graph
5. A Hard Problem on Bit Logic (NEW)

I will try to be as active as possible.

Cheers!

Read more »

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

By rachitjain, history, 11 months ago, In English,

Hello Codeforces Community,
I found this problem very interesting, but couldn't solve it. Also the editorial wasn't clear to me. What I was trying was a greedy solution that passed half of the test cases.

Problem Tags: Trees, dsu
Could someone explain it in a better way?
Thanks!

Read more »

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

By rachitjain, history, 12 months ago, In English,

Hey everyone!
I have just understood the idea of Centroid Decomposition in previous zscoder's contest.
I was doing another problem based on this concept.
Here is my detailed source code
Can someone help me figure out what am I doing wrong. I have checked the integer overflow cases and the code almost seems right. I can't view the test cases of the gym problem.
Thanks.

Read more »

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

By rachitjain, history, 14 months ago, In English,

Editorial Link
Problem C. Family Door and Brackets
Short Intro of Problem: We are given a string B consisting of ( and ). We need to find pairs of strings (A, C) such that A + B + C becomes valid string. A valid string is one which is balanced i.e no of opening and closing brackets is same and also for no position, the prefix sum of number of '('  >  ')'.
Let dp[len][extra] be the ways of arranging brackets such that the resultant length is len and no of  '('   is greater than no of ')'  .
Clearly dp[len][extra] = dp[len - 1][extra + 1] + dp[len - 1][extra - 1] as we can either place ')' or '(' at lenth position.
If extra = 0, then we can't place '(' at end so thats the edge case that we handle.
In the solution, as we select c length of prefix with d balance, we now need to add suffix of length (m - n - c) with balance (d + b), where b is balance of main input string.
But as we add suffix, this balance is opposite in nature. Earlier dp[i][j] meant length i and j extra opening brackets. Now while adding suffix, we need dp2[i][j] which represents length i, and j less opening brackets. Moreover, we have to consider only those ways where the number of closing brackets must never exceed j midway otherwise that would make the overall prefix balance negative and thus we will miscount.
The editorial doesn't proves how dp[i][j] = dp2[i][j]. Can someone help?
If the above statement was not clear, see the following example:
Consider dp2[4][2]. This should not contain the follwing sequence:

  • )))(, Reason -> Though overall balance is 2, there exists a balance of 3( > 2)
    So if we have added 2 extra opening brackets and plan to use the above sequence as a suffix thinking it gives a balance of 2 for nullification, it will make the prefix balance  < 0 at some position and thus it should not be counted in dp2[4][2]

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By rachitjain, history, 14 months ago, In English,

Problem Link — 466C. Number of Ways
Solution Link with comments
I am getting WA on test case 14. I have ensured that integer overflow doesn't exist. Can someone help?

Read more »

 
 
 
 

By rachitjain, history, 16 months ago, In English,

Problem: http://codeforces.com/contest/677/problem/B
The user is doing rem = a[i];
while(rem) {if (rem >= k) rem -= k; }
See the image for his code:
http://codeforces.com/predownloaded/0a/2d/0a2d8f1ff5bca1d364d6224513611c725c9a0df2.png
If I set k = 1, and rem = 10^9 Clearly it will timeout, but I was given an unsuccessful hacking attempt. Why?

Test case I gave:
1 1000000000 1
1000000000
Result-> Unsuccessful

I thought compiler would be doing some optimizations. So turned k to 2. Still it gave unsuccessful hacking attempt. IInd Test case I gave:
1 1000000000 2
1000000000
Result-> Unsuccessful

UPD -> His code got TLE after the final system checks. -_- http://codeforces.com/contest/677/submission/18191327

This is a great way to suffer a loss of 200 points.

Read more »

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

By rachitjain, history, 16 months ago, In English,

struct node{
int i, j, val;
};

set<node> A;
I insert many nodes in A. Now I want to get the lower_bound for some val = k. How do I use A.lower_bound() in this case?

Read more »

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

By rachitjain, history, 16 months ago, In English,

The following problem deals with finding the biconnected components in an Undirected graph and treating them as vertices. The code provided in editorial isn't easy for me to understand. Can someone share a template code for how to find biconnected components?
The code given on GeeksforGeeks finds the edges in a biconnected component. I do not trust it as in the solution given there, he talks about cross-edge and stuff. Cross-edge in undirected graph?
Link to the Problem --> Problem E. Pursuit For Artifacts

Read more »

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

By rachitjain, history, 16 months ago, In English,

The question I am asking is very vague but if some experts can share some of their tricks or tips while solving DP questions would be really helpful. The problems I face is how to think of such complex DP states, and even if I think of them, how should I initialse the base values(e.g dp[0][0] = 1or0). Consider the two problems
1. D. Magic Numbers
2. B. Numbers
Both of them have DP based solutions.
D.Magic Numbers Tutorial link
Brief Solution: dp[i][j][k] is our dp state that represents number of magic prefixes of length i with remainder j modulo m. If k  =  0 than the prefix should be less than the corresponding prefix in n and if k  =  1 then the prefix should be equal to the prefix of n (it can not be greater).
First of all, how does one realises the need of having that [k] in out DP. Also in the solution, for k = 0, line 54 is letting the digit at new position be greater than a[i]. I understand that the over all number should be less than or equal to the prefix of our original number. So the digits in the number we are forming can exceed the digit at corresponding position in original number a, but how is everything working is really difficult to think. How are so many people able to think about it and how do they begin to solve such DP problems?

Let's assume I magically understood the DP state. After that, the problem I faced was to initialise the base values. I was going to initialise the dp[1][j][k] values but that would be too longer. On looking at the solution, dp[0][0][1] = 1 was enough. It took me time to see how magically it was finding the correct answers.

B. Numbers Tutorial link
Brief Solution: dp[i][j] is our dp state that represents numbers of length i formed by using digits from [j, 9]. Thus dp[i][j] +  = dp[i - x][j + 1] * C[i][x], where x is number of times I use digit j. Perfect! But what I could think of is that I have to count the number of permutations of length [sum(a[i]), n] such that occ[i] >  = a[i], and I began to think of how to solve this.

I clearly understand that more practise is needed, but seeing the tutorials for DP problems I was wondering whether there are some DP states that are very common or some standard DP techniques that one must master. One example being the usage of "Subset Hack" in E. Compatible Numbers. I couldn't even find tutorial on what "Subset Hack" is.

Read more »

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

By rachitjain, history, 16 months ago, In English,

Problem Link — E. Train and Statistics
Working on Ideone whereas
RTE on codeforces
Can some help me find out what's the problem here?

Read more »

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

By rachitjain, history, 19 months ago, In English,

I am solving the problem QTREE2 on Spoj. http://www.spoj.com/problems/QTREE2/ I am learning LCA and I am not able to detect the reason for WA. Could someone help me? Here is my code: http://ideone.com/KTmgd2

Read more »

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