### rachitiitr's blog

By rachitiitr, history, 7 years ago,

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!

• +70

 » 7 years ago, # |   +5 Thank you !! it will be very useful
 » 7 years ago, # |   +5 I'm curious about the 3rd problem. What if I write 1 'a' times, 2 'b' times, and so on. I will binary search on 'a' so it's <= N, and as the number of subsequences = aC2 + aC4 + ...., therefore, a can be very small, I mean 'a' can be as small as 30 to take up almost 10^12 subsequences. Once I've found the maximum 'a', I go to 'b' and so on. We see that a sequence like 111112223 will never have good subsequences involving more than one label, ie: 1122 is not good. Is my approach wrong somehow?
•  » » 7 years ago, # ^ |   0 Yes, that will work too. Good work!
•  » » » 7 years ago, # ^ |   0 I feel problem 2 has similarities with Snackdown 2017 snake temple problem. for i = 1 to n: height[i] = height[i-1] + 1 if a[i] > height[i-1] height[i] = min( a[i], height[i-1] ) if a[i] <= height[i-1] Now with 2 pointers technique: i=j=1; while(j height[j-1] )j++ ans[i++] = height[j-1] while(i
 » 7 years ago, # | ← Rev. 2 →   +5 In "A connectivity problem on directed graph", you can use bitarray (not bitset) — 64bit integer array that contains all true/false element in binary notation. You can express 64 true/false value in one 64bit integer. So this problem can solve in O(N2 / 64). My solution of City Construction is here, and it passed in 0.14s.
 » 7 years ago, # |   +5 Great initiative and it will be very helpful.
 » 7 years ago, # |   -11 go on, i'm hungry and want to eat DP(good and unique ones) :)