rachitiitr's blog

By rachitiitr, 3 years ago, In English

Hi Community,

It's been a while I wrote a blog post here.
You can follow more such tricks on —

How debug macros work?

Straight to the point, I have often used the debug macro which stringifies the variable names and their values.

#define deb(x) cout << #x << " " << x 
int ten = 10;
deb(ten); // prints "ten = 10"

This is often useful in debugging.

The Problem with this macro — its not scalable

However, when you have multiple variables to log, you end up with more deb2 and deb3 macros.

#define deb(x) cout << #x << " " << x 
#define deb2(x) cout << #x << " " << x << " "  << #y << " " << y 
#define deb3(x, y, z) cout << #x << " " << x << " "  << #y << " " << y << " "  << #z << " " << z 

This is not scalable.

Solution using a powerful macro

Here is the solution using variadic macros and fold expressions,

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
}

int xx = 3, yy = 10, xxyy = 103;
deb(xx); // prints "xx = 3"
deb(xx, yy, xxyy); // prints "xx, yy, xxyy = 3, 10, 103"

Hope this helps, this is going to my template for sure

Full text and comments »

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

By rachitiitr, history, 5 years ago, In English

Hi,

Long time indeed!
I have been busy with Software Engineering + running a YouTube channel, and hence dropped off my active participation on Codeforces.

Though most of your rating comes from your programming skills, I still feel we can save a lot of time by using automation tools for testing your solution code against multiple test cases.

This particular JavaScript bot would be -
- Parsing all the problems A,B,C,D,... of a given Codeforces contest,
- Run your solution code (in C++) against all of these test cases
- Compare your output with expected sample output
- Create a diff report for all sample test cases for a quick view.

Here is the Github repo with setup and usage steps: click here
Here is the YouTube demo: click here

As I mentioned in the Github README, this was created as a fun side project I did in a night where I wasn't able to sleep. Would appreciate if users contribute to this by raising pull requests.

Full text and comments »

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

By rachitiitr, history, 6 years ago, In English

Hi CF community,

I am glad to see that there are increasing number of tutorial posts on Codeforces.

I had been making video for problem solving, data structures, algorithms for a while now on my YouTube channel and I want to share a good lecture series here on "Dynamic Programming on Trees".

I have covered problems like -
- Easy DP: Find the size of every node's subtree in a rooted Tree.
- Medium In/Out DP: Find the height of the tree for all scenarios where every node is considered root of the tree one by one.
- Hard DP: Binary Lifting on Trees (LCA, etc)

If you are beginner in Dynamic Programming, I would recommend you to watch this playlist "Dynamic Programming: From Zero to Hero" first.

In this lecture series, I have tried my best to explain three types of DP techniques you can apply on Trees. This covers most of the problems that we see in Software Interviews and Competitive Programming. There are more techniques, but I am not sure when I will be able to make videos for them.

I hope beginners find this useful. I would really like the feedback.

Happy Coding!

Full text and comments »

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

By rachitiitr, history, 7 years ago, In English

Hi

Its been a while that I posted on Codeforces.
If you don't know me, I maintain my YouTube channel for data structures, algorithms, problem solving, etc.

I have made three video for beginners where I explain how Codeforces can be used to improve yourself.
- What is Upsolving?
- What and Why Virtual Contests on Codeforces
- How to master new topics | Find good problems

I hope it helps. There is still a lot to cover, and I will add more such videos in future.

Feedback is most welcome.

Full text and comments »

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

By rachitiitr, history, 7 years ago, In English

Hi

I went live with a video session with some talented juniors from my college:
1. gvaibhav21
2. saharshluthra
3. adkroxx

Congratulations adkroxx for becoming orange :)

They are popularly known as the team "Triangulation" in India, and will be going to ACM ICPC World Finals this year.

Watch the video to know a bit more about them, their journey, and grab their advices on preparation for ACM ICPC and Competitive Programming.

Comment down your questions on YouTube video if they were not covered in the video itself.

I wish great success for Triangulation and hope India produces more such legendary coders in the coming future.

Happy Coding!

Full text and comments »

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

By rachitiitr, history, 7 years ago, In English

Hi

I frequently think of problems on my own, and try to solve them.
But this simple problem got me dazzled!

Problem Description:
You have a set A, size N, Ai upto 109.
You play N - 1 steps on it.
Each step, pick any 2 elements x, y and remove both of them. Add back abs(x - y) to A.
Print the max value possible at end.

I was thinking that DP might solve this, but I was wrong about the approach that was coming to my mind.

My Approach:
The ans can't be greater than max element, say M.
So find out the minimum possible value that you can have from the remaining N - 1 elements.
A simple DP can be used for this, but this approach is wrong :)

Can anyone solve this?

Happy Coding!

Full text and comments »

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

By rachitiitr, history, 7 years ago, In English

Hi

Its been a while that I've made some video on competitive programming.

The problem that I want to talk about today is:

You are given an array A of size N < 1000 with elements upto 1018.
You have to print any subset S such that:
1. The AND resultant of all elements in S is 0.
2. The AND resultant of any 2 elements in S is not 0.

The problem looks easy but is quite twisted, and can be solved once you pick up the hidden observation here.
I read this problem sometime back in Petr's blog and wanted to share the solution with you guys.

Check out the video here: https://goo.gl/Pu9gZQ

Its difficult to pick up such observations but this is what I like about Competitive Programming. It makes you smarter gradually and you start looking at things in a different manner.

Happy Coding!

Full text and comments »

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

By rachitiitr, history, 7 years 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!

Full text and comments »

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

By rachitiitr, history, 7 years 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!

Full text and comments »

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

By rachitiitr, history, 7 years 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!

Full text and comments »

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

By rachitiitr, history, 7 years 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.

Full text and comments »

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

By rachitiitr, history, 7 years 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-)

Full text and comments »

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

By rachitiitr, history, 7 years 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.

Full text and comments »

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

By rachitiitr, history, 7 years 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!

Full text and comments »

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

By rachitiitr, history, 7 years 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.

Full text and comments »

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

By rachitiitr, history, 7 years 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?

Full text and comments »

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

By rachitiitr, history, 7 years 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!

Full text and comments »

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

By rachitiitr, history, 7 years ago, In English
  • Vote: I like it
  • +8
  • Vote: I do not like it

By rachitiitr, history, 7 years 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!

Full text and comments »

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

By rachitiitr, history, 8 years 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!

Full text and comments »

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

By rachitiitr, history, 8 years 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.

Full text and comments »

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

By rachitiitr, history, 8 years 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]

Full text and comments »

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

By rachitiitr, history, 8 years 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?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By rachitiitr, history, 8 years ago, In English

Problem: http://codeforces.net/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.net/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.net/contest/677/submission/18191327

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

Full text and comments »

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

By rachitiitr, history, 8 years 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?

Full text and comments »

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